Efficient Continuous Subgraph Matching Scheme Based on Trie Indexing for Graph Stream Processing

With the expansion of the application range of big data and artificial intelligence technologies, graph data have been increasingly used to analyze the relationships among objects. With the advancement of network technology and the spread of social network services, there has been an increasing need...

Full description

Saved in:
Bibliographic Details
Published in:Applied sciences 2023-04, Vol.13 (8), p.5137
Main Authors: Choi, Dojin, Lee, Somin, Kim, Sanghyeuk, Lee, Hyeonbyeong, Lim, Jongtae, Bok, Kyoungsoo, Yoo, Jaesoo
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Artificial intelligence
continuous query processing
Distributed processing
Graph matching
graph stream
Graph theory
Graphs
Indexing
materialized view
Queries
Real time
Social network analysis
Social networks
Social organization
Statistical analysis
stream processing
Streams
subgraph matching
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:With the expansion of the application range of big data and artificial intelligence technologies, graph data have been increasingly used to analyze the relationships among objects. With the advancement of network technology and the spread of social network services, there has been an increasing need for a continuous query processing algorithm that can manage large-volume graph streams generated in real time. In this paper, a sliding-window-based continuous subgraph matching algorithm that can efficiently control graph streams is proposed. The proposed scheme uses a query processing technique based on trie indexing. It establishes an index based on a materialized view of similar queries and conducts continuous query processing based on the materialized view to perform continuous query processing efficiently. It also provides wildcard operations on vertices and edges to consider various query types. Moreover, in this study, a two-level cache technique that can manage frequently used subgraphs and subgraphs that may be used in the future is developed, to handle intermediate query results in the form of a materialized view. Cache replacement techniques based on statistical data are also presented to improve the performance of the developed cache technique. The excellent performance of the proposed algorithm is verified by a conducting independent performance evaluation and comparative performance evaluation.
ISSN:2076-3417
2076-3417
DOI:10.3390/app13085137