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, db/conf/sigmod/TsangarisN91.html},
  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 ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

, 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)
[Cat88]: R. G. G. Cattell: Object-Oriented DBMS Performance Measurement. OODBS 1988: 364-367
[Den68]: Peter J. Denning: The Working Set Model for Program Behaviour. Commun. ACM 11(5): 323-333(1968)
[DK90]: Pamela Drew, Roger King, Scott E. Hudson: The Performance and Utility of the Cactis Implementation Algorithms. VLDB 1990: 135-147
[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
[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)
[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)
[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)
[KL70]: ...
[RC88]: Joel E. Richardson, Michael J. Carey: Persistence in the E Language: Issues and Implementation. Softw., Pract. Exper. 19(12): 1115-1150(1989)
[SS90]: Karen Shannon, Richard T. Snodgrass: Semantic Clustering. POS 1990: 389-402
[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)
[TN90]: ...
[TN91]: ...
[VC90]: Paul Vongsathorn, Scott D. Carson: A System for Adaptive Disk Rearrangement. Softw., Pract. Exper. 20(3): 225-242(1990)
[Won83]: C. K. Wong: Algorithmic Studies in Mass Storage Systems. Computer Science Press 1983
[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)