Search papers, labs, and topics across Lattice.
The paper introduces GP-Tree, a novel in-memory spatial index that combines adaptive grid cells with a prefix tree to improve the efficiency of spatial queries on complex spatial objects. GP-Tree replaces coarse minimum bounding rectangles (MBRs) with fine-grained cell-based approximations within a prefix tree structure, optimizing data organization and query efficiency by leveraging shared prefixes in hierarchical grid cell encodings. Experimental results on real-world datasets show that GP-Tree achieves up to an order-of-magnitude improvement in query efficiency compared to traditional spatial indexes like STR-Tree and Quad-Tree.
Ditch those clunky MBRs: GP-Tree uses fine-grained grid cells in a prefix tree to speed up spatial queries by up to 10x.
Efficient spatial indexing is crucial for processing large-scale spatial data. Traditional spatial indexes, such as STR-Tree and Quad-Tree, organize spatial objects based on coarse approximations, such as their minimum bounding rectangles (MBRs). However, this coarse representation is inadequate for complex spatial objects (e.g., district boundaries and trajectories), limiting filtering accuracy and query performance of spatial indexes. To address these limitations, we propose GP-Tree, a fine-grained spatial index that organizes approximated grid cells of spatial objects into a prefix tree structure. GP-Tree enhances filtering ability by replacing coarse MBRs with fine-grained cell-based approximations of spatial objects. The prefix tree structure optimizes data organization and query efficiency by leveraging the shared prefixes in the hierarchical grid cell encodings between parent and child cells. Additionally, we introduce optimization strategies, including tree pruning and node optimization, to reduce search paths and memory consumption, further enhancing GP-Tree's performance. Finally, we implement a variety of spatial query operations on GP-Tree, including range queries, distance queries, and k-nearest neighbor queries. Extensive experiments on real-world datasets demonstrate that GP-Tree significantly outperforms traditional spatial indexes, achieving up to an order-of-magnitude improvement in query efficiency.
