Mitä Mapsake on rakentanut offline-matkakartatietokannaksi

Koordinaatti ei ole vielä paikka.

Matkakuvassa voi olla sisältyvä leveys- ja pituusaste, joka on erittäin tarkka. Nämä kaksi numeroa eivät kuitenkaan kerro, oliko kamera Japanissa, Kyoto prefektuurissa, Kyotossa tai Kansai International Airportissa kotiin matkalla. Mapsaken tarvitaan tämä hierarkia ennen kuin piste voi muodostua hyväksi matkarekisteriksi.

Komponentti, joka vastaa näihin kysymyksiin, on gazetteeri: rakennettu nimeltä olevien maantieteellisten paikkojen suuntaviivatietokanta. Mapsake sisältää gazetteerinsä sovelluksessaan, yhdessä rajalujuudet, joita käytetään maat ja ensin tason alueiden piirtämiseen ja testaamiseen. Haku, manuaalinen merkintä, kuvan tuonti, paikan tarinat, Passporin tilastot, saavutukset ja jopa muutama ystävän näkymä kaikki riippuvat siitä.

Se olisi helpompaa lähettää jokainen koordinaatti verkkogeokoodattimelle. Se olisi myös tehnyt suuren kuvan tuontin hitaaksi, verkkoon riippuvaiseksi, vaikeammin toistettavaksi ja vähemmän yksityisen. Offline-rahasto vaati enemmän tekniikkaa alussa, mutta se antoi Mapsake:lle vakavan geografisen sanaston, joka toimii samalla tavalla lentokoneessa, kotona ja vuosien päästä lähteiden muutoksista.

Tämä on tarina siitä, miten tämä kerros on rakennettu, missä pisteet ja viivat ovat ristiriidassa ja miksi ”lähin kaupunki” on vain osa oikeaa vastausta.

Neljä avointa datamäärää, neljä eri työtä

Ei yhtä lähteestä löydy kaikkea, mitä Mapsake tarvitsee, joten rakentamisepositiivinen yhdistää neljä eri avointa dataa:

• GeoNames tarjoaa maat, ensimmäisen tason hallinnolliset alueet, asutuspaikat, vakaita tunnisteita, vaihtoehtoiset nimet, koordinaatit ja väkiluku.
• OurAirports tarjoaa lentokentät, IATA- ja ICAO-koodit, nimet, kunta- ja koordinaatit.
• Luontainen Maapallo tarjoaa maan ja admin-1 rajatietoja sekä hyödyllisiä karttatunnisteita.
• Pieni Mapsake-omistettu kerros tallentaa tuotevalintoja, kuten tuetut maamäärätilat, lemmikit ja korjaukset, jotka eivät voida päätellä turvallisesti yleisestä lähteestä.

Jokainen lähteessä on eri hyväksikäyttöinen asia. GeoNames tietää, että kaupunki kuuluu alueeseen ja maahan, mutta kaupungin koordinaatti on piste, ei raja. Natural Earth tietää, missä polygoni on piirretty, mutta sen ominaisuusidentifioinnit eivät aina yhdy selkeästi GeoNamesin kanssa. OurAirports tietää, että KLAX ja LAX viittaavat samaan lentokenttään, mutta se ei ole järjestelmä kaikista paikoista lentokentän ympärillä.

Rakennuscript lataa ja varmistiin tallennettavat yläpuolella olevat tiedostot, normalisoi niitä, vahvistaa suhteita ja luo kaksi komittoidun tulostuksen: luku-asetuksella SQLite-tietokanta ja yksinkertaistettu GeoJSON-geometria. Sovellus toimittaa nämä tulokset. Se ei lataa maailman tietokantaa ensimmäisellä käynnistykseksi tai riippuudu lähteiden olevasta online-tilasta matkalla.

Vahvistettujen tuotteiden luominen tekee myös julkaisun toistettavaksi. Lähetetty versio sisältää tunnetun maailman geografian. Lähteiden päivitys on tarkoituksellinen koodimuutos, joka voidaan testata ja tarkistaa, ei näkymätön palvelimella tapahtuva muutos, joka muuttaa jonkun karttaa yhtä yön aikana.

Tahallisesti tylsä SQLite-tietokanta.

Ensimmäinen gazetteeri sisälsi 252 maata, 3,861 aluetta, 33,744 kaupunkia ja 4,564 lentokenttää noin 14 MB:lla. Se käytti jo olemassa olevaa SQLite -kirjastoa järjestelmästä ja pieniä paikallisia kääntäjiä eikä suurempaa tietokantarakennetta.

Schema on tarkoitettu suoraan. Kontinenteissa on maat. Maissa on alueet. Alueissa on kaupungit. Lentoasemat kantavat maakoodit ja koordinaatit. Stabiili lähteiden tunnisteet muuttuvat tunnisteiksi, jotka tallennetaan Mapsake -merkkiin: ISO alpha-2 maalle, GeoNames hallinto-koodi alueelle, GeoNames ID kaupungille ja IATA-koodi lentoasemelle.

Mapsake muokkaa myös luettavasti kirjoitettua nimeä ja perintöä jokaiseen tallennettuun merkkiin. Tämä kopiointi on hyödyllistä. Henkilökohtainen matkakirja pitäisi pysyä luettavana, jos myöhemmin gazetteeri muuttaa paikan nimeä, poistaa merkinnän tai ei ole läsnä vientiä varten. Tunniste tukee vastaamista; tilaus pysyy käyttäjän datan itsenäisenä.

SQLite sopii tämän työnkulun hyvin, koska tietokanta luodaan kerran ja kysytään monta kertaa. Se tukee indeksejä, transaktioita rakentamisen aikana ja täysjoukkojen hakuja ilman palveluprosessia. Sovellus avaa pakattu tiedosto vain luku-tilassa, joten viiteaineistolla ei ole siirtymävaaraa ja ei ole mahdollista, että kesken jäänyt kirjoitus korruptoi sitä.

Etsintä on enemmän kuin vain sisältää(text)

Manuaalinen merkintä alkaa yhdellä hakukentällä, joka ulottuu matkakontinenteille, maailmankirjoihin, alueisiin, kaupunkeihin ja lentokenttiin. Hakukentän ”san” tulisi löytää merkittävät kaupungit ennen harvinaisia tietoja; ”LAX” tulisi löytää lentokenttä; ja nimeä, joka kirjoitetaan ilman diakriittisia merkkejä, tulisi edelleen toimia.

Rakennus luo FTS5 -taulun, johon sisältyvät näyttöluettelot, valitut vaihtoehtoiset nimet, koodit, alkuperät, koordinaatit, tyyppi ja tärkeysarvo. Unicode-tokenisointi poistaa diakritiikat vertailuun. Hakuaikaan Mapsake yhdistää kirjaimet ja diakritiikat, poistaa merkit, jotka voivat muodostaa täysin tekstiä, lisää etuliitevertailua jokaiselle tokenille ja arvostaa tarkkoja nimien yli etuliitteiden ja yleisten vastausten edellä.

Tärkeys katkoo jäädytyneet yhteydet. Kontinenteilla ja mailla ei tulisi kadota samannimisiin kyläihin. Kaupunkien väkiluvut antavat merkittävimmille paikoille tarkemman painon. Suuret lentoasemat rankkautuvat pienempien yläpuolelle, kun tekstiviesti on muuten samanlainen.

Vaihtoehtoiset nimet ovat tarkoitettu rajoitettuksi. GeoNames voi tarjota hyvin pitkän monikielisen listan suosituille paikoille. Kaikkien kirjoituksen kopioiminen laitteen indeksin sisälle lisäisi kohinaa ja kokoaa. Rakentaja säilyttää rajoitettavan, deduploidun osan hyödyllisistä vaihtoehdoista ja säilyttää alkuperäisen näyttöpäätteen erillisesti sen muokattua etsintämuodosta.

Etsintäpohjaiset tulokset palauttavat saman GazetteerPlace -mallin, jota käytetään hierarkisen selaamisen yhteydessä. Käyttäjä voi etsiä suoraan tai selaamaan mantereita, maita, alueita ja kaupunteja ilman, että luodaan kaksi geografista järjestelmää, jotka voisivat olla ristiriitaisia.

Viivat vastaavat eri kysymystä kuin pisteet

Ensimmäinen kuvan analysoija valitsi lähimmän kaupungin ja perssi sen maan ja alueen. Tiheissä alueissa tämä näyttää usein täydellisenä. Rajojen läheisyydessä se voi olla väärin tavalla, jota on vaikea huomata.

Kuvittele valokuva, joka otettiin juuri Montana:n sisällä, kun lähimmäinen asutuspaikka tietokannassa on rajojen yli North Dakota:ssa. Lähimmän kaupungin laskenta toimii oikein, mutta tuloksena ei ole hallinnollinen paikka, jossa valokuva otettiin. Samainen ongelma esiintyy kansainvälisillä rajoilla, lähellä enklaveja ja vesillä, jossa harva rannikko ei ole lähellä asutusta.

Rajageometria vastaa sisällyttämistä eikä läheisyyttä. Päästö tulkkaa Natural Earth maan ja admin-1 -polygonit, tarkistaa, sisältääkö ringit koordinaatin ja käyttää tätä tulosta suojamaan maan ja alueen määrittelyä. Se voi sitten hakea lähimmän kaupungin rajojen maan tai alueen sisällä.

Tämä luo hyvän työjakajan:

1. Monikulmion sisältäminen määrittää hallinnollisen alueen.
2. Gazetteerin hierarkia tarjoaa vakaita tunnisteita ja nimet.
3. Rajoitettu lähin kaupunki -haku tarjoaa hyödyllisen paikallistuksen ilman, että ylitetään raja, joka juuri on määritelty.
4. Lähellä olevan lentokentän tarkistus lisää lentokentän vain tarkasti rajoitetussa etäisyydessä.

Ei kumpaakaan linjan tietoa eikä paikan hakemistoa ole riittävä yksinään. Yhdessä ne muuttavat koordinaatin puolustettavaksi ketjuksi

admin-1 -tarkastelu paljasti järjestelmällisiä vastaavuusongelmia

Maa- ja aluepolygoineita tuli eri Natural Earth -kerroksesta, ja aluekerroksen tunnisteet eivät olleet aina yhtenevät GeoNamesin kanssa. Joissain tapauksissa virheet olivat selvät, mutta muissa syntyivät mahdollisesti väärin täyttyneet täyttyneet.

Yksi varhainen muunnoskaavio määritteli Quebecille uudistuksen New Brunswickille. Muissa ominaisuuksissa puuttui koodia, siirrettiin koodi viereisestä järjestelmästä tai esitettiin hallinnollinen yksikkö eri tavalla kuin gazetteerissa. Maailman karttaa ei voinut näkemällä löytää kaikkia näitä virheitä luotettavasti.

Korvaavat tilat käsittelevät kaupunkeja orakelina. Jokaiselle ehdokkaalle monikulmalle kysytään, mikä gazetteerin alueen omat kaupungit todella sijaitsevat sen sisällä. Olemassa olevat Natural Earth -koodit validoidaan eikä luotettavasti oteta käyttöön. Vaihdettavien ominaisuuksien, jotka eivät läpäise validointia, voidaan siirtää paikallisesti, jakaa tai poistaa. Lopullinen tuloste käyttää tarkasti alueiden tunnuksia, jotka ovat jo olemassa SQLite -tietokannassa.

Tämä on käytännön muoto kriittisestä tietojen testauksesta. Monikulmio, joka väittää olevansa alue, tulisi sisältää vakuuttava näytteistä kaupunkeista, jotka väittävät saman alueen. Kun kaksi lähdettä ei ole samaa mieltä, rakennus tuottaa näytön sijaan ei valitse hiljaisesti, mitä arvoa laitettiin ensin.

Saman tarkastelun mukaan löytyi erikoistapauksia, kuten asutut alueet, jotka on suljetuksi vanhan maan geometriaksi. Mapsake korjaa pieni määrä näistä tapauksista, jotta kuva voi viitata samaan maahan, johon gazetteer ja maan-asiakirjan asetukset ymmärtävät.

Täysin selkeät viivat ilman lähtösuuruuden maailman lähettämistä

Ensimmäinen Atlas käytti Natural Earthin 1:110 miljoonan maakunnan kerros. Se oli tiivis ja nopea, mutta rannikot muuttuivat näkyvästi kapeiksi, kun Mapsake lisäsi lähempiä karttoja, paikan tarinat ja alueellista tarkastelua.

Karta siirtyi myöhemmin 1:10 miljoonan kerros. Tämä lähde on paljon tarkempi, joten pakkaaminen ja renderöinti muuttumattomana olisi lisännyt tallennustilaa, decode-aikaa, overlay-konstruktioa ja väritystä. Rakennuspiiri yksinkertaistaa jokaisen renkaisen Douglas-Peucker -toleranssilla noin 0.004 asteella, ja pyöristää koordinaatit vakaa tarkkuudella.

Saadun maakunnan tiedostossa on noin 6.5 MB. Se säilyttää hyödyllisen rannan yksityiskohtien zoom-tasolla, jota Mapsake esittelee, poistaa kärkipisteet, jotka olisivat sijainneet hyvin saman pixelin päällä. Admin-1 -geometria kulkee saman validointipolun ja yksinkertaistamisen kautta.

Yksinkertaistaminen on oikeudenmukaisuuden rajoitus: pienempi monikulmio on vielä vastustanut samat päätökset todellisten fototodistusten koordinaateille. Myöhemmin benchmark-asetukset tarkoittavat tarkasti pisteitä reunojen ympärillä ja vertaavat optimoidun osaamisen testaamista jäädytetyn viitteen kanssa. Nopeammat viivat ovat hyödyllisiä vain silloin, kun ne vastaavat vielä saman sisällyksen kysymyksen.

Laajentamalla 34,000:sta 234,000:aan kaupunkiin

Ensimmäinen tietokanta käytti GeoNames -kaupunkeja, joissa asutti yli 15,000. Se säilytti paketin pieneksi, mutta jätti maaseututuksia, pieniä saaria, polkutuksia ja monia kotipaikkoja liian kaukana olevina niminä.

Mapsake otti myöhemmin vastaan GeoNames kaupungit500, kattaen asutettuja paikkoja, joiden asukasluku on noin 500 ihmistä tai enemmän, sekä hallinnollisia keskuksia. Kaupunkitaulukko kasvoi noin seitseminkertaiseksi, noin 234,000 merkintään, ja paketoitu tietokanta kasvoi noin 14 megatavusta noin 69 megatavun kokoiseksi.

Se kauppa tehtiin, kun App Clip poistettiin. Clipin latausrajalla oli ollut vahvin syy rajoittaa tietokantaa. Kun pääsovellus oli ainoa kuluttaja, parempi kattavuus oli arvokkaampi kuin säilyttää tekojärjestelmässä pienikotila-rajapiste.

Koko tekstiindeksin säilyttää valitsemat kohdat pienille paikoille ja alueiden selailu rajoittaa edelleen, mitä se näyttää kerralla. Tietoja voidaan olla laajaa ilman, että jokainen näkymä tarvitsee materiaalisia koko taulukkoa.

Kattavuus on tärkein paikassa, jossa verkko-geokoodaus olisi vähiten luotettava. Pieni kylä kaukona matkalla ei tulisi merkitä kaupunkiksi tunnettuja tunteja vain siksi, että tiukka datajoukko siihen ei sisältänyt.

Lähimmän kaupungin löytäminen muodostaa jakamisen kautta yhteisen suorituskyvyn ongelman

Alkuperäinen lähimmän kaupungin kysely laajensi leveys- ja pituusasteen laatikkoa, kysyi SQLite:ltä laskemaan painotettua etäisyyttä jokaiselle ehdokkaalle, rakensi väliaikaisen lajittelun ja palautti lähimmän rivin. Se oli helppoa ymmärtää ja riittävän tarkka, mutta 82,000-fotolibrary muutti pienestä kyselyn kustannuksesta toistuvan työn sekä tuotantoon, muistiin, karttaan ja Konstellatioon.

Ensimmäinen parannus lisäsi kapean 0.4-asteen tutkimuksen laajempien varatoimintojen eteen. Tiheissä paikoissa kaupunkia yleensä löydettiin huomattavasti pienemmästä kandidaattisarjasta. Memoisointi ja pysyvä geografinen solukokoelma estivät myös läheisen kuvan toistamasta samasta työstä.

Suurempi parannus lataa 234,000 kaupunkien numerotiedot latitudin mukaisesti järjestettyyn muistiin tallennettuun indeksin. Binäärihaku löytää tason nykyisen latitudin ikkunassa, rajoitettu silmukka tarkistaa longitudin ja painotetun etäisyyden, ja vain voittaja rivistä haetaan SQLite:stä. Pieni rekisterikasvit pitävät toistuvia voittajia halvalla.

Laajenemisen käyttäytymisen ei muuttunut. Optimoidun funktion valitsee edelleen lähimmän kaupungin ensimmäisessä tyhjä ei ole täysin etsintäikkuna, mukaan lukien deterministinen yhteydenpito. Vain vertailukelpoinen kopio vanhasta SQL -polusta tarkastellaan satoja rajojen runsaasti koordinaatteja tarkasta ID-yhteydestä.

Simulaattorilla keskivälinen lähimmän kaupungin sarja laski 2.11 sekuntia 5.2 millisekuntiin. Fyysinen iPhone -käynnistys laski 3.06 sekuntia 6.35 millisekuntiin. Nämä parannukset saavuttivat useita ominaisuuksia, koska gazetteeri on jakamaton infrastruktuuri, ei yksityinen toteutusimportin näkymän yksityiskohtana.

Kertakäyttöisen polygonin löytämisen tarkkuusvirhe

Suorituskyvyn yhtäsuuruuden turvaajalla löytyi virhe, joka oli olemassa ennen optimointia. Jotkut admin-1 monikulmiot ylittävät toisensa tarkoituksella, erityisesti pääkaupunkiregioissa ympäröivän alueen sisällä. Berliini ja Brandenburgi, Seulassa ja Gyeonggi, sekä Kyivin kaupunki ja sen oblasti ovat esimerkkejä.

Vanha ositus hyväksyi ensimmäisen ilmestyneen vastaavasti monikulmion Swift-sanakirjasta. Sanakirjan iterointijärjestys vaihtelee prosessien välillä, joten sama koordinaatti voi saada eri alueen sovelluksen uudelleenkäynnistysjälkeen.

Mapsake järjestää nyt päällekkäiset kandidaatit monikulmion pinta-alan perusteella ja antaa pienimmälle, tarkimmalle ominaisuudelle prioriteetin. Viiteimplementaatio seuraa samaa sääntöä. 82,000-fotolla jäänyt kiinteä asetus on oltava täysin samanlainen kylmän ja lämmön derivointipolun välillä ennen geometrian optimoinnin hyväksymistä.

Tämä vika on hyvä muistutus siitä, että "polygonin sisällä" ei ole aina kysymys, johon vastataan kyllä tai ei. Geografinen data sisältää enklavit, sisennetyt pääkaupungit, antimeridiaanin ylitykset, monikuvioita, aukot, kiisteltyjä rajoja ja lähteiden sääntöjä. Deterministinen politiikka on yhtä tärkeä kuin piste-kuvioalgoritmi.

Offline on yksityisyysominaisuus ja tuoteominaisuus

Mapsaken fototuonti voi ratkaista suuren kokoisen kokoelman ilman, että sen koordinaatit lähetetään kolmannelle osapuolelle geokoodauspalvelulle. Tämä suojaat tunteita ja kotipaikkoja, poistaa per-kysely-hinnat, välttää rajoitukset ja tekee edistymisen ennustettavaksi.

Se tekee muokkaamisen koherentiksi. Manuaalinen haku, kuvan tuonti, Passporin kortit, saavutukset, ystävien kuvakuvioita, jäljitysryhmittely ja paikan tarinat puhuvat saman kielellä, koska ne käyttävät saman vakaa paikan tunnistetta. Lentoasema, joka on tuotu lentorekisteristä, voi deduplikoida samalla lentoasemalla, joka on havaittu kuvan läheisyydessä. Kaupunki, joka löytyy hakukoneesta, voi vastata kaupunkia, joka on käytetty Then & Now -toiminnossa.

Paketti ei pidetä täydellisenä tai pysyvänä. Lähteiden attribuutiot näkyvät sovelluksessa. Rakennuscriptit säilytetään koodin kanssa. Tiedot korjauksista on selkeästi esitetty. Benchmarksuoja suojaa käyttäytymistä vaikeissa koordinaateissa. Maailman geografisen tietokannan päivittäminen on julkaisun tapahtuma, jolla on tarkastettavissa olevia seurauksia.

Mitä pidäisin, jos rakentaisin sen uudelleen

Vakaimmin kestävät valinnat eivät olleet yksittäisiä algoritmeja. Ne olivat vastuuvälitteitä välillä:

• Käytä pisteitä nimien, vakaita identiteettejä, etsintää ja hierarkiaa varten.
• Käytä viivoja ja monikulmioita sisällön rajoittamiseen.
• Luo luku-asetelma, ei käsittelyä neljästä yläpuolelta tulevasta muodosta älypuhelimeen.
• Tallenna luettavissa oleva näytös käyttäjäandun kanssa säilyttäen lähteensä tunnisteen yhteydenpitämiseksi.
• Varmista, että yleinen offline-rajapinta on deterministinen ennen kuin tehdään nopea.
• Pidä hitaasti toimiva viiteimplementaatio tarpeeksi pitkäksi, jotta todistetaan optimoidun tuloksen ekvivalenssi.

Gazetteeri alkoi varhaisena etsintäominaisuutena. Se muuttui yksi Mapsake:n tukijärjestelmistä, koska lähes jokainen monimutkaisempi ominaisuus tarvitsee lopulta vastata samaan yksinkertaiseen kysymykseen: mikä tämä paikka on?

Saada oikea vastaus tarkoittaa hyväksyä, että geografia ei ole yksi tietokanta tai yksi älykäs kysely. Se on huolellinen sopimus nimistä, pisteistä, viivoista, tuotantosääntöistä ja matkakirjasta, jonka henkilö odottaa tunnistamaan.

• Katso, miten Mapsake luo matkakartan valokuvista
• Tutustu tuettuihin matkailuhistorian tuontiin
• Lue Mapsaken paikallisesti toimiva yksityisyyden malli