research-article

Fast search for dynamic multi-relational graphs

Authors:

Sutanay Choudhury,

Lawrence Holder,

George ChinAuthors Info & Claims

DyNetMM '13: Proceedings of the Workshop on Dynamic Networks Management and Mining

Pages 1 - 8

https://doi.org/10.1145/2489247.2489251

Published: 22 June 2013 Publication History

Abstract

Acting on time-critical events by processing ever growing social media or news streams is a major technical challenge. Many of these data sources can be modeled as multi-relational graphs. Continuous queries or techniques to search for rare events that typically arise in monitoring applications have been studied extensively for relational databases. This work is dedicated to answer the question that emerges naturally: how can we efficiently execute a continuous query on a dynamic graph? This paper presents an exact subgraph search algorithm that exploits the temporal characteristics of representative queries for online news or social media monitoring. The algorithm is based on a novel data structure called the Subgraph Join Tree (SJ-Tree) that leverages the structural and semantic characteristics of the underlying multi-relational graph. The paper concludes with extensive experimentation on several real-world datasets that demonstrates the validity of this approach.

References

[1]

Y.-N. Law, H. Wang, and C. Zaniolo, "Relational languages and data models for continuous queries on sequences and data streams," ACM Trans. Database Syst., June 2011.

Digital Library

[2]

D. Terry, D. Goldberg, D. Nichols, and B. Oki, "Continuous queries over append-only databases," SIGMOD Rec., 1992.

Digital Library

[3]

W. Fan, J. Li, J. Luo, Z. Tan, X. Wang, and Y. Wu, "Incremental graph pattern matching," ser. SIGMOD '11, 2011.

Digital Library

[4]

P. Zhao, X. Li, D. Xin, and J. Han, "Graph cube: on warehousing and olap multidimensional networks," in SIGMOD '11.

Digital Library

[5]

E. Spyropoulou and T. D. Bie, "Interesting multi-relational patterns," in ICDM, 2011, pp. 675--684.

Digital Library

[6]

L. Chen and C. Wang, "Continuous subgraph pattern search over certain and uncertain graph streams," IEEE Trans, on Knowl. and Data Eng., vol. 22, no. 8, pp. 1093--1109, Aug. 2010.

Digital Library

[7]

S. Chandrasekaran, O. Cooper, A. Deshpande, M. J. Franklin, J. M. Hellerstein, W. Hong, S. Krishnamurthy, S. R. Madden, F. Reiss, and M. A. Shah, "Telegraphcq: continuous dataflow processing," ser. SIGMOD '03.

Digital Library

[8]

A. Arasu, B. Babcock, S. Babu, M. Datar, K. Ito, I. Nishizawa, J. Rosenstein, and J. Widom, "Stream: The Stanford stream data manager," in SIGMOD '03.

Digital Library

[9]

B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom, "Models and issues in data stream systems," ser. PODS '02.

Digital Library

[10]

D. Conte, P. Foggia, C. Sansone, and M. Vento, "Thirty years of graph matching in pattern recognition," Intl. Journal of Pattern Recognition and Artificial Intelligence, 2004.

[11]

J. R. Ullmann, "An algorithm for subgraph isomorphism," J. ACM, vol. 23, pp. 31--42, January 1976.

Digital Library

[12]

L. Cordelia, P. Foggia, C. Sansone, and M. Vento, "A (sub) graph isomorphism algorithm for matching large graphs," IEEE Trans. on Pattern Analysis and Machine Intelli., 2004.

Digital Library

[13]

Y. Tian and J. Patel, "Tale: A tool for approximate large graph matching," in ICDE '08.

Digital Library

[14]

H. Tong, C. Faloutsos, B. Gallagher, and T. Eliassi-Rad, "Fast best-effort pattern matching in large attributed graphs," ser. KDD '07.

Digital Library

[15]

P. Zhao and J. Han, "On graph query optimization in large networks," PVLDB., vol. 3, pp. 340--351, September 2010.

Digital Library

[16]

Y. Zhu, L. Qin, J. X. Yu, Y. Ke, and X. Lin, "High efficiency and quality: large graphs matching," in Proceedings of the 20th ACM international conference on Information and knowledge management, ser. CIKM '11.

Digital Library

[17]

L. Zou, L. Chen, and M. T. Özsu, "Distance-join: pattern match query in a large graph database," PVLDB, vol. 2, no. 1, Aug. 2009.

Digital Library

[18]

A. Khan, N. Li, X. Yan, Z. Guan, S. Chakraborty, and S. Tao, "Neighborhood based fast graph search in large networks," ser. SIGMOD'11.

Digital Library

[19]

Z. Sun, H. Wang, H. Wang, B. Shao, and J. Li, "Efficient subgraph matching on billion node graphs," PVLDB, vol. 5, no. 9, 2012.

Digital Library

[20]

H. He and A. K. Singh, "Closure-tree: An index structure for graph queries," ser. ICDE '06.

Digital Library

Cited By

Leutwyler NLezoche MFranciosi CPanetto HTeste LTorres D(2024)Methods for concept analysis and multi-relational data mining: a systematic literature reviewKnowledge and Information Systems10.1007/s10115-024-02139-x66:9(5113-5150)Online publication date: 30-May-2024
https://doi.org/10.1007/s10115-024-02139-x
Wang XZhang QGuo DZhao X(2022)A survey of continuous subgraph matching for dynamic graphsKnowledge and Information Systems10.1007/s10115-022-01753-x65:3(945-989)Online publication date: 19-Oct-2022
https://doi.org/10.1007/s10115-022-01753-x
Hung BJayasumana ABandara V(2019)Finding Emergent Patterns of Behaviors in Dynamic Heterogeneous Social NetworksIEEE Transactions on Computational Social Systems10.1109/TCSS.2019.29387876:5(1007-1019)Online publication date: Oct-2019
https://doi.org/10.1109/TCSS.2019.2938787
Show More Cited By

Index Terms

Fast search for dynamic multi-relational graphs
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

StreamWorks: a system for dynamic graph search
SIGMOD '13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data

Acting on time-critical events by processing ever growing social media, news or cyber data streams is a major technical challenge. Many of these data sources can be modeled as multi-relational graphs. Mining and searching for subgraph patterns in a ...
Fast subgraph query processing and subgraph matching via static and dynamic equivalences
Abstract
Subgraph query processing (also known as subgraph search) and subgraph matching are fundamental graph problems in many application domains. A lot of efforts have been made to develop practical solutions for these problems. Despite the efforts, ...
Efficient continuous top-k keyword search in relational databases
WAIM'10: Proceedings of the 11th international conference on Web-age information management

Keyword search in relational databases has been widely studied in recent years. Most of the previous studies focus on how to answer an instant keyword query. In this paper, we focus on how to find the top-k answers in relational databases for continuous ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DyNetMM '13: Proceedings of the Workshop on Dynamic Networks Management and Mining

June 2013

33 pages

ISBN:9781450322096

DOI:10.1145/2489247

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Center for Adaptive Supercomputing Software - Multithreaded Architecture (CASS-MT) at the US Department of Energy's Pacific Northwest National Laboratory, operated by Battelle Memorial Institute

Conference

SIGMOD/PODS'13

Sponsor:

SIGMOD

SIGMOD/PODS'13: International Conference on Management of Data

June 22 - 27, 2013

New York, New York

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
161
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Leutwyler NLezoche MFranciosi CPanetto HTeste LTorres D(2024)Methods for concept analysis and multi-relational data mining: a systematic literature reviewKnowledge and Information Systems10.1007/s10115-024-02139-x66:9(5113-5150)Online publication date: 30-May-2024
https://doi.org/10.1007/s10115-024-02139-x
Wang XZhang QGuo DZhao X(2022)A survey of continuous subgraph matching for dynamic graphsKnowledge and Information Systems10.1007/s10115-022-01753-x65:3(945-989)Online publication date: 19-Oct-2022
https://doi.org/10.1007/s10115-022-01753-x
Hung BJayasumana ABandara V(2019)Finding Emergent Patterns of Behaviors in Dynamic Heterogeneous Social NetworksIEEE Transactions on Computational Social Systems10.1109/TCSS.2019.29387876:5(1007-1019)Online publication date: Oct-2019
https://doi.org/10.1109/TCSS.2019.2938787
Kanezashi HSuzumura TGarcia-Gasulla DOh MMatsuoka S(2018)Adaptive Pattern Matching with Reinforcement Learning for Dynamic Graphs2018 IEEE 25th International Conference on High Performance Computing (HiPC)10.1109/HiPC.2018.00019(92-101)Online publication date: Dec-2018
https://doi.org/10.1109/HiPC.2018.00019
Ma TYu SCao JTian YAl-Dhelaan AAl-Rodhaan M(2018)A Comparative Study of Subgraph Matching Isomorphic Methods in Social NetworksIEEE Access10.1109/ACCESS.2018.28752626(66621-66631)Online publication date: 2018
https://doi.org/10.1109/ACCESS.2018.2875262
Hung BJayasumana ABandara V(2017)INSiGHT: A system for detecting radicalization trajectories in large heterogeneous graphs2017 IEEE International Symposium on Technologies for Homeland Security (HST)10.1109/THS.2017.7943441(1-7)Online publication date: Apr-2017
https://doi.org/10.1109/THS.2017.7943441
Hung BJayasumana ASubrahmanian VRokne JKumar RCaverlee JTong H(2016)Investigative simulationProceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.5555/3192424.3192580(825-832)Online publication date: 18-Aug-2016
https://dl.acm.org/doi/10.5555/3192424.3192580
Hung BJayasumana ABandara V(2016)Detecting radicalization trajectories using graph pattern matching algorithms2016 IEEE Conference on Intelligence and Security Informatics (ISI)10.1109/ISI.2016.7745498(313-315)Online publication date: Sep-2016
https://doi.org/10.1109/ISI.2016.7745498
Hung BJayasumana ABandara V(2016)Pattern Matching Trajectories for Investigative Graph Searches2016 IEEE International Conference on Data Science and Advanced Analytics (DSAA)10.1109/DSAA.2016.14(71-79)Online publication date: Oct-2016
https://doi.org/10.1109/DSAA.2016.14
Hung BJayasumana A(2016)Investigative simulation: Towards utilizing graph pattern matching for investigative search2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)10.1109/ASONAM.2016.7752333(825-832)Online publication date: Aug-2016
https://doi.org/10.1109/ASONAM.2016.7752333

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents