Cache-Oblivious B-Trees

DOI10.1137/S0097539701389956zbMath1092.68028DBLPjournals/siamcomp/BenderDF05WikidataQ59831031 ScholiaQ59831031MaRDI QIDQ5470694

Erik D. Demaine, Martín Farach-Colton, Michael A. Bender

Publication date: 1 June 2006

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

data structuresmemory hierarchysearch treescache efficiency

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items (21)

Cache-Oblivious Iterated Predecessor Queries via Range Coalescing ⋮ Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing ⋮ Canonical density control ⋮ Tight Lower Bounds for the Online Labeling Problem ⋮ Implicit \(B\)-trees: A new data structure for the dictionary problem ⋮ I/O efficient dynamic data structures for longest prefix queries ⋮ External-memory sorting with comparison errors ⋮ The cost of cache-oblivious searching ⋮ Cache-oblivious hashing ⋮ I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions ⋮ Space efficient dynamic orthogonal range reporting ⋮ On Cartesian trees and range minimum queries ⋮ Cache-oblivious index for approximate string matching ⋮ Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions ⋮ A general approach for cache-oblivious range reporting and approximate range counting ⋮ Orthogonal range searching in linear and almost-linear space ⋮ A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES ⋮ Cache-oblivious R-trees ⋮ On Online Labeling with Large Label Set ⋮ The Online House Numbering Problem: Min-Max Online List Labeling ⋮ Non-Overlapping Indexing - Cache Obliviously

This page was built for publication: Cache-Oblivious B-Trees