Efficient Nearest Neighbor Queries on Non-point Data
Achilleas Michalopoulos, Dimitrios Tsitsigkos, Panagiotis Bouros, Nikos Mamoulis, Manolis Terrovitis · 2023
Nearest neighbor (NN) queries are ubiquitous in spatial databases, but have been studied mainly for point data. Inspired by recent work on indexing non-point objects for range queries, we propose a secondary partitioning scheme for space-partitioning indices, tailored to NN search. Our scheme classifies the contents of each primary partition into 16 secondary partitions, considering the begin and end of objects with respect to the spatial extent of the primary partition. Based on this, we design algorithms for both incremental NN and k-NN search that avoid duplicate results and skip unnecessary computations. We compare our scheme to the state-of-the-art indexing and find that it has a significant performance advantage.