A distribution-sensitive dictionary with low space overhead

DOI10.1016/J.JDA.2011.11.003zbMATH Open1242.68080OpenAlexW2004160229MaRDI QIDQ414433FDOQ414433

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

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

zbMATH Keywords

dictionary problemdistribution sensitivityspace overheadworking set property

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

• Self-adjusting binary search trees
• An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
• Queaps
• A unified access bound on comparison-based dynamic dictionaries
• A data structure for a sequence of string accesses in external memory
• Layered working-set trees
• Title not available (Why is that?)
• Implicit dictionaries with O(1) modifications per update and fast search
• Title not available (Why is that?)
• Optimal worst-case operations for implicit cache-oblivious 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)