A Distribution-Sensitive Dictionary with Low Space Overhead

DOI10.1007/978-3-642-03367-4_10MaRDI QIDQ3183445zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, John Howat, Pat Morin

Publication date 20 October 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://ir.library.carleton.ca/pub/4518

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• A distribution-sensitive dictionary with low space overhead
• Practical implementation of space-efficient dynamic keyword dictionaries
• A trade-off for worst-case efficient dictionaries
• scientific article; zbMATH DE number 1617245
• A locality-preserving cache-oblivious dynamic dictionary
• scientific article; zbMATH DE number 2119641
• Compressed Dictionaries: Space Measures, Data Sets, and Experiments
• On some deterministic dictionaries supporting sparsity
• Fast overcomplete dictionary construction with probabilistic guarantees
• Low redundancy in static dictionaries with constant query 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 unified access bound on comparison-based dynamic dictionaries
• Alternatives to splay trees with O( n) worst-case access times
• 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
• Optimal worst-case operations for implicit cache-oblivious search trees.
• Queaps
• Self-adjusting binary search trees

Cited in

(3)

• A distribution-sensitive dictionary with low space overhead
• Dictionaries using variable-length keys and data, with applications
• A history of distribution-sensitive data structures

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 Q3183445)