A new hashing based nearest neighbors selection technique for big datasets

Jude Tchaye-Kondi, Yanlong Zhai, Liehuang ZhuarXiv 2020 · arXiv

TL;DR

This paper introduces GHN (Grid Hashing Neighborhood), a novel hashing-based approach to accelerate K-Nearest Neighbors (KNN) prediction for large datasets. By intelligently partitioning the data space into a grid and using hashing, GHN efficiently narrows down the search for neighbors to a local region, significantly outperforming traditional KNN in prediction time while maintaining comparable accuracy.

What Problem Does This Paper Address?

The K-Nearest Neighbors (KNN) algorithm is a simple yet powerful tool for classification and regression. However, its primary drawback, especially with large datasets, is its computational inefficiency during prediction. KNN requires comparing a new data point to every point in the training set to find the nearest neighbors, leading to slow decision-making. This makes it impractical for real-time applications or scenarios with massive datasets. Existing solutions like data reduction, hashing (LSH), and tree-based methods (KD-tree, Ball Tree) have their own limitations, such as accuracy degradation, inability to guarantee true nearest neighbors, or poor performance in high-dimensional spaces. This paper aims to bridge this gap by offering a method that significantly speeds up KNN prediction without sacrificing accuracy, even for large datasets.

Methods

The core of GHN lies in its two-phase approach: Cell Sampling (training) and Exploration (prediction).

  • Cell Sampling (Training): During training, GHN divides the data space into a virtual grid of subcells. A hash function is then used to map each training data point to its corresponding cell. This creates a hash table where cells act as buckets for data points. The cell measurements (widths) are determined dynamically to ensure an optimal distribution of data points.
  • Exploration (Prediction): When a new data point needs prediction, GHN first identifies the cell it belongs to using the hash function. Then, instead of searching the entire dataset, it intelligently explores only the central cell and its neighboring cells layer by layer. A buffer (implemented as a min-heap of size k) is used to store the k nearest neighbors found so far. The exploration stops when no new nearest neighbors are found in the subsequent layers, effectively limiting the search to the local neighborhood of the new data point.

Datasets

The authors evaluated GHN on five real-world datasets:

  • Fashion MNIST
  • MNIST
  • Pulsar Star
  • Wine Quality
  • Russian Demography

These datasets were used for classification tasks. The authors also mention using Principal Component Analysis (PCA) for dimensionality reduction and scaling the datasets to ensure features are on a comparable magnitude.

Key Insights and Ideas

  • Local Search is Key: The fundamental insight is that for large datasets, the nearest neighbors are likely to be found in the immediate vicinity of the new data point. GHN exploits this by creating a spatial index (the grid) and focusing the search locally.
  • Hashing as an Efficient Index: Hashing provides a fast way to map data points to cells, enabling quick retrieval of data points within a specific region.
  • Layered Exploration for Adaptability: The layered exploration strategy allows GHN to adapt to different data distributions. It can quickly find neighbors in dense regions (stopping early) or explore more layers if needed.
  • Best-Case O(1) Complexity: In its most favorable scenario (dense data, shallow exploration), GHN can achieve near-constant time complexity for prediction, a significant improvement over traditional KNN.

Key Results

  • Speed: GHN consistently outperformed the original KNN in prediction time across all tested datasets. It was also competitive with, and often faster than, KDTree, especially for non-image data types. For example, on the Russian Demography dataset, GHN took 0.19ms, KDTree 2.92ms, and KNN 0.90ms.
  • Accuracy: GHN achieved accuracies that were almost identical to KNN and KDTree, with only slight variations. For instance, on Fashion MNIST, GHN achieved 86% accuracy, KDTree 80%, and KNN 88%. This demonstrates that the speed improvement did not come at the cost of predictive quality.
  • Scalability: The paper highlights that GHN's performance is less negatively impacted by increasing training data size compared to traditional KNN. In fact, larger datasets can sometimes lead to better performance for GHN as it refines its local search.

Limitations and Future Work

  • Curse of Dimensionality: GHN, like KNN, is susceptible to the curse of dimensionality. In very high-dimensional spaces, the number of cells to explore can grow exponentially, degrading performance. The authors acknowledge this and mention using PCA to mitigate it.
  • Data Distribution Dependence: GHN's performance can degrade if data points are very far apart or if the observation is far from the main data clusters.
  • Not Recommended for Too Many Dimensions: Due to the exponential increase in cells with dimensions, GHN is not recommended for datasets with an extremely high number of features.
  • Future Work: The paper suggests that GHN can be used for both classification and regression tasks, and further research could explore its application in these areas. The authors also mention the importance of data scaling techniques.

Summary updated

BibTeX
@misc{tchayekondi2020new,
  author = {Jude Tchaye-Kondi and Yanlong Zhai and Liehuang Zhu},
  title = {{A new hashing based nearest neighbors selection technique for big datasets}},
  year = {2020},
  eprint = {2004.02290},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2004.02290},
}
Figure