Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets

Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and... We consider the indexable dictionary problem, which consists of storing a set S ⊆ {0,…, m − 1} for some integer m while supporting the operations of rank( x ), which returns the number of elements in S that are less than x if x ∈ S , and −1 otherwise; and select( i ), which returns the i th smallest element in S . We give a data structure that supports both operations in O (1) time on the RAM model and requires B( n, m ) + o ( n ) + O (lg lg m ) bits to store a set of size n , where B( n, m ) = ⌊lg ( m / n )⌋ is the minimum number of bits required to store any n -element subset from a universe of size m . Previous dictionaries taking this space only supported (yes/no) membership queries in O (1) time. In the cell probe model we can remove the O (lg lg m ) additive term in the space bound, answering a question raised by Fich and Miltersen 1995 and Pagh 2001. We present extensions and applications of our indexable dictionary data structure, including: —an information-theoretically optimal representation of a k -ary cardinal tree that supports standard operations in constant time; —a representation of a multiset of size n from {0,…, m − 1} in B( n, m + n ) + o ( n ) bits that supports (appropriate generalizations of) rank and select operations in constant time; and + O (lg lg m ) —a representation of a sequence of n nonnegative integers summing up to m in B( n, m + n ) + o ( n ) bits that supports prefix sum queries in constant time. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets

Download PDF
25 pages

Loading next page...
 
/lp/association-for-computing-machinery/succinct-indexable-dictionaries-with-applications-to-encoding-k-ary-4ZIYzQ2aIi
Publisher
Association for Computing Machinery
Copyright
Copyright © 2007 by ACM Inc.
ISSN
1549-6325
DOI
10.1145/1290672.1290680
Publisher site
See Article on Publisher Site

Abstract

We consider the indexable dictionary problem, which consists of storing a set S ⊆ {0,…, m − 1} for some integer m while supporting the operations of rank( x ), which returns the number of elements in S that are less than x if x ∈ S , and −1 otherwise; and select( i ), which returns the i th smallest element in S . We give a data structure that supports both operations in O (1) time on the RAM model and requires B( n, m ) + o ( n ) + O (lg lg m ) bits to store a set of size n , where B( n, m ) = ⌊lg ( m / n )⌋ is the minimum number of bits required to store any n -element subset from a universe of size m . Previous dictionaries taking this space only supported (yes/no) membership queries in O (1) time. In the cell probe model we can remove the O (lg lg m ) additive term in the space bound, answering a question raised by Fich and Miltersen 1995 and Pagh 2001. We present extensions and applications of our indexable dictionary data structure, including: —an information-theoretically optimal representation of a k -ary cardinal tree that supports standard operations in constant time; —a representation of a multiset of size n from {0,…, m − 1} in B( n, m + n ) + o ( n ) bits that supports (appropriate generalizations of) rank and select operations in constant time; and + O (lg lg m ) —a representation of a sequence of n nonnegative integers summing up to m in B( n, m + n ) + o ( n ) bits that supports prefix sum queries in constant time.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Nov 1, 2007

There are no references for this article.