Radius-aware approximate blank node matching using signatures
详细信息 查看全文
- 作者：Christina Lantzaki ; Panagiotis Papadakos…
- 关键词：RDF ; Blank node matching ; Delta minimization ; Equivalence ; Isomorphism
- 刊名：Knowledge and Information Systems
- 出版年：2017
- 出版时间：February 2017
- 年：2017
- 卷：50
- 期：2
- 页码：505-542
- 全文大小：
- 刊物类别：Computer Science
- 刊物主题：Information Systems and Communication Service; IT in Business;
- 出版者：Springer London
- ISSN：0219-3116
- 卷排序：50
文摘
In the linked open data cloud, the biggest open data graph that currently exists, a remarkable percentage of data are unnamed resources, also called blank nodes. Several fundamental tasks, such as graph isomorphism checking and RDF data versioning, require computing a map between the sets of blank nodes of two graphs. This map aims at minimizing the delta size, i.e. the number of change operations that are required to make the graphs isomorphic. Computing the optimal map is NP-Hard in the general case, and various approximation algorithms have been proposed. In this work, we propose a novel radius-aware signature-based algorithm that is not restricted to the direct neighborhood of the compared blank nodes. Contrary to the older algorithms, the proposed algorithm manages to decrease the deviation from the optimal solution even for graphs that contain connected blank nodes in large and dense structures. The conducted experiments over real and synthetically generated datasets (including datasets from the Billion Triple Challenge 2012 and 2014) show the significantly smaller deltas. For isomorphism checking (simple RDF equivalence), with a wise configuration of radius, the proposed algorithm achieves optimality for \(100\,\%\) of the datasets, while in non-isomorphic datasets the deltas are on average 50–75 % smaller than those of the previous algorithms. Finally, the trade-off between radius, deviation from the optimum and time efficiency is analyzed.