Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Seminar Database Systems FS2017

Cache-Concious and Cache-Oblivious Database Algorithms

Organization: Michael Böhlen and Przemyslaw Uznanski
Teaching language:English
Level:PhD, MSc and advanced BSc students
Academic Year:Spring 2017
Dates: Friday 24.2.2017 14.00-16.00h ETHZ CAB H 52
Saturday 8.4.2017 UZH BIN 2.A.01
Saturday 20.5.2017 ETHZ CAB H 52

Overview and objectives: The area of this year's seminar is Cache-Concious and Cache-Oblivious Database Algorithms. Students learn how to critically read and study research papers, how to summarize the contents of a paper, and how to present it in a seminar.

Teaching format: Each participant writes a self-contained report of about 10 pages and gives a 30 minutes presentation (blackboard, without a computer). Each participant has a buddy. Buddies read the report, make suggestions for improvements, and help with the presentation (e.g., dry runs). The first version of the report is due two weeks before the date of the presentation, and will be discussed with the buddy and the professor about one week before the presentation. The final versions of the report are due on the day of the seminar.

Setup and Organization: The setup of the seminar will be discussed Friday February 24, 2017 from 14:00 until 15:00 in room CAB H 52 at ETHZ. At the first meeting the available slots for the seminar will be distributed and papers will be assigned.

Presentations:

Participation at all three meetings is compulsory for students. The assessment depends on the quality of the report, presentation, active participation during the seminar, and input as a buddy.

Useful links:

Tentative list of seminar papers:

topic presenter buddy professor
April 8
(1) Cache-Oblivious Algorithms Leonard Adolphs Marco Suter Przemysław Uznański
(2) DBMSs on a Modern Processor: Where Does Time Go? Marroquín Mogrovejo Renato Javier Moritz Hoffmann Michael Böhlen
(6) Funnel heap - a cache oblivious priority queue
Cache-oblivious priority queue and graph algorithm applications		 Roy Rutishauser Olga Klimashevska Przemysław Uznański
(10) Mesh layouts for block-based caches Benedikt Steger Dzmitry Katsiuba Michael Böhlen
(11) Cache-Oblivious Streaming B-trees Mrigya Agarwal Naous Houssam Przemysław Uznański
(16) In-Cache Query Co-Processing on Coupled CPU-GPU Architectures Frederik Brix Jonathan Burger Michael Böhlen
May 13
(3) Cache-conscious structure layout Dzmitry Katsiuba Mrigya Agarwal Przemysław Uznański
(4) Cache-oblivious B-trees Marco Suter Benedikt Steger Przemysław Uznański
(5) Making B+-trees cache conscious in main memory Olga Klimashevska Leonard Adolphs Przemysław Uznański
(7) Generic database cost models for hierarchical memory systems Jonathan Burger Florian Chlan Michael Böhlen
(15) Don't Thrash: How to Cache Your Hash on Flash Moritz Hoffmann Frederik Brix Przemysław Uznański
(17) An interval join optimized for modern hardware Naous Houssam Marroquín Mogrovejo Renato Javier Michael Böhlen
(18) GPL: A GPU-based Pipelined Query Processing Engine Florian Chlan Roy Rutishauser Michael Böhlen


List of possible seminar topics:

  1. Frigo, Leiserson, Prokop, Ramachandran. Cache-Oblivious Algorithms. FOCS 1999
  2. Ailamaki, DeWitt, Hill, Wood. 1999. DBMSs on a Modern Processor: Where Does Time Go?. VLDB '99
  3. Chilimbi, Hill, Larus. 1999. Cache-conscious structure layout. PLDI '99, 1-12.
  4. Bender, Demaine, Farach-Colton. Cache-oblivious B-trees. 399-409, FOCS 2000.
  5. Rao, Ross. Making B+-trees cache conscious in main memory. SIGMOD ’00, 475–486.
  6. Brodal, Fagerberg. Funnel heap - a cache oblivious priority queue. 219-228, ISAAC 2002.
    Arge, Bender, Demaine, Holland-Minkley, Munro. Cache-oblivious priority queue and graph algorithm applications. 268-276, STOC 2002.
  7. Manegold, Boncz, Kersten. Generic database cost models for hierarchical memory systems. VLDB ’02.
  8. Brodal, Fagerberg. On the limits of cache-obliviousness. STOC 03, 307-315, 2003.
  9. Harizopoulos, S. and Ailamaki, A. 2006. Improving instruction cache performance in OLTP. TODS. 31, 3, 887–920.
  10. Yoon, Lindstrom. 2006. Mesh layouts for block-based caches. IEEE Transactions on Visualization and Computer Graphics 12, 5, 1213–1220.
  11. Bender, Farach-Colton, Fineman, Fogel, Kuszmaul, Nelson. Cache-Oblivious Streaming B-trees SPAA: 81-92. 2007
  12. Chowdhury, Ramachandran. 2006. Cache-oblivious dynamic programming. SODA '06.
  13. Silvestri: On the limits of cache-oblivious rational permutations. Theor. Comput. Sci. 402(2-3): 221-233 (2008)
  14. He, Luo. Cache-oblivious databases: Limitations and opportunities. ACM Trans. Database Syst. 33(2) (2008)
  15. Bender et al. Don't Thrash: How to Cache Your Hash on Flash, VLDB 2012
  16. Jiong He, Shuhao Zhang, Bingsheng He: In-Cache Query Co-Processing on Coupled CPU-GPU Architectures. PVLDB 8(4): 329-340 (2014)
  17. Danila Piatov, Sven Helmer, Anton Dignös: An interval join optimized for modern hardware. ICDE 2016: 1098-1109
  18. Johns Paul, Jiong He, Bingsheng He: GPL: A GPU-based Pipelined Query Processing Engine. SIGMOD Conference 2016: 1935-1950