On the Performance of Object Clustering Techniques.

Manolis M. Tsangaris, Jeffrey F. Naughton: On the Performance of Object Clustering Techniques. SIGMOD Conference 1992: 144-153

@inproceedings{DBLP:conf/sigmod/TsangarisN92,
  author    = {Manolis M. Tsangaris and
               Jeffrey F. Naughton},
  editor    = {Michael Stonebraker},
  title     = {On the Performance of Object Clustering Techniques},
  booktitle = {Proceedings of the 1992 ACM SIGMOD International Conference on
               Management of Data, San Diego, California, June 2-5, 1992},
  publisher = {ACM Press},
  year      = {1992},
  pages     = {144-153},
  ee        = {http://doi.acm.org/10.1145/130283.130308, db/conf/sigmod/TsangarisN92.html},
  crossref  = {DBLP:conf/sigmod/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We investigate the performance of some of the best-known object clustering algorithms on four different workloads based upon the Tektronix benchmark. For all four workloads, stochastic clustering gave the best performance for a variety of performance metrics. Since stochastic clustering is computationally expensive, it is interesting that for every workload there was at least one cheaper clustering algorithm that matched or almost matched stochastic clustering. Unfortunately, for each workload, the algorithm that approximated stochastic clustering was different. Our experiments also demonstrated that even when the workload and object graph are fixed, the choice of the clustering algorithm depends upon the goals of the system. For example, if the goal is to perform well on traversals of small portions of the database starting with a cold cache, the important metric is the per-traversal expansion factor, and a well-chosen placement tree will be nearly optimal; if the goal is to achieve a high steady-state performance with a reasonably large cache, the appropriate metric is the number of pages to which the clustering algorithm maps the active portion of the database. For this metric, the PRP clustering algorithm, which only uses access probabilities achieves nearly optimal performance.

Copyright © 1992 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

Michael Stonebraker (Ed.): Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, San Diego, California, June 2-5, 1992. ACM Press 1992

, SIGMOD Record 21(2), June 1992
Contents

Online Edition: ACM Digital Library

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

References

[And+90]: T. Lougenia Anderson, Arne-Jørgen Berre, Moira Mallison, Harry H. Porter, Bruce Schneider: The HyperModel Benchmark. EDBT 1990: 317-331
[Bai89]: Peter J. Bailey: Performance Evaluation in a Persistent Object Store. POS 1989: 289-299
[BD90]: ...
[Den68]: Peter J. Denning: The Working Set Model for Program Behaviour. Commun. ACM 11(5): 323-333(1968)
[Deu+91]: O. Deux: The O2 System. Commun. ACM 34(10): 34-48(1991)
[DK90]: Pamela Drew, Roger King, Scott E. Hudson: The Performance and Utility of the Cactis Implementation Algorithms. VLDB 1990: 135-147
[HBD91]: ...
[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)
[KL70]: ...
[PS82]: Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall 1982, ISBN 0-13-152462-3
[PY91]: Mark Palmer, Stanley B. Zdonik: Fido: A Cache That Learns to Fetch. VLDB 1991: 255-264
[RC89]: 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)
[TN91a]: Manolis M. Tsangaris, Jeffrey F. Naughton: A Stochastic Approach for Clustering in Object Bases. SIGMOD Conference 1991: 12-21
[TN91b]: ...
[TN92]: ...
[YSLS85]: Clement T. Yu, Cheing-Mei Suen, K. Lam, M. K. Siu: Adaptive Record Clustering. ACM Trans. Database Syst. 10(2): 180-204(1985)
[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)