%0 Journal Article
%T 分布式Top-k子图匹配技术<br>Distributed Top-k subgraph matching
%A 兰超
%A 张勇
%A 邢春晓
%J 清华大学学报（自然科学版）
%D 2016
%R 10.16511/j.cnki.qhdxxb.2016.25.026
%X Top-k子图匹配是一种应用广泛的图搜索技术。相比于单机环境，分布式环境下的Top-k子图匹配问题具有更大的挑战性。该文分析了已有方法在分布式环境下存在的问题，提出了包括查询拆分、查询执行、结果连接3个步骤的算法。算法通过查询拆分，彻底避免了生成中间结果过程中的数据传输，同时通过优化查询执行和结果连接步骤，避免不必要的中间结果生成，降低单个节点的计算量，提升整体效率。在此基础上，该文对分布式环境下Top-k连接策略进行了进一步优化。在真实图数据上进行的实验测试表明：该文提出的算法能够有效解决分布式环境下Top-k子图匹配问题，具有很好的扩展性，而且使用优化连接策略的算法性能较基础算法的效率有明显的提升。<br>Abstract：Top-k subgraph matching is a key operation in graph queries which is widely used in all kinds of applications such as social networks and knowledge graphs. Top-k subgraph matching is more challenging in distributed environments since it involves data and task transfers. Thus, existing local Top-k subgraph matching methods do not work well in distributed environments. An algorithm was developed to address this issue by dividing the problem into query decomposition, query execution, and ranked join stages. The query decomposition avoids unnecessary data transfers during the querying stage. The ranked join technique avoids generating unnecessary temporal results that reduces the overall latency of the algorithm. The algorithm effectiveness and efficiency were tested using real data and the results indicate that the algorithm, especially the optimized version, effectively solves the distributed Top-k subgraph matching problem.
%K 图搜索
%K 子图匹配
%K Top-k子图匹配
%K 分布式
%K &lt
%K br&gt
%K graph search
%K subgraph matching
%K Top-k subgraph matching
%K distributed systems
%U http://jst.tsinghuajournals.com/CN/Y2016/V56/I8/871