Deduplicating POIs from Multiple Providers

Two feeds describe the same café forty metres apart with names that differ by a suffix, and a third has it at the right coordinate under its former owner’s name. Deciding whether those are one place or three is the whole of POI deduplication, and neither extreme is safe: merging too eagerly collapses a shopping centre’s twelve units into one, and merging too cautiously leaves a map showing three cafés on one corner. What makes it tractable is that the decision does not have to be binary — a scored match with a review band, and a merge that keeps its sources, turns an irreversible guess into an auditable one.

Prerequisites & Versions

Candidate search uses the point index; scoring is client-side.

Requirement Minimum version Install
Python 3.11 —
neo4j (async driver) 5.20 pip install "neo4j>=5.20"
Neo4j Server 5.15 native point, POINT INDEX
rapidfuzz 3.9 pip install "rapidfuzz>=3.9"

Implementation

import math
import re
from dataclasses import dataclass

from rapidfuzz import fuzz

EARTH_R = 6_371_008.8

# Suffixes that carry no identity. Stripping them before comparison stops
# "Blue Door Cafe" and "Blue Door Cafe Ltd" scoring as different places.
NOISE = re.compile(
    r"\b(ltd|limited|plc|inc|llc|gmbh|the|co|company|store|shop|branch)\b|[^\w\s]",
    re.IGNORECASE,
)


@dataclass(frozen=True)
class Poi:
    id: str
    provider: str
    name: str
    lat: float
    lon: float
    category: str | None = None
    phone: str | None = None


@dataclass(frozen=True)
class Match:
    a: Poi
    b: Poi
    score: float
    distance_m: float

    @property
    def verdict(self) -> str:
        # Three bands rather than two. The middle one is the point: a system
        # that must decide every pair will decide the ambiguous ones badly.
        if self.score >= 0.85:
            return "merge"
        if self.score >= 0.60:
            return "review"
        return "distinct"


def normalise(name: str) -> str:
    return " ".join(NOISE.sub(" ", name).lower().split())


def haversine_m(a: Poi, b: Poi) -> float:
    p1, p2 = math.radians(a.lat), math.radians(b.lat)
    dp, dl = p2 - p1, math.radians(b.lon - a.lon)
    h = math.sin(dp / 2) ** 2 + math.cos(p1) * math.cos(p2) * math.sin(dl / 2) ** 2
    return 2 * EARTH_R * math.asin(math.sqrt(h))


def score(a: Poi, b: Poi, tolerance_m: float = 60.0) -> Match:
    """Weighted agreement across the signals, each contributing independently.

    Distance alone is not enough — a shopping centre packs dozens of distinct
    businesses inside the tolerance. Name alone is not enough either, because
    chains repeat the same name across a city. The combination is what
    discriminates, which is why this is a weighted sum rather than a cascade
    of thresholds.
    """
    d = haversine_m(a, b)

    # Decays to zero at the tolerance rather than stepping, so a pair at 59 m
    # and one at 61 m are not treated as categorically different.
    proximity = max(0.0, 1.0 - d / tolerance_m)
    name = fuzz.token_sort_ratio(normalise(a.name), normalise(b.name)) / 100.0

    weights = {"proximity": 0.45, "name": 0.40}
    total = proximity * 0.45 + name * 0.40

    # Corroborating signals only add; their absence never penalises, because
    # most feeds carry them sparsely and a missing phone is not evidence of
    # difference.
    if a.phone and b.phone and _digits(a.phone) == _digits(b.phone):
        total += 0.15
    elif a.category and b.category and a.category == b.category:
        total += 0.05

    return Match(a=a, b=b, score=min(total, 1.0), distance_m=d)


def _digits(phone: str) -> str:
    return re.sub(r"\D", "", phone)[-9:]


# Blocking: only pairs within the tolerance are ever scored. Without this the
# comparison is quadratic in the feed size and unusable past a few thousand rows.
CANDIDATES = """
MATCH (p:Poi)
WHERE p.provider <> $provider
  AND p.location.latitude  >= $min_lat AND p.location.latitude  <= $max_lat
  AND p.location.longitude >= $min_lon AND p.location.longitude <= $max_lon
RETURN p.id AS id, p.provider AS provider, p.name AS name,
       p.location.latitude AS lat, p.location.longitude AS lon,
       p.category AS category, p.phone AS phone
"""

# The merge keeps its inputs. A canonical node links to every source record, so
# a wrong match is undone by deleting one relationship rather than by trying to
# reconstruct data that was overwritten.
MERGE_INTO_CANONICAL = """
MERGE (c:Place {canonical_id: $canonical_id})
  ON CREATE SET c.location = point({latitude: $lat, longitude: $lon}),
                c.name = $name, c.created_at = datetime()
WITH c
UNWIND $source_ids AS sid
MATCH (p:Poi {id: sid})
MERGE (p)-[r:SAME_AS]->(c)
  ON CREATE SET r.score = $score, r.matched_at = datetime(), r.method = 'auto'
RETURN count(r) AS linked
"""

How It Works

Blocking makes the problem linear. Comparing every POI against every other is quadratic and impossible past a few thousand records; restricting candidates to those within the tolerance turns it into a bounded index seek per record. The block is the same latitude-corrected box a radius query uses, and the tolerance doubles as both the block radius and the proximity denominator.

No single signal discriminates, which is why the score is a weighted sum. Distance fails inside a shopping centre where dozens of distinct businesses sit within metres of each other. Name fails on chains, where a dozen genuinely different branches share a name across a city. Together they separate cleanly: same name and same place is a strong signal that neither provides alone. Corroborating signals like a matching phone number add confidence without being required, because feeds carry them inconsistently and a missing field is not evidence of difference.

Three bands, not two. The middle band is the design decision that makes this safe to run automatically. A system forced to decide every pair will decide the genuinely ambiguous ones arbitrarily; routing them to review means the automatic merges are the confident ones and a human sees exactly the cases where the evidence is mixed. On real feeds that band is small — typically a few per cent of pairs — which is what makes reviewing it affordable.

Why neither distance nor name discriminates alone Three pairs of records plotted against name similarity and separation distance. Twelve units inside one shopping centre are all within twenty metres of each other and have completely different names — close but distinct. Two branches of a coffee chain across the same city have identical names and are four kilometres apart — same name but distinct. The same café listed by two providers is thirty metres apart with names differing only by a company suffix — the only pair that scores highly on both axes, and the only one that should merge. A threshold on either axis alone would misclassify two of the three. Name similarity against separation 100%50%0% name match 0 m60 m500 m5 km separation merge band same café, two providers — 30 m, names differ by "Ltd" 12 units in one shopping centre — close, unrelated names two branches of a chain — identical name, 4 km apart A distance threshold alone merges the shopping centre; a name threshold alone merges the chain. Only the corner does both.

Common Failure Patterns

1. Merging destructively. Overwriting one record with another loses the evidence that would let a wrong match be undone, and wrong matches are inevitable at any threshold. Linking sources to a canonical node with SAME_AS keeps every original intact, so reversing a merge is deleting a relationship rather than restoring from a backup.

2. Letting a missing field count against a pair. A provider that does not publish phone numbers would otherwise score systematically lower against every other feed, purely because of what it omits. Corroborating signals should only ever add — absence is not evidence.

3. Applying one tolerance everywhere. Sixty metres is generous in a dense high street and tight in a retail park where the same store’s two records sit either side of a car park. Deriving the tolerance from local POI density, or simply from the category, keeps the same score meaningful in both.

# Density-aware tolerance: tighter where places are packed together.
def tolerance_for(local_poi_count: int, area_km2: float) -> float:
    density = local_poi_count / max(area_km2, 0.01)
    return 30.0 if density > 400 else 60.0 if density > 80 else 120.0

Performance Notes

Blocking is what makes the cost tractable, and the arithmetic is worth stating because it is the difference between a job that runs and one that does not:

$$C_{\text{naive}} = O(n^2), \qquad C_{\text{blocked}} \approx n \cdot (\log n + \bar{k})$$

with $\bar{k}$ the mean candidate count inside the tolerance — typically under ten even in dense areas. On a million-record feed, the naive comparison is 5 × 10¹¹ pairs and the blocked one is about 10⁷ scored comparisons, which is minutes rather than never.

The string comparison is then the inner-loop cost, and normalising once rather than per comparison matters more than the choice of algorithm: each record’s normalised name should be computed when it is loaded and stored, not recomputed for every candidate pair it participates in. That single change is usually worth more than swapping the similarity function.

Deduplication is also a natural fit for incremental work. Most of a feed is unchanged between refreshes, so re-scoring everything is waste — matching only records whose name or coordinate moved, plus their neighbours, reduces a full pass to a few per cent. That requires the same content-hash discipline that makes an incremental re-import affordable, and it pays off twice for the same bookkeeping.

Pairs scored, with and without spatial blocking Scored comparisons against feed size. Without blocking, every record is compared with every other, so the count grows with the square of the feed and reaches five hundred billion pairs at a million records. With blocking, only records inside the tolerance of each other are ever compared, so the count grows close to linearly and reaches about ten million at the same feed size. The answers are identical, because every pair the blocked version skips is further apart than the tolerance and would have scored below the distinct threshold anyway. Pairs actually scored, by feed size 10¹²10⁹10⁶10³ 1k10k100k1M10M records in the feed all pairs — 5 × 10¹¹ at 1M blocked — 10⁷ at 1M Identical output: every pair the blocked version skips is beyond the tolerance and would have scored as distinct regardless.

One further property makes the canonical model worth the extra node. Because every source record survives and links to the place rather than being folded into it, provenance is queryable: which providers assert this place exists, when each last confirmed it, and which of them supplied the coordinate currently in use. That turns a class of downstream question from guesswork into a lookup — a place asserted by three feeds and confirmed last week is a different proposition from one asserted by a single feed two years ago, and a consumer choosing which POIs to show can act on that distinction without knowing anything about how the matching worked.

It also gives the review band somewhere to live. A pair in the middle band can be recorded as a candidate link with its score and left unmerged, so the reviewer’s queue is a query rather than a separate system, and a decision writes the same SAME_AS relationship the automatic path writes with its method set to manual. Keeping both paths in one shape means the confidence distribution of the whole dataset stays inspectable, which is the thing you want when someone asks how trustworthy the deduplication actually is.

This guide is part of POI Enrichment Workflows, within Spatial Graph Construction & OSM Ingestion.

Siblings