Towards multi-purpose main-memory storage structures: Exploiting sub-space distance equalities in totally ordered data sets for exact knn queries. Issue 101 (November 2021)

• Record Type: Journal Article
• Authors: Schäler, Martin; Tex, Christine; Köppen, Veit; Broneske, David; Saake, Gunter
• Is Part Of: Information systems. Issue 101(2021)
• Publication Date: 2021-11
• Subjects: Data storage structures -- k-nearest neighbor queries -- Main memory; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2021.101791
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: Efficient knn computation for high-dimensional data is an important, yet challenging task. Today, most information systems use a column-store back-end for relational data. For such systems, multi-dimensional indexes accelerating selections are known. However, they cannot be used to accelerate knn queries. Consequently, one relies on sequential scans, specialized knn indexes, or trades result quality for speed. To avoid storing one specialized index per query type, we envision multipurpose indexes allowing to efficiently compute multiple query types. In this paper, we focus on additionally supporting knn queries as first step towards this goal. To this end, we study how to exploit total orders for accelerating knn queries based on the sub-space distance equalities observation. It means that non-equal points in the full space, which are projected to the same point in a sub space, have the same distance to every other point in this sub space. In case one can easily find these equalities and tune storage structures towards them, this offers two effects one can exploit to accelerate knn queries. The first effect allows pruning of point groups based on a cascade of lower bounds. The second allows to re-use previously computed sub-space distances between point groups. This results in a worst-case execution bound, which is independent of the distance function. We present knn algorithms exploiting both effects and show how to tune a storage structure already known to work well for multi-dimensional selections. Our investigations reveal that the effects are robust to increasing, e.g., the dimensionality, suggesting generally good knn performance. Comparing our knn algorithms to well-known competitors reveals large performance improvements up to one order of magnitude. Furthermore, the algorithms deliver at least comparable performance as the next fastest competitor suggesting that the algorithms are only marginally affected by the curse of dimensionality. Highlights: To accelerate knn queries, we exploit two effects offered by sub-space distance equalities. We develop knn algorithms exploiting both effects and show how to tune corresponding indexes. Worst-case distance computations is distance function independent and guaranteed to be smaller than O ( | D | ) . Examining influence of dimensionality, and distance function reveals robust algorithm performance. Algorithm run time is at least competitive, and in many cases superior, to highly potent competitors.