Implicit Data Structures for the Dictionary Problem

DOI10.1145/322358.322364zbMath0497.68032MaRDI 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 performance; partial match retrieval; on-line complexity

Mathematics Subject Classification ID

68P10: Searching and sorting

Related Items

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