Constrained declustering

Declustering have attracted a lot of interest over the last few years. Except for a few cases it is not possible to find declustering schemes that are optimal for all spatial range queries. As a result of this, most of the research on declustering have focused on finding schemes with low worst case additive error. However, additive error based schemes have many limitations including lack of progressive guarantees and existence of small nonoptimal queries. In this paper, we take a different approach and investigate schemes that provide progressive guarantees. We investigate the threshold k such that all spatial range queries with /spl les/ k buckets are optimal. By dividing a query into nonoverlapping rectangles each with /spl les/ k buckets the guarantees of threshold can be extended to larger queries. Theoretical analysis shows that threshold k is bounded above by N/2 for N-by-N declustering system with N disks. We propose a number-theoretic threshold algorithm. Experimental results show that proposed algorithm returns schemes with high threshold and low worst-case additive error.