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.2086045e-05
Overall Rank: 9,200 | 38.17%
DOI: 10.14778/3717755.3717768
PDF: Download (CC BY-NC-ND 4.0)

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,589	LLM-Powered Interactive Graph Search: A Scalable and Practical Approach	2026	SIGMOD	4.9769913e-05
10,859	Noisy Interactive Graph Search: An Uncertainty-Based Approach with Online Modeling of Latent Expertise and Difficulty	2026	VLDB	4.9769913e-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
750	So Who Won? Dynamic Max Discovery with the Crowd	2012	SIGMOD	0.00014258988
787	Human-Assisted Graph Search: It’s Okay to Ask Questions	2011	VLDB	0.00013982951
934	Question Selection for Crowd Entity Resolution	2013	VLDB	0.00012998402
987	CrowdScreen: Algorithms for Filtering Data with Humans	2012	SIGMOD	0.00012655094
1,043	YAGO3: A Knowledge Base from Multilingual Wikipedias	2015	CIDR	0.00012331034
1,265	CDAS: A Crowdsourcing Data Analytics System	2012	VLDB	0.00011277921
1,926	Counting with the Crowd	2013	VLDB	9.3636304e-05
3,199	iCrowd: An Adaptive Crowdsourcing Framework	2015	SIGMOD	7.5419863e-05
3,409	Waldo: An Adaptive Human Interface for Crowd Entity Resolution	2017	SIGMOD	7.3230153e-05
3,839	Optimal Crowd-Powered Rating and Filtering Algorithms	2014	VLDB	6.9896853e-05
4,482	Top-k Sorting Under Partial Order Information	2018	SIGMOD	6.5783263e-05
5,572	Efficient Algorithms for Crowd-Aided Categorization	2020	VLDB	6.078318e-05
6,633	Budget Constrained Interactive Search for Multiple Targets	2021	VLDB	5.724725e-05
6,928	Interactive Graph Search	2019	SIGMOD	5.6397012e-05
8,258	Optimal Algorithms for Multiway Search on Partial Orders	2022	PODS	5.3659871e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,731	Exploratory Keyword Search on Data Graphs	2010	SIGMOD
2	5,481	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD
3	3,769	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB
4	12,101	IDAR: Fast Supergraph Search Using DAG Integration	2020	VLDB
5	10,589	LLM-Powered Interactive Graph Search: A Scalable and Practical Approach	2026	SIGMOD
6	10,859	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,543	Interactive Graph Search Made Simple	2025	SIGMOD
9	6,928	Interactive Graph Search	2019	SIGMOD
10	6,633	Budget Constrained Interactive Search for Multiple Targets	2021	VLDB