Main Memory Indexing: The Case for BD-Tree

descriptionPublicationkeyboard_double_arrow_right Article 01 Jul 2004 English Publisher:Institute of Electrical and Electronics Engineers (IEEE)Journal:IEEE Transactions on Knowledge and Data Engineering, volume 16, pages 870-874 (issn: 1041-4347,

Copyright policy )

Authors: Cui, B.; Ooi, B.C.; Su, J.; Tan, K.-L.;

doi: 10.1109/tkde.2004.1318568

Main Memory Indexing: The Case for BD-Tree

- Summary
- Subjects
- Metrics

Abstract

We adapt and optimize the BD-tree for main memory data processing. We compare the memory-based BD-tree against the B/sup +/-tree and CSB/sup +/-tree. We present cost models for exact match query for these indexes, including L2 cache and translation lookahead buffer (TLB) miss model and execution time model. We also implemented these structures and conducted experimental study. Our analytical and experimental results show that a well-tuned BD-tree is superior in most cases.

Related Organizations

National University of Singapore
Singapore
University of California, Santa Barbara
United States
National University of Singapore Libraries
Singapore

Keywords

B +-tree, BD-tree, Main memory databases, CSB +-tree, 004, 620

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	9
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average