Circular Data-space Partitioning for Similarity Queries andParallel Disk Allocation

In a multiple disk environment it is desirable to have techniques for efficientparallel execution of similarity queries. Usually many buckets that may havethe query result are needed to be retrieved from secondary storage, which is acostly operation. To achieve efficiency, there are two major factors that needto be considered. These are the number of buckets retrieved by the query, andthe degree of parallelism provided by the disk allocation method. In thispaper, we develop efficient techniques for parallel similarity searching byoptimizing these two factors defined for data-sets that are circular in nature,and similarity queries consisting of query disks centered at the query point.Our partitioning technique minimizes the expected number of buckets retrievedby a random query among a spectrum of partitioning schemes which have equi-areaconcentric rings and equi-area central wedges as its two extremes. A simpledisk allocation technique for the proposed partitioning method that maximizesthe degree of parallelism obtained is also described.