Publications Related to Fractal Tree Indexing

Publications Related to Fractal Tree Indexing

PREVIOUS POST
NEXT POST

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.

PREVIOUS POST
NEXT POST

Share this post

Comments (5)

  • Robert Collins Reply

    The link for Cache-Oblivious Dynamic Search Trees points to prokop99.pdf; any chance you could update it to the real paper?

    June 10, 2009 at 2:15 am
  • Robert Collins Reply

    The cache-oblivious string b-trees link is also broken.

    June 10, 2009 at 3:35 am
  • Nathan Fiedler Reply

    Several of the links are broken or misdirected, any chance anyone is paying attention here and can fix these?

    June 12, 2009 at 2:52 pm
  • Tom Hotchkiss Reply

    Sorry for the broken links – we’ll be fixing them shortly and post another comment when it’s done.

    June 12, 2009 at 4:10 pm
  • Martin Farach-Colton Reply

    The links should all work now.

    June 15, 2009 at 7:08 pm

Leave a Reply