K-tree: large scale document clustering

ABSTRACT

We introduce K-tree in an information retrieval context. It is an efficient approximation of the k-means clustering algorithm. Unlike k-means it forms a hierarchy of clusters. It has been extended to address issues with sparse representations. We compare performance and quality to CLUTO using document collections. The K-tree has a low time complexity that is suitable for large document collections. This tree structure allows for efficient disk based implementations where space requirements exceed that of main memory.

REFERENCES

• 1: K-tree project page, http://ktree.sourceforge.net. 2009.
• 2: Ludovic Denoyer , Patrick Gallinari, The Wikipedia XML corpus, ACM SIGIR Forum, v.40 n.1, June 2006 [doi>10.1145/1147197.1147210]
• 3: S. Geva. K-tree: a height balanced tree structured vector quantizer. Neural Networks for Signal Processing X, 2000. Proceedings of the 2000 IEEE Signal Processing Society Workshop, 1:271--280 vol.1, 2000.
• 4: G. Karypis. CLUTO-A Clustering Toolkit. 2002.
• 5: L. Kaufman, P. Rousseeuw, Delft(Netherlands). Dept. of Mathematics Technische Hogeschool, and Informatics. Clustering by means of medoids. Technical report, Technische Hogeschool, Delft(Netherlands). Dept. of Mathematics and Informatics., 1987.
• 6: Y. Song, W.Y. Chen, H. Bai, C.J. Lin, and E.Y. Chang. Parallel Spectral Clustering. 2008.
• 7: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: A New Data Clustering Algorithm and Its Applications, Data Mining and Knowledge Discovery, v.1 n.2, p.141-182, 1997 [doi>10.1023/A:1009783824328]

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, Performance

Keywords:
B-tree, K-means, K-tree, document clustering, search tree