Vector Databases: A Technical Primer [pdf]
tge-data-web.nyc3.digitaloceanspaces.com
tge-data-web.nyc3.digitaloceanspaces.com
- A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challenge, https://arxiv.org/abs/2310.11703
- Survey of Vector Database Management Systems, https://arxiv.org/abs/2310.14021
- What are Embeddings, https://raw.githubusercontent.com/veekaybee/what_are_embeddi...
---
h/t: https://twitter.com/eatonphil/status/1745524630624862314 and https://twitter.com/ChristophMolnar/status/17457316026829826...
- Wikipedia article: https://en.wikipedia.org/wiki/Vector_database
- Vector Database 101: https://zilliz.com/learn/introduction-to-unstructured-data
- ANN & Similarity search: https://vinija.ai/concepts/ann-similarity-search/
- Distributed database: https://15445.courses.cs.cmu.edu/fall2021/notes/21-distribut...
Available as an annotated presentation + an optional 38 minute video.
If all your vectors have the same 2-norm, the cosine similarity of two vectors is a monotonic function of their euclidean distance (i.e. the minimum in one measure will be the minimum in the other).
If all your vectors don't have the same norm, where's the sense in projecting them onto the unit sphere and measuring the angle between them? You're throwing away important information about the embedding.
Could anyone explain?
In semantic search the magnitude of vectors isn’t relevant - if you needed a measure that took magnitude into account than Euclidean would make sense. E.g. image embeddings based on pixel intensity.
There is other aspect: if all vectors are normalized then cosine distance is just dot product. It is faster to calculate than euclidean distance.
Additionally, the scale of q (the query) is constant across any given search, so might as well normalize q; the results won't change.
Then the only question is whether the scale of v matters... It, again, doesn't tell us anything about the relationship between q and v. So, might as well normalize... And then we are just doing cosine similarity.
Think of partitioning the space by taking random hyperplanes. This can be computed by computing the dot product of the normal to the plane with any given point to see which side of the plane the point is on.
For two points that are very close to each other in Euclidean distance, the chance that a random hyperplane gets right in the middle of them is very low. This is, of course, the angle between as measured from the origin, but that angle gets very small the closer the two points are to each other, in Euclidean norm, and the further they are from the origin. By bisecting the space randomly and seeing which side points are on, we get a decent hashing function, binning similar points together.
Now, a point could be very close the origin and have a small angle to another point very far from the origin but, in some sense, there needs to be a conspiracy for this to happen. If you assume some kind of random distribution of points in D dimensional space, drawn in some sort of uniform like distribution in the D dimensional hyper cube or hyper sphere, the chances that a point will be very near the origin go down, as does the chance it'll lie in a thin cone within some other point.
I believe the basic assumption here is that independent features will be randomly distributed where as correlated features will be clumped together (in Euclidean distance). The randomness pushes unrelated points away from the origin and gives decreasing probability that the angle between them is low.
If points aren't random enough, maybe many of them are very close to the origin while others aren't, or maybe there's some other dependence that causes problems, then this could foil the hyperplane trick.
I believe I heard this basic argument from a talk on locality-sensitive hashing [0]. I think I have the basic intuition, but maybe that talk will be more enlightening.
I've recently been using Simon Willison's (hi simonw) excellent `llm` tool that can help with embeddings, and it takes the simplest approach possible: just store embeddings in SQLite with a few UDFs for calculating distance etc.
The simplicity of that approach is very appealing, but presumably at some level of traffic+data an application will outgrow it and need a more specialized database. Does anyone have a good intuition for where that cutoff might be?
That’s maybe 1kLOC so I didn’t need an external one after all.
The best option by far I know of is turbopuffer.com , which is like 100x cheaper than pinecone and seems to actually scale.
Since it's not listed in the suggested vector dbs section of the slides, wanted to lob it in as a solid suggestion :)
https://github.com/google-research/google-research/blob/mast...
The course is a mix of theory and demos discussing some of the underlying concepts of Vectors, Vector Databases, Indexing, Search Similarity and ending with demos specifically for Pinecone and Weaviate databases.
https://www.udemy.com/course/vector-databases-deep-dive/?cou...
I already have a Udemy account so when I went to checkout and logged in it said the promo was for new users only. But I went back to the course page again and reloaded the page so that I was logged in and then I was able to buy it with the coupon applied.
This is the step that introduces, rather subtly and sometimes almost ignorably, human judgement into what otherwise feels like a very automated and "it's just math" system.
Let's take audio. What features will you select from it to make your N-dimensional vector? An easy answer might appear to be "as many as possible". However, your first problem is that you may not have access to feature characterization even for just the features you can trivially name. Your second problem is that without deep knowledge of the domain, you may not even be aware of potential features that you should probably be using. Your third problem is that even with deep knowledge of the domain, you may still be unaware of potential features that you probably should be using.
A practical example may help. Perhaps you're a fan of Reichian phase-shifting minimalist music. You (indirectly) interrogate a vector database to find music similar to a canonical piece from this genre (say, Piano Phase). The database uses many audio & music related features, including but not limited to: dominant frequency, note onset intervals, volume, frequency-distribution-based timbral characteristics, apparent root notes and scales etc etc etc.
Unfortunately for you, the feature set in the database does not include "note-to-note intervals over time is constant". Your query will manage to find things that are timbrally, harmonically, melodically and rythmically similar, but it will be by sheer good luck that any of them share the key characteristic: steady changes in the relative phase of two different (or the same) melodic lines.
This is just one example. It's not hard to cook up equivalents for visual, textual, numerical ... any data at all.
Now of course, none of this makes vector databases and feature classification useless. It does mean that when you do or do not find match patterns in a given data set, one of the early questions you need to ask yourself is whether the feature set has any strong guarantee of being complete, and if not, how it may need to be expanded.
Note: current state of the art text to vector models like E5-Mistral (note: very different from original E5) don’t even require human curation in the dataset
I give you an audio file (let's say just regular old PCM wav format). You cannot do anything with this without making some decisions about what happens next to the data. For audio, you're very minimally faced with the question of whether to do a transform into the frequency domain. If you don't do that, there's a ton of feature classification that can never be done. No audio to vector model can make that sort of decision for itself - humans have to make the possible.
Raw inputs are suitable for some things, but essentially E5 is just one that has already had a large number of assumptions built into it that happen to give pretty good results. Nevertheless, were you interested for some weird reason in a very strange metric of text similarity, nothing prebuilt, even E5, is going to give that to you. Let's look at what E5 does:
> The primary purpose of embedding models is to convert discrete symbols, such as words, into continuous-valued vectors. These vectors are designed in such a way that similar words or entities have vectors that are close to each other in the vector space, reflecting their semantic similarity.
This is great, but useful for only a particular type of textual similarity consideration.
And oh, what's this:
> However, the innovation doesn’t stop there. To further elevate the model’s performance, supervised fine-tuning was introduced. This involved training the E5 embeddings with labeled data, effectively incorporating human knowledge into the learning process. The outcome was a consistent improvement in performance, making E5 a promising approach for advancing the field of embeddings and natural language understanding.
Hmmm ....
Anyway, my point still stands: choosing how to transform raw data into "features" is a human activity, even if the actual transformation itself is automated.
> Unlike existing methods that often depend on multi-stage intermediate pre-training with billions of weakly-supervised text pairs, followed by fine-tuning with a few labeled datasets, our method does not require building complex training pipelines or relying on manually collected datasets… We leverage proprietary LLMs to generate diverse synthetic data for hundreds of thousands of text embedding tasks across nearly 100 languages.
It’s true that ultimately there’s a judgement call (what does “distance” mean?), but I think the original post far overcomplicates what’s standard practice today.
You cannot determine frequencies from audio PCM data. If you want to build a vector database of audio, with frequency/frequencies as one of the features, at the very least you will have to arrange for a transform to the frequency domain. Unless you claim that a system is somehow capable of discovering fourier's theorem and implementing the transform for itself, this is a necessary precursor to any system being able to embed using a vector that includes frequency considerations.
But ... that's a human decision because humans think that frequencies are important to their experience of music. A person who totally deaf, however, and thus has extremely limited frequency perception, can (often) still detect rythmic structure due to bone conduction. Such a person who was interested in similarity analysis of audio would have no reason to perform a domain transform, and would be more interested in timing correlations that probably could be fully automated into various models as long as someone remembers to ensure that the system is time-aware which is, again, just another particular human judgement regarding what aspects of the audio have significance.
I just read the E5 Mistral paper. I don't see anything that contradicts my point, which wasn't about the need for human labelling, but about the need for human identification of significant features. In the case of text, because of the way languages evolve, we know that a semantic-free character-based analysis will likely bump into lots of interesting syntactic and semantic features. Doing that for arbitrary data (images, sound, air pressure, temperature) lacks any such pre-existing reason to treat the data in any particular way.
Consider, for example, if the "true meaning" of text was encoded in a somewhat Kaballah-esque type scheme, in which far distance words and even phonemes create tangled loops of reference and meaning. Even a system like E5 Mistral isn't going to find that, because that's absolutely not how we consider language to work, and thus that's not part of the fundamentals of how even E5 Mistral operates.
Understanding audio with inputs in the frequency domain isn’t required for understanding frequencies in audio.
A large enough system with sufficient training data would definitely be able to come up with a Fourier transform (or something resembling one), if encoding it helped the loss go down.
> In computer vision, there has been a similar pattern. Early methods conceived of vision as searching for edges, or generalized cylinders, or in terms of SIFT features. But today all this is discarded. Modern deep-learning neural networks use only the notions of convolution and certain kinds of invariances, and perform much better.
Today’s diffusion models learn representations from raw pixels, without even the concept of convolutions.
Ditto for language - as long as the architecture is 1) capable of modeling long range dependencies and 2) can be scaled reasonably, whether you pass in tokens, individual characters, or raw ASCII bytes is irrelevant. Character based models perform just as well (or better than) token/word level models at a given parameter count/training corpus size - the main reason they aren’t common (yet) is due to memory limitations, not anything fundamental.
For further reading, I’d recommend literature on transformer circuits for learning arithmetic without axioms: https://www.lesswrong.com/posts/CJsxd8ofLjGFxkmAP/explaining...
However, I do love several of the pieces by Marc Mellits, check out "Real Quiet plays the music of Marc Mellits". All rather short, but some totally lovely.
You may enjoy an 80's album by Andrew Poppy, in particular the track "The Object is a Hungry Wolf".
Do be sure to check "Shift" by Chris Hughes, which are re-instrumentations of several early Reich pieces including Piano Phase.
It's quite different in many ways from Mf18M, and you may have heard it, but I adore "The Chairman Dances" by John Adams. It couples the "chugging along" of Mf18M with much less minimalist melodic and harmonic structures. YMMV.
I'm sure I am going to remember a bunch more after I send this, so check back here in a couple of days, and I'll reply again with any extras.
Do you have any "similars" ?
welcome any PRs
Though it looks like S3 has the same problem: https://news.ycombinator.com/item?id=38876761
There's precedent for this elsewhere though - sites on a x.github.io subdomain have special treatment here: https://news.ycombinator.com/from?site=lfranke.github.io
Things like mentioning they’re clustered by meaning and optimized for analytics are questionable.
The clustering depends on the embedding you calculate. If you think that the embedding is a good semantic approximation of the data then maybe this is a fine way of thinking about it. But it’s not hard to imagine embeddings that may violate this — eg if I use an audio file and a text file that are identical in meaning through the same embed process, unless it is multimodal they will likely be distant in the embedding vector space.
I fully expect to see embeddings that put things close together in the vector space based on utilization rather than semantic similarity. If I’m creating a recommender system, I don’t want to group different varieties of one off purchases closely. For instance, the most semantically similar flight is going to be another fight to the same destination at a different time or a flight to a nearby airport. But I would want to group hotels often purchased by people who have previously bought the flight.
Vector databases also allow you to provide extra dimensionality into the data, like time awareness. Nothing is forcing you to use a vector that encodes semantic meaning.
And from this, you can see that we’re optimized for lookups or searches based on an input vector. This is not analogous to OLAP queries. This is more akin to elasticsearch than snowflake. If you are using a vector database thinking it’s going to give you reporting or large scale analytics on the vector space afaik there isn’t a readily available offering.
edit: it seems like calculating embeddings would be something an ML algorithm would do but then, again, you have to train that one first. ...it's training all the way down.
I think in 10y we will see retail systems heavily utilizing vector dbs and many embedding as a service products that take into account things like conversion. In this model you can add metadata about products to the vector db and direct program flow instead of querying back out to one or more databases to retrieve relevant metadata.
They’ll also start to enable things like search via image for features like “show us your favorite outfit” pulling up a customized wardrobe based on individual items extracted from the photo and run through the embedder.
Just one of many ways these products will exist outside of RAG. I think we’ll actually see a lot of the opposite — GAR.
"Use HNSW or Annoy for very large datasets where query speed is more important than precision": Graph-based methods have huge memory overhead and construction cost, and they aren't practical for billion-scale datasets. Also, they will usually be more accurate and faster than IVF techniques (as you would need to visit a large number of IVF cells to get comparable accuracy), though IVF can scale to trillion-sized databases without much overhead yet with reasonable speed/accuracy tradeoffs unlike other techniques. I'd say "use for medium-scale datasets where query speed is important, yet high accuracy is still desired and flat/brute-force indexing is impractical".
Also, distance comparisons are usually of the "ADC" (asymmetric distance comparison) form: the query vector is in full floating point format, and vectors, if quantized/compressed in the database, are effectively decompressed and compared in the full floating point domain. This is true even with PQ, as the distance between the query vector subspaces with each of the 2^n PQ codes for the same subspace are precomputed before comparison (and then the distance computation becomes a lookup-add based on the precomputed distance tables).
LSH techniques unlike PQ are more accurately described as an indexing technique, since the buckets into which vectors are placed are based on their encoding (via hashing/binarization) and are fully compared in that space.
For Go I recently started building chromem-go, inspired by the Chroma interface: https://github.com/philippgille/chromem-go
It's neither advanced nor for scale yet, but the RAG demo works.
Disclaimer: I'm the primary author of txtai.
I suspect the main downsides would be increased CPU usage and having to load vectors to RAM all the time. However, for small projects with low RPS you could probably get away without a special database?
Does anyone know of any benchmarks where they compare vector databases to a plain linear search? How they scale in regards to increased vector count and RPS, etc.
Yes.
>doing an exact search with 100k vectors takes about 1 second.
The speed can depend on the language/runtime of your choice and the number of dimensions. What language/runtime did you use, how many dimensions in a vector? (I heard too many dimensions for vector search is an overkill)
From my https://rare-technologies.com/performance-shootout-of-neares... benchmark of kNN libs:
"Brute force doesn’t care about the number of neighbours, so its performance is 679ms/query regardless of “k”. When run in batch mode (issuing all 100 queries at once), average query time drops to 354ms/query."
This was 500 dimensions over a 3.7M dataset (the English Wikipedia), in 2014. So, ~700ms/search, or half that if you can batch several searches together at once. YMMV.
You could maybe use Cube for euclidean space search, but you're better off using optimized algorithms for embedding space search.
This article covers the advantages of semantic search over keyword search - https://medium.com/neuml/getting-started-with-semantic-searc...
I've had Weaviate return a dog given a human as input when doing an image similarity search, so I was wondering if there's some way to improve the results or whether I'm barking up the wrong tree.
For your use-case, it should be pretty simple. You could use a CNN and train it, or use YOLO, Deepface, or other face detection algos, then within the face, find the hair and find the skin.
From there you can use a vector database to get the colors that resemble other inputs, or you can use a simple CNN to classify the hair and skin to the closest label.
The approaches increase in complexity. It also allows for dataset bootstrap:
Let's say you want to classify cats by breed. You could start by embedding images and text descriptors and distance-matching the embedded descriptors to the images. This gives you a dataset that might be 90% correct; you can then clean it up, which would be easier to do than manually labelling it. Based on that improved dataset, you can train a custom embedding for the labels or a classification layer on top of the image embedding network.
[1] RagTag - https://ragtag.weaveapi.com