Papers related to cache oblivious data structures

cache-oblivious.md

Cache Oblivious and Cache Aware Data Structure and Algorithms

1. Cache-Oblivious Algorithms and Data Structures - Erik Demaine (One of the earliest papers in cache oblivious data structures and algorithms that introduces the cache oblivious model in detail and examines static and dynamic cache oblivious data structures built between 2000-2003)

2. Cache Oblivious B-Trees - Bender, Demaine, Farch-Colton (This paper presents two dynamic search trees attaining near-optimal performance on any hierarchical memory. One of the fundamental papers in the field where both search trees discussed match the optimal search bound of Θ(1+log (B+1)N) memory transfers)

3. Cache Oblivious Search Trees via Binary Trees of Small Height - Brodal, Fagerberg, Jacob (The data structure discussed in this paper works on the version of [2] but avoids the use of weight balanced B-trees, and can be implemented as just a single array of data elements, without the use of pointers. The structure also improves space utilization)

4. Cache Oblivious Algorithms - Frigo, Leiserson, Prokop, Ramachandran (Possibly the fundamental paper that proposed the cache oblivious model and using vEB as the base search tree in this model)

5. An Introduction to Bε-trees and Write-Optimization - Michael A. Bender, Martin Farach-Colton, William Jannen, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter, Jun Yuan, and Yang Zhan (Introduces B ε -tree, an example of a write-optimized data structure that can be used to organize on-disk storage for an application such as a database or file system. This article describes the B ε -tree, compares its asymptotic performance to B-trees and Log-Structured Merge trees (LSM-trees), and presents real-world performance measurements)

6. BetrFS: A Right-Optimized Write-Optimized File System - William Jannen, Jun Yuan et. al. (Introduces the Bε-tree File System, or BetrFS, (pronounced “better eff ess”) is the first in-kernel file system to use a write-optimized index. Write optimized indexes (WOIs) are promising building blocks for storage systems because of their potential to implement both microwrites and large scans efficiently)

7. BetrFS: A Right-Optimized Write-Optimized File System - a talk by Rob Johnson on BetrFS

8. Cache-Oblivious Streaming B-trees - Bender, Farach-Colton et al (A streaming B-tree is a dictionary that efficiently implements insertions and range queries. This paper presents two cache-oblivious streaming B-trees, the shuttle tree, and the cache-oblivious lookahead array (COLA))

9. B-epsilon-tree and cache-oblivious lookahead array: a comparative study of two write-optimised data structures - Yevhen Khavrona

10. Write-Optimized Data Structures - Michael Bender

11. Evaluation of a Cache-Oblivious Data Structure - Maks Verver

12. The Cost of Cache-Oblivious Searching - Bender, Brodal, Fagerberg et al

13. Cache-Oblivious Data Structures for Orthogonal Range Searching - Pankaj Agarwal, Lars Arge et al

14. Cache-oblivious planar orthogonal range searching and counting. - Lars Arge, Gerth Stlting Brodal, Rolf Fagerberg, and Morten Laustsen (We present the first cache-oblivious data structure for planar orthogonal range counting, and improve on previous results for cache-oblivious planar orthogonal range searching.Our range counting structure uses O(N log2 N) space and answers queries using O(logB N) memory transfers, where B is the block size of any memory level in a multilevel memory hierarchy)

15. A locality-preserving cache-oblivious dynamic dictionary - Bneder, Duan, Iacono, Wu

16. Concurrent Cache-Oblivious B-Trees - Bender, Fineman et al (This paper extends the cache-oblivious model to a parallel or distributed set- ting and present three concurrent CO B-trees)

17. The Algorithmics of write optimization - Bender

18. External-Memory Search Trees with Fast Insertions - Jelani Nelson (MS Thesis)

19. Engineering a cache-oblivious sorting algorithm - Brodal, Fagerberg et al (This paper is an algorithmic engineering study of cache-oblivious sorting. We investigate by empirical methods a number of implementation issues and parameter choices for the cache-oblivious sorting algorithm Lazy Funnelsort and compare the final algorithm with Quicksort, the established standard for comparison-based sorting, as well as with recent cache-aware proposals)

20. Cache Oblivious Sorting - Brodal

21. Sample funnel sort implementation

22. Cache Oblivious Distribution Sweeping - Brodal, Fagerberg (This paper adapts the distribution sweeping method to the cache oblivious model. Distribution sweeping is the name used for a general approach for divide-and-conquer algorithms where the combination of solved subproblems can be viewed as a merging process of streams)

23. Simple and semi-dynamic structures for cache-oblivious planar orthogonal range searching - Lars Arge, Norbert Zeh (This paper develops improved cache-oblivious data structures for two- and three-sided planar orthogonal range searching)

24. Cache-Oblivious Representation of B-Tree Structures - Lukáš Ondráček, Ondřej Mička

25. Integrating Cache Oblivious Approach with Modern Processor Architecture: The Case of Floyd-Warshall Algorithm - Toshio Endo

26. BP-tree: Overcoming the Point-Range Operation Tradeo! for In-Memory B-trees by Helen Xu et al - a variant of the B-tree, that overcomes the decades-old point-range operation tradeo" in traditional B-trees.

Comparison between Cache-aware and Cache-oblivious algorithms

• Reddit Thread
• An Experimental Comparison of Cache-oblivious and Cache-conscious Programs - Yotov et al
• Is Cache-oblivious DGEMM viable - an IBM Research Report
• Blog Post - Cache Money Hoes

s/Strucutre/Structure/ in the first heading

s/Strucutre/Structure/ in the first heading

fixed .. thanks.