Paper Info
Title
MultiMap: Preserving disk locality for multidimensional datasets
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.
Year
DOI
Venue
2007
10.1109/ICDE.2007.367938
ICDE
Keywords
Field
DocType
revealing disk-specific details,spatial locality,multimap,full streaming bandwidth,data mining,multidimensional datasets,distributed databases,disk locality preservation,storage system,database systems,prototypes,multidimensional systems,relational databases,bandwidth,hilbert space
Hilbert space,Data mining,Locality,Relational database,Computer science,Bandwidth (signal processing),Throughput,Distributed database,Multimap,Database,Multidimensional systems
Conference
ISSN
ISBN
Citations 
1084-4627
1-4244-0802-4
2
PageRank 
References 
Authors
0.38
31
6
Name
Order
Citations
PageRank
Minglong Shao11849.53
Steven W. Schlosser229923.66
Stratos Papadomanolakis318613.71
Jiri Schindler441126.82
Anastasia Ailamaki54178349.12
Gregory R. Ganger64560383.16