DBScholar

Back to papers

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)

Paper ID
h6146fa793e90514e
Venue
VLDB
Year
2019
Pagerank
0.00013162662
Overall Rank
897 | 93.99%
DOI
10.14778/3342263.3342637
PDF
Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

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 27 of 27 citing papers.

Rank Citing Paper Year Venue Pagerank
1,744 Nearest Neighbor Classifiers over Incomplete Information: From Certain Answers to Certain Predictions 2021 VLDB 9.7253583e-05
1,858 Data Market Platforms: Trading Data Assets to Solve Data Problems 2020 VLDB 9.4779185e-05
3,694 Secure Shapley Value for Cross-Silo Federated Learning 2023 VLDB 7.0721664e-05
3,736 Protecting Data Markets from Strategic Buyers 2022 SIGMOD 7.0427076e-05
3,789 Dealer: An End-to-End Model Marketplace with Differential Privacy 2021 VLDB 6.998403e-05
4,930 Data-Sharing Markets: Model, Protocol, and Algorithms to Incentivize the Formation of Data-Sharing Consortia 2023 SIGMOD 6.3383989e-05
4,955 Efficient Sampling Approaches to Shapley Value Approximation 2023 SIGMOD 6.3262068e-05
5,448 Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple Games 2024 SIGMOD 6.1108214e-05
5,759 Optimizing Data Acquisition to Enhance Machine Learning Performance 2024 VLDB 5.9856409e-05
6,130 Equitable Data Valuation Meets the Right to Be Forgotten in Model Markets 2023 VLDB 5.8595306e-05
6,406 On Shapley Value in Data Assemblage Under Independent Utility 2022 VLDB 5.7790819e-05
7,558 Automating and Optimizing Data-Centric What-If Analyses on Native Machine Learning Pipelines 2023 SIGMOD 5.4788791e-05
7,651 mlwhatif: What If You Could Stop Re-Implementing Your Machine Learning Pipeline Analyses Over and Over? 2023 VLDB 5.4596612e-05
8,173 P-Shapley: Shapley Values on Probabilistic Classifiers 2024 VLDB 5.369694e-05
8,233 Contributions Estimation in Federated Learning: A Comprehensive Experimental Evaluation 2024 VLDB 5.3571186e-05
8,326 Demonstration of Dealer: An End-to-End Model Marketplace with Differential Privacy 2021 VLDB 5.3385147e-05
9,759 Shapley Value Estimation Based on Differential Matrix 2025 SIGMOD 5.115551e-05
10,492 ASSS: Adaptive Stratified Sampling for Shapley-like Values 2026 SIGMOD 4.9605343e-05
10,508 CoShap: A Scalable Coalition Growth Approach to Shapley Value Approximation 2026 SIGMOD 4.9605343e-05
10,666 Reliable and Private Utility Signaling for Data Markets 2026 SIGMOD 4.9605343e-05
10,827 Efficient Banzhaf-Based Data Valuation for k-Nearest Neighbors Classification 2026 VLDB 4.9605343e-05
10,935 Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuation 2026 VLDB 4.9605343e-05
11,283 WeShap: Weak Supervision Source Evaluation with Shapley Values 2025 VLDB 4.9605343e-05
11,386 PS-MI: Accurate, Efficient, and Private Data Valuation in Vertical Federated Learning 2025 VLDB 4.9605343e-05
11,466 mlidea: Interactively Improving ML Data Preparation Code via “Shadow Pipelines” 2025 VLDB 4.9605343e-05
11,607 Performance-Based Pricing for Federated Learning via Auction 2024 VLDB 4.9605343e-05
11,986 Ease.ML: A Lifecycle Management System for MLDev and MLOps 2021 CIDR 4.9605343e-05
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
20 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00057610161
1,868 On Arbitrage-free Pricing for General Data Queries 2014 VLDB 9.4560065e-05
2,725 Toward Practical Query Pricing with QueryMarket 2013 SIGMOD 8.0713119e-05
3,087 Price-Optimal Querying with Data APIs 2016 VLDB 7.6458839e-05
4,540 How to Price Shared Optimizations in the Cloud 2012 VLDB 6.539392e-05
5,988 QueryMarket Demonstration: Pricing for Online Data Markets 2012 VLDB 5.9067784e-05
6,689 QIRANA Demonstration: Real Time Scalable Query Pricing 2017 VLDB 5.6917932e-05
7,260 A Demonstration of Sterling: A Privacy-Preserving Data Marketplace 2018 VLDB 5.5571922e-05
Previous Page 1 / 1 Next

Semantically Similar Papers