Compact dictionaries for variable-length keys and data with applications
Authors:
Open Access
- 29 May 2008
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 4 (2) , 1-25
Abstract
We consider the problem of maintaining a dynamic dictionary T of keys and associated data for which both the keys and data are bit strings that can vary in length from zero up to the length w of a machine word. We present a data structure for this variable-bit-length dictionary problem that supports constant time lookup and expected amortized constant-time insertion and deletion. It uses O ( m + 3 n − n log 2 n ) bits, where n is the number of elements in T , and m is the total number of bits across all strings in T (keys and data). Our dictionary uses an array A [1 … n ] in which locations store variable-bit-length strings. We present a data structure for this variable-bit-length array problem that supports worst-case constant-time lookups and updates and uses O ( m + n ) bits, where m is the total number of bits across all strings stored in A . The motivation for these structures is to support applications for which it is helpful to efficiently store short varying-length bit strings. We present several applications, including representations for semidynamic graphs, order queries on integers sets, cardinal trees with varying cardinality, and simplicial meshes of d dimensions. These results either generalize or simplify previous results.Keywords
Funding Information
- Advanced Cyberinfrastructure (ACI-0086093CCR-0085982CCR-0122581)
- National Science Foundation (ACI-0086093CCR-0085982CCR-0122581)
This publication has 24 references indexed in Scilit:
- Cuckoo hashingJournal of Algorithms, 2004
- Separators for sphere-packings and nearest neighbor graphsJournal of the ACM, 1997
- Short encodings of planar graphs and mapsDiscrete Applied Mathematics, 1995
- Bounded ordered dictionaries in O(log log N) time and O(n) spaceInformation Processing Letters, 1990
- On the succinct representation of graphsDiscrete Applied Mathematics, 1984
- Storing a Sparse Table with 0 (1) Worst Case Access TimeJournal of the ACM, 1984
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- List processing in real time on a serial computerCommunications of the ACM, 1978
- Design and implementation of an efficient priority queueTheory of Computing Systems, 1976
- Universal codeword sets and representations of the integersIEEE Transactions on Information Theory, 1975