Parallel PathFinder algorithms for mining structures from graphs

Samson Hauguel, Chengxiang Zhai, Jiawei Han

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

Abstract

PathFinder networks are increasingly used in Data Mining for different purposes, like network visualization or knowledge extraction. This novel way of representing graphical data has been proven to give better results than other link reduction algorithms, like minimum spanning networks. However, this increase in quality comes with a high computation cost, typically of the order of n̂3 or higher, where n is the number of nodes in the graph. While this problem has previously been tackled by using mathematical properties to speed up the algorithm, in this paper, we propose two new algorithms to speed up PathFinder computation based on parallelization techniques to take advantage of the increasingly available multi-core hardware platform. Experiments show that both new algorithms are more efficient than the state of the art algorithms; one of them can achieve speed-ups of up to x127 with an average of x23 on recent hardware (2007).

Original languageEnglish (US)
Title of host publicationICDM 2009 - The 9th IEEE International Conference on Data Mining
Pages812-817
Number of pages6
DOIs
StatePublished - Dec 1 2009
Event9th IEEE International Conference on Data Mining, ICDM 2009 - Miami, FL, United States
Duration: Dec 6 2009Dec 9 2009

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)1550-4786

Other

Other9th IEEE International Conference on Data Mining, ICDM 2009
Country/TerritoryUnited States
CityMiami, FL
Period12/6/0912/9/09

Keywords

  • Graph mining
  • Parallel computing

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint

Dive into the research topics of 'Parallel PathFinder algorithms for mining structures from graphs'. Together they form a unique fingerprint.

Cite this