Algorithms and Complexity Group PhD Seminar

2012 Oct 24 at 13:30

DC 1304

Succinct Data Structures for Path Queries

Gelin Zhou, PhD candidate, David R. Cheriton School of Comp. Sci., Univ. Waterloo

Consider a tree T on n nodes, each having a weight drawn from [1..\sigma]. In this paper, we design succinct data structures to encode T using nH(W_T) + o(n\lg\sigma) bits of space, such that we can support path counting queries in O(lg\sigma / lglgn + 1) time, path reporting queries in O((occ+1)(lg\sigma / lglgn + 1)) time, and path median and path selection queries in O(lg\sigma / lglg\sigma) time, where H(W_T) is the entropy of the multiset of the weights of the nodes in T. Our results not only improve the best known linear space data structures[15], but also match the lower bounds for these path queries[18, 19, 16] when \sigma = \Omega(n / polylog(n)).

This is joint work with Meng He and J. Ian Munro, and appears in ESA 2012.