Come Mapsake ha creato la sua geolocalizzazione di viaggio offline.

Una coordinata non è ancora un luogo.

Una foto di viaggio può contenere una latitudine e una longitudine con una precisione impressionante. Questi due numeri non indicano sempre se la fotocamera era in Giappone, nella prefettura di Kyoto, a Kyoto o all'aeroporto internazionale di Kansai sulla via del ritorno a casa. Mapsake ha bisogno di questa gerarchia prima che un punto possa diventare una registrazione di viaggio utile.

Il componente che risponde a queste domande è un elenco geografico: un elenco strutturato di luoghi geografici con nome. Mapsake include il suo elenco geografico all'interno dell'app, insieme alle linee di confine utilizzate per disegnare e testare paesi e regioni di primo livello. La ricerca, la marcatura manuale, l'importazione di foto, le storie dei luoghi, le statistiche di Passport, i risultati e persino alcune visualizzazioni di amici dipendono da esso.

Sarebbe stato più semplice inviare ogni coordinata a un geocodificatore web. Ciò avrebbe anche reso l'importazione di grandi quantità di foto più lenta, dipendente dalla rete, più difficile da riprodurre e meno privata. L'approccio offline ha richiesto più ingegneria all'inizio, ma ha fornito a Mapsake un vocabolario geografico stabile che funziona allo stesso modo su un aereo, a casa e anni dopo che un set di dati di origine è cambiato.

Questa è la storia di come è stato costruito questo livello, dove i punti e le linee non coincidono e perché "città più vicina" è solo l'inizio di una risposta corretta.

Quattro set di dati aperti, quattro lavori diversi

Nessuna singola fonte contiene tutto ciò di cui Mapsake ha bisogno, quindi il processo di compilazione combina quattro tipi di dati aperti:

• GeoNames fornisce paesi, regioni amministrative di primo livello, luoghi abitati, identificatori stabili, nomi alternativi, coordinate e popolazione.
• I nostri aeroporti fornisce aeroporti, codici IATA e ICAO, nomi, comuni e coordinate.
• Natural Earth fornisce la geometria dei confini del paese (admin-1) e punti di etichetta della mappa utili.
• Un livello piccolo e di proprietà di Mapsake registra le decisioni relative al prodotto, come il numero di paesi supportati, gli alias e le correzioni che non possono essere dedotti in modo sicuro da una fonte generica.

Ogni fonte è brava in qualcosa di diverso. GeoNames sa che una città appartiene a una regione e a un paese, ma una coordinata di città è un punto, non un confine. Natural Earth sa dove è disegnato un poligono, ma i suoi identificatori di funzionalità non corrispondono sempre perfettamente a GeoNames. OurAirports sa che KLAX e LAX si riferiscono allo stesso aeroporto, ma non è una gerarchia di tutti i luoghi intorno all'aeroporto.

Lo script di compilazione scarica e memorizza nella cache i file di origine, li normalizza, convalida le relazioni e genera due artefatti compilati: un database SQLite di sola lettura e una geometria GeoJSON semplificata. L'app fornisce questi risultati. Non scarica un database mondiale all'avvio e non dipende dalla disponibilità dei siti di origine durante un viaggio.

L'impegno degli artefatti generati rende anche la versione riproducibile. Una versione distribuita ha un mondo geografico noto. L'aggiornamento delle fonti è una modifica del codice intenzionale che può essere testata e revisionata, e non una modifica invisibile lato server che altera la mappa di qualcuno dall'oggi al domani.

Un database SQLite deliberatamente semplice.

Il primo Gazetteer conteneva 252 paesi, 3,861 regioni, 33,744 città e 4,564 aeroporti, per un totale di circa 14 MB. Ha utilizzato la libreria SQLite già fornita dal sistema operativo e un piccolo wrapper locale anziché un framework di database più grande.

Lo schema è intenzionalmente diretto. I continenti contengono paesi. I paesi contengono regioni. Le regioni contengono città. Gli aeroporti hanno codici paese e coordinate. Gli identificatori di origine stabili diventano gli identificatori memorizzati con un elemento Mapsake: ISO alpha-2 per un paese, un codice amministrativo GeoNames per una regione, un ID GeoNames per una città e un codice IATA per un aeroporto.

Mapsake normalizza anche il nome leggibile dall'uomo e la genealogia in ogni marcatore salvato. Questa duplicazione è utile. Un registro di viaggio personale deve rimanere leggibile se un gazetteer successivo rinomina un luogo, elimina un record o non è disponibile durante un'esportazione. L'identificatore serve per la corrispondenza; lo snapshot mantiene i dati dell'utente in modo autonomo.

SQLite è adatta a questo carico di lavoro perché il database viene generato una volta e interrogato molte volte. Supporta indici, transazioni durante la compilazione e la ricerca di testo completo senza un processo di servizio. L'app apre il file incluso solo in lettura, quindi non vi è alcun rischio di migrazione per i dati di riferimento e non vi è alcuna possibilità che una scrittura interrotta lo corrompa.

La ricerca è più di 'contiene(testo)'

La marcatura manuale inizia con un singolo campo di ricerca che copre continenti, paesi, regioni, città e aeroporti. Una ricerca per "san" dovrebbe trovare città pertinenti prima di record oscuri; "LAX" dovrebbe trovare l'aeroporto; e un nome digitato senza le sue dieresi dovrebbe comunque funzionare.

Lo script di compilazione crea una tabella FTS5 con nomi di visualizzazione, nomi alternativi selezionati, codici, ascendenza, coordinate, tipo e un valore di importanza. Il tokenizer Unicode rimuove i diacritici per la corrispondenza. Durante la query, Mapsake normalizza maiuscole e minuscole e diacritici, rimuove i caratteri che potrebbero diventare una sintassi di testo completo, aggiunge una corrispondenza di prefisso a ogni token e classifica i nomi esatti prima dei prefissi e delle corrispondenze generali.

L'importanza risolve i pareggi rimanenti. I continenti e i paesi non devono scomparire sotto villaggi con nomi simili. La popolazione di una città conferisce un peso adeguato ai luoghi importanti. I grandi aeroporti vengono classificati al di sopra dei piccoli quando la corrispondenza del testo è altrimenti comparabile.

I nomi alternativi sono intenzionalmente limitati. GeoNames può fornire un elenco molto lungo e multilingue per un luogo popolare. Copiare ogni ortografia nell'indice del dispositivo aggiungerebbe rumore e dimensioni. Il costruttore mantiene un insieme limitato e de-duplicato di varianti utili e conserva il nome di visualizzazione originale separatamente dal suo modulo di ricerca piegato.

I risultati della ricerca mostrano lo stesso modello GazetteerPlace utilizzato per la navigazione gerarchica. Un utente può cercare direttamente o navigare per continente, paese, regione e città senza creare due sistemi geografici che potrebbero essere diversi.

Le linee rispondono a una domanda diversa rispetto ai punti.

Il primo risolutore di foto ha scelto la città più vicina e ha ereditato il paese e la regione di quella città. Nelle aree densamente popolate, questo sembra spesso perfetto. Vicino a un confine, potrebbe essere sbagliato in un modo difficile da notare.

Immagina una foto scattata appena all'interno del Montana quando il luogo abitato più vicino nel database si trova dall'altra parte del confine, nel North Dakota. Il calcolo della città più vicina funziona correttamente, ma il risultato non è il luogo amministrativo in cui è stata scattata la foto. Lo stesso problema si verifica ai confini internazionali, vicino alle enclavi e attraverso l'acqua dove una costa scarsamente popolata non ha un punto abitato nelle vicinanze.

La geometria del confine risponde alla domanda se contiene piuttosto che alla prossimità. Mapsake decodifica i poligoni di paesi e amministrazioni di Natural Earth-1, verifica quali anelli contengono la coordinata e utilizza questo risultato per proteggere l'assegnazione di paese e regione. Può quindi cercare la città più vicina limitata al paese o alla regione del poligono.

Questo crea una utile divisione del lavoro:

1. Il contenimento per poligoni stabilisce l'area amministrativa.
2. La gerarchia del gazetteer fornisce ID e nomi stabili.
3. Una ricerca della città più vicina, limitata, fornisce una localizzazione utile senza superare il limite appena stabilito.
4. Un controllo dell'aeroporto più vicino aggiunge un aeroporto solo all'interno di una distanza deliberatamente limitata.

Né i dati della linea né il catalogo dei luoghi sono sufficienti da soli. Insieme, trasformano una coordinata in una catena verificabile.

L'audit admin-1 ha rilevato discrepanze sistemiche.

I poligoni dei paesi e i poligoni delle regioni provenivano da diversi livelli di Natural Earth, e gli identificativi del livello delle regioni non corrispondevano sempre a GeoNames. Alcuni errori erano evidenti, mentre altri hanno prodotto risultati plausibili ma errati.

Durante una conversione iniziale, la geometria del New Brunswick è stata assegnata al Quebec. Altre funzionalità mancavano di un codice, avevano un codice proveniente da un sistema vicino o rappresentavano un'unità amministrativa in modo diverso rispetto all'elenco. Uno sguardo visivo alla mappa del mondo non poteva trovare in modo affidabile tutti questi errori.

Il meccanismo di sostituzione tratta le città come un oracolo. Per ogni poligono candidato, chiede a quale regione del Gazetteer appartengono le città che si trovano effettivamente all'interno di esso. I codici Natural Earth esistenti vengono validati anziché essere considerati attendibili ciecamente. Le funzionalità che non superano la validazione possono essere riassegnate spazialmente, divise o escluse. L'output generato utilizza quindi gli ID di regione esatti che sono già presenti in SQLite.

Questo è una forma pratica di test inter-set di dati. Un poligono che afferma di essere una regione dovrebbe contenere un campione convincente di città che affermano di essere la stessa regione. Quando le due fonti non sono d'accordo, il sistema genera una prova invece di scegliere silenziosamente il valore che è stato caricato per primo.

La stessa verifica ha rilevato casi particolari, come dipendenze abitate integrate nella geometria di un paese. Mapsake corregge un piccolo numero di tali casi in modo che una foto possa essere associata allo stesso paese che comprendono le impostazioni del Gazetteer e del contatore di paesi.

Linee più nitide senza inviare il mondo nelle dimensioni originali.

La prima versione ha utilizzato il livello di paesi di 1:110 milioni di Natural Earth. Era compatto e veloce, ma le coste sono diventate visibilmente imprecise quando Mapsake ha aggiunto mappe più dettagliate, storie di luoghi e viste regionali.

La mappa è stata successivamente spostata nello strato 1:10 milioni. Questa fonte è molto più dettagliata, quindi includerla e renderla senza modifiche avrebbe aumentato lo spazio di archiviazione, il tempo di decodifica, la costruzione dell'overlay e il lavoro di ricollorazione. La pipeline di compilazione semplifica ogni anello utilizzando Douglas-Peucker con una tolleranza di circa 0.004 gradi, quindi arrotonda le coordinate a una precisione stabile.

Il file paese risultante ha circa 6.5 MB. Mantiene i dettagli utili della costa ai livelli di zoom che Mapsake mostra, rimuovendo al contempo i vertici che si troverebbero sugli stessi pixel. La geometria Admin-1 subisce un percorso di validazione e semplificazione simile.

La semplificazione ha un vincolo di correttezza: un poligono più piccolo deve comunque prendere le stesse decisioni per le coordinate reali delle foto. I test di riferimento successivi posizionano deliberatamente punti attorno ai bordi e confrontano la rilevazione degli impatti ottimizzata con un riferimento fisso. Le linee più veloci sono utili solo se rispondono ancora alla stessa domanda di contenimento.

Espansione da 34,000 a 234,000 città.

Il primo database ha utilizzato città di GeoNames con una popolazione superiore a 15,000. Questo ha permesso di mantenere il pacchetto compatto, ma ha lasciato i viaggi nelle zone rurali, le piccole isole, le città escursionistiche e molti luoghi di residenza con un'etichetta inutilmente distante.

Mapsake ha successivamente adottato GeoNames. città500, che copre i luoghi abitati con una popolazione di circa 500 persone, oltre ai centri amministrativi. La tabella delle città è cresciuta di circa sette volte, raggiungendo circa 234,000 record, e il database incluso è passato da circa 14 MB a circa 69 MB.

Questo scambio è stato effettuato dopo la rimozione dell'App Clip. Il limite di download del Clip era la ragione principale per la restrizione del database. Una volta che l'app principale era l'unico consumatore, una migliore copertura era più preziosa della conservazione di un limite artificiale per le piccole città.

L'indice di testo completo rimane selettivo per i nomi alternativi dei luoghi minori, e la navigazione per regione limita ancora ciò che viene renderizzato contemporaneamente. I dati possono essere ampi senza richiedere che ogni schermata materializzi l'intera tabella.

La copertura è più importante quando un geocodificatore di rete sarebbe meno affidabile. Una piccola città in un viaggio remoto non deve essere etichettata come una città a ore di distanza semplicemente perché il set di dati compatto l'ha omessa.

La ricerca della città più vicina è diventata un problema di prestazioni condiviso.

La query originale della città più vicina espandeva una casella di latitudine e longitudine, richiedeva a SQLite di calcolare una distanza ponderata per ogni candidato, creava un ordinamento temporaneo e restituiva la riga più vicina. Era facile da capire e abbastanza preciso, ma una libreria di foto 82,000 ha trasformato un piccolo costo per query in secondi di lavoro ripetuto durante le importazioni, i ricordi, la derivazione della mappa e Constellations.

Il primo miglioramento ha aggiunto una ricerca di test di 0.4 gradi di larghezza prima di utilizzare opzioni più ampie. Le posizioni dense trovavano generalmente una città da un insieme di candidati molto più piccolo. La memorizzazione nella cache e una cache persistente di celle geografiche hanno impedito alle foto vicine di ripetere lo stesso lavoro.

Il miglioramento più importante carica le coordinate numeriche delle città 234,000 in un indice in memoria ordinato per latitudine. Una ricerca binaria trova la sezione all'interno della finestra di latitudine corrente, un ciclo limitato verifica la longitudine e la distanza ponderata, e viene recuperata solo la riga vincente da SQLite. Una piccola cache di record mantiene i risultati ripetuti a basso costo.

Il comportamento di regolazione automatica non è cambiato. La funzione ottimizzata sceglie ancora la città più vicina all'interno della prima area di ricerca non vuota, inclusa una risoluzione deterministica delle uguaglianze. Una versione di riferimento del vecchio codice SQL verifica centinaia di coordinate vicino ai confini per un'equivalenza di ID esatta.

Sul simulatore, il tempo medio per la derivazione della città più vicina è passato da 2.11 secondi a 5.2 millisecondi. Su un iPhone fisico, il tempo è passato da 3.06 secondi a 6.35 millisecondi. Questi miglioramenti hanno permesso diverse funzionalità perché il geodati è un'infrastruttura condivisa piuttosto che un dettaglio di implementazione privato dello schermo di importazione.

Sono stati rilevati poligoni sovrapposti, il che ha rivelato un bug di correttezza.

Il meccanismo di verifica delle prestazioni ha rilevato un bug che esisteva prima dell'ottimizzazione. Alcuni poligoni admin-1 si sovrappongono intenzionalmente, in particolare le regioni delle capitali all'interno di una regione circostante. Berlino e Brandeburgo, Seoul e Gyeonggi, e la città di Kiev e la sua oblast sono esempi.

Il test di collisione originale accettava il poligono corrispondente che appariva per primo in un dizionario Swift. L'ordine di iterazione di un dizionario cambia tra i processi, quindi la stessa coordinata potrebbe acquisire una regione diversa dopo il riavvio dell'app.

Mapsake ora ordina i candidati sovrapposti in base all'area del poligono e consente alla caratteristica più piccola e specifica di vincere. L'implementazione di riferimento segue la stessa regola. Una foto di riferimento 82,000 deve produrre zero differenze tra i percorsi di derivazione a freddo e a caldo prima che un'ottimizzazione della geometria venga accettata.

Questo bug è un buon promemoria del fatto che "all'interno di un poligono" non è sempre una domanda di sì o no. I dati geografici contengono enclave, capitali nidificati, attraversamenti dell'antimeridiano, multipoligoni, buchi, confini contestati e convenzioni di origine. Una politica deterministica è importante quanto l'algoritmo di punto all'interno del poligono.

La modalità offline è una funzionalità di privacy e una funzionalità del prodotto.

L'importazione di foto di Mapsake può elaborare un'ampia libreria senza inviare le coordinate a un servizio di geocodifica di terze parti. Ciò protegge le posizioni di viaggio e domestiche sensibili, elimina i costi per richiesta, evita la limitazione della velocità e rende i progressi prevedibili.

Rende anche la modifica coerente. La ricerca manuale, l'importazione di foto, le carte di passaporto, i risultati, gli snapshot degli amici, l'abbinamento dei timbri e le storie dei luoghi parlano la stessa lingua perché utilizzano gli stessi ID di posizione stabili. Un aeroporto importato da un registro di volo può essere deduplicato con lo stesso aeroporto rilevato vicino a una foto. Una città trovata tramite una ricerca può corrispondere alla città utilizzata da Then & Now.

Questo pacchetto non è considerato perfetto o definitivo. Gli attributi di origine sono visibili nell'app. Gli script di compilazione vengono mantenuti insieme al codice. Le correzioni note sono esplicite. Gli elementi di riferimento proteggono il comportamento in coordinate difficili. L'aggiornamento del mondo geografico è un evento di rilascio con conseguenze verificabili.

Cosa terrei se dovessi ricostruirlo

Le scelte più durature non erano algoritmi singoli. Erano i confini delle responsabilità:

• Utilizzare i punti per nomi, identità stabili, ricerca e gerarchia.
• Utilizzare linee e poligoni per il contenimento.
• Genera un artefatto di prodotto in sola lettura invece di analizzare quattro formati di origine su un telefono.
• Salva uno snapshot leggibile con i dati dell'utente mantenendo l'ID sorgente per la corrispondenza.
• Rendi il percorso offline abituale deterministico prima di accelerarlo.
• Mantieni un'implementazione di riferimento lenta abbastanza a lungo da dimostrare che l'output ottimizzato è equivalente.

Il gazetteer è iniziato come una funzione di ricerca precoce. È diventato uno dei sistemi fondamentali di Mapsake, perché quasi tutte le funzionalità più avanzate devono alla fine rispondere alla stessa umile domanda: qual è questo luogo?

Per ottenere la risposta corretta, è necessario accettare che la geografia non è un singolo database o una query intelligente. È un accordo attento tra nomi, punti, linee, regole del prodotto e l'itinerario che una persona si aspetta di riconoscere.

• Vedi come Mapsake crea una mappa di viaggio dalle foto.
• Esplora le importazioni di cronologia dei viaggi supportate.
• Scopri il modello di privacy locale di Mapsake.