Partitioning similarity graphs: A framework for declustering problems

檔案

日期

1996-09-01

類型

期刊名稱

INFORMATION SYSTEMS

卷期與頁次

第 21 卷第 6 期,頁 475–496

ISSN

0306-4379

語言

英文

摘要

Declustering problems are well-known in the databases for parallel computing environments. In this paper, we propose a new similarity-based technique for declustering data. The proposed method can adapt to the available information about query distribution (e.g. size,shape and frequency) and can work with alternative atomic data-types. Furthermore, the proposed method is flexible and can work with alternative 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 atomic data-items that are frequently accessed together by queries are allocated to distinct disks. We describe the application of the proposed method to parallelizing Grid Files at the data page level. Detailed experiments in this context show that the proposed method adapts to query distribution and data distribution, and that it outperforms traditional mapping-function-based methods for many interesting query distributions as well for several non-uniform data distributions. Copyright (C) 1996 Elsevier Science Ltd

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Liu, D., & Shekhar, S. (1996). Partitioning similarity graphs: A framework for declustering problems. INFORMATION SYSTEMS, 21(6), 475–496. https://doi.org/10.1016/0306-4379(96)00024-5

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/1068