Answering range queries is a common database operation. Methods based on hashing techniques to minimise the cost of answering range queries by taking the query distribution into account have previously been proposed. These methods have all assumed a uniform distribution of data to disk pages to achieve good performance. This assumption makes them less useful in practice because most real data distributions are non-uniform. In this paper, we discuss a method to eliminate this restriction. Extensive experimentation using a multi-dimensional file structure, the BANG file, indicates that our method results in good performance for all data distributions. In one case an improvement of over 36 times was achieved without compromising the storage utilisation. Our method also results in a stable and efficient file organisation. If the query distribution does not change substantially, an optimised file organisation rarely requires reorganisation.
|Title of host publication||Proceedings - 11th Australasian Database Conference, ADC 2000|
|Editors||Maria E. Orlowska|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||9|
|ISBN (Electronic)||0769505287, 9780769505282|
|State||Published - 2000|
|Name||Proceedings - 11th Australasian Database Conference, ADC 2000|
Bibliographical noteFunding Information:
The authors were supported by Australian Research Council grants. The first author was also supported by a Monash University postgraduate scholarship. We also thank Prof. Srinivasan for his helpful comments.
© 2000 IEEE.
ASJC Scopus subject areas
- Hardware and Architecture
- Information Systems