DocumentCode :
2731138
Title :
MultiMap: Preserving disk locality for multidimensional datasets
Author :
Minglong Shao ; Schlosser, S.W. ; Papadomanolakis, S. ; Schindler, J. ; Ailamaki, Anastasia ; Ganger, Gregory R.
Author_Institution :
Carnegie Mellon Univ., Pittsburgh, PA, USA
fYear :
2007
fDate :
15-20 April 2007
Firstpage :
926
Lastpage :
935
Abstract :
MultiMap is an algorithm for mapping multidimensional datasets so as to preserve the data´s spatial locality on disks. Without revealing disk-specific details to applications, 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 total I/O time by over 50% when compared to traditional linearized layouts and by over 30% when compared to space-filling curve approaches such as Z-ordering and Hilbert curves. For scans of the primary dimension, MultiMap and traditional linearized layouts provide almost two orders of magnitude higher throughput than space-filling curve approaches.
Keywords :
data mining; distributed databases; MultiMap; disk locality preservation; full streaming bandwidth; multidimensional datasets; revealing disk-specific details; spatial locality; Bandwidth; Database systems; Delay; Disk drives; Hilbert space; Image databases; Multidimensional systems; Multimedia databases; Prototypes; Relational databases;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on
Conference_Location :
Istanbul
Print_ISBN :
1-4244-0802-4
Type :
conf
DOI :
10.1109/ICDE.2007.367938
Filename :
4221741
Link To Document :
بازگشت