Nearest Neighbor Classifiers over Incomplete Information: From Certain Answers to Certain Predictions
Summary: Introduces Certain Predictions (CP): a test point is certain when classifiers trained over all possible worlds of incomplete data agree on its label. For nearest-neighbor models, CP checking/counting is tractable despite exponentially many worlds, powering CPClean. (summarized by gpt-5.6-luna on Jul 24 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Bojan Karlaš (ETH Zurich)
- 2. Peng Li (Georgia Institute of Technology)
- 3. Renzhi Wu (Georgia Institute of Technology)
- 4. Nezihe Merve Gürel (ETH Zurich)
- 5. Xu Chu (Georgia Institute of Technology)
- 6. Wentao Wu (Microsoft)
- 7. Ce Zhang (ETH Zurich)
BibTeX Citation
@article{karlas_vldb21,
title = {{Nearest Neighbor Classifiers over Incomplete Information: From Certain Answers to Certain Predictions}},
author = {Karlaš, Bojan and Li, Peng and Wu, Renzhi and Gürel, Nezihe Merve and Chu, Xu and Wu, Wentao and Zhang, Ce},
journal = {PVLDB},
series = {{VLDB} '21},
volume = {14},
number = {3},
pages = {255--267},
doi = {10.14778/3430915.3430917},
url = {https://doi.org/10.14778/3430915.3430917},
year = {2021}
}Incoming Citations (Sorted by Pagerank)
Showing 22 of 22 citing papers.
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 33 | Consistent Query Answers in Inconsistent Databases | 1999 | PODS | 0.00049435337 |
| 100 | HoloClean: Holistic Data Repairs with Probabilistic Inference | 2017 | VLDB | 0.00033951027 |
| 460 | ActiveClean: Interactive Data Cleaning For Statistical Modeling | 2016 | VLDB | 0.00017836918 |
| 897 | Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms | 2019 | VLDB | 0.00013162662 |
| 1,099 | KATARA: A Data Cleaning System Powered by Knowledge Bases and Crowdsourcing | 2015 | SIGMOD | 0.00012008783 |
| 1,721 | A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data | 2014 | SIGMOD | 9.7821782e-05 |
| 4,828 | Nearest-Neighbor Searching Under Uncertainty | 2012 | PODS | 6.3849385e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 4,828 | Nearest-Neighbor Searching Under Uncertainty | 2012 | PODS |
| 2 | 11,045 | Minimal Data Cleaning for Model Training by MinPrep | 2026 | VLDB |
| 3 | 4,321 | Data Series Progressive Similarity Search with Probabilistic Quality Guarantees | 2020 | SIGMOD |
| 4 | 1,641 | Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases | 2008 | VLDB |
| 5 | 5,918 | On Efficient Approximate Queries over Machine Learning Models | 2023 | VLDB |
| 6 | 12,142 | Minimization of Classifier Construction Cost for Search Queries | 2020 | SIGMOD |
| 7 | 3,757 | GoodCore: Data-effective and Data-efficient Machine Learning through Coreset Selection over Incomplete Data | 2023 | SIGMOD |
| 8 | 10,140 | Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations | 2025 | PODS |
| 9 | 5,296 | Enriching Data Imputation with Extensive Similarity Neighbors | 2015 | VLDB |
| 10 | 11,570 | Certain and Approximately Certain Models for Statistical Learning | 2024 | SIGMOD |