Hacker News Reader

Comment by tomasreimers | Hacker News Reader

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?)

View on HN

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-...

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)

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).

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.

Reply on news.ycombinator.com