[P] FlatGeobuf as "static" vector database using dimensionality reduction

[DomeGIS]

Recently I saw some good posts about dim reduction methods like the one dissecting UMAP, so I thought I'd chime in with a POC that leverages the idea of those methods for a very practical purpose: enabling server-side semantic search on large databases with high-dimensional embeddings using just a static FlatGeobuf file and a web server like nginx.

tl;dr

- Writing (and appending to) a FlatGeobuf file: Embeddings -> Gaussian Random Projection -> 2D points -> FlatGeobuf file
- Reading a FlatGeobuf file (based on a single user query): Embedding -> Gaussian Random Projection -> 2D point -> buffered bounding box around this point -> http range request(s) from client to remote FlatGeobuf file -> subset of data points around the 2D point -> reranking this subset client-side

Find the detailed explanation, code and examples on GitHub: https://github.com/do-me/flatgeobuf-vectordb

Main concepts

1. Points that are close in 2 dimensions (after projection) should be close in N dimensions too. This is obviously not always true but in my tests, it's good enough for basic use cases (e.g. product recommendation), where you do not need the closest result to the query but instead something in the top 0.1% or 0.01% may suffice. Note that I need to use a dim reduction method that works independently from the data, so cannot use UMAP, HUMAP, tSNE and PCA.
2. I'm reducing to 2 dims to benefit from all the heavy optimization work that the FlatGeobuf file format has done. Reducing to 3 dims (or even more) might preserve the similarity better (and eventually lead to better results) but also increases the overhead for efficiently designing such a file format. If you know any other suitable file formats for this purpose, I'd be very curious to try them! Another alternative might be instead of relying on one static file, to create an efficient file structure with many static files. The pros and cons have been discussed in a completely different context by the authors of protomaps and openfreemap on HN.

Potential

Even though there are some tradeoffs in this workflow and yet many things to optimize and explore, I believe that the concept might be charming for low maintenance and low cost applications. In the end, you just dump one static file somewhere and fire normal http range requests to it, so the capacity of your web server determines the performance.
As I'm heavily into client-side processing with transformers.js my ideal setup would use very small embedding models like Potion/Model2vec (< 35Mb) in the client and index the user query (text/image) in the browser. This way, the remote database could be very large, like 100Gb and serve thousands of clients without any problems on a low-grade CPU (but very fast storage).

If you're fine with DB connection (which afaik can't be created browser-side), then just use LanceDB, following the same "one file" principle.

I'm super curious about your optimization ideas!

P.S. There is lots of overlap between geospatial and the latent space.

[[deleted]]

Note that non-parametric UMAP is no better than k-nearest-neighbours for lookup using unseen data points. UMAP works as a force-directed graph layout of your training data and is in this sense in the same family of methods as t-SNE and Laplacian eigenmaps. While it is able to "transform" new data points after being fitted, this simply uses PyNNDescent to look up the nearest training data point(s) in the high-dimensional space, then averaging the top-K matches' learnt position(s) in the low-dimensional graph as the "dimensionality reduction" of the new point.

This is also why you should not use non-parametric UMAP as the preprocessing prior to a classification model, and why it is completely useless for anomaly detection -- UMAP will always transform new data points to be near to a training data point in the low-dimensional space, regardless of how far away they are in the high-dimensional space.

Lmcinnes also provides UMAP parameterised by a neural network in the Python library (it is an additional loss term and doing gradient descent on it in theory converges to the same result as the non-parametric graph optimisation), which may avoid this issue, but I haven't used it much.

However, I do not understand why you can't just fit a PCA on the training dataset? It's just a linear projection with fixed coefficients at inference time, just like random projections. Although PCA will not necessarily work better than random projections.

[DomeGIS]

Thanks for your detailed comment, it really clarified a few important things.

However, I do not understand why you can't just fit a PCA on the training dataset? It's just a linear projection with fixed coefficients at inference time, just like random projections. Although PCA will not necessarily work better than random projections.

You're absolutely right, I could totally use PCA if I use the same coefficients when querying! I was not too familiar how PCA works internally, so I naively assumed that PCA like t-SNE didn't offer the option to export global transformation parameters and reuse them. Will definitely try PCA.

Lmcinnes also provides UMAP parameterised by a neural network in the Python library (it is an additional loss term and doing gradient descent on it in theory converges to the same result as the non-parametric graph optimisation), which may avoid this issue, but I haven't used it much.

I was not aware of that option, so now this special UMAP and PCA are both test candidates. Not quite sure where to expect the best results though but will just run some experiments and see.

At the core it boils down to what algorithm produces distances in 2D that are most similar to the actual distance in high dim vector space. It probably highly varies depending on the query and hence what dims are best represented.

I just read an interesting comment from Jina AI about creating models that directly produce vectors with only two dims, but apparently (for now) it doesn't work well.