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

searchupdateimplicit dictionary

Mathematics Subject Classification ID

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

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 the Dictionary Problem
• Implicit data structures for fast search and update
• Partial match retrieval in implicit data structures
• Searching Semisorted Tables
• Should Tables Be Sorted?

Cited in

(18)

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

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)