Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Reminder: Succinct Data Structures for Path Queries
1 view
Skip to first unread message
web...@cs.uwaterloo.ca
Oct 24, 2012, 10:03:01 AM10/24/12
to
This is a reminder for the event detailed below.
http://www.cs.uwaterloo.ca/odyssey/event/1608
Succinct Data Structures for Path Queries
Description:
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.
Date: Wednesday, October 24, 2012
Time: 13:30
Duration: 60 minutes
Updated: Tuesday, October 16, 2012 8:50
Room Location: DC 1304
Show On Front Page: Yes
Speaker/Affiliation: Gelin Zhou, PhD candidate, David R. Cheriton School of Comp. Sci., Univ. Waterloo
Send Reminder: Yes
http://www.cs.uwaterloo.ca/odyssey/event/1608
Succinct Data Structures for Path Queries
Description:
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.
Date: Wednesday, October 24, 2012
Time: 13:30
Duration: 60 minutes
Updated: Tuesday, October 16, 2012 8:50
Room Location: DC 1304
Show On Front Page: Yes
Speaker/Affiliation: Gelin Zhou, PhD candidate, David R. Cheriton School of Comp. Sci., Univ. Waterloo
Send Reminder: Yes
0 new messages