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: 13969
Venue: VLDB
Year: 2025
Pagerank: 5.214913e-05
Overall Rank: 9,812 | 32.69%
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 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,382	LLM-Powered Interactive Graph Search: A Scalable and Practical Approach	2026	SIGMOD	5.093636e-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
743	So Who Won? Dynamic Max Discovery with the Crowd	2012	SIGMOD	0.00014421358
767	Human-Assisted Graph Search: It’s Okay to Ask Questions	2011	VLDB	0.00014208622
933	Question Selection for Crowd Entity Resolution	2013	VLDB	0.00013111293
997	CrowdScreen: Algorithms for Filtering Data with Humans	2012	SIGMOD	0.00012755983
1,057	YAGO3: A Knowledge Base from Multilingual Wikipedias	2015	CIDR	0.00012387149
1,270	CDAS: A Crowdsourcing Data Analytics System	2012	VLDB	0.00011388453
1,910	Counting with the Crowd	2013	VLDB	9.4972788e-05
3,262	iCrowd: An Adaptive Crowdsourcing Framework	2015	SIGMOD	7.5846052e-05
3,496	Waldo: An Adaptive Human Interface for Crowd Entity Resolution	2017	SIGMOD	7.3634471e-05
3,914	Optimal Crowd-Powered Rating and Filtering Algorithms	2014	VLDB	7.0204052e-05
4,610	Top-k Sorting Under Partial Order Information	2018	SIGMOD	6.6079578e-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,313	Interactive Graph Search	2019	SIGMOD	5.6480084e-05
8,094	Optimal Algorithms for Multiway Search on Partial Orders	2022	PODS	5.4881309e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,853	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB
2	12,434	Exploratory Keyword Search on Data Graphs	2010	SIGMOD
3	5,370	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD
4	3,709	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB
5	11,793	IDAR: Fast Supergraph Search Using DAG Integration	2020	VLDB
6	10,382	LLM-Powered Interactive Graph Search: A Scalable and Practical Approach	2026	SIGMOD
7	767	Human-Assisted Graph Search: It’s Okay to Ask Questions	2011	VLDB
8	10,792	Interactive Graph Search Made Simple	2025	SIGMOD
9	7,313	Interactive Graph Search	2019	SIGMOD
10	7,021	Budget Constrained Interactive Search for Multiple Targets	2021	VLDB