{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:35:47Z","timestamp":1768109747530,"version":"3.49.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:00:00Z","timestamp":1699833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"GRF","award":["14222822, 14203421, 14207820"],"award-info":[{"award-number":["14222822, 14203421, 14207820"]}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["369116833, 431183758"],"award-info":[{"award-number":["369116833, 431183758"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p><jats:italic>Partial order multiway search<\/jats:italic>(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 \ud835\udc9c and an oracle, conducted on a directed acyclic graph \ud835\udca2 known to both parties. Initially, the oracle selects a vertex<jats:italic>t<\/jats:italic>in \ud835\udca2 called the<jats:italic>target<\/jats:italic>. Subsequently, \ud835\udc9c must identify the target vertex by probing reachability. In each<jats:italic>probe<\/jats:italic>, \ud835\udc9c selects a set<jats:italic>Q<\/jats:italic>of vertices in \ud835\udca2, the number of which is limited by a pre-agreed value<jats:italic>k<\/jats:italic>. The oracle then reveals, for each vertex<jats:italic>q<\/jats:italic>\u2208<jats:italic>Q<\/jats:italic>, whether<jats:italic>q<\/jats:italic>can reach the target in \ud835\udca2. The objective of \ud835\udc9c is to minimize the number of probes. We propose an algorithm to solve POMS in<jats:inline-formula content-type=\"math\/tex\"><jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(\\log _{1+k} n + \\frac{d}{k} \\log _{1+d} n)\\)<\/jats:tex-math><\/jats:inline-formula>probes, where<jats:italic>n<\/jats:italic>represents the number of vertices in \ud835\udca2, and<jats:italic>d<\/jats:italic>denotes the largest out-degree of the vertices in \ud835\udca2. The probing complexity is asymptotically optimal. Our study also explores two new POMS variants: The first one, named<jats:italic>taciturn POMS<\/jats:italic>, is similar to classical POMS but assumes a weaker oracle, and the second one, named<jats:italic>EM POMS<\/jats:italic>, is a direct extension of classical POMS to the<jats:italic>external memory<\/jats:italic>(EM) model. For both variants, we introduce algorithms whose performance matches or nearly matches the corresponding theoretical lower bounds.<\/jats:p>","DOI":"10.1145\/3626956","type":"journal-article","created":{"date-parts":[[2023,10,9]],"date-time":"2023-10-09T12:18:08Z","timestamp":1696853888000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Partial Order Multiway Search"],"prefix":"10.1145","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7517-7252","authenticated-orcid":false,"given":"Lu","family":"Shangqi","sequence":"first","affiliation":[{"name":"Chinese University of Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9480-3522","authenticated-orcid":false,"given":"Wim","family":"Martens","sequence":"additional","affiliation":[{"name":"University of Bayreuth, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2032-5374","authenticated-orcid":false,"given":"Matthias","family":"Niewerth","sequence":"additional","affiliation":[{"name":"University of Bayreuth, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3883-5452","authenticated-orcid":false,"given":"Yufei","family":"Tao","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,11,13]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"crossref","unstructured":"Shangqi Lu Wim Martens Matthias Niewerth and Yufei Tao. 2022. Optimal algorithms for multiway search on partial orders. PODS 2022 175\u2013187.","DOI":"10.1145\/3517804.3524150"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9510-9"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_3_3_5_2","article-title":"I\/O-efficient point location using persistent B-trees","volume":"8","author":"Arge Lars","year":"2003","unstructured":"Lars Arge, Andrew Danner, and Sha-Mayn Teh. 2003. I\/O-efficient point location using persistent B-trees. ACM J. Experim. Algor. 8 (2003).","journal-title":"ACM J. Experim. Algor."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195998000175"},{"key":"e_1_3_3_7_2","volume-title":"The Cost of Searching in General Trees versus Complete Binary Trees","author":"Ben-Asher Yosi","year":"1997","unstructured":"Yosi Ben-Asher and Eitan Farchi. 1997. The Cost of Searching in General Trees versus Complete Binary Trees. Technical Report. https:\/\/researcher.watson.ibm.com\/researcher\/view_person_pubs.php?person=il-FARCHI&t=1"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979731858X"},{"key":"e_1_3_3_9_2","first-page":"39","volume-title":"Proceedings of the Conference on Extending Database Technology (EDBT\u201998)","author":"Bertino Elisa","year":"1998","unstructured":"Elisa Bertino, Barbara Catania, and Boris Shidlovsky. 1998. Towards optimal indexing for segment databases. In Proceedings of the Conference on Extending Database Technology (EDBT\u201998). 39\u201353."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60220-8_78"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.06.001"},{"issue":"2","key":"e_1_3_3_12_2","article-title":"Decision trees for entity identification: Approximation algorithms and hardness results","volume":"7","author":"Chakaravarthy Venkatesan T.","year":"2011","unstructured":"Venkatesan T. Chakaravarthy, Vinayaka Pandit, Sambuddha Roy, Pranjal Awasthi, and Mukesh K. Mohania. 2011. Decision trees for entity identification: Approximation algorithms and hardness results. ACM Trans. Algor. 7, 2 (2011), 15:1\u201315:22.","journal-title":"ACM Trans. Algor."},{"key":"e_1_3_3_13_2","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1007\/978-3-642-02927-1_19","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201909)","author":"Chakaravarthy Venkatesan T.","year":"2009","unstructured":"Venkatesan T. Chakaravarthy, Vinayaka Pandit, Sambuddha Roy, and Yogish Sabharwal. 2009. Approximating decision trees with multiway branches. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201909). 210\u2013221."},{"key":"e_1_3_3_14_2","first-page":"206","volume-title":"Proceedings of the International Symposium on Algorithms and Computation (ISAAC\u201910)","author":"Cicalese Ferdinando","year":"2010","unstructured":"Ferdinando Cicalese, Tobias Jacobs, Eduardo Sany Laber, and Marco Molinaro. 2010. On greedy algorithms for decision trees. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC\u201910). 206\u2013217."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.08.042"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9715-6"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.06.023"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.07.019"},{"key":"e_1_3_3_19_2","volume-title":"Introduction to Algorithms, Second Edition","author":"Cormen Thomas H.","year":"2001","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001. Introduction to Algorithms, Second Edition. The MIT Press."},{"issue":"6","key":"e_1_3_3_20_2","doi-asserted-by":"crossref","first-page":"592","DOI":"10.1007\/BF01189071","article-title":"Optimal edge ranking of trees in polynomial time","volume":"13","author":"Torre Pilar de la","year":"1995","unstructured":"Pilar de la Torre, Raymond Greenlaw, and Alejandro A. Sch\u00e4ffer. 1995. Optimal edge ranking of trees in polynomial time. Algorithmica 13, 6 (1995), 592\u2013618.","journal-title":"Algorithmica"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/1144344.1705240"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.03.007"},{"issue":"3","key":"e_1_3_3_23_2","first-page":"273","article-title":"Efficient parallel query processing by graph ranking","volume":"69","author":"Dereniowski Dariusz","year":"2006","unstructured":"Dariusz Dereniowski and Marek Kubale. 2006. Efficient parallel query processing by graph ranking. Fundam. Inform. 69, 3 (2006), 273\u2013285.","journal-title":"Fundam. Inform."},{"key":"e_1_3_3_24_2","unstructured":"Dariusz Dereniowski Stefan Tiegel Przemyslaw Uznanski and Daniel Wolleb-Graf. 2019. A framework for searching in graphs in the presence of errors. In Proceedings of the Symposium on Simplicity in Algorithms (SOSA) 4:1\u20134:17."},{"key":"e_1_3_3_25_2","first-page":"519","volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC\u201916)","author":"Emamjomeh-Zadeh Ehsan","year":"2016","unstructured":"Ehsan Emamjomeh-Zadeh, David Kempe, and Vikrant Singhal. 2016. Deterministic and probabilistic binary search in graphs. In Proceedings of the ACM Symposium on Theory of Computing (STOC\u201916). 519\u2013532."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792226825"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0518-2"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90012-L"},{"key":"e_1_3_3_29_2","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1007\/978-3-642-14165-2_45","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201910)","author":"Jacobs Tobias","year":"2010","unstructured":"Tobias Jacobs, Ferdinando Cicalese, Eduardo Sany Laber, and Marco Molinaro. 2010. On the complexity of searching in trees: Average-case minimization. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201910). 527\u2013539."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1515\/crll.1869.70.185"},{"key":"e_1_3_3_31_2","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/3-540-48447-7_17","volume-title":"Proceedings of the Algorithms and Data Structures Workshop (WADS\u201999)","author":"Kosaraju S. Rao","year":"1999","unstructured":"S. Rao Kosaraju, Teresa M. Przytycka, and Ryan S. Borgstrom. 1999. On an optimal split tree problem. In Proceedings of the Algorithms and Data Structures Workshop (WADS\u201999). 157\u2013168."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.5555\/3118745.3118911"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0653(04)00232-X"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010076"},{"key":"e_1_3_3_35_2","first-page":"1096","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Mozes Shay","year":"2008","unstructured":"Shay Mozes, Krzysztof Onak, and Oren Weimann. 2008. Finding an optimal tree searching strategy in linear time. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). 1096\u20131105."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80064-8"},{"key":"e_1_3_3_37_2","unstructured":"J. Ian Munro and Yakov Nekrich. 2019. Dynamic planar point location in external memory. In Proceedings of the Symposium on Computational Geometry (SoCG) Vol. 129 52:1\u201352:15."},{"key":"e_1_3_3_38_2","first-page":"379","volume-title":"Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906)","author":"Onak Krzysztof","year":"2006","unstructured":"Krzysztof Onak and Pawel Parys. 2006. Generalization of binary search: Searching in trees and forest-like partial orders. In Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906). 379\u2013388."},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2010.03.003"},{"key":"e_1_3_3_40_2","first-page":"1393","volume-title":"Proceedings of the ACM Management of Data Conference (SIGMOD\u201919)","author":"Tao Yufei","year":"2019","unstructured":"Yufei Tao, Yuanbing Li, and Guoliang Li. 2019. Interactive graph search. In Proceedings of the ACM Management of Data Conference (SIGMOD\u201919). 1393\u20131410."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626956","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626956","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:44:16Z","timestamp":1750290256000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626956"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,13]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1145\/3626956"],"URL":"https:\/\/doi.org\/10.1145\/3626956","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,13]]},"assertion":[{"value":"2022-12-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-14","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}