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.1913816e-05
Overall Rank: 9,223 | 38.18%
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,651	LLM-Powered Interactive Graph Search: A Scalable and Practical Approach	2026	SIGMOD	4.9605343e-05
10,920	Noisy Interactive Graph Search: An Uncertainty-Based Approach with Online Modeling of Latent Expertise and Difficulty	2026	VLDB	4.9605343e-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
754	So Who Won? Dynamic Max Discovery with the Crowd	2012	SIGMOD	0.00014226032
788	Human-Assisted Graph Search: It’s Okay to Ask Questions	2011	VLDB	0.00013946699
932	Question Selection for Crowd Entity Resolution	2013	VLDB	0.00012981731
991	CrowdScreen: Algorithms for Filtering Data with Humans	2012	SIGMOD	0.00012632003
1,036	YAGO3: A Knowledge Base from Multilingual Wikipedias	2015	CIDR	0.00012357949
1,267	CDAS: A Crowdsourcing Data Analytics System	2012	VLDB	0.00011253716
1,932	Counting with the Crowd	2013	VLDB	9.3441665e-05
3,210	iCrowd: An Adaptive Crowdsourcing Framework	2015	SIGMOD	7.5170875e-05
3,414	Waldo: An Adaptive Human Interface for Crowd Entity Resolution	2017	SIGMOD	7.3058225e-05
3,841	Optimal Crowd-Powered Rating and Filtering Algorithms	2014	VLDB	6.9697568e-05
4,503	Top-k Sorting Under Partial Order Information	2018	SIGMOD	6.5565742e-05
5,586	Efficient Algorithms for Crowd-Aided Categorization	2020	VLDB	6.0582193e-05
6,644	Budget Constrained Interactive Search for Multiple Targets	2021	VLDB	5.7057955e-05
6,948	Interactive Graph Search	2019	SIGMOD	5.6210529e-05
8,273	Optimal Algorithms for Multiway Search on Partial Orders	2022	PODS	5.3482438e-05

Semantically Similar Papers

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