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: 12039
Venue: VLDB
Year: 2020
Pagerank: 5.343155e-05
Overall Rank: 5,744 | 60.08%
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,583	Budget Constrained Interactive Search for Multiple Targets	2021	VLDB	4.9979684e-05
9,678	Interactive Graph Search for Multiple Targets on DAGs	2025	VLDB	4.3006524e-05
10,091	LLM-Powered Interactive Graph Search: A Scalable and Practical Approach	2026	SIGMOD	4.1905499e-05
10,528	Interactive Graph Search Made Simple	2025	SIGMOD	4.1905499e-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
246	Crowdsourced Databases: Query Processing with People	2011	CIDR	0.00030952631
265	CrowdER: Crowdsourcing Entity Resolution	2012	VLDB	0.00029904018
266	Human-powered Sorts and Joins	2012	VLDB	0.00029884758
691	Human-Assisted Graph Search: It’s Okay to Ask Questions	2011	VLDB	0.00018068414
863	Leveraging Transitive Relations for Crowdsourced Joins	2013	SIGMOD	0.00015793243
1,154	CrowdScreen: Algorithms for Filtering Data with Humans	2012	SIGMOD	0.00013616867
1,242	Question Selection for Crowd Entity Resolution	2013	VLDB	0.00013088272
1,842	Crowdsourcing Algorithms for Entity Resolution	2014	VLDB	0.00010342022
2,255	Counting with the Crowd	2013	VLDB	9.1846281e-05
2,796	Finish Them!: Pricing Algorithms for Human Computation	2014	VLDB	8.1119959e-05
2,944	Truth Inference in Crowdsourcing: Is the Problem Solved?	2017	VLDB	7.8457167e-05
3,268	QASCA: A Quality-Aware Task Assignment System for Crowdsourcing Applications	2015	SIGMOD	7.3027561e-05
3,324	iCrowd: An Adaptive Crowdsourcing Framework	2015	SIGMOD	7.2163115e-05
4,483	Optimal Crowd-Powered Rating and Filtering Algorithms	2014	VLDB	6.1431599e-05
5,254	CDB: A Crowd-Powered Database System	2018	VLDB	5.5991922e-05
7,112	Answering Planning Queries with the Crowd	2013	VLDB	4.8227734e-05
7,534	Interactive Graph Search	2019	SIGMOD	4.7133212e-05
8,062	Where To: Crowd-Aided Path Selection	2014	VLDB	4.5902135e-05
11,824	DOCS: Domain-Aware Crowdsourcing System	2017	VLDB	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,358	Minimizing Efforts in Validating Crowd Answers	2015	SIGMOD	4.5324924e-05
11,713	A Rating-Ranking Method for Crowdsourced Top-k Computation	2018	SIGMOD	4.1905499e-05
3,020	Scaling Up Crowd-Sourcing to Very Large Datasets: A Case for Active Learning	2015	VLDB	7.6987905e-05
7,112	Answering Planning Queries with the Crowd	2013	VLDB	4.8227734e-05
4,483	Optimal Crowd-Powered Rating and Filtering Algorithms	2014	VLDB	6.1431599e-05
13,228	Automated Category Tree Construction in E-Commerce	2022	SIGMOD	-
11,910	The Importance of Being Expert: Efficient Max-Finding in Crowdsourcing	2015	SIGMOD	4.1905499e-05
11,599	Minimization of Classifier Construction Cost for Search Queries	2020	SIGMOD	4.1905499e-05
1,242	Question Selection for Crowd Entity Resolution	2013	VLDB	0.00013088272
4,832	An Online Cost Sensitive Decision-Making Method in Crowdsourcing Systems	2013	SIGMOD	5.8883457e-05