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

DOI10.1016/0304-3975(88)90018-7MaRDI QIDQ1108806zbMATH OpenOpenAlexFDO

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

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

implicit dictionarysearchupdate

Mathematics Subject Classification ID

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

Review text

An implicit dictionary can be viewed as a set of allowable permutations together with an associated search algorithm and an associated update algorithm (a comparison-based model, with elements drawn from a totally ordered universe, is used in this paper). The authors study lower bounds for the search time, given a constant-time update algorithm. It is proved that if update is easy (constant-time), then situations in which search is difficult (super-logarithmic time) occur. The first and the final paragraphs constitute a very good exposition of related results, ideas and open problems.

Recommendations

• scientific article; zbMATH DE number 140496
• Optimal worst-case operations for implicit cache-oblivious search trees.
• A tradeoff between search and update in dictionaries
• scientific article; zbMATH DE number 2038720
• scientific article; zbMATH DE number 3956454

Cites work

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

Cited in

(18)

• The number of tests required to search an unordered table
• An implicit data structure for searching a multikey table in logarithmic time
• A data structure for lattice representation
• A tradeoff between search and update in dictionaries
• An efficient implicit data structure for relation testing and searching in partially ordered sets
• Optimal implicit dictionaries over unbounded universes
• Computing (and Life) Is All about Tradeoffs
• A Survey of Data Structures in the Bitprobe Model
• A Cache-Oblivious Implicit Dictionary with the Working Set Property
• scientific article; zbMATH DE number 3956454 (Why is no real title available?)
• scientific article; zbMATH DE number 140496 (Why is no real title available?)
• Implicit O(1) Probe Search
• scientific article; zbMATH DE number 2038720 (Why is no real title available?)
• scientific article; zbMATH DE number 2079398 (Why is no real title available?)
• New Tight Bounds on Uniquely Represented Dictionaries
• Finger search in the implicit model
• scientific article; zbMATH DE number 6297800 (Why is no real title available?)
• Implicit \(B\)-trees: A new data structure for the dictionary problem

This page was built for publication: A tradeoff between search and update time for the implicit dictionary problem

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