Abstract
We propose a new similarity-based technique for declustering data. The proposed method can adapt to available information about query distributions, data distributions, data sizes and partition-size constraints. The method is based on max-cut partitioning of a similarity graph defined over the given set of data, under constraints on the partition sizes. It maximizes the chances that a pair of data-items that are to be accessed together by queries are allocated to distinct disks. We show that the proposed method can achieve optimal speed-up for a query-set, if there exists any other declustering method which will achieve the optimal speed-up. Experiments in parallelizing Grid Files show that the proposed method outperforms mapping-function-based methods for interesting query distributions as well for non-uniform data distributions.
| Original language | English (US) |
|---|---|
| Title of host publication | Proceedings - International Conference on Data Engineering |
| Publisher | IEEE |
| Pages | 373-381 |
| Number of pages | 9 |
| State | Published - Jan 1 1995 |
| Event | Proceedings of the 1995 IEEE 11th International Conference on Data Engineering - Taipei, Taiwan Duration: Mar 6 1995 → Mar 10 1995 |
Other
| Other | Proceedings of the 1995 IEEE 11th International Conference on Data Engineering |
|---|---|
| City | Taipei, Taiwan |
| Period | 3/6/95 → 3/10/95 |