Implicit \(B\)-trees: A new data structure for the dictionary problem

DOI10.1016/j.jcss.2003.11.003zbMath1074.68014MaRDI QIDQ598254

Roberto Grossi, Linda Pagli, Gianni Franceschini, J. Ian Munro

Publication date: 6 August 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2003.11.003

zbMATH Keywords

Searching; \(B\)-trees; External memory; Implicit data structures

Mathematics Subject Classification ID

68P05: Data structures

Related Items

Implicit \(B\)-trees: A new data structure for the dictionary problem, Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection, Computing (and Life) Is All about Tradeoffs, A Survey on Priority Queues

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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 tradeoff between search and update time for the implicit dictionary problem
• Implicit data structures for fast search and update
• An implicit data structure for searching a multikey table in logarithmic time
• A tradeoff between search and update in dictionaries
• Low Redundancy in Static Dictionaries with Constant Query Time
• Cache-Oblivious Algorithms
• Self-Organizing Heuristics for Implicit Data Structures
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Implicit Data Structures for the Dictionary Problem
• Membership in Constant Time and Almost-Minimum Space
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Cache-Oblivious B-Trees
• Algorithms and Data Structures