KIT | KIT-Bibliothek | Impressum | Datenschutz

Exploiting subspace distance equalities in Highdimensional data for knn queries

Schäler, Martin; Broneske, David; Köpen, Veit; Saake, Gunter

Abstract:

Efficient k-nearest neighbor computation for high-dimensional data is an important, yet challenging task. The response times of stateof-the-art indexing approaches highly depend on factors like distribution of the data. For clustered data, such approaches are several factors faster than a sequential scan. However, if various dimensions contain uniform or Gaussian data they tend to be clearly outperformed by a simple sequential scan. Hence, we require for an approach generally delivering good response times, independent of the data distribution. As solution, we propose to exploit a novel concept to efficiently compute nearest neighbors. We name it sub-space distance equality, which aims at reducing the number of distance computations independent of the data distribution. We integrate knn computing algorithms into the Elf index structure allowing to study the sub-space distance equality concept in isolation and in combination with a main-memory optimized storage layout. In a large comparative study with twelve data sets, our results indicate that indexes based on sub-space distance equalities compute the least amount of distances. For clustered data, our Elf knn algorithm delivers at least a performance increase of factor two up to an increase of two magnitudes without losing the performance gain compared to sequential scans for uniform or Gaussian data.


Volltext §
DOI: 10.5445/IR/1000083093
Veröffentlicht am 28.05.2018
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Programmstrukturen und Datenorganisation (IPD)
Publikationstyp Forschungsbericht/Preprint
Publikationsjahr 2018
Sprache Englisch
Identifikator ISSN: 2190-4782
urn:nbn:de:swb:90-830934
KITopen-ID: 1000083093
Verlag Karlsruher Institut für Technologie (KIT)
Umfang 11 S.
Serie Karlsruhe Reports in Informatics ; 2018,6
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page