Optimal Algorithms for Multiway Search on Partial Orders

Summary: Defines POMS—querying sets of ≤k vertices for reachability to an unknown target in a DAG—and gives an optimal algorithm using O(log_{1+k} n + d k log_{1+d} n) probes with a matching lower bound. Introduces an EM variant: an O(n/B)-space structure achieving optimal O(log_B n + d B log_{1+d} n) I/Os and a black-box conversion to I/O-efficient pointer-machine structures. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1876
Venue: PODS
Year: 2022
Pagerank: 5.4881309e-05
Overall Rank: 8,094 | 44.47%
DOI: 10.1145/3517804.3524150

Incoming Non-self Citations Over Time

Authors

1. Shangqi Lu (Chinese University of Hong Kong)
2. Wim Martens (University of Bayreuth)
3. Matthias Niewerth (University of Bayreuth)
4. Yufei Tao (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{lu_pods22,
        address = {New York, NY, USA},
        series = {{PODS} '22},
        title = {{Optimal Algorithms for Multiway Search on Partial Orders}},
        url = {https://dl.acm.org/doi/10.1145/3517804.3524150},
        doi = {10.1145/3517804.3524150},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Lu, Shangqi and Martens, Wim and Niewerth, Matthias and Tao, Yufei},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,812	Interactive Graph Search for Multiple Targets on DAGs	2025	VLDB	5.214913e-05
10,161	Near-Optimality for Single-Source Personalized PageRank	2026	PODS	5.093636e-05
10,792	Interactive Graph Search Made Simple	2025	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
7,313	Interactive Graph Search	2019	SIGMOD	5.6480084e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,520	Approximately Counting Subgraphs in Data Streams	2022	PODS
2	4,474	Querying Big Graphs within Bounded Resources	2014	SIGMOD
3	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
4	3,261	Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity	2015	SIGMOD
5	1,511	Speedup Graph Processing by Graph Ordering	2016	SIGMOD
6	11,970	Write-Optimized Skip Lists	2017	PODS
7	3,553	On the Complexity of Approximate Query Optimization	2002	PODS
8	12,239	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD
9	12,028	Efficient Top-k Indexing via General Reductions	2016	PODS
10	6,753	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS