GrabMaps stă la baza aplicației Grab oferind oportunitatea de a îmbunătăți serviciile noastre și de a îmbogăți harta cu date hiperlocale. Indiferent de scenariul analizat, localizarea drumurilor joacă un rol important în procesul de creare a hărții Grab. Cu toate acestea, localizarea drumurilor implică gestionarea unui volum semnificativ de date, fiind un efort costisitor și consumator de timp. În acest articol, explorăm strategiile implementate pentru a reduce costurile și pentru a diminua timpul de procesare asociat localizării drumurilor.
În 2022, Grab a devenit autosuficient în ceea ce privește serviciile sale Geo. Ca parte a acestei tranziții, un pas crucial a fost decizia de a utiliza o hartă dezvoltată intern, adaptată specificului pieței în care operează Grab.
Având control total asupra hărții, aceasta poate fi extinsă cu mai multe date sau îmbunătățită, în funcție de nevoile serviciilor care o folosesc. Un aspect cheie pe care această tranziție l-a adus a fost posibilitatea de a crea date hiperlocale la nivel de hartă.
De exemplu, prin identificarea țării căreia aparține o stradă, putem deduce automat limba oficială a acelei țări și să afișăm numele străzii în acea limbă. Un alt exemplu, cunoscând țara pentru o anumită stradă, putem deduce automat partea pe care se conduce în acea țară (stânga sau dreapta) aceasta generând o experiență de navigare mai plăcută.
În plus, această capacitate permite, de asemenea, gestionarea mai eficientă a diverse scenarii. De exemplu, știind că o stradă face parte dintr-o comunitate închisă, o zonă cu acces restricționat pentru șoferii noștri, putem împiedica tranzitul prin acea zonă.
Acestea sunt doar câteva exemple ale oportunităților create având control complet asupra hărții. Având o hartă internă putem alinia conținutul hărților noastre cu specificul piețelor în care operează Grab oferind astfel o experiență mai plăcută pentru partenerii noștri, șoferi și clienți.
Pentru ca toate acestea să fie posibile, primul pas a fost localizarea drumurilor din hartă. Scopul final a fost includerea datelor hiperlocale în hartă, date specifice unei anumite zone, cum ar fi o țară, un oraș sau chiar o parte mai mică a orașului, cum ar fi o comunitate închisă. În același timp, harta trebuie livrată cu o frecvență ridicată, așadar, a fost nevoie să găsim modalitatea potrivită de a procesa această cantitate mare de date în timp ce continuam să creăm hărți într-o manieră rentabilă din punct de vedere al costurilor.
În secțiunile următoare ale acestui articol, vom folosi un extras din harta Asiei de Sud-Est pentru a reprezenta vizual conceptele discutate.
În Figura 1, Imaginea 1 conține o vizualizare a rețelei de drumuri, drumurile care aparțin acestei zone. Liniile colorate din Imaginea 2 reprezintă granițele care identifică țările din aceeași zonă. Suprapunând informațiile din Imaginea 1 și Imaginea 2, putem extrapola și spune că întreaga suprafață inclusă într-o anumită graniță ar putea avea aceeași serie de proprietăți comune, așa cum este arătat în Imaginea 3. În Imaginea 4, continuăm prin identificarea drumurilor localizate pentru fiecare zonă.
Figura 1 - Harta Asiei de Sud-Est
Pentru ca acest lucru să fie posibil, trebuie să găsim o modalitate de a localiza fiecare drum și de a identifica țara asociată acestuia. Odată ce acest proces de localizare este complet, putem replica toate aceste informații specifice unei anumite granițe pe fiecare drum în parte. Aceste informații includ detalii precum numele țării, partea de drum pe care se conduce și limba oficială. Putem merge chiar mai departe și să extragem și mai multe informații și să adăugăm date hiperlocale. De exemplu, în Vietnam, putem împiedica automat accesul motocicletelor pe autostrăzi.
Atribuirea fiecărui drum de pe hartă unei anumite zone, cum ar fi o țară, zonă de serviciu sau subdiviziune, reprezintă o sarcină complexă. Așadar, cum se poate realiza eficient acest lucru?
Cea mai directă abordare ar fi testarea includerii fiecărui drum în interiorul fiecărei granițe. Cu aproape 30 de milioane de segmente de drum în harta Asiei de Sud-Est și peste zece mii de granițe, costul computațional al determinării includerii sau intersecției între o linie și un poligon este mare.
Soluția găsită la această provocare implică înlocuirea operației costisitoare și precise cu o aproximare decentă. Pentru aceasta folosim o entitate intermediară, geohashul, atât pentru a aproxima zonele, cât și pentru a localiza drumurile.
Operația de includere geometrică se înlocuiește cu o serie de operații mai simple și mai puțin costisitoare. Mai întâi, efectuăm o precalculare ieftină în care se identifică toate geohashurile care aparțin unei anumite zone sau care se află într-o graniță predefinită. Apoi identificăm geohashurile prin care trec drumurile. La final folosim aceste valori precalculate pentru a crea legătura dintre setul de drumuri și cel de granițe. Acest proces este mai ieftin din punct de vedere computațional.
Având în vedere suprafața mare pe care o procesăm, folosim tehnici de Big Data pentru a distribui execuția pe mai multe noduri accelerând astfel operația. Se dorește livrarea zilnică a hărții și aceasta este una dintre multele operații care fac parte din procesul de creare a hărții.
Pentru a înțelege mai bine implementarea noastră, trebuie să înțelegem conceptul de geohash. Un geohash este un identificator unic al unei regiuni specifice de pe Pământ. Ideea de bază este că Pământul este împărțit în regiuni de dimensiuni definite de utilizator și fiecărei regiuni îi este asignat un ID unic, cunoscut sub numele de geohash. Pentru o anumită locație de pe Pământ, algoritmul geohash convertește longitudinea și latitudinea într-un șir de caractere.
Geohashurile folosesc un sistem de codificare alfabetică în baza 32, compus din caractere cuprinse între 0 și 9 și literele de la A la Z, cu excepția "A", "I", "L" și "O". Considerăm suprafața Pământului împărțită într-o grilă cu 32 de celule. Primul caracter dintr-un geohash identifică locația inițială a uneia dintre aceste 32 de celule. Fiecare dintre aceste celule este apoi subdivizată în alte 32 de celule mai mici. Acest proces de subdivizare continuă și se rafinează până se ajunge la locația dorită. Adăugarea de caractere la geohash împarte o celulă, focalizând efectiv către o zonă mai detaliată.
Factorul de precizie al geohashului determină dimensiunea celulei. De exemplu, un factor de precizie de unu creează o celulă cu dimensiunile de 5.000 km x 5.000 km. Un factor de precizie de șase creează o celulă având dimensiunile de 0,61 km x 1,22 km. În plus, un factor de precizie de nouă creează o celulă de 4,77 m x 4,77 m. Este important de menționat că celulele nu sunt întotdeauna pătrate și pot avea dimensiuni variate.
În Figura 2, am exemplificat o grilă geohash de 6, având codul wdts33.
Figura 2 - Exemplu de geohash de lungime 6 (wdts33)
Calcularea incluziunii drumurilor într-o anumită graniță este o operație costisitoare. Cu toate acestea, este dificil de cuantificat exact costul deoarece acesta depinde de mai mulți factori. Un factor este complexitatea graniței. Granițele sunt în general poligoane neregulate și foarte detaliate, deoarece trebuie să reflecte corect granița reală. Complexitatea geometriei drumurilor este un alt factor care joacă un rol important, din cauză că drumurile nu sunt întotdeauna linii drepte.
Figura 3 - Drumuri de localizat
Întrucât această operațiune este costisitoare atât în ceea ce privește costurile de cloud, cât și timpul necesar pentru executare, este nevoie de o metoda mai ieftină și mai rapidă care să ofere rezultate similare. Știind că complexitatea granițelor este principala cauza a problemei, am încercat să folosim o variantă diferită, și anume un dreptunghi. Calcularea incluziunii unei polilinii într-un dreptunghi este o operație mai ieftină.
Figura 4 - Drumuri în interiorul unui dreptunghi
Astfel, transformăm această operație mare, realizată într-un singur pas, într-o serie de operațiuni mai mici, în care efectuăm următorii pași:
Identificăm toate geohashurile care fac parte dintr-o anumită zonă sau aparțin unei anumite granițe. În acest proces, includem și zone suplimentare pentru a ne asigura că acoperim întreaga suprafață din interiorul graniței.
În Figura 5, se observă că drumul din vizualizare traversează două geohashuri și vedem, de asemenea, că cele două geohashuri fac parte din granița pe care o folosim.
Figura 5 - Geohashuri ca proxy
Acum, tot ce trebuie să facem este să unim cele două seturi de date. Acest tip de operație este un candidat excelent pentru o abordare de tip Big Data, deoarece ne permite să o executăm în paralel și să accelerăm timpul de procesare.
Am menționat mai devreme că înlocuim precizia cu o aproximare decentă. Să evaluăm mai în detaliu compromisul real introdus prin adoptarea acestei abordări.
Primul aspect relevant al acestei abordări este faptul că am înlocuit precizia cu costul. Costurile de procesare se reduc datorită faptului că această abordare folosește mai puține resurse hardware și timp de calcul. Totuși, această reducere a preciziei afectează în special drumurile situate în apropierea granițelor, întrucât acestea ar putea fi clasificate greșit.
Revenind la exemplul inițial, să luăm cazul drumului extern, situat pe partea stângă a zonei considerate. După cum se vede în Figura 6, este clar că drumul nu aparține graniței noastre. Dar atunci când aplicăm abordarea geohash, acesta este inclus în geohashul din mijloc.
Figura 6 - Localizare greșită a drumului
Având în vedere că doar o mică parte a geohashului cade în interiorul graniței, întregul geohash va fi clasificat ca aparținând acelei zone și, ca urmare, drumul care aparține acelui geohash va fi localizat greșit la rândul său. Acesta este o consecință directă a compromisului de precizie. Deci, cum putem rezolva aceasta?
O opțiune ar fi să creștem precizia geohashului. Prin utilizarea geohashurilor din ce în ce mai mici, se poate reflecta mai corect zona reală. Mergând mai adânc și împărțind geohashul și mai mult, putem urmări precis granița. Cu toate acestea, o precizie mare a geohashului echivalează și cu o operațiune intensivă din punct de vedere computațional, aducându-ne înapoi la situația inițială. Prin urmare, este crucial să găsim echilibrul între dimensiunea geohashului și complexitatea operațiunilor.
Figura 7 - Precizia geohashului
Pentru a găsi un echilibru între precizie și pierderea de date, am introdus un alt concept, calcularea ratei de acoperire a geohashului. De exemplu, în Figura 8, geohashul albastru este complet în interiorul graniței. Aici putem spune că acest geohash are o acoperire de 100% în interiorul graniței.
Figura 8 - Geohash în interiorul graniței
Cu toate acestea, să luăm de exemplu geohashul din Figura 9. Acesta atinge granița și are doar aproximativ 80% din suprafața sa în interiorul ariei considerate. Având în vedere că cea mai mare parte a suprafeței sale este în interiorul graniței, putem totuși spune că aparține zonei.
Figura 9 - Geohash parțial în interiorul graniței
Să considerăm un alt exemplu. În Figura 10, doar o mică parte a geohashului se află în interiorul graniței. Putem spune că procentajul de acoperire al acestui geohash este de aproximativ 5%. În astfel de cazuri devine dificil să determinăm dacă geohashul aparține zonei. Care ar fi un compromis bun în acest caz?
Figura 10 - Geohash puțin în interiorul graniței
Pentru a merge un pas mai departe, putem lua în considerare o soluție mixtă, în care să folosim forma graniței, însă doar pentru acele geohashuri care ating granița. Aceasta ar fi încă o operație computațională intensivă, dar numărul de drumuri situate în aceste geohashuri va fi mult mai mic, deci totuși un câștig.
Pentru geohashurile cu acoperire completă în interiorul zonei, vom folosi geohashul pentru localizare, operația mai simplă. Pentru geohashurile aflate în apropierea graniței, vom folosi o abordare diferită. Pentru a crește precizia în jurul granițelor, putem tăia geohashul urmând forma graniței. În loc să avem un dreptunghi, vom folosi o formă mai complexă, care totuși este mai simplă decât forma inițială a graniței.
Figura 11 - Geohash tăiat după forma graniței
Am început cu o abordare simplă, pe care am continuat să o îmbunătățim pentru a crește precizia. Odată cu aceasta a crescut și complexitatea operației. În această secțiune, am încercat să evaluăm beneficiile reale ale acestei abordări.
În primul rând, am creat o referință prin extragerea unei mici mostre de date pentru care am rulat procesul de localizare pe un laptop. Mostrele cuprindeau aproximativ 2% din granițe și 0.0014% din drumuri. Am rulat procesul de localizare folosind două abordări.
Cu prima abordare, cea în care am calculat intersecția între toate drumurile și granițele, întreaga operațiune a durat aproximativ 38 de minute.
Pentru a doua abordare, cea în care am optimizat operația folosind geohashurile, timpul de rulare a fost de doar de 78 de secunde (1.3 minute). Cu toate acestea, este important de menționat că aceasta nu este o comparație directă. Operația pe care am măsurat-o a fost localizarea drumurilor, dar nu am inclus aici și operația de umplere a granițelor cu geohashuri.
Aceasta se datorează faptului că această operație nu trebuie rulată de fiecare dată. Poate fi rulată o dată și utilizată de mai multe ori.
Deși nu este adesea necesar, este totuși important să luăm în considerare operația de precalculare a zonelor și umplerea granițelor cu geohashuri. Procesul de precalculare depinde de mai mulți factori:
Numărul și forma granițelor. Cu cât sunt mai multe granițe și cu cât acestea sunt mai complexe, cu atât operația va dura mai mult.
Precizia geohashului. Cât de precisă trebuie să fie localizarea noastră? Cu cât este mai precisă, cu atât va dura mai mult.
Cu toate că această precalculare ar putea fi costisitoare, ea este rulată relativ rar deoarece granițele nu se schimbă des și rerularea calculării lor poate fi făcută doar la nevoie. Dincolo de acest aspect, operațiunea regulată, cea în care găsim granița în interiorul căreia aparține fiecare drum, este rulată mult mai des deoarece drumurile se schimbă continuu. În sistemul nostru, de exemplu, această localizare se rulează pentru fiecare procesare de hartă.
Abordarea aceasta poate fi optimizată și mai mult aplicând abordarea opusă. Geohashurile care au acoperire completă în interiorul unei granițe pot fi reunite în geohashuri mai mari, simplificând astfel calculul în interiorul graniței. În cele din urmă, putem avea o soluție complet optimizată nevoilor proiectului, cu cel mai bun raport cost-performanță.
Figura 12 - Geohashuri optimizate
Deși geohashurile par a fi soluția potrivită pentru acest tip de problemă, trebuie luat în considerare și conținutul acestora. Densitatea drumurilor într-un geohash joacă un rol important. De exemplu, un geohash în centrul unui oraș are de obicei multe drumuri, în timp ce unul în zonele rurale poate avea mult mai puține. Acest aspect trebuie luat în considerare pentru a avea o operațiune de calcul echilibrată și pentru a profita pe deplin de abordarea Big Data. În cazul nostru, realizăm acest echilibru prin luarea în considerare a numărului de kilometri de drumuri dintr-un geohash.
Figura 13 - Distribuție dezechilibrată de date
Resursele alese pentru rularea procesului de localizare sunt, de asemenea, importante. Trebuie găsit un echilibru între timpul de rulare și costul resurselor. După cum se vede în Figura 14, pe baza datelor de test folosite pentru aceasta rulare, uneori cel mai bun rezultat se obține atunci când folosim mașini mai mici.
Figura 14 - Cost vs. timp de rulare
Realizările și perspectivele prezentate în acest articol sunt datorate contribuțiilor aduse de către Mihai Chintoanu. Expertiza și implicarea sa au adus o valoare semnificativă conținutului și concluziilor prezentate în această lucrare.