GP-Tree: An in-memory spatial index combining adaptive grid cells with a prefix tree for efficient spatial querying

• URL: http://arxiv.org/abs/2603.07517v1
• Date: Sun, 08 Mar 2026 07:59:03 GMT
• Title: GP-Tree: An in-memory spatial index combining adaptive grid cells with a prefix tree for efficient spatial querying
• Abstract summary: GP-Tree is a fine-grained spatial index that organizes approximated grid cells of spatial objects into a prefix tree structure.<n>We introduce optimization strategies, including tree pruning and node optimization, to reduce search paths and memory consumption.<n>Experiments on real-world datasets demonstrate that GP-Tree significantly outperforms traditional spatial indexes.
• Score: 5.732286906919534
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• GONDOR to the Rescue: Satisficing Planning with Low Memory [80.8869960059932]
  GONDOR is a memory-efficient extension of Greedy Best-First Search (GBFS)<n>GONDOR periodically compresses the search tree while retaining a sparse set of anchor states, then upon reaching the goal reconstructs the path by re-searching between the sparse states.<n> Experiments show that GONDOR consistently improves coverage under low memory budgets compared to standard GBFS.
  arXiv  Detail & Related papers  (2026-05-27T13:20:58Z)
• CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data [11.878755010092922]
  CubeGraph is a framework designed to integrate vector search with arbitrary spatial constraints.<n>During query execution, CubeGraph stitches together adjacent cube-level indices on the fly whenever spatial cells intersect with the query filter.
  arXiv  Detail & Related papers  (2026-04-08T02:49:55Z)
• Divide-Then-Rule: A Cluster-Driven Hierarchical Interpolator for Attribute-Missing Graphs [51.13363550716544]
  Deep graph clustering is an unsupervised task aimed at partitioning nodes with incomplete attributes into distinct clusters.<n>Existing imputation methods for attribute-missing graphs often fail to account for the varying amounts of information available across node neighborhoods.<n>We propose Divide-Then-Rule Graph Completion (DTRGC) to address this issue.
  arXiv  Detail & Related papers  (2025-07-12T03:33:19Z)
• Hierarchical Quantized Diffusion Based Tree Generation Method for Hierarchical Representation and Lineage Analysis [49.00783841494125]
  HDTree captures tree relationships within a hierarchical latent space using a unified hierarchical codebook and quantized diffusion processes.<n> HDTree's effectiveness is demonstrated through comparisons on both general-purpose and single-cell datasets.<n>These contributions provide a new tool for hierarchical lineage analysis, enabling more accurate and efficient modeling of cellular differentiation paths.
  arXiv  Detail & Related papers  (2025-06-29T15:19:13Z)
• A Query-Driven Approach to Space-Efficient Range Searching [12.760453906939446]
  We show that a near-linear sample of queries allows the construction of a partition tree with a near-optimal expected number of nodes visited during querying.<n>We enhance this approach by treating node processing as a classification problem, leveraging fast classifiers like shallow neural networks to obtain experimentally efficient query times.<n>Our algorithm, based on a sample of queries, builds a balanced tree with nodes associated with separators that minimize query stabs on expectation.
  arXiv  Detail & Related papers  (2025-02-19T12:01:00Z)
• ReTreever: Tree-based Coarse-to-Fine Representations for Retrieval [64.44265315244579]
  We propose a tree-based method for organizing and representing reference documents at various granular levels.<n>Our method, called ReTreever, jointly learns a routing function per internal node of a binary tree such that query and reference documents are assigned to similar tree branches.<n>Our evaluations show that ReTreever generally preserves full representation accuracy.
  arXiv  Detail & Related papers  (2025-02-11T21:35:13Z)
• The "AI+R"-tree: An Instance-optimized R-tree [8.645596995409647]
  This paper investigates to leverage Machine Learning techniques to enhance the performance of spatial indexes. We introduce a new AI-tree that transforms the search operation of an R-tree into a multi-label classification task. Experiments on real datasets demonstrate that the "AI+R"-tree can enhance the query performance over a traditional R-tree by up to 500%.
  arXiv  Detail & Related papers  (2022-07-01T17:08:17Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  We introduce a new approach based on A* search for clustering. We overcome the prohibitively large search space by combining A* with a novel emphtrellis data structure. We empirically demonstrate that our method achieves substantially higher quality results than baselines for a particle physics use case and other clustering benchmarks.
  arXiv  Detail & Related papers  (2021-04-14T18:15:27Z)
• The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data [33.26284196513858]
  Learned indices have been proposed to replace classic index structures like B-Tree with machine learning (ML) models. We propose a fundamentally different way of using ML techniques to improve on the query performance of the classic R-Tree without the need of changing its structure or query processing algorithms.
  arXiv  Detail & Related papers  (2021-03-08T04:29:58Z)
• The Case for Learned Spatial Indexes [62.88514422115702]
  We use techniques proposed from a state-of-the art learned multi-dimensional index structure (namely, Flood) to answer spatial range queries. We show that (i) machine learned search within a partition is faster by 11.79% to 39.51% than binary search when using filtering on one dimension. We also refine using machine learned indexes is 1.23x to 1.83x times faster than closest competitor which filters on two dimensions.
  arXiv  Detail & Related papers  (2020-08-24T12:09:55Z)
• A Practical Index Structure Supporting Fr\'echet Proximity Queries Among Trajectories [1.9335262420787858]
  We present a scalable approach for range and $k$ nearest neighbor queries under computationally expensive metrics. Based on clustering for metric indexes, we obtain a dynamic tree structure whose size is linear in the number of trajectories. We analyze the efficiency and effectiveness of our methods with extensive experiments on diverse synthetic and real-world data sets.
  arXiv  Detail & Related papers  (2020-05-28T04:12:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.