Home  | Publications | BBK19

K-Distance Approximation for Memory-Efficient RkNN Retrieval

MCML Authors

Peer Kröger

Prof. Dr.

Principal Investigator

* Former Principal Investigator

Abstract

For a given query object, Reverse k-Nearest Neighbor queries retrieve those objects that have the query object among their k-nearest neighbors. However, computing the k-nearest neighbor sets for all points in a database is expensive in terms of computational costs. Therefore, specific index structures have been invented to apply pruning heuristics which aim at reducing the search space. At time, the state-of-the-art index structure for enabling fast RkNN query processing in general metric spaces is the MRkNNCoP-Tree which uses linear functions to approximate lower and upper bounds on the k-distances to prune the search space. Storing those linear functions results in additional storage costs in O(n) which might be infeasible in situation where storage space is limited, e.g., on mobile devices. In this work, we present a novel index based on the MRkNNCoP-Tree as well as recent developments in the field of neural indexing. By learning a single neural network model that approximates the k-nearest neighbor distance bounds for all points in a database, the storage complexity of the proposed index structure is reduced to O(1) while the index is still able to guarantee exact query results. As shown in our experimental evaluations on synthetic and real-world data sets, our approach can significantly reduce the required storage space in trade-off to some growth in terms of refinement sets when relying on exact query processing.

inproceedings

SISAP 2019

12th International Conference on Similarity Search and Applications. Newark, New York, USA, Oct 02-04, 2019.

Authors

M. Berrendorf • F. Borutta • P. Kröger

Links

DOI

Research Area

 A3 | Computational Models

BibTeXKey: BBK19

Back to Top