A systematic survey of point set distance measures for link discovery

Article type: Research Article

Authors: Ahmed Sherif, Mohamed^{; *} | Ngonga Ngomo, Axel-Cyrille

Affiliations: Data Science Group, Paderborn University, Pohlweg 51, D-33098 Paderborn, Germany. E-mails: mohamed.sherif@uni-paderborn.de, axel.ngonga@uni-paderborn.de

Correspondence: [*] Corresponding author. E-mail: mohamed.sherif@uni-paderborn.de.

Abstract: Large amounts of geo-spatial information have been made available with the growth of the Web of Data. While discovering links between resources on the Web of Data has been shown to be a demanding task, discovering links between geo-spatial resources proves to be even more challenging. This is partly due to the resources being described by the means of vector geometry. Especially, discrepancies in granularity and error measurements across data sets render the selection of appropriate distance measures for geo-spatial resources difficult. In this paper, we survey existing literature for point-set measures that can be used to measure the similarity of vector geometries. We then present and evaluate the ten measures that we derived from literature. We evaluate these measures with respect to their time-efficiency and their robustness against discrepancies in measurement and in granularity. To this end, we use samples of real data sets of different granularity as input for our evaluation framework. The results obtained on three different data sets suggest that most distance approaches can be led to scale. Moreover, while some distance measures are significantly slower than other measures, distance measure based on means, surjections and sums of minimal distances are robust against the different types of discrepancies.

Keywords: Link discovery, geographic distances

DOI: 10.3233/SW-170285

Journal: Semantic Web, vol. 9, no. 5, pp. 589-604, 2018