Human-Assisted Graph Search: It’s Okay to Ask Questions

Summary: Introduces HumanGS, the first formal optimization framework for locating unknown targets in DAGs via omniscient reachability queries. Develops algorithms and complexity results under question- and uncertainty-minimization objectives, validated on webpage-taxonomy categorization. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10447
Venue: VLDB
Year: 2011
Pagerank: 0.00014208622
Overall Rank: 767 | 94.74%
DOI: 10.14778/1978335.1978340

Incoming Non-self Citations Over Time

Authors

1. Aditya Parameswaran (Stanford University)
2. Anish Das Sarma (Yahoo)
3. Hector Garcia-Molina (Stanford University)
4. Neoklis Polyzotis (University of California Santa Cruz)
5. Jennifer Widom (Stanford University)

BibTeX Citation

@article{parameswaran_vldb11,
        title = {{Human-Assisted Graph Search: It’s Okay to Ask Questions}},
        author = {Parameswaran, Aditya and Sarma, Anish Das and Garcia-Molina, Hector and Polyzotis, Neoklis and Widom, Jennifer},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {5},
        pages = {267--278},
        doi = {10.14778/1978335.1978340},
        url = {https://doi.org/10.14778/1978335.1978340},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
90	CrowdDB: Answering Queries with Crowdsourcing	2011	SIGMOD	0.00034951786
250	Answering Queries using Humans, Algorithms and Databases	2011	CIDR	0.00023261164
743	So Who Won? Dynamic Max Discovery with the Crowd	2012	SIGMOD	0.00014421358
852	Leveraging Transitive Relations for Crowdsourced Joins	2013	SIGMOD	0.00013604253
997	CrowdScreen: Algorithms for Filtering Data with Humans	2012	SIGMOD	0.00012755983
1,270	CDAS: A Crowdsourcing Data Analytics System	2012	VLDB	0.00011388453
1,643	Falcon: Scaling Up Hands-Off Crowdsourced Entity Matching to Build Cloud Services	2017	SIGMOD	0.00010134956
3,262	iCrowd: An Adaptive Crowdsourcing Framework	2015	SIGMOD	7.5846052e-05
3,314	Finish Them!: Pricing Algorithms for Human Computation	2014	VLDB	7.5279588e-05
4,153	Whom to Ask? Jury Selection for Decision Making Tasks on Micro-blog Services	2012	VLDB	6.8676997e-05
4,428	Arnold: Declarative Crowd-Machine Data Integration	2013	CIDR	6.7094035e-05
4,539	Reducing Uncertainty of Schema Matching via Crowdsourcing	2013	VLDB	6.6403822e-05
5,143	An Online Cost Sensitive Decision-Making Method in Crowdsourcing Systems	2013	SIGMOD	6.3476753e-05
5,343	Crowdsourcing Applications and Platforms: A Data Management Perspective	2011	VLDB	6.259258e-05
5,813	Efficient Algorithms for Crowd-Aided Categorization	2020	VLDB	6.0780519e-05
7,021	Budget Constrained Interactive Search for Multiple Targets	2021	VLDB	5.7242766e-05
7,222	Hear the Whole Story: Towards the Diversity of Opinion in Crowdsourcing Markets	2015	VLDB	5.6679185e-05
7,313	Interactive Graph Search	2019	SIGMOD	5.6480084e-05
7,357	Crowdsourced Data Management: Overview and Challenges	2017	SIGMOD	5.6346837e-05
7,989	Where To: Crowd-Aided Path Selection	2014	VLDB	5.5111036e-05
9,812	Interactive Graph Search for Multiple Targets on DAGs	2025	VLDB	5.214913e-05
10,031	tDP: An Optimal-Latency Budget Allocation Strategy for Crowdsourced MAXIMUM Operations	2015	SIGMOD	5.1741314e-05
10,382	LLM-Powered Interactive Graph Search: A Scalable and Practical Approach	2026	SIGMOD	5.093636e-05
10,792	Interactive Graph Search Made Simple	2025	SIGMOD	5.093636e-05
12,052	Graph Summarization for Geo-correlated Trends Detection in Social Networks	2016	SIGMOD	5.093636e-05
12,310	Mob Data Sourcing	2012	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
250	Answering Queries using Humans, Algorithms and Databases	2011	CIDR	0.00023261164
791	An Interactive Clustering-based Approach to Integrating Source Query Interfaces on the Deep Web	2004	SIGMOD	0.00013995705
866	Pay-as-you-go User Feedback for Dataspace Systems	2008	SIGMOD	0.00013519288
1,871	Efficient Lineage Tracking For Scientific Workflows	2008	SIGMOD	9.5783449e-05
1,873	A Web of Concepts	2009	PODS	9.5751398e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,691	A Flexible Framework for Query-oriented Interactive Community Search	2025	VLDB
2	12,287	Probabilistic Query Rewriting for Efficient and Effective Keyword Search on Graph Data	2013	VLDB
3	997	CrowdScreen: Algorithms for Filtering Data with Humans	2012	SIGMOD
4	5,813	Efficient Algorithms for Crowd-Aided Categorization	2020	VLDB
5	7,018	Answering Planning Queries with the Crowd	2013	VLDB
6	10,382	LLM-Powered Interactive Graph Search: A Scalable and Practical Approach	2026	SIGMOD
7	7,021	Budget Constrained Interactive Search for Multiple Targets	2021	VLDB
8	10,792	Interactive Graph Search Made Simple	2025	SIGMOD
9	9,812	Interactive Graph Search for Multiple Targets on DAGs	2025	VLDB
10	7,313	Interactive Graph Search	2019	SIGMOD