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.2815042e-05
Overall Rank: 9,763 | 32.15%
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.1905499e-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
48	Nearest Neighbor Queries	1995	SIGMOD	0.0006954126
675	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018304179
2,099	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.5429949e-05
4,026	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	6.5166769e-05
4,721	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	5.9647585e-05
7,080	Nearest Neighbor Searching Under Uncertainty II	2013	PODS	4.8353058e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,599	Minimization of Classifier Construction Cost for Search Queries	2020	SIGMOD	4.1905499e-05
4,035	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.5111577e-05
1,293	Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms	2019	VLDB	0.00012749902
9,158	Computing Rule-Based Explanations by Leveraging Counterfactuals	2023	VLDB	4.380727e-05
12,235	K-Nearest Neighbor Search for Fuzzy Objects	2010	SIGMOD	4.1905499e-05
8,687	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	4.4621895e-05
11,558	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	4.1905499e-05
1,535	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011461371
10,942	Relative Keys: Putting Feature Explanation into Context	2024	SIGMOD	4.1905499e-05
2,308	Nearest Neighbor Classifiers over Incomplete Information: From Certain Answers to Certain Predictions	2021	VLDB	9.0634287e-05