A tradeoff between search and update time for the implicit dictionary problem

DOI10.1016/0304-3975(88)90018-7zbMath0654.68078OpenAlexW2069907263MaRDI QIDQ1108806

Allan Borodin, Eli Upfal, Avi Wigderson, Friedhelm Meyer auf der Heide, Faith E. Fich

Publication date: 1988

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(88)90018-7

zbMATH Keywords

searchupdateimplicit dictionary

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Information storage and retrieval of data (68P20)

Related Items

An efficient implicit data structure for relation testing and searching in partially ordered sets, Implicit \(B\)-trees: A new data structure for the dictionary problem, A data structure for lattice representation, An implicit data structure for searching a multikey table in logarithmic time, The number of tests required to search an unordered table, Computing (and Life) Is All about Tradeoffs, A Survey of Data Structures in the Bitprobe Model, A tradeoff between search and update in dictionaries

Cites Work

• Partial match retrieval in implicit data structures
• Implicit data structures for fast search and update
• Efficient searching using partial ordering
• Searching Semisorted Tables
• Should Tables Be Sorted?
• Implicit Data Structures for the Dictionary Problem