Interactive Graph Search for Multiple Targets on DAGs

Summary: Tackles multiple-target interactive graph search on DAGs via "uncertain candidates" and a gain function to select queries, yielding a unified k‑EIS framework for single/multiple targets. Proves worst‑case queries drop from O(n) to O(log^2 n) and empirically outperforms four IGS baselines. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13782
Venue: VLDB
Year: 2025
Pagerank: 4.3006524e-05
Overall Rank: 9,678 | 32.74%
DOI: 10.14778/3717755.3717768

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,091	LLM-Powered Interactive Graph Search: A Scalable and Practical Approach	2026	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
691	Human-Assisted Graph Search: It’s Okay to Ask Questions	2011	VLDB	0.00018068414
805	YAGO3: A Knowledge Base from Multilingual Wikipedias	2015	CIDR	0.00016431373
854	So Who Won? Dynamic Max Discovery with the Crowd	2012	SIGMOD	0.00015879917
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,491	CDAS: A Crowdsourcing Data Analytics System	2012	VLDB	0.00011685731
2,255	Counting with the Crowd	2013	VLDB	9.1846281e-05
3,324	iCrowd: An Adaptive Crowdsourcing Framework	2015	SIGMOD	7.2163115e-05
4,112	Waldo: An Adaptive Human Interface for Crowd Entity Resolution	2017	SIGMOD	6.4329055e-05
4,483	Optimal Crowd-Powered Rating and Filtering Algorithms	2014	VLDB	6.1431599e-05
4,922	Top-k Sorting Under Partial Order Information	2018	SIGMOD	5.8226327e-05
5,744	Efficient Algorithms for Crowd-Aided Categorization	2020	VLDB	5.343155e-05
6,583	Budget Constrained Interactive Search for Multiple Targets	2021	VLDB	4.9979684e-05
7,534	Interactive Graph Search	2019	SIGMOD	4.7133212e-05
9,382	Optimal Algorithms for Multiway Search on Partial Orders	2022	PODS	4.3438908e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,959	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	5.7992713e-05
12,247	Exploratory Keyword Search on Data Graphs	2010	SIGMOD	4.1905499e-05
5,903	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.2757528e-05
4,486	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1413967e-05
11,602	IDAR: Fast Supergraph Search Using DAG Integration	2020	VLDB	4.1905499e-05
10,091	LLM-Powered Interactive Graph Search: A Scalable and Practical Approach	2026	SIGMOD	4.1905499e-05
691	Human-Assisted Graph Search: It’s Okay to Ask Questions	2011	VLDB	0.00018068414
10,528	Interactive Graph Search Made Simple	2025	SIGMOD	4.1905499e-05
7,534	Interactive Graph Search	2019	SIGMOD	4.7133212e-05
6,583	Budget Constrained Interactive Search for Multiple Targets	2021	VLDB	4.9979684e-05