KIT | KIT-Bibliothek | Impressum | Datenschutz

Towards multi-purpose main-memory storage structures: Exploiting sub-space distance equalities in totally ordered data sets for exact knn queries

Schäler, Martin; Tex, Christine 1; Köppen, Veit; Broneske, David; Saake, Gunter
1 Karlsruher Institut für Technologie (KIT)


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

Verlagsausgabe §
DOI: 10.5445/IR/1000133822
Veröffentlicht am 14.06.2021
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Programmstrukturen und Datenorganisation (IPD)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2021
Sprache Englisch
Identifikator ISSN: 0306-4379, 0094-453X, 1873-6076
KITopen-ID: 1000133822
Erschienen in Information Systems
Verlag Pergamon
Band 101
Seiten Art.-Nr.: 101791
Schlagwörter Data storage structures; k-nearest neighbor queries; Main memory
Nachgewiesen in Web of Science
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page