.png){kind=icon}
返回
TC-Match: Fast Time-Constrained Continuous Subgraph Matching
.png){kind=icon}
PRE
AI
DOI：10.14778/3681954.3681963.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
对流图中结构模式的持续监控是许多实时图应用中的一个关键任务。本文研究了流图上时间约束的连续子图匹配问题（简称TCSM）。给定一个具有时序约束的查询图Q和一个数据图流G，TCSM旨在针对G的每次更新，报告Q在G中的所有增量匹配，其中匹配需同时满足Q的结构约束（即同构）和时序约束。尽管TCSM在如网络攻击检测和信用卡欺诈检测等领域有广泛应用，但该问题尚未得到充分解决。现有方法存在索引空间成本高和中间结果维护成本高等局限性。本文提出TC-Match，一种解决TCSM的有效方法。首先，我们设计了一种空间和时间高效索引CSS，其本质上是一个k-部图结构，其中每个节点对应G中的一条边。通过精心创建节点间的连接，我们可以将G中边之间的部分嵌入和时序信息封装到CSS中。我们从理论上证明CSS具有多项式空间和构造时间复杂度。其次，基于CSS的性质，我们开发了一种高效的增量匹配算法，并引入了有效的节点合并优化。大量实验表明，TC-Match相比基线方法可提升高达3个数量级的查询性能，同时内存消耗降低48.7%-86.7%。
Keyword:
QUERY OPTIMIZATION
EFFICIENT
ALGORITHM
GRAPH
ORDER
期刊
P
IF:
3.3
论文数:
563
被引数:
1.2W
机构
引用论文
Hasse diagram based algorithm for continuous temporal subgraph query in graph stream基于Hasse图的图流连续时间子图查询算法
PREAI
分享收藏
A Hybrid Approach to Temporal Pattern Matching一种时空模式匹配的混合方法.png)
2020 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)
OAAI
2020 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)IF0
OAAI分享收藏
查看更多内容