dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

A Stochastic Approach for Clustering in Object Bases.

Manolis M. Tsangaris, Jeffrey F. Naughton: A Stochastic Approach for Clustering in Object Bases. SIGMOD Conference 1991: 12-21
@inproceedings{DBLP:conf/sigmod/TsangarisN91,
  author    = {Manolis M. Tsangaris and
               Jeffrey F. Naughton},
  editor    = {James Clifford and
               Roger King},
  title     = {A Stochastic Approach for Clustering in Object Bases},
  booktitle = {Proceedings of the 1991 ACM SIGMOD International Conference on
               Management of Data, Denver, Colorado, May 29-31, 1991},
  publisher = {ACM Press},
  year      = {1991},
  pages     = {12-21},
  ee        = {http://doi.acm.org/10.1145/115790.115792},
  crossref  = {DBLP:conf/sigmod/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Object clustering has long been recognized as important to the performance of object bases, but in most work to date, it is not clear exactly what is being optimized or how optimal are the solutions obtained. We give a rigorous treatment of a fundamental problem in clustering: given an object base and a probabilistic description of the expected access patterns, what is an optimal object clustering, and how can this optimal clustering be found or approximated? We present a system model for the clustering problem and discuss two models for access patterns in the system. For the first, exact optimal clustering strategies can be found; for the second, we show that the problem is NP-complete, but that it is an instance of a well-studied graph partitioning problem. We propose a new clustering algorithm based upon Kernighan's heuristic graph partitioning algorithm, and present a preliminary experimental comparison of this new clustering algorithm with several previously proposed clustering algorithms.

Copyright © 1991 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.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

James Clifford, Roger King (Eds.): Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 29-31, 1991. ACM Press 1991 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 20(2), June 1991
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 944 KB]

References

[All78]
...
[Bar84]
...
[BD90]
...
[BVJ84]
...
[CAC+84]
W. Paul Cockshott, Malcolm P. Atkinson, Kenneth Chisholm, Peter J. Bailey, Ronald Morrison: Persistent Object Management System. Softw., Pract. Exper. 14(1): 49-71(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cat88]
R. G. G. Cattell: Object-Oriented DBMS Performance Measurement. OODBS 1988: 364-367 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Den68]
Peter J. Denning: The Working Set Model for Program Behaviour. Commun. ACM 11(5): 323-333(1968) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DK90]
Pamela Drew, Roger King, Scott E. Hudson: The Performance and Utility of the Cactis Implementation Algorithms. VLDB 1990: 135-147 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GJ79]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GS73]
David D. Grossman, Harvey F. Silverman: Placement of Records on a Secondary Storage Device to Minimize Access Time. J. ACM 20(3): 429-438(1973) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HK89]
Scott E. Hudson, Roger King: Cactis: A Self-Adaptive, Concurrent Implementation of an Object-Oriented Database Management System. ACM Trans. Database Syst. 14(3): 291-321(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HZ87]
Mark F. Hornick, Stanley B. Zdonik: A Shared, Segmented Memory System for an Object-Oriented Database. ACM Trans. Inf. Syst. 5(1): 70-95(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KL70]
...
[RC88]
Joel E. Richardson, Michael J. Carey: Persistence in the E Language: Issues and Implementation. Softw., Pract. Exper. 19(12): 1115-1150(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SS90]
Karen Shannon, Richard T. Snodgrass: Semantic Clustering. POS 1990: 389-402 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sta84]
James W. Stamos: Static Grouping of Small Objects to Enhance Performance of a Paged Virtual Memory. ACM Trans. Comput. Syst. 2(2): 155-180(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[TN90]
...
[TN91]
...
[VC90]
Paul Vongsathorn, Scott D. Carson: A System for Adaptive Disk Rearrangement. Softw., Pract. Exper. 20(3): 225-242(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Won83]
C. K. Wong: Algorithmic Studies in Mass Storage Systems. Computer Science Press 1983
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[YW73]
P. C. Yue, C. K. Wong: On the Optimality of the Probability Ranking Scheme in Storage Applications. J. ACM 20(4): 624-633(1973) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Tue Sep 18 00:25:05 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page