Storing a Sparse Table.
Abstract
In this paper, we examine two good worst-case methods of storing sparse tables. For the dynamic case, a trie data structure requires O(kn) storage while allowing O(log sub k (N/n)) access time, where k is a parameter whose value is chosen in advance. The method supports table deletions as well as insertions. A more sophisticated method is presented which handles the static case.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1978
- Accession Number
- ADA065284
Entities
People
- Robert Tarjan
Organizations
- Stanford University