The time required for a sequence of operations on a data structure is usually measured in terms of the worst possible such sequence. This, however, is often an overestimate of the actual time required. Distribution-sensitive data structures attempt to take advantage of underlying patterns in a sequence of operations in order to reduce time complexity, since access patterns are non-random in many applications. Many of the distribution-sensitive structures in the literature require a great deal of space overhead in the form of pointers. We present a dictionary data structure that makes use of both randomization and existing space-efficient data structures to yield low space overhead while maintaining distribution sensitivity in the expected sense. We further show a modification that allows predecessor searches in a similar time bound.

Additional Metadata
Keywords Dictionary problem, Distribution sensitivity, Space overhead, Working set property
Persistent URL
Journal Journal of Discrete Algorithms
Bose, P, Howat, J. (John), & Morin, P. (2012). A distribution-sensitive dictionary with low space overhead. Journal of Discrete Algorithms, 10(1), 140–145. doi:10.1016/j.jda.2011.11.003