Partitioning similarity graphs: A framework for declustering problems

Duen Ren Liu, Shashi Shekhar

Research output: Contribution to journalArticlepeer-review

50 Scopus citations


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 denned 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.

Original languageEnglish (US)
Pages (from-to)475-496
Number of pages22
JournalInformation Systems
Issue number6
StatePublished - Sep 1996

Bibliographical note

Funding Information:
Acknowledgements --This work was done while the author was pursuing the Ph.D. degree in the Department of Computer Science, University of Minnesota. This research was supported by the Federal Highway Authority (FHWA), Minnesota Dept. of Transportation and the Center for Transportation Studies at the University of Minnesota. We would like to thank Prof. C.K. Cheng (University of California, San Diego) and Dr. L.T. Liu (AT&T Bell Labs) for helping with the ratio-cut program. Besides, we would like to thank several individuals who helped in the implementation and discussion of the grid file, including Y. Zhou and M. Coyle.


  • Declustering
  • Geographic Databases
  • Grid File
  • Parallel Databases
  • Similarity Graph


Dive into the research topics of 'Partitioning similarity graphs: A framework for declustering problems'. Together they form a unique fingerprint.

Cite this