A System for Aligning Geographical Entities from Large Heterogeneous Sources

André Melo, Btissam Er-Rahmadi, Jeff Z. PanISPRS Int. J. Geo Inf 2022 · DOI

TL;DR

This paper introduces GLEAN, a scalable system for aligning geographical entities (like points of interest) from diverse, large-scale datasets. It tackles challenges like differing data formats, languages, and hierarchical structures by combining sophisticated text similarity with spatial partitioning and an unsupervised type embedding approach, significantly improving alignment quality and efficiency.

What Problem Does This Paper Address?

Geographical information systems (GIS) and mapping services rely on vast amounts of data, often sourced from various providers. A crucial task is aligning geographical entities – determining if different entries across datasets refer to the same real-world place (e.g., a specific restaurant or landmark). This is challenging because datasets often have:

  • Inconsistent data: Different naming conventions, languages, levels of detail in labels and addresses.
  • Varying type hierarchies: Categories for places can be structured very differently, making direct comparison difficult.
  • Coordinate inaccuracies: Location data might have different precision or even be missing.
  • Massive scale: Datasets can contain tens or hundreds of millions of entities, making brute-force comparison computationally infeasible.

Existing methods often struggle with these issues, particularly with scalability and handling multilingual data or complex type systems. This paper aims to bridge this gap by providing a robust and efficient system for aligning large, heterogeneous geographical datasets.

Methods

GLEAN employs a multi-faceted approach to tackle the alignment problem:

  • Spatial Partitioning with Adaptable Margins: To handle large datasets, GLEAN divides the geographical space into partitions. An "adaptable margin" is introduced around each partition to ensure that entities that are close but fall into adjacent partitions are still considered for matching, mitigating issues with large or sparse regions.
  • Sophisticated Label Similarity:
    • Local Context Token Relevance (LIDF): This novel approach measures how relevant a word (token) is within a specific geographical context. For example, "Edinburgh" might be highly relevant for a specific landmark in London but less so for another landmark within Edinburgh itself. This is quantified using an inverse document frequency (IDF) approach.
  • Multilingual Sentence Encoders (MUSE): Pre-trained models are used to generate embeddings for labels, enabling cross-lingual similarity comparisons.
  • Combined Label Score: The final label similarity is the maximum of the LIDF-based similarity and the sentence encoder-based similarity, leveraging both local context and semantic understanding.
  • Unsupervised Type Embeddings: Instead of relying on manually crafted mappings between type hierarchies (which are often complex and inconsistent), GLEAN learns type embeddings. This allows for computing nuanced similarity scores between types, even when their names or structures differ significantly. High-confidence alignments from a preliminary run are used to generate training data for this unsupervised model.
  • Type Demotion: To address potential false positives arising from similar labels or coordinates, a type demotion mechanism is introduced. This mechanism reduces the alignment score for pairs where types are known to be disjoint, even if other attributes suggest a match.
  • Address Similarity: A local IDF-weighted Jaccard similarity is used for addresses, similar to the label similarity, to account for the varying relevance of address components.
  • Geographical Distance Component: This component transforms real-world distances into a similarity score, adapting to the "type" of entity (e.g., a 1km distance is more significant for restaurants than for cities). It uses bounding box information where available, or estimates it based on entity type.
  • Post-processing Rules: A set of rules are applied to refine alignment scores, addressing edge cases and improving precision and recall.

Datasets

The paper uses two primary datasets for its experiments:

  • HuaweiPD: A privately owned dataset from Huawei.
  • Wikidata: A large, open-source knowledge base.

The paper notes that Wikidata entities often lack direct address information, requiring it to be constructed from relations. For the Wikidata-HuaweiPD alignment experiments, the address component was omitted due to the low quality of constructed addresses. A manually annotated gold standard of 1942 Wikidata entities with corresponding HuaweiPD matches was created for evaluation.

Key Insights and Ideas

  • Local Context is Crucial for Labels: The "Synagogue" example vividly illustrates that the relevance of a word depends heavily on its geographical context. This insight drives the LIDF approach, which significantly improves label matching.
  • Unsupervised Type Embeddings are Powerful: The ability to learn type similarities without manual mapping is a significant advantage, especially given the complexity and scale of real-world type hierarchies. This allows GLEAN to find matches even when type labels are very different.
  • Type Demotion Prevents False Positives: The type demotion mechanism is key to preventing misalignments when entities share similar labels or coordinates but are fundamentally different types (e.g., a "Bus Stop" and a "Street").
  • Scalability Through Partitioning and Early Pruning: The combination of spatial partitioning and using inexpensive embedding similarities (label and type) to pre-filter candidates is essential for making the alignment process efficient on massive datasets.

Key Results

  • High Alignment Quality: The full GLEAN system achieved an F1-score of 0.913, with high precision (0.973) and accuracy (0.953).
  • Impact of Components:
    • Removing the multilingual sentence encoder (MLSE) resulted in the lowest F1-score (0.792), highlighting its importance for recall.
  • The LIDF component significantly improved recall when combined with MLSE.
  • Type embeddings and type demotion together substantially improved both precision and recall.
  • Scalability: The partition-based approach, combined with parameter tuning (e.g., rerank k, partition margin), enables GLEAN to handle large-scale datasets efficiently. The system processed over 400,000 partitions and generated nearly 4 million alignments in about 23 hours on a 72-core machine.
  • Example Alignments: The paper showcases examples where GLEAN successfully aligns entities with different labels and types, demonstrating the effectiveness of its sophisticated components. It also shows cases where it correctly identifies non-matches despite superficial similarities.

Limitations and Future Work

  • Recall vs. Runtime Trade-off: The paper acknowledges that achieving high scalability often comes at the cost of some recall, meaning a small number of true matches might be missed. However, they argue this trade-off is attractive.
  • Address Component Dependency: The address similarity component relies on entities having coordinates to define a geographical context.
  • Future Work:
    • Integrating local context token relevance into transformer networks for text encoding, allowing attention to coordinates.
  • Exploring unsupervised or weakly supervised learning for embedding geographical entities, aiming to encode all attributes without extensive labeled data.

Summary updated

BibTeX
@article{melo2022system,
  author = {André Melo and Btissam Er-Rahmadi and Jeff Z. Pan},
  title = {{A System for Aligning Geographical Entities from Large Heterogeneous Sources}},
  journal = {ISPRS Int. J. Geo Inf.},
  year = {2022},
  doi = {10.3390/ijgi11020096},
}
Figure