UnkClus: Efficient clustering via heterogeneous semantic links

Xiaoxin Yin, Jiawei Han, Philip S. Yu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Uata objects in a relational database are cross-linked with each other via multi-typed links. Links contain rich seman-tic information that may indicate important relationships among objects. Most current clustering methods rely only on the properties that belong to the objects per se. Howler, the similarities between objects are often indicated by the links, and desirable clusters cannot be generated using only the properties of objects. In this paper we explore linkage-based clustering, in which the similarity between two objects is measured based on the similarities between the objects linked with them. In comparison with a previous study (SimRank) that computes links recursively on all pairs of objects, we take advantage of the power law distribution of links, and develop a hi-erarchical structure called SimTree to represent similarities in multi-granularity manner. This method avoids the high cost of computing and storing pairwise similarities but still thoroughly explore relationships among objects. An efficient algorithm is proposed to compute similarities between objects by avoiding pairwise similarity computations through Purging computations that go through the same branches In the SimTree. Experiments show the proposed approach achieves high efficiency, scalability, and accuracy in clustering multi-typed linked objects.

Original languageEnglish (US)
Title of host publicationVLDB 2006 - Proceedings of the 32nd International Conference on Very Large Data Bases
PublisherAssociation for Computing Machinery
Pages427-438
Number of pages12
ISBN (Print)1595933859, 9781595933850
StatePublished - 2006
Event32nd International Conference on Very Large Data Bases, VLDB 2006 - Seoul, Korea, Republic of
Duration: Sep 12 2006Sep 15 2006

Publication series

NameVLDB 2006 - Proceedings of the 32nd International Conference on Very Large Data Bases

Other

Other32nd International Conference on Very Large Data Bases, VLDB 2006
Country/TerritoryKorea, Republic of
CitySeoul
Period9/12/069/15/06

ASJC Scopus subject areas

  • Hardware and Architecture
  • Information Systems
  • Software
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'UnkClus: Efficient clustering via heterogeneous semantic links'. Together they form a unique fingerprint.

Cite this