geo
Geospatial Nearest Neighbour
Which store is actually nearest?
The same 'what is near me' question as the geohash, answered by a vector index.
A vector index is a nearest-neighbour structure over any space you can put a point in, and a map is one. Project latitude and longitude onto the unit sphere and a place becomes three numbers; the straight-line gap between two of them rises and falls exactly with the distance you would walk. Same seven places as the Store Locator, same question, and the answer comes back ranked and with no cell boundary in it.
The model
Place
A store, carried twice: as a geohash for the cell query, and as a point on the unit sphere.
- pk
- PLACE#<placeId>
Attributes: name (S), lat (N), lon (N), geohash (S), openUntil (S), GSI1PK (S), GSI1SK (S), position (L)
Access patterns
- SearchVectors · by-positionThe five nearest, ranked
The five closest places to a point, in order, with the distance as the score.
- Query · GSI1Everything in the geohash cell
The same question answered the usual way, by reading one geohash cell. Run it after the search and compare the two lists.
Design notes
Two dimensions do not fit in one sort key. Three fit in a vector.why
The Store Locator interleaves latitude and longitude into one string because a sort key is one dimension and a position is two. A vector index has no such limit: it takes as many dimensions as you declare. So the position does not have to be flattened at all, and once it is not flattened there is no cell, no prefix, and no boundary.
Why latitude and longitude are not the vectorwhy
Two naive attempts both fail. Cosine on a raw lat/long pair measures the angle that pair makes at the origin of a degree grid, a point off the west coast of Africa that means nothing, so two places on opposite sides of the world can score as identical. Euclidean on raw lat/long is closer to sane but distorts with latitude: a degree of longitude is 111 km at the equator and 66 km in Leeds, so a circle in degree space is an ellipse on the ground, and it tears completely at the antimeridian, where 179.9 east and 179.9 west are 22 km apart on the equator and 360 units away from each other in the grid. Neither is fixable by choosing a different distance function, because the problem is the space, not the metric.
Project to the unit sphere, and Euclidean is forcedmodelling
x = cos(lat)cos(lon), y = cos(lat)sin(lon), z = sin(lat), with both angles in radians. Every place is now a point on a sphere of radius one, and the straight-line gap between two of them, which is what EUCLIDEAN reports, is 2*sin(theta/2) for a central angle theta. That climbs without ever turning back as theta goes from zero to pi, so the order a Euclidean search returns is exactly the order of true great-circle distance. Nothing here is approximated. The score converts back: kilometres = 2 * 6371 * asin(score / 2), which on this seed agrees with haversine to within half a metre.
The cell returns the further place and misses the nearer onetrade-off
Run both patterns and read the two lists side by side. The search returns Briggate at 0.45 km, The Headrow at 0.48, Kirkgate Market at 0.53, Holbeck at 0.92 and Hyde Park at 2.24, which is the true order. The cell query returns four places and Holbeck is not among them, because Holbeck sits in gcwc while the phone sits in gcwf. It is the fourth-nearest and the cell cannot see it, while Hyde Park, two and a half times further away, comes back because it happens to share a prefix. That is the geohash's known edge case, and it is not an edge: at a 23 km cell, every query near a boundary has one. Reading one cell is the naive form of the pattern, though, and comparing a search against it flatters the search. The third run is what a service would actually ship.
Nine queries fix it, and cost nine queriestrade-off
The simplest correct form reads the query's cell and its eight neighbours, merges them, then sorts and filters the merged list by true distance in the application. Here that is gcwf plus gcw9, gcwc, gcwd, gcwe, gcwg, gcx1, gcx4 and gcx5. It finds Holbeck, and the five places that survive a five-kilometre filter are the same five the search returns, in the same order. So on the answer the geohash is not beaten. What it costs is nine requests instead of one, and 4.5 read units against the single cell's 0.5. They go out in parallel, so that is roughly one round trip rather than nine. Six of the nine come back empty and are still billed half a unit each, which is DynamoDB's floor rather than this engine's quirk: an empty Query still rounds up to 4 KB, and a GSI read is always eventually consistent, which halves it. Those six are not pure waste, because you cannot know a cell is empty without reading it and that is the completeness the single cell lacked. A seventh returns York from gcx4, 35 km away, read and paid for and discarded. Libraries like dynamodb-geo and H3 size a covering set to the radius instead of always reading nine; this is the form you can read, not the tightest one.
The cell size is the parameter you have to get rightmodelling
A four-character cell is 19.5 km north to south by 23.1 km east to west, so the nine together cover roughly 59 km by 69 km, which is how two shops in York end up in a query about Leeds. The number that governs the choice is not the block's span, though. The query point can sit anywhere inside the middle cell, so what nine cells guarantee to reach in every direction is one cell's shorter side, not three cells. Four characters guarantees 19.5 km, comfortably more than the five kilometres this run filters to. Five characters guarantees 2.9 km, which is not: on these seven shops it happens to return the same five, and for the same 4.5 units, but a query point a few hundred metres away inside that cell could miss something at 4 km and nothing would say so. Holding five kilometres there would take twenty-five cells, not nine. Six characters guarantees 0.6 km and loses both Holbeck at 0.92 km and Hyde Park at 2.24 km, so nine calls return three places where one call returned four. The bill does not move across any of this: nine calls is 4.5 units whatever they hold, because every one of them sits on the floor. What moves is the share of it buying nothing, six ninths to seven to eight, and whether the radius you advertise is one the key can honour. And that number is global. The same cell size serves the city centre and the moors, though one of them holds a thousand places per cell and the other holds none, so the count you get back is decided by where the caller happens to be standing. That is the geohash's real limitation rather than the boundary the single-cell run shows: nine cells fix a boundary, and nothing fixes one resolution chosen once for everywhere. A vector search is bounded by count instead of by geometry, which is the same trade read from the other end.
There is no radius, and there is no page twotrade-off
A search takes a TopK and nothing else. You cannot ask for everything within five kilometres, and if the five nearest branches are all in another county you will get them anyway with no hint that they are far. Filtering by score afterwards is your application's job, and it spends from a budget of at most a hundred results with no LastEvaluatedKey to continue from. The geohash has the opposite shape: it is bounded by geometry rather than by count, so a dense city centre returns everything and the moors return nothing. That is where a real radius comes from, and it is why the nine-cell run can honour five kilometres while the search cannot. Neither is the general answer, which is why both are on this table.
The index stores 32-bit copies, so the floor is under a metreoperations
A unit-sphere component sits between minus one and one, and a 32-bit float resolves a value that size to about one part in seventeen million, which is roughly 40 cm on the Earth's surface. Two doorways a few centimetres apart are the same point as far as this index is concerned. That is fine for finding a branch and wrong for anything surveying-grade, and it is a property of the vector index rather than of the projection: the base table still holds whatever precision you wrote.
Nothing here is a model, and the write path is arithmeticwhy
Three trigonometric calls turn a coordinate into this vector. There is no inference, no weights to ship, no cost per write and nothing to re-embed when a library version moves. That is the difference worth noticing: a vector index is a nearest-neighbour structure over a space, and whether that space came out of a neural network or out of cos and sin is not something the index knows or cares about.
Read it against
- Store Locator
The same seven places and the same question, answered twice: a geohash prefix on a sort key, and a nearest-neighbour search over the projected coordinates.
Taught in the course
- A different key for a different question - A secondary index re-keys your items so you can Query them on a new axis.
- A vector is just an attribute - A vector is a list of numbers on an item. An index is what makes it searchable.
- Three ways to be near - The metric is fixed at index creation, and the space your numbers came from has usually already chosen it.
The five closest places to a point, in order, with the distance as the score.
Choose an access pattern above, or build your own request. See what comes back and what it costs.
Write transactions, streams, tags and TTL are among the operations this browser build leaves out. dynoxide's native build has them.