Efficient range query retrieval for non-uniform data distributions

S. Mohammed, E. P. Harris, K. Ramamohanarao

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations


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.

Original languageEnglish
Title of host publicationProceedings - 11th Australasian Database Conference, ADC 2000
EditorsMaria E. Orlowska
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages9
ISBN (Electronic)0769505287, 9780769505282
StatePublished - 2000
Externally publishedYes

Publication series

NameProceedings - 11th Australasian Database Conference, ADC 2000

Bibliographical note

Funding 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.

Publisher Copyright:
© 2000 IEEE.

ASJC Scopus subject areas

  • Hardware and Architecture
  • Information Systems


Dive into the research topics of 'Efficient range query retrieval for non-uniform data distributions'. Together they form a unique fingerprint.

Cite this