Survey on Exact kNN Queries over High-Dimensional Data Space

Nimish Ukey, Zhengyi Yang, Binghao Li, Guangjian Zhang, Yiheng Hu, Wenjie Zhang

TL;DR

This paper provides the first comprehensive survey of exact kNN (k-Nearest Neighbors) query techniques specifically for high-dimensional data. It categorizes and analyzes 29 different methods, offering a crucial resource for researchers and practitioners needing accurate kNN results in complex, high-dimensional datasets.

What Problem Does This Paper Address?

Finding the k-Nearest Neighbors (kNN) is a fundamental operation in many fields, from data mining and recommendation systems to IoT and Industry 4.0. However, as datasets grow in dimensionality (i.e., the number of features or attributes per data point), traditional kNN algorithms struggle. This is often referred to as the "curse of dimensionality." While many approximate kNN (ANN) algorithms exist that sacrifice accuracy for speed, there's a critical need for exact kNN solutions when precision is paramount. Existing surveys often focus on low-dimensional data or approximate methods, leaving a gap in understanding the landscape of exact kNN techniques for high-dimensional spaces. This paper aims to fill that gap by systematically reviewing and categorizing existing exact kNN search and join methods.

Methods

The authors present a comprehensive survey of exact kNN query techniques, focusing on two main types:

  • kNN Search: For a given query point, find its k closest neighbors in a dataset.
  • kNN Join: For each point in a query dataset, find its k closest neighbors in another dataset.

They categorize the surveyed algorithms based on five key factors:

  1. Indexing Technique: How data structures are used to speed up searches (e.g., R-trees, B+-trees, iDistance).
  2. Partitioning Strategies: How data or space is divided (e.g., space-based, data-based).
  3. Dimensionality Reduction Strategy: Techniques to reduce the number of dimensions.
  4. Distance Computation Approach: The metric used to measure similarity (primarily Euclidean, but also Bregman).
  5. Computing Paradigm: How the computation is handled (e.g., I/O-based, main-memory-based, parallel, distributed).

The paper reviews 20 kNN Search methods and 9 kNN Join methods, providing detailed discussions on their mechanisms, strengths, and weaknesses.

Datasets

The paper discusses various techniques and their experimental evaluations, referencing studies that used datasets with dimensionalities ranging from 12D to over 500D. However, the paper itself does not introduce new datasets or benchmarks. It relies on existing literature that has utilized synthetic and real-world datasets for evaluating the discussed kNN algorithms.

Key Insights and Ideas

  • The "Curse of Dimensionality" is Real: Traditional indexing structures that work well in low dimensions often degrade significantly or become less effective than brute-force scans in high-dimensional spaces.
  • Exact vs. Approximate Trade-off: While approximate methods offer speedups, many applications demand exact results, necessitating specialized techniques for high dimensions.
  • No Single "Best" Approach: The effectiveness of kNN techniques is highly dependent on factors like dataset size, dimensionality, distribution, and the specific application's requirements.
  • Hybrid Approaches are Promising: Combining different strategies (e.g., dimensionality reduction with specialized indexing, or parallel processing with efficient partitioning) often yields better results.
  • The Landscape is Evolving: The survey highlights a continuous effort to develop more efficient indexing, partitioning, and computing paradigms to tackle the challenges of high-dimensional kNN.

Key Results

The paper's primary contribution is a structured overview and comparative analysis of existing exact kNN Search and Join techniques for high-dimensional data. It synthesizes information on 29 distinct methods, classifying them by their underlying strategies. The authors provide tables summarizing the merits and demerits of each technique, offering insights into their performance characteristics, scalability, and limitations. For instance, they note that while some methods show significant speedups (e.g., BF-CUDA up to 400x faster than CPU-based BF), they may not scale well to very large datasets or high dimensionalities. The paper also identifies that many approaches do not effectively support dynamic datasets, a growing concern for real-world applications.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Dynamic Datasets: Most existing approaches do not adequately support dynamic datasets (handling insertions/deletions), which is crucial for real-world applications. Future work should focus on developing robust dynamic kNN solutions.
  • Clustering and Partitioning: Finding the optimal number of clusters for partitioning is often dataset-dependent. Research could explore more adaptive and efficient clustering strategies.
  • Triangle Inequality: While triangle inequality is useful, optimizing its application, particularly in selecting optimal cluster centers and reference points, could further reduce space and time complexity.
  • Parallel and Distributed Exact kNN Join: The paper notes a lack of parallel and distributed exact kNN Join approaches for high-dimensional data. Leveraging distributed computing paradigms could significantly improve performance.
  • Dimensionality Thresholds: The paper points out the lack of a standard definition for "high-dimensional" and suggests that future research should consider a wider range of dimensionalities, especially beyond 20D, for which some existing approaches are limited.

Summary updated

Abstract

k nearest neighbours (kNN) queries are fundamental in many applications, ranging from data mining, recommendation system and Internet of Things, to Industry 4.0 framework applications. In mining, specifically, it can be used for the classification of human activities, iterative closest point registration and pattern recognition and has also been helpful for intrusion detection systems and fault detection. Due to the importance of kNN queries, many algorithms have been proposed in the literature, for both static and dynamic data. In this paper, we focus on exact kNN queries and present a comprehensive survey of exact kNN queries. In particular, we study two fundamental types of exact kNN queries: the kNN Search queries and the kNN Join queries. Our survey focuses on exact approaches over high-dimensional data space, which covers 20 kNN Search methods and 9 kNN Join methods. To the best of our knowledge, this is the first work of a comprehensive survey of exact kNN queries over high-dimensional datasets. We specifically categorise the algorithms based on indexing strategies, data and space partitioning strategies, clustering techniques and the computing paradigm. We provide useful insights for the evolution of approaches based on the various categorisation factors, as well as the possibility of further expansion. Lastly, we discuss some open challenges and future research directions.
BibTeX
@inproceedings{ukey2023survey,
  author = {Nimish Ukey and Zhengyi Yang and Binghao Li and Guangjian Zhang and Yiheng Hu and Wenjie Zhang},
  title = {{Survey on Exact kNN Queries over High-Dimensional Data Space}},
  booktitle = {Sensors},
  year = {2023},
  url = {https://openreview.net/forum?id=8uL9KtUkBa},
}
Figure