5 ms·
Nobody has mentioned Approximate Nearest Neighbor search (aka vector search), which IMO, are fundamental data structures advancements. Basically given a set of
by softwaredoug 4y ago
Nobody has mentioned Approximate Nearest Neighbor search (aka vector search), which IMO, are fundamental data structures advancements.
Basically given a set of million (billion, trillion...) ~1000 valued vectors, and a query ~1000 valued vector, find the closest vector in the indexed set. This is "nearest neighbor" search and there have been increasingly more and more sophisticated approaches:
http://ann-benchmarks.com http://ann-benchmarks.com
https://haystackconf.com/us2022/talk-6/ https://haystackconf.com/us2022/talk-6/
And has spawned companies like Weaviate, Pinecone, etc etc (a half a dozen others)
- fzliu 4y agoMost commonly used ANN algorithms today are clever optimizations atop "old" data structures. DiskANN is a recent favorite: https://milvus.io/blog/2021-09-24-diskann.md https://milvus.io/blog/2021-09-24-diskann.md
- kokanee 4y ago"Most commonly used X today are clever optimizations atop old Y" is pretty much the story of technology, isn't it?
- RoyGBivCap 3y agoIt's lego all the way down to the clock cycle.
- marginalia_nu 4y agoWhat sort of dataset are you indexing that has trillion entries? That's 100,000 english wikipedias or 50 googles.
- lacker 3y agoThat's about the number of pixels in a 2-hour movie at 4k. Not too common yet, but once it's possible we're going to want to feed this amount of data into neural networks.
- marginalia_nu 3y agoUsing an approximate nearest neighbors search for this is just worse though. You can retrieve the exact information even faster. From an (x,y,t) coordinate, you can find the exact index in constant time
- yes_man 4y agoDumb example but still example from practical world. Your body (assuming you are a human) has trillions of cells. Each cell way more complicated than what a 1000-dimensional vector can represent, but maybe it could be a loose estimate of some properties in each cell. Now the algorithm could be about finding the most similar cell. Could be useful for finding e.g. other cancer cells based on properties in one cancer cell. Not that this is a practical example because we technically cannot index all cells in each body. But even if such an algorithm being studied today might be useful one day when we do capability to collect such data
- marginalia_nu 4y agoWhere are you going to store this data? It's dozens of petabytes.
- yes_man 4y agoShould theoretical research of data structures and algorithms have been capped at 1GB in 1980 because that was the biggest single hard drive available back then and you couldn’t store for example a 2GB dataset on a disk?
- marginalia_nu 4y agoNot at all, I'll still call out fantastic claims when I see them though.
- karpierz 4y agoGoogle has definitely indexed over a trillion pages.
- marginalia_nu 4y agoDo you have any sources for this claim? As far as I am aware Google doesn't publish any statistics about the size of its index, which no doubt varies.
- de_nied 4y agoOne application are LLMs. I've seen a project use Pinecone to enable "infinite context" for GPT-3.
- marginalia_nu 4y agoThis is still several orders of magnitude more items than the entire training corpus for all GPT models combined. I guess if you were to index individual codepoints in the training corpus, we'd start to see those volumes.
- travisjungroth 3y agoYou don't index the training data, but other data. It gives LLMs the medium-term memory that they're missing. Think of it like an accountant. Weights are all of their experience. Prompt is the form in front of them. A vector database makes it easier to find the appropriate tax law and have that open (in the prompt) as well. This is useful for people as well, like literally this example. But the LLM + vector combination is looking really powerful because of the tight loops.
- maerF0x0 4y agoThere's about 14B trades per year on the NYSE which i'm sure could represent 10x that in entities (buyer, seller, broker, etc) and could easily hit 1000x that in log lines. The shares per day is in the billions, so hitting 1T if each share is represented uniquely.
- marginalia_nu 4y agoYou don't typically use vector search for trade data though. It's already ridculously well structured. Assets have identifiers, parties and counterparties have IDs, etc. I'm not sure what nearest neighbors in a vector space would add.
- l33t233372 4y agoNonetheless it’s an example you asked for of a dataset with over a trillion entries.
- marginalia_nu 4y agoI asked which dataset they were indexing that was of this size, not whether any such dataset exists in other domains.
- captaincrowbar 3y agoI believe I hear the sound of a True Scotsman knocking at the door.
- marginalia_nu 3y agoMy exact words are still up there > What sort of dataset are you indexing that has trillion entries? It doesn't say > What sort of dataset has a trillion entries?
- perfmode 3y agoindex every photo taken in the past ten years (1.8 trillion per year) for each photo, extract and index SIFT vectors https://en.m.wikipedia.org/wiki/Scale-invariant_feature_transform https://en.m.wikipedia.org/wiki/Scale-invariant_feature_tran...
- chaxor 3y agoPerhaps one example would be 100 billion websites, but with a set of vectors for each website (chunked bert encoding, sum chunked glove vecs, whatever). Then you could have something like 3-100ish vectors for each website, which would be a few trillion vecs. I'm not in the we scraping/search area, so idk about the 100B website thing (other than it's Google order of size), but the encoding would take some mega amount of time depending on how it's done, hence the suggested sum of GloVe chunks (potentially doable with decent hardware in months) rather than throwing LLM on there (would take literal centuries to process).
- ukuina 3y agoFor context stuffing LLMs with small token limits(AKA Retriever Augmentation), you will need to break up each article in few-sentence chunks. You can get to a large number of these chunks very rapidly.