Projects · Buddhi Ashan

A green polygon with a thought bubble: find all polygons that share a similar shape

IEEE BigData 2025Acceptance rate 18.7%

ShapeToVec: shape similarity search at scale

Shape-based similarity queries over large GIS datasets. This needs feature vectors that preserve shape and area. However, polygon areas in real polygonal datasets span exponential ranges and uniform rasterization fails at both ends. ShapeToVec encodes each polygon on a quadtree-based non-uniform grid that adapts resolution to local vertex density, and searches with weighted Jaccard distance implemented natively inside an HNSW index. It reaches 97% recall on top-50 queries over 1.7 million polygons. We are the first system to perform shape-based Jaccard similarity search at this scale.

Quadtree encodingWeighted JaccardHNSW · NMSLIBPython · C++

Paper Presentation video Poster Code Dataset NSF #2313039 Animation: quadtree encoding

ACM SIGSPATIAL 2026JPQ under review

ShapeToVec+: compressing the index toward a billion polygons

Recall was not the binding constraint for ShapeToVec; memory was. ShapeToVec+ decouples area from the stored signature, where the signature carries only grid-cell occupancy, while a precomputed cell-area look-up table supplies the true weights at query time. Integer-arithmetic encoding gives 4× compression and bitwise encoding 8× to 32×, with the weighted-Jaccard metric intact and SIMD distance kernels at query time. We are extending this work with JPQ, the first product quantizer formulated for weighted Jaccard, which stores each 3,082-dimensional vector in 64 bytes and brings a 1.05-billion-polygon index within commodity server memory.

CompressionBitwise encodingSIMDProduct quantization

Paper Code Code: JPQ Animation: quadtree encoding

Examples of degenerate polygon intersections

IEEE/ACM CCGrid 2023Best paper finalist

Parallel polygon clipping on GPUs, handling degenerate cases properly

Polygonal operations are fundamental in graphics, CAD, and GIS, and handling degenerate cases matters when real spatial data is used. The popular Greiner–Hormann algorithm cannot handle them without perturbing vertices. This work parallelizes the O(n²) general clipping algorithm by Foster et al., which handles degenerate cases without perturbation. The CREW PRAM algorithm clips in O(log n) time using n + k processors, and the CUDA implementation adds three filters: common minimum-bounding-rectangle, count-based, and line-segment MBR, that reduce candidate edge-pair comparisons by 80–99%, yielding up to 40× speedup on real-world datasets.

CUDAPRAMComputational geometryC++

Paper Code Animation: CMBR filter Animation: LSMBR filter

Line segments and their related segment tree

ACM ICPP 2024

Segment trees for polygon clipping, parallelized with OpenMP and OpenACC

The first work to extend a segment tree data structure to practical polygon clipping, leveraging Chazelle's cover-list and end-list augmentation. Tree construction, the augmented lists, and line-segment intersection finding are parallelized with OpenMP directives, and the intersection kernels are offloaded with OpenACC. The augmented tree eliminates 99% of non-intersecting edge pairs (63% for the best prior filter), enough that a single CPU core beats the state-of-the-art GPU implementation.

Segment treeOpenMPOpenACCC++

Paper Code

IEEE PerCom 2025NSF #2234516

ScooterLab: a participatory sensing testbed on micromobility vehicles

ScooterLab is an NSF-funded research testbed built on instrumented e-scooters. I lead the team behind its Research Activities Management Portal (RAMP): a Laravel backend for managing researchers and experiments, and an ArcGIS-based map tool for visualizing trip trajectories and their sensor data.

Laravel · PHPArcGIS JSMultimodal sensing

scooterlab.utsa.edu NSF #2234516 PerCom 2025 paper Workshop 2025 Workshop 2026