  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 n^2) time, which is a significant
improvement over the O(2^n)$ 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.
