Vectorzoekopdrachten uitgelegd: hoe we miljoenen beelden matchen in seconden

De naald in een miljoen hooibergen

GeoPin’s referentiedatabase bevat miljoenen geotagde beelden op straatniveau die Nederland dekken. Wanneer je een foto uploadt, moeten we de visueel meest vergelijkbare beelden in die database vinden — en dat moet in milliseconden, niet in minuten. Dit is een vectorzoekprobleem, en het efficient oplossen ervan is een van de belangrijkste technische uitdagingen achter de dienst.

Wat zijn embeddings?

Een embedding is een numerieke representatie van data in een continue vectorruimte. In ons geval wordt elk beeld door het CosPlace-model omgezet in een lijst van 512 getallen (een 512-dimensionale vector). Deze getallen zijn individueel niet betekenisvol — je kunt niet naar dimensie 247 kijken en zeggen “dat vertegenwoordigt het aantal ramen in het beeld.” In plaats daarvan is de betekenis verdeeld over alle dimensies collectief.

De cruciale eigenschap van goed getrainde embeddings is dat vergelijkbare items dichtbij zijn in de vectorruimte. Twee foto’s genomen op hetzelfde kruispunt produceren vectoren die dicht bij elkaar liggen. Twee foto’s van tegenovergestelde uiteinden van het land produceren vectoren die ver van elkaar liggen. De embedding vertaalt visuele gelijkenis naar wiskundige nabijheid.

Beschouw het als volgt: als je op de een of andere manier een 512-dimensionale ruimte zou kunnen visualiseren (dat kan niet, maar ga even mee met de analogie), zouden alle foto’s van een bepaald Amsterdams grachtenpand een strakke cluster vormen. Foto’s uit dezelfde buurt zouden zich in de bredere omgeving bevinden. Foto’s uit een totaal andere stad zouden zich in een afgelegen regio van de ruimte bevinden.

Gelijkenis meten: cosinusgelijkenis

Gegeven twee embeddingvectoren hebben we een manier nodig om te kwantificeren hoe vergelijkbaar ze zijn. De standaardmaat is cosinusgelijkenis, die de cosinus berekent van de hoek tussen twee vectoren. Het resultaat loopt van -1 (tegengestelde richtingen) tot 1 (dezelfde richting), met 0 als indicatie van geen gelijkenis.

Omdat onze embeddings L2-genormaliseerd zijn (magnitude van 1), vereenvoudigt cosinusgelijkenis tot slechts het inproduct — het vergelijken van twee 512-dimensionale genormaliseerde vectoren vereist precies 512 vermenigvuldigingen en 511 optellingen. Voor genormaliseerde vectoren produceren cosinusgelijkenis en Euclidische afstand dezelfde rangschikking van dichtstbijzijnde buren, maar cosinusgelijkenis heeft de voorkeur omdat het zich richt op de richting van vectoren, wat beter aansluit bij hoe embeddings plaatsidentiteit coderen.

Het brute-force-probleem

Als onze database 1.000 beelden zou bevatten, zou het vinden van de dichtstbijzijnde buren triviaal zijn. Maar met miljoenen beelden vereist een brute-force-zoekopdracht ruwweg 2,5 miljard drijvende-kommaberekeningen per query. Dat schaalt niet fraai — verdubbel de database, verdubbel de querytijd. Dit is waar approximate nearest neighbor (ANN)-algoritmen essentieel worden.

Benaderde dichtstbijzijnde buren: precisie inruilen voor snelheid

Het inzicht achter ANN-algoritmen is dat we zelden de wiskundig exacte dichtstbijzijnde buren nodig hebben. Door een minimale benadering te accepteren, bereiken ANN-algoritmen dramatische versnellingen — het vinden van dichtstbijzijnde buren in logaritmische in plaats van lineaire tijd.

HNSW: Hierarchical Navigable Small World

Het ANN-algoritme dat onze zoekopdrachten aandrijft is HNSW (Hierarchical Navigable Small World). Het organiseert vectoren in een meerlagige graaf:

• Niveau 0 (onderste): Elk beeld is een knooppunt, verbonden met zijn dichtstbijzijnde buren. Dicht en precies, maar traag om te doorlopen.
• Niveau 1: Een willekeurige deelverzameling van beelden, verbonden met hun dichtstbijzijnde buren binnen de deelverzameling. IJler, waardoor grotere sprongen mogelijk zijn.
• Niveau 2 en hoger: Progressief kleinere deelverzamelingen die nog grotere sprongen mogelijk maken.

Om te zoeken begin je op het bovenste niveau en beweeg je gretig naar de queryvector toe. Op elk niveau, zodra je niet dichterbij kunt komen, daal je af en ga je verder met meer precisie. Op Niveau 0 ben je in de juiste buurt en verken je alleen lokaal.

Dit betekent dat het doorzoeken van 39 miljoen vectoren mogelijk slechts het bezoeken van een paar honderd knooppunten vereist — een dramatische verbetering ten opzichte van brute force.

Cloudflare Vectorize

GeoPin draait op de infrastructuur van Cloudflare, en we gebruiken Cloudflare Vectorize als onze vectordatabase. Deze keuze weerspiegelt ons architectuurprincipe om alles op een platform te houden voor eenvoud en prestaties.

Vectorize slaat onze vooraf berekende CosPlace-embeddings op samen met metadata (GPS-coordinaten, beeldidentificatoren, opnametijdstempels). Wanneer een query binnenkomt, voert het de ANN-zoekopdracht uit en retourneert de top-K dichtstbijzijnde buren met gelijkenisscores en metadata.

Belangrijke kenmerken: edge-deployment op het wereldwijde netwerk van Cloudflare voor query’s met lage latentie; metadatafiltering zodat zoekopdrachten beperkt kunnen worden tot specifieke regio’s of tijdsbereiken; en schaalbaarheid naarmate onze referentiedatabase groeit zonder dat we zelf infrastructuur hoeven te beheren.

Van vectormatch naar locatie

De uitvoer van de vectorzoekopdracht is een gerangschikte lijst van referentiebeelden, elk met een cosinusgelijkenisscore en GPS-coordinaten. Maar dit is niet het definitieve antwoord — het is de kandidaatset. Visueel vergelijkbare scenes kunnen op verschillende locaties bestaan, en daarom laat onze pijplijn op de vectorzoekopdracht een geometrische verificatie volgen met LightGlue om te bevestigen dat kandidaten dezelfde fysieke scene tonen.

Om een concreet gevoel van schaal te geven:

• Embeddinggrootte: 512 dimensies, 32-bit float = 2 KB per beeld
• Databasegrootte: Miljoenen embeddings = meerdere gigabytes aan vectordata
• Querytijd: Doorgaans minder dan 50 milliseconden voor top-100 ophaling
• Recall: HNSW behaalt circa 95%+ recall vergeleken met exacte zoekopdrachten

Vanaf het moment dat de embedding van je foto is berekend, wordt het relevante deel van Nederland geidentificeerd in een fractie van een seconde. De geometrische verificatie die de match bevestigt, kan vervolgens zijn rekenkracht richten op de meest veelbelovende kandidaten.

Vectorzoekopdrachten zijn geen glamoureuze technologie. Maar zonder zou de gehele pijplijn onpraktisch traag zijn. Het is de infrastructuur die realtime geolocatie op schaal mogelijk maakt.