Data Structures for Path Queries

作者：He Meng^*; Munro J Ian; Zhou Gelin

来源：ACM Transactions on Algorithms, 2016, 12(4): 53.

DOI：10.1145/2905368

• Path queries
• succinct data structures
• tree extraction
• path counting
• path reporting
• path median
• path selection

Consider a tree T on n nodes, each having a weight drawn from [1..sigma]. In this article, we study the problem of supporting various path queries over the tree T. The path counting query asks for the number of the nodes on a query path whose weights are in a query range, while the path reporting query requires to report these nodes. The path median query asks for the median weight on a path between two given nodes, and the path selection query returns the k-th smallest weight. We design succinct data structures to encode T using nH(W-T) + 2n + o(n lg sigma) bits of space, such that we can support path counting queries in O(lg sigma / lg lg n + 1) time, path reporting queries in O((occ + 1)(lg sigma / lg lg n + 1)) time, and path median and path selection queries in O(lg sigma / lg lg sigma) time, where H(W-T) is the entropy of the multiset of the weights of the nodes in T and occ is the size of the output. Our results not only greatly improve the best known data structures [Chazelle 1987; Krizanc et al. 2005], but also match the lower bounds for path counting, median, and selection queries [Patrascu 2007, 2011; Jorgensen and Larsen 2011] when sigma = Omega (n/polylog(n)).

• 出版日期2016-9