|
|
|
     |
                                     |
Return to Streams and Indexing
We consider the index selection problem. Given either a fixed query workload or an unknown probability distribution on possible future queries, and a bound B on how much space is available to build indices, we seek to build a collection of indices for which the average query response time is minimized. We give strong negative and positive peformance bounds. Let m be the number of queries in the workload. We show how to obtain with high probability a collection of indices using space O(B lnm) for which the average query cost is opt_B, the optimal performance possible for indices using at most B total space. Moreover, this space relaxation is nec- essary: unless NP is asubset of n^O(log log n), no polynomial time algo- rithm can guarantee average query cost less than M^(1-epsilon) opt_B using space alpha B, for any constant alpha, where M is the size of the dataset. We quantify the error in performance introduced by running the algorithm on a sample drawn from a query distribution.
@inproceedings {DBLP:conf/pods/HeerenJP03, author = {C. Heeren and H. V. Jagadish and L. Pitt}, booktitle = {PODS}, title = {Optimal indexing using near-minimal space.}, pages = {244-251}, year = {2003}, url = {db/conf/pods/pods2003.html#HeerenJP03}, ee = {http://doi.acm.org/10.1145/773153.773177}, crossref = {conf/pods/2003}, bibsource = {DBLP, http://dblp.uni-trier.de} }  ©2004 Association for Computing Machinery |
