Towards multi-purpose main-memory storage structures: Exploiting sub-space distance equalities in totally ordered data sets for exact knn queries
作者：
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.
摘要
•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.
论文关键词：Data storage structures,k-nearest neighbor queries,Main memory
论文评审过程：Received 15 May 2020, Revised 21 March 2021, Accepted 28 April 2021, Available online 12 May 2021, Version of Record 25 May 2021.
论文官网地址：https://doi.org/10.1016/j.is.2021.101791
