论文导读 | 连续图上的子图匹配(Continuous Subgraph Matching)_百度知 ...
发布网友
共1个回答
热心网友
论文摘要：连续图上的子图匹配算法概述
连续子图匹配（Continuous Subgraph Matching, CSM）算法是一种实时检测给定模式在不断变化的数据图流中出现实例的技术。在数据图流中，数据图会发生连续的增删操作。本文主要介绍针对这类问题的处理策略和优化方向。
CSM的核心是寻找一个映射规则，将查询图上的节点与数据图对应，同时满足标签和边的关系。优化策略包括设计剪枝策略，优化节点枚举顺序，以及利用辅助数据结构减少重复计算。对于连续图，关注的是在边的增删操作后，找出包含这些变化的匹配实例。
现有的研究工作主要分为两类：一类不维护索引，如IncIsoMatch、Graphflow和RapidFlow，每次更新重新计算；另一类则是通过设计特殊辅助结构加速，如SJ-Tree、TurboFlux、IEDyn和SymBi。例如，Graphflow采用最优情况下的连接执行顺序以减少中间结果，而Binary join则在每次添加或合并边时进行匹配。
TurboFlux和IDEyn通过维护辅助数据结构来判断数据点与查询点匹配时是否存在匹配子结构，以实现剪枝。SymBi则利用非树边信息构建有向无环图，通过Dynamic candidate space (DCS)结构进行更精确的剪枝。
后续研究发现，优化匹配顺序和处理自同构结构是关键。RapidFlow通过两层索引结构，全局和局部索引，减少重复搜索和自同构结构的枚举。
总结来说，连续图上的子图匹配涉及在线处理复杂数据流，通过多种策略和技术优化搜索效率和剪枝效果，以实现实时和高效地检测模式在流式图中的变化。
