The cost of cache-oblivious searching

DOI10.1007/s00453-010-9394-0zbMath1223.68032MaRDI QIDQ639274

Simai He, Haodong Hu, John Iacono, Gerth Stølting Brodal, Alejandro López-Ortiz, Rolf Fagerberg, Michael A. Bender, Dong-Dong Ge

Publication date: 20 September 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9394-0

zbMATH Keywords

cache-oblivious B-tree; cache-oblivious searching; van Emde Boas layout

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68P10: Searching and sorting

Related Items

Cache-oblivious hashing, The cost of cache-oblivious searching

Cites Work

• The cost of cache-oblivious searching
• Preserving order in a forest in less than logarithmic time and linear space
• The uniform memory hierarchy model of computation
• Algorithms for parallel memory, I: Two-level memories
• Algorithms for parallel memory. II: Hierarchical multilevel memories
• Optimal implicit dictionaries over unbounded universes
• Organization and maintenance of large ordered indexes
• A locality-preserving cache-oblivious dynamic dictionary
• Cache-Oblivious Algorithms
• Towards a theory of cache-efficient algorithms
• The Influence of Caches on the Performance of Sorting
• Cache-oblivious data structures for orthogonal range searching
• Cache-Oblivious B-Trees
• Algorithms and Data Structures
• New algorithms for disk scheduling
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item