Indexing schemes for range query workloads.

摘要

We investigate a fundamental problem in data storage systems, the efficient retrieval of d-dimensional range queries from external memory. For multidimensional data this problem is inherently hard because of the nature of secondary memory devices; data must be grouped together for fast access. This introduces locality of reference issues absent from the internal memory problem.;We consider the tradeoff between storage redundancy and access overhead, using the indexing scheme measure of Hellerstein, Koutsoupias, and Papadimitriou. These parameters measure the size of a database, and its speed in answering queries.;We give upper and lower bounds on the tradeoff required for arbitrary 2-dimensional workloads (point sets), and for random d-dimensional workloads. These bounds are tight with respect to the total size of the workload, and exhibit a threshold behavior: redundancy values less than the threshold imply near worst case data access patterns, while slightly higher values permit near optimal access performance.;We also study generalizations of indexing schemes for multiple disks, fault tolerant replication, and alternate complexity measures. In each case, our results are promising, especially for multiple disks: we show the surprising result that for some workloads, D disks increase access speeds substantially more than a factor of D.