Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations

Summary: Explores feature-level explanations for k-NN, introducing abductive minimum-sufficient-reason explanations and counterfactual explanations for classifications. Charts a complexity landscape across discrete vs continuous features and distance functions, and enables practical computation via Integer Quadratic Programming and SAT. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 1968
Venue: PODS
Year: 2025
Pagerank: 4.2856106e-05
Overall Rank: 9,761 | 32.10%
DOI: 10.1145/3725234

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,269	Database Views as Explanations for Relational Deep Learning	2026	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
47	Nearest Neighbor Queries	1995	SIGMOD	0.0007015885
682	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018201541
2,107	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.5330494e-05
4,021	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	6.5225987e-05
4,724	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	5.9697823e-05
7,084	Nearest Neighbor Searching Under Uncertainty II	2013	PODS	4.839879e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,595	Minimization of Classifier Construction Cost for Search Queries	2020	SIGMOD	4.1945683e-05
4,070	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.4784181e-05
1,298	Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms	2019	VLDB	0.00012758104
9,158	Computing Rule-Based Explanations by Leveraging Counterfactuals	2023	VLDB	4.3849295e-05
12,227	K-Nearest Neighbor Search for Fuzzy Objects	2010	SIGMOD	4.1945683e-05
8,693	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	4.466142e-05
11,554	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	4.1945683e-05
1,542	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011456321
10,939	Relative Keys: Putting Feature Explanation into Context	2024	SIGMOD	4.1945683e-05
2,302	Nearest Neighbor Classifiers over Incomplete Information: From Certain Answers to Certain Predictions	2021	VLDB	9.0668832e-05