4th USENIX Conference on File and Storage TechnologiesAbstract
Pp. 225238 of the Proceedings
Awarded Best Paper!
On multidimensional data and modern disks
Steven W. Schlosser, Intel Research Pittsburgh; Jiri Schindler, EMC Corporation; Stratos Papadomanolakis, Minglong Shao,
Anastassia Ailamaki, Christos Faloutsos, and Gregory R. Ganger, Carnegie Mellon University
With the deeply-ingrained notion that disks can efficiently access only one dimensional data, current approaches
for mapping multidimensional data to disk
blocks either allow efficient accesses in only one dimension,
trading off the efficiency of accesses in other dimensions,
or equally penalize access to all dimensions.
Yet, existing technology and functions readily available
inside disk firmware can identify non-contiguous logical
blocks that preserve spatial locality of multidimensional
datasets. These blocks, which span on the order of a
hundred adjacent tracks, can be accessed with minimal
positioning cost. This paper details these technologies,
analyzes their trends, and shows how they can be exposed
to applications while maintaining existing abstractions.
The described approach can achieve the best possible
access efficiency afforded by the disk technologies:
sequential access along primary dimension and access
with minimal positioning cost for all other dimensions.
Experimental evaluation of a prototype implementation
demonstrates a reduction of overall I/O time for multidimensional
data queries between 30% and 50% when
compared to existing approaches.
- View the full text of this paper in HTML and PDF.
The Proceedings are published as a collective work, © 2005 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.