A direct mining approach to efficient constrained graph pattern discovery

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisKonferenceartikelForskningpeer review

  • Feida Zhu, Singapore Management University, Singapore
  • Zequn Zhang, University of Science and Technology of China, Kina
  • Qiang Qu, Danmark
Despite the wealth of research on frequent graph pattern mining, how to efficiently mine the complete set of those with constraints still poses a huge challenge to the existing algorithms mainly due to the inherent bottleneck in the mining paradigm. In essence, mining requests with explicitly-specified constraints cannot be handled in a way that is direct and precise. In this paper, we propose a direct mining framework to solve the problem and illustrate our ideas in the context of a particular type of constrained frequent patterns --- the "skinny" patterns, which are graph patterns with a long backbone from which short twigs branch out. These patterns, which we formally define as l-long δ-skinny patterns, are able to reveal insightful spatial and temporal trajectory patterns in mobile data mining, information diffusion, adoption propagation, and many others.

Based on the key concept of a canonical diameter, we develop SkinnyMine, an efficient algorithm to mine all the l-long δ-skinny patterns guaranteeing both the completeness of our mining result as well as the unique generation of each target pattern. We also present a general direct mining framework together with two properties of reducibility and continuity for qualified constraints. Our experiments on both synthetic and real data demonstrate the effectiveness and scalability of our approach.
OriginalsprogEngelsk
TidsskriftAssociation for Computing Machinery. Special Interest Group on Management of Data. International Conference Proceedings
Sider (fra-til)821-832
Antal sider12
ISSN0730-8078
DOI
StatusUdgivet - 1 jan. 2013
BegivenhedACM SIGMOD International Conference on Management of Data - New York, USA
Varighed: 22 jun. 201327 jun. 2013

Konference

KonferenceACM SIGMOD International Conference on Management of Data
LandUSA
ByNew York
Periode22/06/201327/06/2013

Bibliografisk note

title of the vol.: SIGMOD '13 Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data/ ed. by Kenneth Ross, Divesh Srivastava. ISBN: 978-1-4503-2037-5

Se relationer på Aarhus Universitet Citationsformater

ID: 166878466