Efficient Algorithms for Crowd-Aided Categorization

Summary: Online crowd-aided categorization under a category hierarchy, minimizing questions to place each object. Hardness holds even with known distribution; presents a 2-approximation and an FPTAS, plus an online strategy with near-optimal guarantees. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12038
Venue: VLDB
Year: 2020
Pagerank: 5.3482904e-05
Overall Rank: 5,734 | 60.12%
DOI: 10.14778/3389133.3389139

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,584	Budget Constrained Interactive Search for Multiple Targets	2021	VLDB	5.0027686e-05
9,678	Interactive Graph Search for Multiple Targets on DAGs	2025	VLDB	4.3047774e-05
10,091	LLM-Powered Interactive Graph Search: A Scalable and Practical Approach	2026	SIGMOD	4.1945683e-05
10,519	Interactive Graph Search Made Simple	2025	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
249	Crowdsourced Databases: Query Processing with People	2011	CIDR	0.00030740523
263	CrowdER: Crowdsourcing Entity Resolution	2012	VLDB	0.00029862413
267	Human-powered Sorts and Joins	2012	VLDB	0.00029690405
697	Human-Assisted Graph Search: It’s Okay to Ask Questions	2011	VLDB	0.00018043655
866	Leveraging Transitive Relations for Crowdsourced Joins	2013	SIGMOD	0.00015801196
1,164	CrowdScreen: Algorithms for Filtering Data with Humans	2012	SIGMOD	0.00013564823
1,242	Question Selection for Crowd Entity Resolution	2013	VLDB	0.00013096655
1,841	Crowdsourcing Algorithms for Entity Resolution	2014	VLDB	0.00010348858
2,334	Counting with the Crowd	2013	VLDB	9.0161817e-05
2,792	Finish Them!: Pricing Algorithms for Human Computation	2014	VLDB	8.1197186e-05
2,937	Truth Inference in Crowdsourcing: Is the Problem Solved?	2017	VLDB	7.853108e-05
3,263	QASCA: A Quality-Aware Task Assignment System for Crowdsourcing Applications	2015	SIGMOD	7.3097573e-05
3,322	iCrowd: An Adaptive Crowdsourcing Framework	2015	SIGMOD	7.2230626e-05
4,479	Optimal Crowd-Powered Rating and Filtering Algorithms	2014	VLDB	6.149053e-05
5,279	CDB: A Crowd-Powered Database System	2018	VLDB	5.5902418e-05
7,113	Answering Planning Queries with the Crowd	2013	VLDB	4.8274062e-05
7,535	Interactive Graph Search	2019	SIGMOD	4.7178467e-05
8,056	Where To: Crowd-Aided Path Selection	2014	VLDB	4.5946189e-05
11,816	DOCS: Domain-Aware Crowdsourcing System	2017	VLDB	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,362	Minimizing Efforts in Validating Crowd Answers	2015	SIGMOD	4.5366717e-05
11,707	A Rating-Ranking Method for Crowdsourced Top-k Computation	2018	SIGMOD	4.1945683e-05
3,118	Scaling Up Crowd-Sourcing to Very Large Datasets: A Case for Active Learning	2015	VLDB	7.5379338e-05
7,113	Answering Planning Queries with the Crowd	2013	VLDB	4.8274062e-05
4,479	Optimal Crowd-Powered Rating and Filtering Algorithms	2014	VLDB	6.149053e-05
13,214	Automated Category Tree Construction in E-Commerce	2022	SIGMOD	-
11,902	The Importance of Being Expert: Efficient Max-Finding in Crowdsourcing	2015	SIGMOD	4.1945683e-05
11,595	Minimization of Classifier Construction Cost for Search Queries	2020	SIGMOD	4.1945683e-05
1,242	Question Selection for Crowd Entity Resolution	2013	VLDB	0.00013096655
4,827	An Online Cost Sensitive Decision-Making Method in Crowdsourcing Systems	2013	SIGMOD	5.8938399e-05