On the performance of object clustering techniques

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.

REFERENCES

• And+90: T. Lousenia Anderson et al. The Tektronix HyperModel Benchmark. EDBT, 1990.
• Bai89: Peter J. Bailey, Performance Evaluation in a Persistent Object Store, Proceedings of the Third International Workshop on Persistent Object Systems, p.289-299, January 10-13, 1989
• BD90: Veronique Benzaken and Claude Delobel. Enhancing performance in a persistent object store: Clustering strategies in 02. Technical Report 50-90, Altair, August 1990.
• Den68: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• Deu+91: O. Deux, The O2 system, Communications of the ACM, v.34 n.10, p.34-48, Oct. 1991 [doi>10.1145/125223.125238]
• DK90: Pamela Drew , Roger King , Scott E. Hudson, The performance and utility of the Cactis implementation algorithms, Proceedings of the sixteenth international conference on Very large databases, p.135-147, September 1990, Brisbane, Australia
• HBD91: Gilbert Harrus, Veronique Benzaken, and Claude Delobel. Measuring performance of clustering strategies: the CluB-0 benchmark. Technical Report 66-91, Altair, January 1991.
• HK89: Scott E. Hudson , Roger King, Cactis: a self-adaptive, concurrent implementation of an object-oriented database management system, ACM Transactions on Database Systems (TODS), v.14 n.3, p.291-321, Sept. 1989 [doi>10.1145/68012.68013]
• KL70: B.W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49(2):291-307, February 1970.
• PS82: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• PZ91: Mark Palmer , Stanley B. Zdonik, Fido: A Cache That Learns to Fetch, Proceedings of the 17th International Conference on Very Large Data Bases, p.255-264, September 03-06, 1991
• RC89: Joel E. Richardson , Michael J. Carey, Persistence in the E Language: Issues and implementation, Software—Practice & Experience, v.19 n.12, p.1115-1150, Dec. 1989
• SS90: Karen Shannon and Richard Snodgrass. Semantic clustering. In Proceedings of the $-th Int'l Workshop in Persistent Object Systems, pages 361-374, Martha's Vineyard, MA, September 1990.
• Sta84: James W. Stamos, Static grouping of small objects to enhance performance of a paged virtual memory, ACM Transactions on Computer Systems (TOCS), v.2 n.2, p.155-180, May 1984 [doi>10.1145/190.194]
• TN91a: Manolis M. Tsangaris , Jeffrey F. Naughton, A stochastic approach for clustering in object bases, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.12-21, May 29-31, 1991, Denver, Colorado, United States
• TN91b: Manolis M. Tsangaris and Jeffrey F. Naughton. A stochastic approach for clustering in object stores. Technical Report 1017, University of Wisconsin, Computer Sciences Dept., April 1991.
• TN92: Manolis M. Tsangaris and Jeffrey F. Naughton. On the performance of object clustering techniques. Technical report, University of Wisconsin, Computer Sciences Dept., March 1992.
• YSLS85: C. T. Yu , Cheing-mei Suen , K. Lam , M. K. Siu, Adaptive record clustering, ACM Transactions on Database Systems (TODS), v.10 n.2, p.180-204, June 1985 [doi>10.1145/3857.3861]
• YW73: P. C. Yue , C. K. Wong, On the Optimality of the Probability Ranking Scheme in Storage Applications, Journal of the ACM (JACM), v.20 n.4, p.624-633, Oct. 1973 [doi>10.1145/321784.321790]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

General Terms:
Algorithms, Measurement, Performance, Theory