language: en

Efficient Disk Allocation for Fast Similarity Searching

Sunil Prabhakar Divyakant Agrawal Amr El Abbadi
Department of Computer Science University of California
Santa Barbara CA 93106, U.S.A.
{sunilp,agrawal,amr}@cs.ucsb.edu

Abstract As databases increasingly integrate non-textual information it is becoming necessary to support efficient similarity searching in addition to range searching. Recently, declustering techniques have been proposed for improving the performance of similarity searches through parallel I/O. In this paper, we propose a new scheme which provides good declus-tering for similarity searching. In particular, it does global declustering as opposed to local declustering, exploits the availability of extra disks and does not limit the partitioning of the data space. Our technique is based upon the Cyclic declustering schemes which were developed for range and partial match queries. We establish, in general, that Cyclic declustering techniques outperform previously proposed techniques.

[Appeared in Proc. 10th ACM Symposium on Parallel Algorithms and Architectures (SPAA '98), Puerto Vallarta, Mexico]

1 Introduction