ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

A Decomposition-Based Simulated Annealing Technique for Data Clustering.

Kien A. Hua, Sheau-Dong Lang, Wen K. Lee: A Decomposition-Based Simulated Annealing Technique for Data Clustering. PODS 1994: 117-128
@inproceedings{DBLP:conf/pods/HuaLL94,
  author    = {Kien A. Hua and
               Sheau-Dong Lang and
               Wen K. Lee},
  title     = {A Decomposition-Based Simulated Annealing Technique for Data
               Clustering},
  booktitle = {Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 24-26, 1994, Minneapolis,
               Minnesota},
  publisher = {ACM Press},
  year      = {1994},
  isbn      = {0-89791-642-5},
  pages     = {117-128},
  ee        = {http://doi.acm.org/10.1145/182591.182605, db/conf/pods/pods94-117.html},
  crossref  = {DBLP:conf/pods/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

It has been demonstrated that simulated annealing provides high-quality results for the data clustering problem. However, existing simulated annealingschemes are memory-based algorithms; they are not suited for solving large problems such as data clustering which typically are too big to fit in the memory space in its entirety. Various buffer replacement policies, assuming either temporal or spatial locality, are not useful in this case since simulated annealing is based on a randomized search process. Poor locality of references will cause the memory to thrash because too many replacements are required. This phenomenon will incur excessive disk accesses and force the machine to run at the speed of the I/O subsystem. In this paper, we formulate the data clustering problem as a graph partition problem (GPP), and propose a decomposition-based approach to address the issue of excessive disk accesses during annealing. We apply the statistical sampling technique to randomly select subgraphs of the GPP into memory for annealing. Both the analytical and experimental studies indicate that the decomposition-based approach can dramatically reduce the costly disk I/O activities while obtainingexcellent optimized results.

Copyright © 1994 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 24-26, 1994, Minneapolis, Minnesota. ACM Press 1994, ISBN 0-89791-642-5
Contents BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1122 KB]

References

[AK89]
...
[AvL85]
...
[BMS90]
...
[Fel50]
...
[IK91]
Yannis E. Ioannidis, Younkyung Cha Kang: Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and its Implications for Query Optimization. SIGMOD Conference 1991: 168-177 BibTeX
[KGV83]
...
[KL70]
...
[LD88]
...
[LV91]
Rosana S. G. Lanzelotte, Patrick Valduriez: Extending the Search Strategy in a Query Optimizer. VLDB 1991: 363-373 BibTeX
[MB87]
...
[MBM90]
F. J. McErlean, David A. Bell, Sally I. McClean: The use of simulated annealing for clustering data in databases. Inf. Syst. 15(2): 233-245(1990) BibTeX
[MRSV86]
...
[SSV85]
...
[Swa89]
Arun N. Swami: Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques. SIGMOD Conference 1989: 367-376 BibTeX
[TN91]
Manolis M. Tsangaris, Jeffrey F. Naughton: A Stochastic Approach for Clustering in Object Bases. SIGMOD Conference 1991: 12-21 BibTeX
[TN92]
Manolis M. Tsangaris, Jeffrey F. Naughton: On the Performance of Object Clustering Techniques. SIGMOD Conference 1992: 144-153 BibTeX
[vL88]
...
[vLA88]
...

Referenced by

  1. Bernd-Uwe Pagel, Hans-Werner Six, Mario Winter: Window Query-Optimal Clustering of Spatial Objects. PODS 1995: 86-94
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:10 2009