ABSTRACT

Carnegie Mellon University Parallel Data Lab Technical Report CMU-PDL-05-102, March 2005. Superceded by IEEE 23rd International Conference on Data Engineering (ICDE 2007) Istanbul, Turkey, April 2007.

MultiMap: Preserving disk locality for multidimensional datasets

Minglong Shao*, Steven W. Schlosser, Stratos Papadomanolakis*, Jiri Schindler, Anastassia Ailamaki*, Christos Faloutsos*, Gregory R. Ganger

School of Computer Science*
Electrical and Computer Engineering
Carnegie Mellon University
Pittsburgh, PA 15213

http://www.pdl.cmu.edu/

MultiMap is a new approach to mapping multidimensional datasets to the linear address space of storage systems. MultiMap exploits modern disk characteristics to provide full streaming bandwidth for one (primary) dimension and maximally efficient non-sequential access (i.e., minimal seek and no rotational latency) for the other dimensions. This is in contrast to existing approaches, which either severely penalize non-primary dimensions or fail to provide
full streaming bandwidth for any dimension. Experimental evaluation of a prototype implementation demonstrates MultiMap’s superior performance for range and beam queries. On average, MultiMap reduces overall I/O time by over 50% when compared to traditional naive layouts and by over 30% when compared to a Hilbert curve approach. For scans of the primary dimension, MultiMap and naive both provide almost two orders of magnitude higher throughput
than the Hilbert curve approach.

KEYWORDS: multidimensional dataset, disk performance, database access, spacial locality

FULL TR: pdf
FULL CONFERENCE PAPER: pdf