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: h2709ff5a7ad29b7e
Venue: VLDB
Year: 2020
Pagerank: 6.0811968e-05
Overall Rank: 5,570 | 62.56%
DOI: 10.14778/3389133.3389139

Incoming Non-self Citations Over Time

Authors

1. Yuanbing Li (Tsinghua University)
2. Xian Wu (Tsinghua University)
3. Yifei Jin (Tsinghua University)
4. Jian Li (Tsinghua University)
5. Guoliang Li (Tsinghua University)

BibTeX Citation

@article{li_vldb20,
        title = {{Efficient Algorithms for Crowd-Aided Categorization}},
        author = {Li, Yuanbing and Wu, Xian and Jin, Yifei and Li, Jian and Li, Guoliang},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {8},
        pages = {1221--1233},
        doi = {10.14778/3389133.3389139},
        url = {https://doi.org/10.14778/3389133.3389139},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,629	Budget Constrained Interactive Search for Multiple Targets	2021	VLDB	5.7274363e-05
9,191	Interactive Graph Search for Multiple Targets on DAGs	2025	VLDB	5.2110714e-05
9,535	Interactive Graph Search Made Simple	2025	SIGMOD	5.163649e-05
10,578	LLM-Powered Interactive Graph Search: A Scalable and Practical Approach	2026	SIGMOD	4.9793485e-05
10,850	Noisy Interactive Graph Search: An Uncertainty-Based Approach with Online Modeling of Latent Expertise and Difficulty	2026	VLDB	4.9793485e-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
198	CrowdER: Crowdsourcing Entity Resolution	2012	VLDB	0.00025555196
257	Crowdsourced Databases: Query Processing with People	2011	CIDR	0.00022962347
266	Human-powered Sorts and Joins	2012	VLDB	0.00022739124
787	Human-Assisted Graph Search: It’s Okay to Ask Questions	2011	VLDB	0.00013988274
871	Leveraging Transitive Relations for Crowdsourced Joins	2013	SIGMOD	0.00013343705
933	Question Selection for Crowd Entity Resolution	2013	VLDB	0.00013004422
987	CrowdScreen: Algorithms for Filtering Data with Humans	2012	SIGMOD	0.00012660627
1,472	Crowdsourcing Algorithms for Entity Resolution	2014	VLDB	0.00010558263
1,926	Counting with the Crowd	2013	VLDB	9.3637786e-05
3,171	Truth Inference in Crowdsourcing: Is the Problem Solved?	2017	VLDB	7.5691557e-05
3,197	iCrowd: An Adaptive Crowdsourcing Framework	2015	SIGMOD	7.5455503e-05
3,372	Finish Them!: Pricing Algorithms for Human Computation	2014	VLDB	7.3693102e-05
3,838	Optimal Crowd-Powered Rating and Filtering Algorithms	2014	VLDB	6.9929907e-05
3,839	QASCA: A Quality-Aware Task Assignment System for Crowdsourcing Applications	2015	SIGMOD	6.9921604e-05
5,061	CDB: A Crowd-Powered Database System	2018	VLDB	6.2912543e-05
6,925	Interactive Graph Search	2019	SIGMOD	5.6423723e-05
7,089	Answering Planning Queries with the Crowd	2013	VLDB	5.6018191e-05
8,137	Where To: Crowd-Aided Path Selection	2014	VLDB	5.3924339e-05
12,314	DOCS: Domain-Aware Crowdsourcing System	2017	VLDB	4.9793485e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,518	Minimizing Efforts in Validating Crowd Answers	2015	SIGMOD
2	12,212	A Rating-Ranking Method for Crowdsourced Top-k Computation	2018	SIGMOD
3	2,642	Scaling Up Crowd-Sourcing to Very Large Datasets: A Case for Active Learning	2015	VLDB
4	7,089	Answering Planning Queries with the Crowd	2013	VLDB
5	3,838	Optimal Crowd-Powered Rating and Filtering Algorithms	2014	VLDB
6	13,731	Automated Category Tree Construction in E-Commerce	2022	SIGMOD
7	12,394	The Importance of Being Expert: Efficient Max-Finding in Crowdsourcing	2015	SIGMOD
8	12,092	Minimization of Classifier Construction Cost for Search Queries	2020	SIGMOD
9	933	Question Selection for Crowd Entity Resolution	2013	VLDB
10	5,250	An Online Cost Sensitive Decision-Making Method in Crowdsourcing Systems	2013	SIGMOD