Implicit Data Structures for the Dictionary Problem

DOI10.1145/322358.322364zbMath0497.68032OpenAlexW1983433417WikidataQ127332544 ScholiaQ127332544MaRDI QIDQ3962473

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)

Related Items (20)

An efficient implicit data structure for relation testing and searching in partially ordered sets ⋮ 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 ⋮ Searching among intervals and compact routing tables ⋮ Implicit \(B\)-trees: A new data structure for the dictionary problem ⋮ A compact data structure for representing a dynamic multiset ⋮ Improved bounds for finger search on a RAM ⋮ Dynamic interpolation search in o(log log n) time ⋮ A pointer-free data structure for merging heaps and min-max heaps ⋮ A bounded-space tree traversal algorithm ⋮ Representing graphs implicitly using almost optimal space ⋮ An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time ⋮ Dynamic interpolation search revisited ⋮ Unnamed Item ⋮ Computing (and Life) Is All about Tradeoffs ⋮ A Survey on Priority Queues ⋮ Succinct and Implicit Data Structures for Computational Geometry ⋮ Recursively rotated orders and implicit data structures: A lower bound ⋮ Partial match retrieval in implicit data structures

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