Learned k-NN Distance Estimation

Daichi Amagata, Yusuke Arai, Sumio Fujita, Takahiro HaraarXiv 2022 · arXiv

TL;DR

PivNet is a novel machine-learning approach that estimates $k$-nearest neighbor ($k$-NN) distances in constant $O(1)$ time, bypassing the need for expensive data retrieval. By combining grid-based "pivots" with a multi-output neural network, it achieves up to 40x speedups over traditional tree-based methods while maintaining high accuracy for tasks like density estimation and outlier detection.

What Problem Does This Paper Address?

Many data science tasks—such as detecting crime "hot spots," identifying sensor anomalies, or clustering complex datasets—rely on $k$-NN distances to measure local density. Traditionally, calculating these distances requires retrieving the actual neighboring points using spatial indices like $kd$-trees.

However, as datasets grow into the millions of points, this retrieval process becomes a massive computational bottleneck. If an application only needs to know how far away the neighbors are (rather than which specific points they are), performing a full search is overkill. The authors tackle this by asking: Can we learn the underlying distance distribution of a dataset and simply "infer" the distances for any new query point?

Methods

The authors propose PivNet, a regression-based neural network designed for speed and accuracy. Its architecture relies on two main ideas:

  1. Grid-Based Pivots: The data space is divided into a fine-grained grid. The center of each cell acts as a "pivot" point. Before training, the $k$-NN distances for these pivots are precomputed.
  2. Pivotal Features: When a query $q$ arrives, PivNet doesn't just look at $q$'s coordinates. It identifies the nearest pivot $p$ and uses $p$'s precomputed $k$-NN distances as input features. This provides the model with a "local anchor" that significantly improves estimation accuracy.
Figure 1: The left part shows the data space and a grid. Blue stars centered at cells represent pivots and the red star represents a query 𝑞. The right part shows our five-layer fully connected neural network model. The input layer has the coordinates of 𝑞, 𝑑𝑖𝑠𝑡(𝑞, 𝑝2), where 𝑝2 is the nearest pivot of 𝑞, and 𝑑𝑖𝑠𝑡(𝑝2,𝑥𝑘𝑝2) (𝑘∈[1,𝑘𝑚𝑎𝑥]). It has three hidden layers, and its output layer is

Unlike standard regression models that might predict one distance at a time, PivNet uses a multi-output layer to estimate the entire vector of distances (from the 1st to the $k_{max}$-th neighbor) in a single forward pass. This ensures the inference time remains constant regardless of the value of $k$.

Datasets

The model was evaluated on six diverse, publicly available real-world datasets:

  • Crime: 2D geo-locations of crimes in Atlanta.
  • Places: 2D geo-locations of public places across the U.S.
  • Wisdom: 3D gyroscope sensor data from smartphones.
  • Household: 4D power consumption metrics.
  • HEPMASS & PAMAP2: 5D datasets representing high-energy physics and physical activity monitoring, respectively.

Key Insights and Ideas

  • The Power of "Pivots": The authors found that simply using a pivot's distances as an estimate is a decent baseline, but the neural network is essential to "correct" the error introduced by the gap between the query and the pivot.
  • Simplicity is Efficiency: A relatively shallow 5-layer fully connected network was found to be the "sweet spot." Deeper networks increased latency without providing meaningful gains in accuracy.
  • Vectorized Inference: By predicting all $k$ distances simultaneously, the model avoids the $O(k)$ scaling typical of iterative estimation methods, making it highly suitable for real-time visualization.
  • Robustness via Augmentation: To prevent the model from only learning dense regions of the data, the authors augmented the training set with queries sampled uniformly across the entire space.

Key Results

  • Massive Speedups: PivNet is consistently 13x to 40x faster than exact $kd$-tree retrieval across all datasets.
  • High Fidelity: In a case study on density visualization (creating heatmaps), PivNet produced results nearly indistinguishable from exact methods in a fraction of the time.
Figure 2: 𝑘-NN density visualization
  • Effective Outlier Detection: When used for distance-based outlier detection, PivNet achieved precision and recall scores often exceeding 0.90, proving that its estimations are accurate enough for downstream decision-making.
  • Search Acceleration: The authors showed that PivNet's estimates can be used to initialize the search threshold in traditional $k$-NN algorithms, speeding up exact searches by 1.2x to 2.9x.

Limitations and Future Work

The primary limitation acknowledged is the curse of dimensionality. The current pivot-based grid approach works well for low-dimensional data (up to 5D in this paper) but would face exponential space costs in high-dimensional spaces. The authors suggest that dimensionality reduction techniques (like PCA or t-SNE) could be a bridge, but estimating $k$-NN distances in raw high-dimensional space remains an open challenge. Additionally, the model assumes a relatively static dataset; while it can handle batch updates, frequent real-time data insertions would require periodic retraining.

Summary updated

Abstract

Big data mining is well known to be an important task for data science, because it can provide useful observations and new knowledge hidden in given large datasets. Proximity-based data analysis is particularly utilized in many real-life applications. In such analysis, the distances to k nearest neighbors are usually employed, thus its main bottleneck is derived from data retrieval. Much efforts have been made to improve the efficiency of these analyses. However, they still incur large costs, because they essentially need many data accesses. To avoid this issue, we propose a machine-learning technique that quickly and accurately estimates the k-NN distances (i.e., distances to the k nearest neighbors) of a given query. We train a fully connected neural network model and utilize pivots to achieve accurate estimation. Our model is designed to have useful advantages: it infers distances to the k-NNs at a time, its inference time is O(1) (no data accesses are incurred), but it keeps high accuracy. Our experimental results and case studies on real datasets demonstrate the efficiency and effectiveness of our solution.
BibTeX
@misc{amagata2022learned,
  author = {Daichi Amagata and Yusuke Arai and Sumio Fujita and Takahiro Hara},
  title = {{Learned k-NN Distance Estimation}},
  year = {2022},
  eprint = {2208.14210},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2208.14210},
}
Figure