How an Offline Map Knows Which Paris You Mean
The map is open on Warsaw, and someone types Eiffel Tower Paris France. GLMap search starts from the map center:
it opens the detailed maps around it and puts the nearest results first. The Eiffel Tower is 1,370 km away, in a
map file that such a search never opens.
This is what the engine does with that query now, and with the other queries from this post. Each word is coloured by the role the engine gives it:
Words with an orange border are places the engine looks up before the search itself, and a dashed border marks a place name that belongs to the name of something else. The dot marked “map center” is where the map is open, and the circle is the area where the detailed maps are searched.
The map center
For the map center is the right place to start: the cafe
around the corner should come before one in Paris. But people use the same search box to plan a trip, to paste an
address from a message or to find a hotel in another city. The Ritz London United Kingdom says where to look,
and a search that stays near Warsaw ignores half of the query.
The other easy option is to search everywhere. An offline app may have hundreds of downloaded regional maps, and
autocomplete runs on every keystroke, so every keystroke would read from all of them. And someone who types
hotel wants hotels nearby, not the best match on the planet.
So before searching, the engine has to decide which maps to open, and for that it has to know which words are the
place. In Eiffel Tower Paris France two words say what to find and two say where. In
, a business in Warsaw, Paris is part of the name.
The world map as a directory
Next to the detailed regional maps GLMap keeps a compact world map: countries, regions and important cities, without streets, addresses or cafes. We use it as a directory of places.
When a query has strong geographic context, the engine first looks up only that part of it, and only in the world map. Strong context is a city together with its country, a place written after a comma, or a postcode in an address. The application's category and custom object filters are not applied at this step: they describe the result the user wants, not the place where it is.
Once is resolved, the rest of the query,
Eiffel Tower, is searched in the detailed maps around Paris. The map center in Warsaw still takes part in ranking,
but it no longer decides which maps are opened. goes the same way. When the whole query is a place, as in
, the world-map result is the answer, and no detailed
map is opened at all.
The detailed search after this step is the ordinary one, with the same matcher, fallback ladder, scoring and display rules. Only the set of maps it receives has changed.
When a place name is part of a name
A rule that recognises city and country names easily becomes too eager, so we wrote down the cases where it must not fire together with the ones where it must.
Paris Optique typed in Warsaw has to stay a local search. A city name alone is not enough to move the search to
another country; it needs a country, a comma or a postcode next to it. hotel and bed and breakfast stay near
the map center. A request with a category filter does not enter the routing at all: with the cafe filter on,
Paris France has to return nothing, because the words are only matched against cafes near the map center.
There is one exception for a single word. When someone in Warsaw finishes typing
, the exact Wrocław from the world map is added to the
ordinary local results. An unfinished word stays a local prefix, and requests with a category or custom filter stay
local too. The plain l typed on a keyboard matches the Polish ł without any change to the map data.
Villages the world map does not have
The world map is incomplete on purpose, and small places are missing from it. is a village 40 km from Warsaw, searched here with the map centered on Sydney.
Searching every detailed map for it would turn one autocomplete keystroke into work across the whole planet. Instead, the engine resolves Poland in the world map and searches a limited number of detailed maps inside it. The budget is fixed: if no plausible place turns up within it, the search stops.
Global text search without geographic context has a filter of its own. Each detailed map has a Bloom filter of its
words, and maps whose words cannot match the query are skipped without opening them. That filter tells the engine
whether a map can contain the words of London United Kingdom. It does not tell it that London is where the user
wants to look.
Eight results and eight candidates
One failure showed up only after the routing worked. Production requests return at most 30 search results and 8 autocomplete suggestions, and at first those limits also capped how many candidates parts of the engine collected. Some candidates are rejected later: context validation drops the ones outside the resolved place, and autocomplete drops the ones whose visible label does not contain the typed words. When rejected candidates took places in that small pool, a valid result just below them was never collected.
Here is the same thing in miniature, with four visible results instead of eight:
- 1valid
- 2rejected: outside the named place
- 3valid
- 4rejected: typed words not in its label
- 5rejected: outside the named place
- 6valid
- 7rejected: typed words not in its label
- 8rejected: outside the named place
- 9valid
- 10valid
- 11rejected: outside the named place
- 12valid
- 1candidate 1
- 2candidate 3
- 3missing
- 4missing
With the pool as large as the visible list, two of the four places stay empty, though valid candidates exist further down. fills them. The engine now collects a larger internal pool, merges and ranks it, and cuts it down to 30 or 8 only when it returns the results.
One engine
The same C++ search code runs on iOS, Android and our search server; online and offline requests differ only in where the map data is stored. Offline search reads the same memory-mapped map file the renderer draws from. The word index, the tags, the administrative relations and the objects on the map are one file, so a downloaded map can be searched as soon as it is on the device, without a separate search database to build.
Much of what search needs is prepared when the maps are built. Prominence is stored in the map, so an important city beats an obscure namesake without a request to Wikipedia, and localized street names are joined to addressed buildings. Synonyms and a fallback ladder handle abbreviations and incomplete pasted addresses. The routing does not change any of them; it changes which maps they run on.
The corpus
Every search change is checked against a corpus of real queries, each with the results it must return. As of October it has 307 cases: cities and POIs, names in many languages, complete addresses, autocomplete keystroke by keystroke, category searches, distant places and queries that must stay local. 297 pass. The other 10 are marked as known failures, each with the data or engine gap behind it, and if one of them starts passing, the run fails until we look at it and reclassify it.
These are the 30 geographic cases:
| Query | Center | Request | Must return |
|---|---|---|---|
| Paris France | Warsaw | search | Paris |
| Wroclaw | Warsaw | search | Wrocław |
| Wroclaw | Warsaw | autocomplete | Wrocław |
| Wroclaw Poland | Warsaw | search | Wrocław |
| Wroclaw Poland | Warsaw | autocomplete | Wrocław |
| Paris, France | Warsaw | search | Paris |
| Paris France | Warsaw | autocomplete | Paris |
| Paris, France | Warsaw | autocomplete | Paris |
| Paris France | Sydney | search | Paris |
| Paris France | Sydney | autocomplete | Paris |
| Berlin Germany | Singapore | search | Berlin |
| Berlin Germany | Warsaw | autocomplete | Berlin |
| London United Kingdom | Tokyo | search | London |
| London United Kingdom | Warsaw | autocomplete | London |
| Парыж Францыя | Warsaw | search | Paris, Парыж |
| Парыж Францыя | Warsaw | autocomplete | Paris, Парыж |
| Mochty-Smok Poland | Sydney | search | Mochty-Smok |
| Mochty-Smok Poland | Sydney | autocomplete | Mochty-Smok |
| Eiffel Tower Paris France | Warsaw | search | Eiffel |
| Eiffel Tower Paris France | Warsaw | autocomplete | Tour Eiffel |
| The Ritz London United Kingdom | Warsaw | search | The Ritz London |
| The Ritz London United Kingdom | Warsaw | autocomplete | The Ritz London |
| Baker Street London United Kingdom | Warsaw | search | Baker Street |
| Baker Street London United Kingdom | Warsaw | autocomplete | Baker Street |
| 221B Baker Street London United Kingdom | Warsaw | search | 221B Baker Street, Sherlock Holmes Museum |
| 221B Baker Street London United Kingdom | Warsaw | autocomplete | 221B Baker Street, Sherlock Holmes Museum |
| Paris Optique | Warsaw | search | Paris Optique |
| Paris Optique | Warsaw | autocomplete | Paris Optique |
| Paris France | Warsaw | search | nothing, with the cafe category filter |
| Paris France | Warsaw | autocomplete | nothing, with the cafe category filter |
Most queries are there twice, as a search and as autocomplete. Autocomplete sees an unfinished last word and returns a short list, and a plan that works for search often breaks there first.
On the full corpus in August the engine took 130 ms at the median and 758 ms at the 95th percentile on our test host. A city with its country resolves in 4 to 14 ms, and the village cases take about 22 ms. Complete addresses in autocomplete are the slowest. The corpus records the time of every case, so a slow fallback cannot hide behind a correct result.
To try the engine in your app, create an API key. For offline or custom deployments, write to [email protected].