Design Apple Maps Search Autocomplete

Problem Statement

Design the search autocomplete system for Apple Maps. As a user types a location query, return ranked suggestions (POIs, addresses, cities) within 80ms P99. Results must be biased toward the user's current region and personalised based on prior searches.

Requirements Clarification

Functional:

• Return top 5–8 location suggestions on every keystroke
• Rank by: proximity to current location, query frequency, personalisation score
• Support 195 countries and 40+ languages
• New businesses appear in autocomplete within 24 hours of being added to the POI database

Non-Functional:

• 5B queries/day (~58k QPS average, peaks to 300k QPS)
• P99 < 80ms globally (including network RTT from edge)

Index Structure

The autocomplete index is a prefix trie over location names with two additions:

Popularity score per node: normalised query frequency from the past 90 days, used for initial ranking within a prefix match.

Geographic bounding box per POI: used to boost results near the user's current GPS coordinates at re-ranking time.

The trie is pre-built offline (hourly Spark job), serialised to a compact binary format, and distributed to edge POPs globally. Edge nodes serve the trie in memory: lookup is O(k) where k is the query prefix length.

Two-Stage Serving

Stage 1: Edge node queries the local trie replica for the typed prefix. Returns top 20 raw candidates based on popularity score alone.

Stage 2: Re-ranking pass applies proximity boost (haversine distance from device GPS), personalisation score, and freshness penalty (demote POIs with recent closures). Returns top 8 to the client.

This two-stage design keeps the trie simple and fast while allowing contextual re-ranking without a round-trip to a central server.

Personalisation Without Raw Query Logging

User query history is stored locally on-device. At query time, the device sends an anonymous feature vector (not raw history) to the re-ranking layer. The vector encodes recency-weighted category preferences (coffee shops, gyms, airports) without identifying specific past searches.