Minimization of Classifier Construction Cost for Search Queries

Summary: Minimize classifier construction cost for search over massive item sets by selecting which classifiers to train under non-uniform costs. Proves NP-hard inapproximability; presents approximation algorithms with guarantees and an exact algorithm for a common special case, validated on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6032
Venue: SIGMOD
Year: 2020
Pagerank: 5.093636e-05
Overall Rank: 11,790 | 19.11%
DOI: 10.1145/3318464.3389755

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Shay Gershtein (Tel Aviv University)
2. Tova Milo (Tel Aviv University)
3. Gefen Morami (Tel Aviv University)
4. Slava Novgorodov (eBay)

BibTeX Citation

@inproceedings{gershtein_sigmod20,
        title = {{Minimization of Classifier Construction Cost for Search Queries}},
        author = {Gershtein, Shay and Milo, Tova and Morami, Gefen and Novgorodov, Slava},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3389755},
        url = {https://dl.acm.org/doi/10.1145/3318464.3389755},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,112	Classifier Construction Under Budget Constraints	2022	SIGMOD	5.1319012e-05
11,777	MC3: A System for Minimization of Classifier Construction Cost	2020	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
11	Implementing Data Cubes Efficiently	1996	SIGMOD	0.00071822821
929	Materialized View Selection and Maintenance Using Multi-Query Optimization	2001	SIGMOD	0.00013152103
2,219	Chimera: Large-Scale Classification using Machine Learning, Rules, and Crowdsourcing	2014	VLDB	8.9303727e-05
3,188	On the Complexity of the View-Selection Problem	1999	PODS	7.6547735e-05
9,205	GOLDRUSH: Rule Sharing System for Fraud Detection	2018	VLDB	5.3058708e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,417	Automated Category Tree Construction in E-Commerce	2022	SIGMOD
2	11,833	Regularizing Conjunctive Features for Classification	2019	PODS
3	9,874	Fast Search-By-Classification for Large-Scale Databases Using Index-Aware Decision Trees and Random Forests	2023	VLDB
4	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
5	12,580	Relaxation in Text Search using Taxonomies	2008	VLDB
6	4,657	Finding Near Neighbors Through Cluster Pruning	2007	PODS
7	5,813	Efficient Algorithms for Crowd-Aided Categorization	2020	VLDB
8	7,896	Optimizing Index for Taxonomy Keyword Search	2012	SIGMOD
9	6,906	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD
10	10,112	Classifier Construction Under Budget Constraints	2022	SIGMOD