# Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms

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

## Key facts

- Cited by 148 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Aug 2019.

## Built on by (most cited first, 30 of 148)

- [Training Data Influence Analysis and Estimation: A Survey](https://mlsanity.com/paper/2212.04612/) (2022)
- [Data Banzhaf: A Robust Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2205.15466/) (2022)
- [DataInf: Efficiently Estimating Data Influence in LoRA-tuned LLMs and Diffusion Models](https://mlsanity.com/paper/2310.00902/) (2023)
- [Data Shapley in One Training Run](https://mlsanity.com/paper/2406.11011/) (2024)
- [LAVA: Data Valuation without Pre-Specified Learning Algorithms](https://mlsanity.com/paper/2305.00054/) (2023)
- [OpenDataVal: a Unified Benchmark for Data Valuation](https://mlsanity.com/paper/2306.10577/) (2023)
- [Data-OOB: Out-of-bag Estimate as a Simple and Efficient Data Value](https://mlsanity.com/paper/2304.07718/) (2023)
- [WeightedSHAP: analyzing and improving Shapley based feature attributions](https://mlsanity.com/paper/2209.13429/) (2022)
- [CS-Shapley: Class-wise Shapley Values for Data Valuation in Classification](https://mlsanity.com/paper/2211.06800/) (2022)
- [Get more for less: Principled Data Selection for Warming Up Fine-Tuning in LLMs](https://mlsanity.com/paper/2405.02774/) (2024)
- [DataLens: Scalable Privacy Preserving Training via Gradient Compression and Aggregation](https://mlsanity.com/paper/2103.11109/) (2021)
- [Rethinking Data Shapley for Data Selection Tasks: Misleads and Merits](https://mlsanity.com/paper/2405.03875/) (2024)
- [MediTab: Scaling Medical Tabular Data Predictors via Data Consolidation, Enrichment, and Refinement](https://mlsanity.com/paper/2305.12081/) (2023)
- [Data Selection for Fine-tuning Large Language Models Using Transferred Shapley Values](https://mlsanity.com/paper/2306.10165/) (2023)
- [Stochastic Amortization: A Unified Approach to Accelerate Feature and Data Attribution](https://mlsanity.com/paper/2401.15866/) (2024)
- [Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation](https://mlsanity.com/paper/2308.15709/) (2023)
- [Data Pricing in Machine Learning Pipelines](https://mlsanity.com/paper/2108.07915/) (2021)
- [Efficient Data Shapley for Weighted Nearest Neighbor Algorithms](https://mlsanity.com/paper/2401.11103/) (2024)
- [textttdattri: A Library for Efficient Data Attribution](https://mlsanity.com/paper/2410.04555/) (2024)
- [Data Debugging with Shapley Importance over End-to-End Machine Learning Pipelines](https://mlsanity.com/paper/2204.11131/) (2022)
- [HarsanyiNet: Computing Accurate Shapley Values in a Single Forward Propagation](https://mlsanity.com/paper/2304.01811/) (2023)
- [Data Valuation and Detections in Federated Learning](https://mlsanity.com/paper/2311.05304/) (2023)
- [Variance reduced Shapley value estimation for trustworthy data valuation](https://mlsanity.com/paper/2210.16835/) (2022)
- [Performance Scaling via Optimal Transport: Enabling Data Selection from Partially Revealed Sources](https://mlsanity.com/paper/2307.02460/) (2023)
- [The Mirrored Influence Hypothesis: Efficient Data Influence Estimation by Harnessing Forward Passes](https://mlsanity.com/paper/2402.08922/) (2024)
- [TokenShapley: Token Level Context Attribution with Shapley Value](https://mlsanity.com/paper/2507.05261/) (2025)
- [DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation](https://mlsanity.com/paper/2306.02071/) (2023)
- [LayerIF: Estimating Layer Quality for Large Language Models using Influence Functions](https://mlsanity.com/paper/2505.23811/) (2025)
- [From Points to Coalitions: Hierarchical Contrastive Shapley Values for Prioritizing Data Samples](https://mlsanity.com/paper/2512.19363/) (2025)
- [A Note on "Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms"](https://mlsanity.com/paper/2304.04258/) (2023)

## Abstract (arXiv)

Given a data set D containing millions of data points and a data consumer who is willing to pay for X to train a machine learning (ML) model over D, how should we distribute this X to each data point to reflect its "value"? In this paper, we define the "relative value of data" via the Shapley value, as it uniquely possesses properties with appealing real-world interpretations, such as fairness, rationality and decentralizability. For general, bounded utility functions, the Shapley value is known to be challenging to compute: to get Shapley values for all N data points, it requires O(2N) model evaluations for exact computation and O(Nlog N) for (ε, δ)-approximation. In this paper, we focus on one popular family of ML models relying on K-nearest neighbors (KNN). The most surprising result is that for unweighted KNN classifiers and regressors, the Shapley value of all N data points can be computed, exactly, in O(Nlog N) time -- an exponential improvement on computational complexity! Moreover, for (ε, δ)-approximation, we are able to develop an algorithm based on Locality Sensitive Hashing (LSH) with only sublinear complexity O(Nh(ε,K)log N) when ε is not too small and K is not too large. We empirically evaluate our algorithms on up to 10 million data points and even our exact algorithm is up to three orders of magnitude faster than the baseline approximation algorithm. The LSH-based approximation algorithm can accelerate the value calculation process even further. We then extend our algorithms to other scenarios such as (1) weighed KNN classifiers, (2) different data points are clustered by different data curators, and (3) there are data analysts providing computation who also requires proper valuation.