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.00013206323
Overall Rank
894 | 94.00%
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,847 Data Market Platforms: Trading Data Assets to Solve Data Problems 2020 VLDB 9.5091361e-05
1,848 Nearest Neighbor Classifiers over Incomplete Information: From Certain Answers to Certain Predictions 2021 VLDB 9.5075544e-05
3,686 Secure Shapley Value for Cross-Silo Federated Learning 2023 VLDB 7.095629e-05
3,731 Protecting Data Markets from Strategic Buyers 2022 SIGMOD 7.0660724e-05
3,782 Dealer: An End-to-End Model Marketplace with Differential Privacy 2021 VLDB 7.0216208e-05
4,906 Data-Sharing Markets: Model, Protocol, and Algorithms to Incentivize the Formation of Data-Sharing Consortia 2023 SIGMOD 6.3594272e-05
4,929 Efficient Sampling Approaches to Shapley Value Approximation 2023 SIGMOD 6.3471946e-05
5,432 Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple Games 2024 SIGMOD 6.1310946e-05
5,748 Optimizing Data Acquisition to Enhance Machine Learning Performance 2024 VLDB 6.0054988e-05
6,116 Equitable Data Valuation Meets the Right to Be Forgotten in Model Markets 2023 VLDB 5.8789701e-05
6,393 On Shapley Value in Data Assemblage Under Independent Utility 2022 VLDB 5.7982545e-05
7,544 Automating and Optimizing Data-Centric What-If Analyses on Native Machine Learning Pipelines 2023 SIGMOD 5.496984e-05
7,635 mlwhatif: What If You Could Stop Re-Implementing Your Machine Learning Pipeline Analyses Over and Over? 2023 VLDB 5.4777741e-05
8,156 P-Shapley: Shapley Values on Probabilistic Classifiers 2024 VLDB 5.3875084e-05
8,216 Contributions Estimation in Federated Learning: A Comprehensive Experimental Evaluation 2024 VLDB 5.3748914e-05
8,312 Demonstration of Dealer: An End-to-End Model Marketplace with Differential Privacy 2021 VLDB 5.3562257e-05
9,728 Shapley Value Estimation Based on Differential Matrix 2025 SIGMOD 5.1325223e-05
10,426 ASSS: Adaptive Stratified Sampling for Shapley-like Values 2026 SIGMOD 4.9769913e-05
10,442 CoShap: A Scalable Coalition Growth Approach to Shapley Value Approximation 2026 SIGMOD 4.9769913e-05
10,604 Reliable and Private Utility Signaling for Data Markets 2026 SIGMOD 4.9769913e-05
10,766 Efficient Banzhaf-Based Data Valuation for k-Nearest Neighbors Classification 2026 VLDB 4.9769913e-05
10,874 Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuation 2026 VLDB 4.9769913e-05
11,227 WeShap: Weak Supervision Source Evaluation with Shapley Values 2025 VLDB 4.9769913e-05
11,332 PS-MI: Accurate, Efficient, and Private Data Valuation in Vertical Federated Learning 2025 VLDB 4.9769913e-05
11,413 mlidea: Interactively Improving ML Data Preparation Code via “Shadow Pipelines” 2025 VLDB 4.9769913e-05
11,558 Performance-Based Pricing for Federated Learning via Auction 2024 VLDB 4.9769913e-05
11,942 Ease.ML: A Lifecycle Management System for MLDev and MLOps 2021 CIDR 4.9769913e-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.0005758001
1,859 On Arbitrage-free Pricing for General Data Queries 2014 VLDB 9.4873717e-05
2,714 Toward Practical Query Pricing with QueryMarket 2013 SIGMOD 8.0980837e-05
3,078 Price-Optimal Querying with Data APIs 2016 VLDB 7.6712439e-05
4,518 How to Price Shared Optimizations in the Cloud 2012 VLDB 6.5610867e-05
5,977 QueryMarket Demonstration: Pricing for Online Data Markets 2012 VLDB 5.9263743e-05
6,676 QIRANA Demonstration: Real Time Scalable Query Pricing 2017 VLDB 5.7106759e-05
7,241 A Demonstration of Sterling: A Privacy-Preserving Data Marketplace 2018 VLDB 5.5756287e-05
Previous Page 1 / 1 Next

Semantically Similar Papers