An Optimal Algorithm for Partial Order Multiway Search
Abstract
Partial order multiway search (POMS) is an important problem that finds use in crowdsourcing, distributed file systems, software testing, etc. In this problem, a game is played between an algorithm A and an oracle, based on a directed acyclic graph G known to both parties. First, the oracle picks a vertex t in G called the target; then, A aims to figure out which vertex is t by probing reachability. In each probe, A selects a set Q of vertices in G whose size is bounded by a pre-agreed value k, and the oracle then reveals, for each vertex q 2 Q, whether q can reach the target in G. The objective of A is to minimize the number of probes. This article presents an algorithm to solve POMS in O(log1+k n + d k log1+d n) probes, where n is the number of vertices in G, and d is the largest out-degree of the vertices in G. The probing complexity is asymptotically optimal.
References
[1]
M. Adler and B. Heeringa. Approximating optimal binary decision trees. Algorithmica, 62(3--4):1112--1121, 2012.
[2]
E. M. Arkin, H. Meijer, J. S. B. Mitchell, D. Rappaport, and S. Skiena. Decision trees for geometric models. International Journal of Computational Geometry and Applications, 8(3):343--364, 1998.
[3]
Y. Ben-Asher and E. Farchi. The cost of searching in general trees versus complete binary trees. Technical report, 1997.
[4]
Y. Ben-Asher, E. Farchi, and I. Newman. Optimal search in trees. SIAM J. of Comp., 28(6):2090--2102, 1999.
[5]
R. Carmo, J. Donadelli, Y. Kohayakawa, and E. S. Laber. Searching in random partially ordered sets. Theo. Comp. Sci., 321(1):41--57, 2004.
[6]
V. T. Chakaravarthy, V. Pandit, S. Roy, P. Awasthi, and M. K. Mohania. Decision trees for entity identification: Approximation algorithms and hardness results. ACM Transactions on Algorithms, 7(2):15:1--15:22, 2011.
[7]
V. T. Chakaravarthy, V. Pandit, S. Roy, and Y. Sabharwal. Approximating decision trees with multiway branches. In ICALP, pages 210--221, 2009.
[8]
F. Cicalese, T. Jacobs, E. S. Laber, and M. Molinaro. On greedy algorithms for decision trees. In ISAAC, pages 206--217, 2010.
[9]
F. Cicalese, T. Jacobs, E. S. Laber, and M. Molinaro. On the complexity of searching in trees and partially ordered structures. Theoretical Computer Science, 412(50):6879--6896, 2011.
[10]
F. Cicalese, T. Jacobs, E. S. Laber, and M. Molinaro. Improved approximation algorithms for the average-case tree searching problem. Algorithmica, 68(4):1045--1074, 2014.
[11]
F. Cicalese, T. Jacobs, E. S. Laber, and C. D. Valentim. The binary identification problem for weighted trees. Theoretical Computer Science, 459:100--112, 2012.
[12]
F. Cicalese, B. Keszegh, B. Lidick´y, D. P´alv¨olgyi, and
[13]
P. de la Torre, R. Greenlaw, and A. A. Sch¨affer. Optimal edge ranking of trees in polynomial time. Algorithmica, 13(6):592--618, 1995.
[14]
D. Dereniowski. Edge ranking of weighted trees. Discrete Applied Mathematics, 154(8):1198--1209, 2006.
[15]
D. Dereniowski. Edge ranking and searching in partial orders. Discrete Applied Mathematics, 156(13):2493--2500, 2008.
[16]
D. Dereniowski and M. Kubale. Efficient parallel query processing by graph ranking. Fundamenta Informaticae, 69(3):273--285, 2006.
[17]
D. Dereniowski, S. Tiegel, P. Uznanski, and D. Wolleb-Graf. A framework for searching in graphs in the presence of errors. In Proceedings of Symposium on Simplicity in Algorithms (SOSA), pages 4:1--4:17.
[18]
E. Emamjomeh-Zadeh, D. Kempe, and V. Singhal. Deterministic and probabilistic binary search in graphs. In STOC, pages 519--532, 2016.
[19]
A. V. Iyer, H. D. Ratliff, and G. Vijayan. On an edge ranking problem of trees and graphs. Discrete Applied Mathematics, 30(1):43--52, 1991.
[20]
T. Jacobs, F. Cicalese, E. S. Laber, and M. Molinaro. On the complexity of searching in trees: Average-case minimization. In ICALP, pages 527--539, 2010.
[21]
C. Jordan. Sur les assemblages de lignes. Journal f¨ur die reine und angewandte Mathematik, 70:185--190, 1869.
[22]
S. R. Kosaraju, T. M. Przytycka, and R. S. Borgstrom. On an optimal split tree problem. In WADS, pages 157--168, 1999.
[23]
E. S. Laber and M. Molinaro. An approximation algorithm for binary searching in trees. Algorithmica, 59(4):601--620, 2011.
[24]
E. S. Laber and L. T. Nogueira. Fast searching in trees. Electronic Notes in Discrete Mathematics, 7:90--93, 2001.
[25]
T. W. Lam and F. L. Yue. Optimal edge ranking of trees in linear time. Algorithmica, 30(1):12--33, 2001.
[26]
S. Lu, W. Martens, M. Niewerth, and Y. Tao. Optimal algorithms for multiway search on partial orders. In PODS, pages 175--187, 2022.
[27]
S. Mozes, K. Onak, and O. Weimann. Finding an optimal tree searching strategy in linear time. In SODA, pages 1096--1105, 2008.
[28]
K. Onak and P. Parys. Generalization of binary search: Searching in trees and forest-like partial orders. In FOCS, pages 379--388, 2006.
[29]
Y. Tao, Y. Li, and G. Li. Interactive graph search. In SIGMOD, pages 1393--1410, 2019.
Recommendations
Partial Order Multiway Search
Partial order multiway search (POMS) is a fundamental problem that finds applications in crowdsourcing, distributed file systems, software testing, and more. This problem involves an interaction between an algorithm 𝒜 and an oracle, conducted on a ...
Optimal Algorithms for Multiway Search on Partial Orders
PODS '22: Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database SystemsWe study partial order multiway search (POMS), which is a game between an algorithm A and an oracle, played on a directed acyclic graph G known to both parties. First, the oracle picks a vertex t in G called the target. Then, A needs to figure out which ...
Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. The clique-transversal number and clique-independence number of G are the sizes of a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2023
118 pages
ISSN:0163-5808
DOI:10.1145/3604437
- Editors:
- Rada Chirkova,
- Vanessa Braganholo,
- Wim Martens,
- Manos Athanassoulis,
- Marcelo Arenas,
- Marianne Winslett,
- Susan B. Davidson,
- Lyublena Antova,
- Aaron J. Elmore,
- Kyriakos Mouratidis,
- Dan Olteanu,
- Immanuel Trummer,
- Yannis Velegrakis,
- Renata Borovica-Gajic,
- Tamer Özsu,
- Pınar Tözün,
- Wook-Shin Han,
- Kenneth Ross,
- Alfons Kemper,
- Samuel Madden
Copyright © 2023 Copyright is held by the owner/author(s).
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 08 June 2023
Published in SIGMOD Volume 52, Issue 1
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 72Total Downloads
- Downloads (Last 12 months)44
- Downloads (Last 6 weeks)5
Reflects downloads up to 01 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in