| 摘要: |
| 在确定图上进行的相似性连接已有许多研究成果.然而，在实际应用中会有许多因素使得图结构数据变得不确定.研究了不确定图数据库上的相似性连接问题.采用联合概率分布表示法来描述图中边的不确定性，结合一种新的图的相似性度量方法，给出了不确定图数据库上的相似性连接的形式化定义，并设计了一组过滤策略来减少连接过程中候选图对的数量.大量的实验数据表明，所提出的方法具有较好的可行性和准确性. |
| 关键词: 不确定图 联合概率分布 相似性连接 过滤策略 |
| DOI：10.13328/j.cnki.jos.005286 |
| 分类号: |
| 基金项目:国家科技支撑计划（2015BAH10F00）；国家自然科学基金（61472099，61133002）；福建省自然科学基金（2018J01555）；福建省教育厅中青年项目（JAT170653）；宁德师范学院校级青年专项基金（2014Q51） |
|
| Method for Similarity Join on Uncertain Graph Database |
|
MIAO Feng-Yu1, WANG Hong-Zhi2
|
|
1.College of Information & Mechanical and Electrical Engineering, Ningde Normal University, Ningde 352100, China;2.School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China
|
| Abstract: |
| Many studies have been conducted on similarity join over certain (deterministic) graphs. However, in reality, graphs are often uncertain due to various factors. This paper studies similarity join on uncertain graph databases. The study employs the joint probability distribution to describe the uncertainty of edges in the graph, combines a new measure to evaluate graph similarity, and gives the formal definition of the similarity join on uncertain graph database. The paper also designs a group of filtering strategies to reduce the candidate pairs in the similarity join. A large number of experimental data show that, the method proposed in the paper is feasible and accurate. |
| Key words: uncertain graph joint probability distribution similarity join filtering strategy |
