Detecting Duplicate Locations in a Points-of-Interest Dataset

Two records, 18 metres apart, called “Starbucks” and “Starbucks Coffee #4412”. Obviously the same shop. Now do that four million times, without merging the two genuinely different Starbucks in Terminal 2.

Why neither signal works alone

Distance alone fails because dense retail is dense. In a shopping centre or a high street, a dozen distinct businesses sit within 20 m of each other, and the coordinate precision in a merged dataset is often worse than that anyway — a rooftop point and a street-entrance point for the same building differ by 15 m legitimately.

Name alone fails because chains exist. There are thousands of records called “Starbucks” and they are nearly all different shops. A name match with no spatial constraint collapses an entire brand into one point.

The product of the two is what carries the signal: close and similarly named. That is a scoring problem, and the interesting design work is in the normalisation and in what you do with scores near the threshold.

Blocking: not comparing everything to everything

Four million records is 8 × 10¹² unordered pairs. You cannot score them. Blocking restricts comparison to candidate pairs that could plausibly match, and geography gives you a natural blocking key.

• Cell-based. Assign every record an H3 cell or a geohash prefix at a resolution whose cells are a bit larger than your maximum match distance, and compare only within a cell plus its immediate neighbours. The neighbour ring is not optional: two records 10 m apart either side of a cell boundary are in different cells, and forgetting the ring loses exactly the pairs that are hardest to notice missing.
• Index-based. Alternatively run a radius query per record against an R-tree or GiST index. Same result, no boundary problem, more query overhead.

Either way the pair count drops from quadratic in the dataset to roughly linear in it times the local density, which is what makes the rest of this tractable.

Normalising and scoring the name

Normalise before comparing, or the comparison is measuring formatting. Case-fold; strip punctuation and diacritics; remove legal suffixes (Ltd, GmbH, Inc, B.V.); remove branch identifiers such as store numbers and airport terminal codes into a separate field rather than deleting them, because you will want them later; and expand or drop the generic category word (“coffee”, “pharmacy”) that some sources append and others do not.

Then pick a similarity that survives one name being a superset of the other, because that is the dominant pattern here. Plain Jaccard over token sets punishes it hard: {starbucks} against {starbucks, coffee, 4412} scores 1/3. A token-set ratio, which compares the shared tokens against each side separately and takes the best, scores the same pair near 1.0. Jaro–Winkler is the other common choice and is deliberately biased toward matching prefixes, which suits business names where the brand comes first.

A worked pair

record A   "Starbucks"                 51.50740, -0.12780
record B   "Starbucks Coffee #4412"    51.50754, -0.12795

distance
  dLat = 0.00014 deg -> 15.6 m
  dLon = 0.00015 deg -> 0.00015 * 111320 * cos(51.5) = 10.4 m
  d    = sqrt(15.6^2 + 10.4^2) = 18.7 m

normalised names
  A -> "starbucks"
  B -> "starbucks coffee"   (branch id 4412 moved to its own field)

distance score, with d_max = 100 m
  s_d = 1 - (18.7 / 100) = 0.813

name score, token-set ratio                = 0.86

combined, weights 0.6 distance / 0.4 name
  s = 0.6 * 0.813 + 0.4 * 0.86 = 0.488 + 0.344 = 0.832

threshold 0.75  ->  DUPLICATE

The two dials are d_max and the threshold, and they should be set per place type rather than globally. A petrol station is a large object and two records for it can be 60 m apart; a market stall cannot. Setting one d_max for the whole dataset guarantees you are too loose somewhere and too tight elsewhere.

Two extra signals are worth adding before tuning the weights any further, because both are near-decisive when present: an exact match on a normalised phone number or website domain, and a category mismatch (a pharmacy and a hairdresser at the same coordinate are two tenants, not one record twice). Address strings help too, once put through the same normalisation treatment.

The transitivity trap

Pairwise scores are not an equivalence relation. A matches B, B matches C, and A does not match C — this happens constantly, because B sits between them in both space and name. If you resolve duplicates by taking connected components of the match graph, that chain merges A and C, and long chains along a high street can merge a dozen distinct businesses into one entity. Single-link clustering is exactly this failure, and it is why the naive implementation gets worse as the dataset grows denser.

The fixes are all about refusing to close the chain. Require the cluster to have a bounded diameter — every member within d_max of every other, not merely of one other — which is complete-link rather than single-link. Or run the components and then split any cluster whose spatial extent exceeds a cap. Or, when the decision matters commercially, send ambiguous components to human review: components of size 2 with a high score are safe to merge automatically, and components of size 8 almost never are.

The cases the threshold cannot decide

• Two real branches in one building. A large airport terminal genuinely contains two shops of the same chain 40 m apart. No distance-plus-name score separates them from a duplicate; only the branch identifier does, which is the reason to keep it in a field rather than strip it.
• The tenant changed. Two records at one address with different names may be a duplicate, or may be a closed business and its successor. Without a timestamp on each record this is undecidable, and merging them creates a POI that never existed.
• Nested places. A pharmacy counter inside a supermarket is a real POI at the supermarket’s coordinate. It is not a duplicate and it is not independent either; a containment relation models it and a merge destroys it.
• Multi-entrance venues. A station with four entrances legitimately has several coordinates under one name. Whether those are one POI or several depends on what the data is for — and if it is for delivery or navigation, keeping them apart is the point, as entrance snapping depends on exactly that.

The general shape of the answer: automate the confident middle, measure your false-merge rate on a hand-labelled sample rather than assuming it, and remember that a wrong merge is far harder to undo later than a missed one, because the losing record’s identifiers are gone.