Emergency

Publications Related to Fractal Tree Indexing


Posted on:

|

By:


PREVIOUS POST
NEXT POST
Share Button

The TokuDB storage engine for MySQL employs Fractal Tree technology. We’ve been planning to write a white paper explaining how fractal tree indexing works, but haven’t gotten to it yet. In the mean time, here are links to some academic papers that relate to our technology.

  • Cache-Oblivious B-Trees by Michael A. Bender, Erik D. Demaine and Martin Farach-Colton in SICOMP 35:2, pp. 341-358, 2005. An early version of this paper appeared in FOCS in 2000.
  • The Cost of Cache-Oblivious Searching by Michael A. Bender, Gerth Stlting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono, and Alejandro López-Ortiz in FOCS 2003 p. 271.
  • A Locality-Preserving Cache-Oblivious Dictionary by Michael A. Bender, Ziyang Duan, John Iacono, and Jing Wu in Journal of Algorithms 53:2 pp. 115-136, November 2004.
  • An Adaptive Packed-Memory Array by Michael A. Bender and Haodong Hu, in TODS 32:4, November 2007.
  • Cache-Oblivious Streaming B-trees by Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Yonatan Fogel, Bradley Kuszmaul, and Jelani Nelson, in the Proceedings of the Nineteenth ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), June 9–11, 2007, San Diego, California, pp. 81-92
  • Concurrent Cache-Oblivious B-Trees by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Bradley C. Kuszmaul, in the Proceedings of the Seventeenth ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), July 17–20, 2005, Las Vegas, Nevada, pp. 228-237.
  • Cache-Oblivious String B-Trees by Michael A. Bender, Martin Farach-Colton, and Bradley C. Kuszmaul, in the Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, June, 2006, Chicago, IL, pp. 223–242
  • Cache-Oblivious Dynamic Search Trees by Zardosht Kasheff, Master’s Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, June, 2004.
  • Cache-Oblivious Algorithms by Harald Prokop, Master’s Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, June, 1999.

The research groups’ web pages can be found at

Incidentally, there’s another data structure in the literature called a `Fractal Tree’ (see e.g. http://www.pdl.cmu.edu/ftp/Database/fpbtree.ps), which is unrelated to our work.

Share Button
PREVIOUS POST
NEXT POST


Categories:
Tokutek, TokuView


Comments

Leave a Reply

Your email address will not be published. Required fields are marked *