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: h93c9b1d80a5f1c6c
Venue: PODS
Year: 2022
Pagerank: 5.3685285e-05
Overall Rank: 8,252 | 44.52%
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,191	Interactive Graph Search for Multiple Targets on DAGs	2025	VLDB	5.2110714e-05
9,535	Interactive Graph Search Made Simple	2025	SIGMOD	5.163649e-05
10,378	Near-Optimality for Single-Source Personalized PageRank	2026	PODS	4.9793485e-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
6,925	Interactive Graph Search	2019	SIGMOD	5.6423723e-05

Semantically Similar Papers

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