# Optimizing Data Shapley Interaction Calculation from O(2^n) to O(t n^2) for KNN models

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 12 references that are in the map.
- First posted on arXiv 2 Apr 2023.

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [Interpretation of Neural Networks is Fragile](https://mlsanity.com/paper/1710.10547/) (2017)
- [Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2110.14049/) (2021)
- [The Shapley Taylor Interaction Index](https://mlsanity.com/paper/1902.05622/) (2019)
- [Data Valuation using Reinforcement Learning](https://mlsanity.com/paper/1909.11671/) (2019)

## Built on by (most cited first, 4 of 4)

- [Efficient Data Shapley for Weighted Nearest Neighbor Algorithms](https://mlsanity.com/paper/2401.11103/) (2024)
- [Pairwise Difference Learning for Classification](https://mlsanity.com/paper/2406.20031/) (2024)
- [LossVal: Efficient Data Valuation for Neural Networks](https://mlsanity.com/paper/2412.04158/) (2024)
- [Validation-Induced Shapley Shifts: How Validation Structure Distorts Data Valuation](https://mlsanity.com/paper/2607.03675/) (2026)

## Abstract (arXiv)

With the rapid growth of data availability and usage, quantifying the added value of each training data point has become a crucial process in the field of artificial intelligence. The Shapley values have been recognized as an effective method for data valuation, enabling efficient training set summarization, acquisition, and outlier removal. In this paper, we introduce "STI-KNN", an innovative algorithm that calculates the exact pair-interaction Shapley values for KNN models in O(t n2) time, which is a significant improvement over the O(2n) time complexity of baseline methods. By using STI-KNN, we can efficiently and accurately evaluate the value of individual data points, leading to improved training outcomes and ultimately enhancing the effectiveness of artificial intelligence applications.