Interactive Graph Search for Multiple Targets on DAGs

Summary: Extends interactive graph search to multiple hidden targets on DAGs using uncertain candidates and a gain-driven query strategy. The unified k-EIS framework handles single and multiple targets, reducing worst-case questions from O(n) to O(log² n) and enabling subgraph decomposition. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h565ef0c8422a0a20
Venue: VLDB
Year: 2025
Pagerank: 5.2110714e-05
Overall Rank: 9,191 | 38.21%
DOI: 10.14778/3717755.3717768

Incoming Non-self Citations Over Time

Authors

1. Zheng Wu (Hong Kong Baptist University)
2. Xuliang Zhu (Shanghai Jiao Tong University)
3. Yixiang Fang (Chinese University of Hong Kong)
4. Jianliang Xu (Hong Kong Baptist University)
5. Xin Huang (Hong Kong Baptist University)

BibTeX Citation

@article{wu_vldb25,
        title = {{Interactive Graph Search for Multiple Targets on DAGs}},
        author = {Wu, Zheng and Zhu, Xuliang and Fang, Yixiang and Xu, Jianliang and Huang, Xin},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {4},
        pages = {1091--1103},
        doi = {10.14778/3717755.3717768},
        url = {https://doi.org/10.14778/3717755.3717768},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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 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
749	So Who Won? Dynamic Max Discovery with the Crowd	2012	SIGMOD	0.00014265279
787	Human-Assisted Graph Search: It’s Okay to Ask Questions	2011	VLDB	0.00013988274
933	Question Selection for Crowd Entity Resolution	2013	VLDB	0.00013004422
987	CrowdScreen: Algorithms for Filtering Data with Humans	2012	SIGMOD	0.00012660627
1,042	YAGO3: A Knowledge Base from Multilingual Wikipedias	2015	CIDR	0.00012336872
1,264	CDAS: A Crowdsourcing Data Analytics System	2012	VLDB	0.0001128316
1,926	Counting with the Crowd	2013	VLDB	9.3637786e-05
3,197	iCrowd: An Adaptive Crowdsourcing Framework	2015	SIGMOD	7.5455503e-05
3,409	Waldo: An Adaptive Human Interface for Crowd Entity Resolution	2017	SIGMOD	7.3264601e-05
3,838	Optimal Crowd-Powered Rating and Filtering Algorithms	2014	VLDB	6.9929907e-05
4,478	Top-k Sorting Under Partial Order Information	2018	SIGMOD	6.5814419e-05
5,570	Efficient Algorithms for Crowd-Aided Categorization	2020	VLDB	6.0811968e-05
6,629	Budget Constrained Interactive Search for Multiple Targets	2021	VLDB	5.7274363e-05
6,925	Interactive Graph Search	2019	SIGMOD	5.6423723e-05
8,252	Optimal Algorithms for Multiway Search on Partial Orders	2022	PODS	5.3685285e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,725	Exploratory Keyword Search on Data Graphs	2010	SIGMOD
2	5,477	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD
3	3,767	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB
4	12,095	IDAR: Fast Supergraph Search Using DAG Integration	2020	VLDB
5	10,578	LLM-Powered Interactive Graph Search: A Scalable and Practical Approach	2026	SIGMOD
6	10,850	Noisy Interactive Graph Search: An Uncertainty-Based Approach with Online Modeling of Latent Expertise and Difficulty	2026	VLDB
7	787	Human-Assisted Graph Search: It’s Okay to Ask Questions	2011	VLDB
8	9,535	Interactive Graph Search Made Simple	2025	SIGMOD
9	6,925	Interactive Graph Search	2019	SIGMOD
10	6,629	Budget Constrained Interactive Search for Multiple Targets	2021	VLDB