4 ms·

I have a dumb question: isn't the the same set algorithms and technology we've needed to develop for geospatial search (given coordinates, find the nearest coor

I have a dumb question: isn't the the same set algorithms and technology we've needed to develop for geospatial search (given coordinates, find the nearest coordinates)? I remember reading about how Google maps did a very similar thing to figure out which points of interest to load based on your coordinates and zoom. Can't we repurpose that technology? Or did those bake in assumptions around being 2 dimensional (while this is highly dimensional?)

ninja3925 3y ago
The main problem is that the embeddings are getting larger and larger (1,000+ dimensions). The pressure is then on reducing memory use through techniques such as Product Quantization while not losing too much accuracy. Once this is done, the search heuristics are not difficult (find the cells to explore and return nearest neighbors).
softwaredoug 3y ago
Things get really weird in high dimensions. Orthogonality is expected, for example. Proximity is really rare. See: https://softwaredoug.com/blog/2023/02/28/probability-of-dot-product.html https://softwaredoug.com/blog/2023/02/28/probability-of-dot-...
pnathan 3y ago
Higher dimensional algorithms get very messy - see X-trees vs R-trees. E.g., KNN is very fast, if and only if you have a high performing R-tree query. so while the 2d algos might "fall out" of the sophisticated cases, the sophisticated cases will need to go in a different optimization direction.
pbadams 3y ago
Apart from the comments you've already gotten, another goal of geospatial systems is to support range queries (e.g. for the bounding box of the user's screen, what are all the businesses in that box). In higher dimensions range queries are mostly useless and the focus is on NN queries. But as the other comments have mostly said, it's mainly dimensionality and scale differences that drive the design differences (e.g. graphs end up working better than trees in high dimensions)

ninja3925 3y ago

The main problem is that the embeddings are getting larger and larger (1,000+ dimensions). The pressure is then on reducing memory use through techniques such as Product Quantization while not losing too much accuracy. Once this is done, the search heuristics are not difficult (find the cells to explore and return nearest neighbors).

softwaredoug 3y ago

Things get really weird in high dimensions. Orthogonality is expected, for example. Proximity is really rare. See: https://softwaredoug.com/blog/2023/02/28/probability-of-dot-product.html https://softwaredoug.com/blog/2023/02/28/probability-of-dot-...

pnathan 3y ago

Higher dimensional algorithms get very messy - see X-trees vs R-trees. E.g., KNN is very fast, if and only if you have a high performing R-tree query. so while the 2d algos might "fall out" of the sophisticated cases, the sophisticated cases will need to go in a different optimization direction.

pbadams 3y ago

Apart from the comments you've already gotten, another goal of geospatial systems is to support range queries (e.g. for the bounding box of the user's screen, what are all the businesses in that box). In higher dimensions range queries are mostly useless and the focus is on NN queries. But as the other comments have mostly said, it's mainly dimensionality and scale differences that drive the design differences (e.g. graphs end up working better than trees in high dimensions)