A distribution-sensitive dictionary with low space overhead

DOI10.1016/J.JDA.2011.11.003MaRDI QIDQ414433zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, John Howat, Pat Morin

Publication date 11 May 2012

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2011.11.003

zbMATH Keywords

dictionary problemdistribution sensitivityspace overheadworking set property

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• A Distribution-Sensitive Dictionary with Low Space Overhead
• A history of distribution-sensitive data structures
• Publication:4952655
• Deterministic dictionaries
• Constructing Efficient Dictionaries in Close to Sorting Time

Cites work

• scientific article; zbMATH DE number 5764838 (Why is no real title available?)
• scientific article; zbMATH DE number 2079398 (Why is no real title available?)
• A data structure for a sequence of string accesses in external memory
• A unified access bound on comparison-based dynamic dictionaries
• An implicit data structure supporting insertion, deletion, and search in O( ^ 2\,n) time
• Implicit dictionaries with O(1) modifications per update and fast search
• Layered working-set trees
• Optimal worst-case operations for implicit cache-oblivious search trees.
• Queaps
• Self-adjusting binary search trees

Cited in

(5)

• Family trees, an ordered dictionary with optimal congestion, locality, degree, and search time
• Low-contention data structures
• Dictionaries using variable-length keys and data, with applications
• A history of distribution-sensitive data structures
• A Distribution-Sensitive Dictionary with Low Space Overhead

This page was built for publication: A distribution-sensitive dictionary with low space overhead

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414433)