Partition-based clustering in object bases: From theory to practice

Carsten Gerlhof, Alfons Kemper, Christoph Kilger, Guido Moerkotte

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

21 Scopus citations


We classify clustering algorithms into sequence-based techniques-which transform the object net into a linear sequence—and partition-based clustering algorithms. Tsangaris and Naughton [TN91, TN92] have shown that the partition-based techniques are superior. However, their work is based on a single partitioning algorithm, the Kernighart and Lin heuristics, which is not applicable to realistically large object bases because of its high running-time complexity. The contribution of this paper is two-fold: (1) we devise a new class of greedy object graph partitioning algorithms (GGP) whose running-time complexity is moderate while still yielding good quality results. (2) Our extensive quantitative analysis of all well-known partitioning algorithms indicates that no one algorithm performs superior for all object net characteristics. Therefore, we propose an adaptable clustering strategy according to a multi-dimensional grid: the dimensions correspond to particular characteristics of the object base-given by, e.g., number and size of objects, degree of object sharing-and the grid entries indicate the most suitable clustering algorithm for the particular configuration.

Original languageEnglish
Title of host publicationFoundations of Data Organization and Algorithms - 4th International Conference, FODO 1993, Proceedings
EditorsDavid B. Lomet
PublisherSpringer Verlag
Number of pages16
ISBN (Print)9783540573012
StatePublished - 1993
Externally publishedYes
Event4th International Conference on Foundations of Data Organization and Algorithms, FODO 1993 - Chicago, United States
Duration: 13 Oct 199315 Oct 1993

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume730 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference4th International Conference on Foundations of Data Organization and Algorithms, FODO 1993
Country/TerritoryUnited States


Dive into the research topics of 'Partition-based clustering in object bases: From theory to practice'. Together they form a unique fingerprint.

Cite this