# Learned k-NN Distance Estimation

arXiv: https://arxiv.org/abs/2208.14210 · HTML: https://mlsanity.com/paper/2208.14210/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 59 references that are in the map.
- First posted on arXiv 29 Aug 2022.

## Builds on (most cited first, 14 of 14)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)](https://mlsanity.com/paper/1610.02455/) (2016)
- [An End-to-End Learning-based Cost Estimator](https://mlsanity.com/paper/1906.02560/) (2019)
- [Deep Unsupervised Cardinality Estimation](https://mlsanity.com/paper/1905.04278/) (2019)
- [Learning Multi-dimensional Indexes](https://mlsanity.com/paper/1912.01668/) (2019)
- [Benchmarking Learned Indexes](https://mlsanity.com/paper/2006.12804/) (2020)
- [Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads](https://mlsanity.com/paper/2006.13282/) (2020)
- [FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation](https://mlsanity.com/paper/2011.09022/) (2020)
- [Theoretically-Efficient and Practical Parallel DBSCAN](https://mlsanity.com/paper/1912.06255/) (2019)
- [Fast Density-Peaks Clustering: Multicore-based Parallelization Approach](https://mlsanity.com/paper/2207.04649/) (2022)
- [Consistent and Flexible Selectivity Estimation for High-Dimensional Data](https://mlsanity.com/paper/2005.09908/) (2020)
- [Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach](https://mlsanity.com/paper/2002.06442/) (2020)
- [Fast and Exact Outlier Detection in Metric Spaces: A Proximity Graph-based Approach](https://mlsanity.com/paper/2110.08959/) (2021)

## Abstract (arXiv)

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.