Implicit Data Structures for the Dictionary Problem

DOI10.1145/322358.322364MaRDI QIDQ3962473zbMATH OpenOpenAlexWikidataFDO

Authors Greg N. Frederickson

Publication date 1983

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/322358.322364

zbMATH Keywords

average performancepartial match retrievalon-line complexity

Mathematics Subject Classification ID

Searching and sorting (68P10)

Cited in

(20)

• An implicit data structure supporting insertion, deletion, and search in O( ^ 2\,n) time
• A bounded-space tree traversal algorithm
• A compact data structure for representing a dynamic multiset
• Recursively rotated orders and implicit data structures: A lower bound
• Implicit \(B\)-trees: A new data structure for the dictionary problem
• A pointer-free data structure for merging heaps and min-max heaps
• Searching among intervals and compact routing tables
• Designing networks with compact routing tables
• A tradeoff between search and update time for the implicit dictionary problem
• Representing graphs implicitly using almost optimal space
• Fast dynamic arrays
• Succinct and Implicit Data Structures for Computational Geometry
• Dynamic interpolation search revisited
• Searching among intervals and compact routing tables
• Improved bounds for finger search on a RAM
• Dynamic interpolation search in \(o(\log\log n)\) time
• Computing (and Life) Is All about Tradeoffs
• Partial match retrieval in implicit data structures
• A survey on priority queues
• An efficient implicit data structure for relation testing and searching in partially ordered sets

This page was built for publication: Implicit Data Structures for the Dictionary Problem

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