Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms
Summary: Makes Shapley data valuation tractable for KNN: exact values for all points in O(N log N), versus exponential general-case cost. LSH yields sublinear approximation, with extensions to weighted KNN, multiple curators, and analyst compensation. (summarized by gpt-5.6-luna on Jul 24 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Ruoxi Jia (University of California Berkeley)
- 2. David Dao (ETH Zurich)
- 3. Boxin Wang (Zhejiang University)
- 4. Frances Ann Hubis (ETH Zurich)
- 5. Nezihe Merve Gurel (ETH Zurich)
- 6. Bo Li (University of Illinois Urbana-Champaign)
- 7. Ce Zhang (ETH Zurich)
- 8. Costas Spanos (University of California Berkeley)
- 9. Dawn Song (University of California Berkeley)
BibTeX Citation
@article{jia_vldb19,
title = {{Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms}},
author = {Jia, Ruoxi and Dao, David and Wang, Boxin and Hubis, Frances Ann and Gurel, Nezihe Merve and Li, Bo and Zhang, Ce and Spanos, Costas and Song, Dawn},
journal = {PVLDB},
series = {{VLDB} '19},
volume = {12},
number = {11},
pages = {1610--1623},
doi = {10.14778/3342263.3342637},
url = {https://doi.org/10.14778/3342263.3342637},
year = {2019}
}
Incoming Citations (Sorted by Pagerank)
Showing 25 of 25 citing papers.
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 8 of 8 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 21 | Similarity Search in High Dimensions via Hashing | 1999 | VLDB | 0.00056760516 |
| 1,861 | On Arbitrage-free Pricing for General Data Queries | 2014 | VLDB | 9.5965642e-05 |
| 2,719 | Toward Practical Query Pricing with QueryMarket | 2013 | SIGMOD | 8.209612e-05 |
| 3,081 | Price-Optimal Querying with Data APIs | 2016 | VLDB | 7.7743445e-05 |
| 4,521 | How to Price Shared Optimizations in the Cloud | 2012 | VLDB | 6.6468071e-05 |
| 6,036 | QueryMarket Demonstration: Pricing for Online Data Markets | 2012 | VLDB | 5.9995474e-05 |
| 6,769 | QIRANA Demonstration: Real Time Scalable Query Pricing | 2017 | VLDB | 5.7788116e-05 |
| 7,107 | A Demonstration of Sterling: A Privacy-Preserving Data Marketplace | 2018 | VLDB | 5.700522e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 4,927 | Neighbor-Sensitive Hashing | 2016 | VLDB |
| 2 | 6,783 | Counterfactual Explanation of Shapley Value in Data Coalitions | 2024 | VLDB |
| 3 | 2,424 | Computing the Shapley Value of Facts in Query Answering | 2022 | SIGMOD |
| 4 | 10,906 | A Comprehensive Study of Shapley Value in Data Analytics | 2025 | VLDB |
| 5 | 5,441 | Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple Games | 2024 | SIGMOD |
| 6 | 8,250 | P-Shapley: Shapley Values on Probabilistic Classifiers | 2024 | VLDB |
| 7 | 10,214 | CoShap: A Scalable Coalition Growth Approach to Shapley Value Approximation | 2026 | SIGMOD |
| 8 | 10,796 | Understanding the Black Box: A Deep Empirical Dive into Shapley Value Approximations for Tabular Data | 2025 | SIGMOD |
| 9 | 6,272 | On Shapley Value in Data Assemblage Under Independent Utility | 2022 | VLDB |
| 10 | 6,145 | Equitable Data Valuation Meets the Right to Be Forgotten in Model Markets | 2023 | VLDB |