Partial Order Multiway Search
Shangqi Lu, Wim Martens, Matthias Niewerth, Yufei Tao Β· ACM Transactions on Database Systems Β· 2023
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 directed acyclic graph π’ known to both parties. Initially, the oracle selects a vertextin π’ called thetarget. Subsequently, π must identify the target vertex by probing reachability. In eachprobe, π selects a setQof vertices in π’, the number of which is limited by a pre-agreed valuek. The oracle then reveals, for each vertexqβQ, whetherqcan reach the target in π’. The objective of π is to minimize the number of probes. We propose an algorithm to solve POMS in \(O(\log _{1+k} n + \frac{d}{k} \log _{1+d} n)\) probes, wherenrepresents the number of vertices in π’, andddenotes the largest out-degree of the vertices in π’. The probing complexity is asymptotically optimal. Our study also explores two new POMS variants: The first one, namedtaciturn POMS, is similar to classical POMS but assumes a weaker oracle, and the second one, namedEM POMS, is a direct extension of classical POMS to theexternal memory(EM) model. For both variants, we introduce algorithms whose performance matches or nearly matches the corresponding theoretical lower bounds.