[HN Gopher] Spann: Highly-Efficient Billion-Scale Approximate Ne...
___________________________________________________________________
Spann: Highly-Efficient Billion-Scale Approximate Nearest Neighbor
Search (2021)
Author : ksec
Score : 116 points
Date : 2024-11-02 20:02 UTC (1 days ago)
(HTM) web link (arxiv.org)
(TXT) w3m dump (arxiv.org)
| aaronblohowiak wrote:
| Kinda related, hopefully someone here in comments can help:
| what's your favorite precise nn search that works on arm Macs for
| in memory dataset; 100k times / 300 float32 dims per item ?
| Ideally supporting cosine similarity
|
| Faiss seems big to get going, tried n2 but doesn't seem to want
| to install via pip.. if anyone has a go-to I'd be grateful.
| Thanks.
| teaearlgraycold wrote:
| Why in memory? What are your latency requirements? I found
| pgvector to be surprisingly performant.
| ebursztein wrote:
| Try Usearch - it's really fast and under rated
| https://github.com/unum-cloud/usearch
| contravariant wrote:
| Out of interest is nearest neighbour even remotely effective
| with 300 dimensions?
|
| Seems to me that _unless_ most of the variation is in only a
| couple of directions, pretty much _no_ points are going to be
| anywhere near one another.
|
| So with cosine similarity you're either going to get low scores
| for pretty much everything or a basic PCA should be able to
| reduce the dimensionality significantly.
| ttul wrote:
| I think you are referring to what's known as the "curse of
| dimensionality," where as dimensionality increases, the
| distance between points tends to become more uniform and
| large. However, nearest neighbor search can still work
| effectively because of several key factors:
|
| 1. Real data rarely occupies the full high-dimensional space
| uniformly. Instead, it typically lies on or near a lower-
| dimensional manifold embedded within the high-dimensional
| space. This is often called the "manifold hypothesis."
|
| 2. While distances may be large in absolute terms, _relative_
| distances still maintain meaningful relationships. If point A
| is closer to point B than to point C in this high-dimensional
| space, that proximity often still indicates semantic
| similarity.
|
| 3. The data points that matter for a given problem often
| cluster in meaningful ways. Even in high dimensions, these
| clusters can maintain separation that makes nearest neighbor
| search useful.
|
| Let me give a concrete example: Consider a dataset of images.
| While an image might be represented in a very high-
| dimensional space (e.g., thousands of pixels), images of dogs
| will tend to be closer to other dog images than to images of
| cars, even in this high-dimensional space. The meaningful
| features create a structure that nearest neighbor search can
| exploit.
|
| Spam filtering is another area where nearest neighbor is used
| to good effect. When you know that a certain embedding
| representing a spam message (in any medium - email, comments,
| whatever), then if other messages come along and are
| _relatively_ close to that one, you may conclude that they
| are on the right side of the manifold to be considered spam.
|
| You could train a special model to define this manifold, but
| spam changes all the time and constant training doesn't work
| well.
| osigurdson wrote:
| >> as the "curse of dimensionality," where as
| dimensionality increases, the distance between points tends
| to become more uniform and large
|
| Since embeddings are the middle layer of an ANN, doesn't
| this suggest that there are too many dimensions used during
| training. I would think a training goal would be to have
| relatively uniform coverage of the space
| mhuffman wrote:
| >Out of interest is nearest neighbour even remotely effective
| with 300 dimensions?
|
| They are/can be anyway. I had data with 50,000 dimensions,
| which after applying dimensionality reduction techniques got
| it "down to" around 300! ANN worked very well on those
| vectors. This was prior to the glut of vector dbs we have
| available now, so it was all in-memory and used direct
| library calls to find neighbors.
| geysersam wrote:
| When dimensionality increases so does distance, but distance
| doesn't matter, we only care about relative distance compared
| to different points.
|
| If clustering works or not has nothing to do with the
| dimensionality of the space, and everything to do with the
| distribution of the points.
| peterldowns wrote:
| Annoy
| lmcinnes wrote:
| If you just want in-memory then PyNNDescent
| (https://github.com/lmcinnes/pynndescent) can work pretty well.
| It should install easily with pip, works well at the scales you
| mention, and supports a large number of metrics, including
| cosine.
| mhuffman wrote:
| Annoy is old, but works surprisingly well and is fast.
| wood_spirit wrote:
| And nowadays Spotify uses voyager
| https://engineering.atspotify.com/2023/10/introducing-
| voyage...
| mhuffman wrote:
| And also looks like full support for Mac ARM so, good info
| wood_spirit.
| visarga wrote:
| For just 100K items why don't you simply load the embeds into
| numpy and use cosine similarity directly? It's like 2 lines of
| code and works well for "small" number of documents. This would
| be exact NN search.
|
| Use approximate NN search when you have high volume of searches
| over millions of vectors.
| HDThoreaun wrote:
| 100k 300 dimension float 32s is less than a gigabyte. Just use
| numpy to do the NN search in memory.
| singhrac wrote:
| Maybe worth a (2021) tag.
| rbranson wrote:
| One of the only (the only?) commercial grade implementations was
| launched recently by us at PlanetScale:
|
| https://planetscale.com/blog/announcing-planetscale-vectors-...
| noahbp wrote:
| No ability to host offline, and for 1/8th CPU + 1GB RAM + 800
| GB storage, the price is $1,224/month?
|
| I'm sure it works great, but at that price point, I'm stuck
| with self-hosting Postgres+pgvector.
| TechDebtDevin wrote:
| Which works completely fine as long as you know how to manage
| your own db without getting wrecked!
|
| But yes, I it seems extereme. But it is also cheaper than
| hiring a dedicated postgres/db guy who will cost 5 to 10x
| more per month.
| mhuffman wrote:
| There are plenty of set-it-and-forget-it vector dbs right
| now, maybe too many![0]
|
| [0]https://news.ycombinator.com/item?id=41985176
| bddicken wrote:
| Just pointing out that what you're paying for is actually 3x
| these resources. By default you get a primary server and two
| replicas with whatever specification you choose. This is
| primarily for data durability, but you can also send queries
| to your replicas.
| 3abiton wrote:
| What's the advantage of NN over vectordb anymore? Are we
| losing some info when we embed?
| Sirupsen wrote:
| It works great. We've had SPANN in production since October of
| 2023 at https://turbopuffer.com/
| bratao wrote:
| SPANN is also implemented in the open-source Vespa.ai
| jbellis wrote:
| Actual SPANN or janky "inspired by SPANN" IVF with HNSW in
| front? Only real SPANN (with SPTAG, and partitioning designed
| to work with SPTAG) delivers good results. A superficial read
| of the paper LOOKS like you can achieve similar results by
| throwing off the shelf components at it, but it doesn't
| actually work well.
| uptownfunk wrote:
| Can we build an OS version of this and make it easy for solo dev
| to self host / roll their own?
| graycat wrote:
| Hmm, how to do a statistical hypothesis of nearest neighbor data?
| Distribution free?
| utopcell wrote:
| For anyone that wants to see how this compares on ann-
| benchmarks.com, the project is called 'sptag'.
___________________________________________________________________
(page generated 2024-11-03 23:01 UTC)