Efficient Distance Queries on Non-point Data

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 se...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on spatial algorithms and systems 2025-03, Vol.11 (1), p.1-37
Main Authors: Michalopoulos, Achilleas, Tsitsigkos, Dimitrios, Bouros, Panagiotis, Mamoulis, Nikos, Terrovitis, Manolis
Format: Article
Language:English
Subjects:
Geographic information systems
Information systems
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2374-0353
2374-0361
DOI:10.1145/3698194