Multi-Source Spatial Entity Linkage

Suela Isaj, Torben Bach Pedersen, Esteban Zimányi

Abstract

Besides the traditional cartographic data sources, spatial information can also be derived from location-based sources. However, even though different location-based sources refer to the same physical world, each one has only partial coverage of the spatial entities, describe them with different attributes, and sometimes provide contradicting information. Hence, we introduce the spatial entity linkage problem, which finds which pairs of spatial entities belong to the same physical spatial entity. Our proposed solution ( <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">QuadSky</i> ) starts with a time-efficient spatial blocking technique ( <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">QuadFlex</i> ), compares pairwise the spatial entities in the same block, ranks the pairs using Pareto optimality with the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SkyRank</i> algorithm, and finally, classifies the pairs with our novel <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SkyEx-*</i> family of algorithms that yield 0.85 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">precision</i> and 0.85 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">recall</i> for a manually labeled dataset of 1,500 pairs and 0.87 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">precision</i> and 0.6 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">recall</i> for a semi-manually labeled dataset of 777,452 pairs. Moreover, we provide a theoretical guarantee and formalize the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SkyEx-FES</i> algorithm that explores only 27 percent of the skylines without any loss in <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">F-measure</i> . Furthermore, our fully unsupervised algorithm <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SkyEx-D</i> approximates the optimal result with an <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">F-measure</i> loss of just 0.01. Finally, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">QuadSky</i> provides the best trade-off between <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">precision</i> and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">recall</i> , and the best <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">F-measure</i> compared to the existing baselines and clustering techniques, and approximates the results of supervised learning solutions.
BibTeX
@inproceedings{isaj2019multi,
  author = {Suela Isaj and Torben Bach Pedersen and Esteban Zimányi},
  title = {{Multi-Source Spatial Entity Linkage}},
  booktitle = {SSTD},
  year = {2019},
  doi = {10.1145/3340964.3340979},
}

Loading related content...

Figure