Efficient Distance Queries on Non-point Data
Open Access
- 12 November 2024
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Spatial Algorithms and Systems
- Vol. 11 (1) , 1-37
Abstract
Distance queries, including distance-range queries, k -nearest neighbors search, and distance joins, are very popular in spatial databases. However, they have been studied mainly for point data. Inspired by a recent approach on indexing non-point objects for rectangular range queries, we propose a secondary partitioning approach for space-partitioning indices, which is appropriate for distance queries. Our approach classifies the contents of each primary partition into 16 secondary partitions, taking into consideration the begin and end values of objects with respect to the spatial extent of the primary partition. Based on this, we define algorithms for three popular spatial query types, that avoid duplicate results and skip unnecessary computations. We compare our approach to the previous secondary partitioning method and to state-of-the-art data-partitioning indexing and find that it has a significant performance advantage.Keywords
Funding Information
- “2nd Call for HFRI Research Projects to support Faculty Members and Researchers” (2757)
This publication has 42 references indexed in Scilit:
- Two-Layer Space-Oriented Partitioning for Non-Point DataIEEE Transactions on Knowledge and Data Engineering, 2023
- Indexing Metric Spaces for Exact Similarity SearchACM Computing Surveys, 2022
- Spatial data management in apache spark: the GeoSpark perspective and beyondGeoInformatica, 2018
- Spatio-textual user matching and clustering based on set similarity joinsThe VLDB Journal, 2018
- Main Memory Evaluation of Monitoring Queries Over Moving ObjectsDistributed and Parallel Databases, 2004
- Speeding up construction of PMR quadtree-based spatial indexesThe VLDB Journal, 2002
- Distance browsing in spatial databasesACM Transactions on Database Systems, 1999
- Multidimensional access methodsACM Computing Surveys, 1998
- Computational Geometry1985
- Data Structures for Range SearchingACM Computing Surveys, 1979