Implicit Data Structures for the Weighted Dictionary Problem (preliminary version)

Several new data structures are presented for dictionaries containing elements with different weights (access probabilities). The structures use just one location in addition to those required for the values of the elements, and support access times that are within a constant multiplicative factor of optimal, in terms of the rank of the weight of the desired element. Self-organizing heuristics are analyzed, in terms of both weights and "near-ranks" of weights. The benefits of additional space are investigated within the context of self-organization and unsuccessful search.

Authors

• Greg N. Frederickson

Keywords

• Data structures
• Dictionaries
• Binary search trees
• Computer science
• Data Structure
• Heuristic
• State Structures
• Transition Probabilities
• Constant Factor
• Access Time
• Sequence Search
• Group Elements
• Search Optimization
• Tree Search
• Binary Tree
• Partial Order
• Lexicographic
• Additional Space
• Binary Search
• Tree Representation
• Self-organized Structures
• Left Child
• Successful Search
• Access Probability
• Weight Of Elements
• Group Size