ALCOMFT-TR-02-40

Alon Itai and Irit Katriel
Implicit dictionaries for internal and external memory
MPI. Work packages 1 and 4. May 2002.

Abstract: A data structure is called implicit if it uses a constant amount of space to store information other than the data it holds. In particular, it does not use more than a constant number of pointers.

In this work we design the Sparse Table, an implicit data structure for the dictionary problem which performs searches in O(log n) time and updates in O(log² n) amortized time. To the best of our knowledge, this is the first implicit dictionary that achieves O(log n) search time and polylogarithmic update time.

Based on the sparse table, we construct the B-table, an implicit data structure that achieves the same I/O complexity for queries as the B^+tree. The B-table is inferior to the B^+tree in the complexity of updates. However, it can be viewed as superior in terms of space utilization, as it offers a tradeoff between time and space. It is also the first I/O efficient implicit dictionary.

Postscript file: ALCOMFT-TR-02-40.ps.gz (105 kb).