Pricing  Docs  Learn  Company  Contact  We're hiring! Log In  Sign Up Free  Product Quantization: Compressing high- dimensional vectors by 97%  Faiss: The Missing Manual  Chapters:  1. Introduction to Facebook  AI Similarity Search (Faiss)  2. Nearest Neighbor  Indexes for Similarity Search  3. Locality Sensitive  Hashing (LSH): The Illustrated Guide  4. Random Projection for  Locality Sensitive Hashing  5.

Product Quantization  What is Quantization How Product Quantization Works PQ Implementation in Faiss References  6. Hierarchical Navigable Small Worlds (HNSW)  7. Composite Indexes and the Faiss Index Factory  Share:  Pinecone lets you add vector search to applications without knowing anything about algorithm optimizations, and it’s free to try. However, we know you like seeing how things work, so enjoy learning about memory-efficient search with product quantization! Vector similarity search can require huge amounts of memory. Indexes containing 1M dense vectors (a small dataset in today’s world) will often require several GBs of memory to store. The problem of excessive memory usage is exasperated by high- dimensional data, and with ever-increasing dataset sizes, this can very quickly become unmanageable.

Product quantization (PQ) is a popular method for dramatically compressing high-dimensional vectors to use 97% less memory, and for making nearest-neighbor search speeds 5.5x faster in our tests. A composite IVF+PQ index speeds up the search by another 16.5x without affecting accuracy, for a whopping total speed increase of 92x compared to non-quantized indexes. In this article, we will cover all you need to know about PQ: How it works, pros and cons, implementation in Faiss, composite IVFPQ indexes, and how to achieve the speed and memory optimizations mentioned above.

Product Quantization for Vector Similarity Search (+ Python)  Watch on  What is Quantization  Quantization is a generic method that refers to the compression of data into a smaller space.

I know that might not make much sense — let me explain. First, let’s talk about dimensionality reduction — which is not the same as quantization. Let’s say we have a high-dimensional vector, it has a dimensionality of 128 . These values are 32-bit floats in the range of 0.0 -> 157.0 (our scope  S ).

Through dimensionality reduction, we aim to produce another, lower-dimensionality vector. Dimensionality reduction reduces the dimensionality  D  of vectors, but not the scope S.  On the other hand, we have quantization. Quantization does not care about dimensionality  D . Instead, it targets the potential scope of values.

Rather than reducing  D , we reduce  S . Quantization reduces the scope S of possible vectors. Note that with pre-quantization the scope is typically infinite.

There are many ways of doing this. For example, we have clustering. When we cluster a set of vectors we replace the larger scope of potential values (all possible vectors), with a smaller discrete and symbolic set of centroids.

And this is really how we can define a quantization operation. The transformation of a vector into a space with a finite number of possible values, where those values are symbolic representations of the original vector. Just to make it very clear, these symbolic representations vary in form.

They can be centroids as is the case for PQ, or binary codes like those produced by LSH. Why Product Quantization? Quantization is primarily used to reduce the memory footprint of indexes — an important task when comparing large arrays of vectors as they must all be loaded in memory to be compared. PQ is not the only quantization method that does this, however — but other methods do not manage to reduce memory size as effectively as PQ. We can actually calculate memory usage and quantization operation complexity for PQ and other methods like so:  kmeans = kD PQ = mk^*D^* = k^{1/m}D  We know that  D  represents the dimensionality of our input vectors, but k  and  m  may be new. k  represents the total number of centroids (or codes) that will be used to represent our vectors. And  m  represents the number of subvectors that we will split our vectors into (more on that later). (A ‘code’ refers to the quantized representation of our vectors)  Memory usage (and complexity) vs dimensionality using k=2048 and m=8.

The problem here is that for good results, the recommended  k  value is of  2048  (211) or more[1]. Given a vector dimensionality of  D , clustering without PQ leaves us with very high memory requirements and complexity:  Operation  Memory and complexity  k-means  kD = 2048×128 = 262144  PQ  mk*D* = (k^(1/m))×D = (2048^(1/8))×128 = 332  means_compare.md hosted with ❤ by GitHub  view raw  Given an m value of  8 , the equivalent memory usage and assignment complexity for PQ is significantly lower — thanks to the chunking of vectors into subvectors and the subquantization process being applied to those smaller dimensionalities  k*  and  D* , equal to  k/m  and  D/m respectively. A second important factor is quantizer training. Quantizers require datasets that are several times larger than k for effective training, that is without product subquantization. Using subquantizers, we only need several multiples of  k* (which is k/m)  — this can still be a large number — but it can be significantly reduced. How Product Quantization Works  Let’s work through the logic of PQ.

We would usually have many vectors (all of equal length) — but for the sake of simplicity, we will use a single vector in our examples. In short, PQ is the process of:  Taking a big, high-dimensional vector,  Splitting it into equally sized chunks — our subvectors,  Assigning each of these subvectors to its nearest centroid (also called reproduction/reconstruction values),  Replacing these centroid values with unique IDs — each ID represents a centroid  High-level view of PQ: Take a big vector, split it into subvectors, assign each to its nearest centroid value, and replace the  centroid value with its unique ID — producing a tiny vector of IDs. At the end of the process, we’ve reduced our highly dimensional vector — that requires a lot of memory — to a tiny vector of IDs that require very little memory. Our vector is of length D 12.

We start by splitting this vector into  m subvectors like so:  Here we are splitting our high-dimensional vector x into several subvectors u_j. x = [1, 8, 3, 9, 1, 2, 9, 4, 5, 4, 6, 2]  m = 4 D = len(x) # ensure D is divisable by m assert D % m == 0 # length of each subvector will be D / m (D* in notation) D_ = int(D / m)  In[1]:  In[2]:  In[3]:  # now create the subvectors u = [x[row:row+D_] for row in range(0, D, D_)] u  Out[3]:  [[1, 8, 3], [9, 1, 2], [9, 4, 5], [4, 6, 2]]  We can refer to each subvector by its position  j . For the next part, think about clustering. As a random example, given a large number of vectors we can say “I want three clusters” — and we then optimize these cluster centroids to split our vectors into three categories based on each vector’s nearest centroid.

For PQ we do the same thing with one minor difference. Each subvector space (subspace) is assigned its own set of clusters — and so what we produce is a set of clustering algorithms across multiple subspaces. In[4]:  k = 2**5 assert k % m == 0 k_ = int(k/m) print(f"{k=}, {k_=}")  Out[4]:  k=32, k_=8  In[5]:  from random import randint  Each of our subvectors will be assigned to one of these centroids. In PQ terminology these centroids are called reproduction values and are represented by  cⱼ,ᵢ  where  j  is our subvector identifier, and  i identifies the chosen centroid (there are k* centroids for each subvector space j). Our subvectors are replaced with a specific centroid vector — which can then be replaced with a unique ID specific to that  centroid vector. In[6]:  def euclidean(v, u):     distance = sum((x - y) ** 2 for x, y in zip(v, u)) ** .5     return distance  def nearest(c_j, u_j):     distance = 9e9     for i in range(k_):         new_dist = euclidean(c_j[i], u_j)         if new_dist < distance:             nearest_idx = i             distance = new_dist     return nearest_idx  In[7]:  ids = [] for j in range(m):     i = nearest(c[j], u[j])     ids.append(i) ids  Out[7]:  [1, 1, 2, 1]  When we process a vector with PQ, it is split into our subvectors, those subvectors are then processed and assigned to their nearest (sub)cluster centroids (reproduction values). Rather than storing our quantized vector to be represented by the  D* - dimensional centroids, we replace it with a centroid ID. Every centroid cⱼ,ᵢ  has its own ID, which can later be used to map those ID values back to the full centroids via our codebook  c .

In[8]:  q = [] for j in range(m):     c_ji = c[j][ids[j]]     q.extend(c_ji)  In[9]:  q  Out[9]:  [1, 7, 7, 6, 3, 6, 7, 4, 4, 3, 9, 6]  With that, we have compressed a 12-dimensional vector into a 4- dimensional vector of IDs. We have used a small dimensionality here for the sake of simplicity, and so the benefits of such a technique may not be inherently clear. Let’s switch from our original 12-dimensional vector of 8-bit integers to a more realistic 128-dimensional vector of 32-bit floats (as we will be using throughout the next section). We can find a good balance in performance after compression to an 8-bit integer vector containing just eight dimensions. Original: 128×32 = 4096 Quantized: 8×8 = 64  That’s a big difference — 64x! PQ Implementation in Faiss  So far we’ve worked through the logic behind a simple, readable implementation of PQ in Python. Realistically we wouldn’t use this because it is not optimized and we already have excellent implementations elsewhere.

Instead, we would use a library like Faiss — or a production-ready service like Pinecone. We’ll take a look at how we can build a PQ index in Faiss, and we’ll even take a look at combining PQ with an Inverted File (IVF) step to improve search speed. Faiss - Vector Compression with PQ and IVFPQ (i…  Watch on  Before we start, we need to get data. We will be using the Sift1M dataset.

It can be downloaded and opened using this script:  In[1]:  import shutil import urllib.request as request from contextlib import closing  # first we download the Sift1M dataset with closing(request.urlopen('ftp://ftp.irisa.fr/local/texmex/corpus/sift.tar.gz'     with open('sift.tar.gz', 'wb') as f:         shutil.copyfileobj(r, f)  In[2]:  import tarfile  # the download leaves us with a tar.gz file, we unzip it tar = tarfile.open('sift.tar.gz', "r:gz") tar.extractall()  In[3]:  import numpy as np  # now define a function to read the fvecs file format of Sift1M dataset def read_fvecs(fp):     a = np.fromfile(fp, dtype='int32')     d = a[0]     return a.reshape(-1, d + 1)[:, 1:].copy().view('float32')  In[4]:  # data we will search through wb = read_fvecs('./sift/sift_base.fvecs')  # 1M samples # also get some query vectors to search with xq = read_fvecs('./sift/sift_query.fvecs') # take just one query (there are many in sift_learn.fvecs) xq = xq[0].reshape(1, xq.shape[1])  In[5]:  xq.shape  Out[5]:  (1, 128)  In[7]:  wb.shape  Out[7]:  (1000000, 128)  Now let’s move onto our first index: IndexPQ. IndexPQ  Our first index is a pure PQ implementation using IndexPQ. To initialize the index we need to define three parameters. In[2]:  import faiss  D = xb.shape[1] m = 8 assert D % m == 0 nbits = 8  # number of bits per subquantizer, k* = 2**nbits index = faiss.IndexPQ(D, m, nbits)  We have our vector dimensionality  D , the number of subvectors we’d like to split our full vectors into (we must  assert  that  D  is divisible by m ).

Finally, we include the nbits parameter. This defines the number of bits that each subquantizer can use, we can translate this into the number of centroids assigned to each subspace as  k_ = 2**nbits . An nbits  of 11 leaves us with  2048  centroids per subspace. Because we are using PQ, which uses clustering — we must train our index using our xb dataset. c = []  # our overall list of reproduction values for j in range(m):     # each j represents a subvector (and therefore subquantizer) position     c_j = []     for i in range(k_):         # each i represents a cluster/reproduction value position *inside* each subspace j         c_ji = [randint(0, 9) for _ in range(D_)]         c_j.append(c_ji)  # add cluster centroid to subspace list     # add subspace list of centroids to overall list     c.append(c_j)  Copy link  Copy link  In[3]:  index.is_trained  Out[3]:  False  In[4]:  index.train(xb)  # PQ training can take some time when using large nbits  And with that, we can go ahead and add our vectors to the index and search . In[6]:  In[7]:  dist, I = index.search(xq, k)  %%timeit index.search(xq, k)  Out[7]:  1.49 ms ± 49.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops  each)  From our search, we will return the top  k  closest matches (not the same  k  used in earlier notation). Returning our distances in  dist , and the indices in  I .

We can compare the recall performance of our  IndexPQ  against that of a flat index — which has ‘perfect’ recall (thanks to not compressing vectors and performing an exhaustive search). In[8]:  In[9]:  l2_index = faiss.IndexFlatL2(D) l2_index.add(xb)  %%time l2_dist, l2_I = l2_index.search(xq, k)  Out[9]:  CPU times: user 46.1 ms, sys: 15.1 ms, total: 61.2 ms Wall time: 15 ms  In[10]:  sum([1 for i in I[0] if i in l2_I])  Out[10]:  50  We’re getting 50% which is a reasonable recall if we are happy to sacrifice the perfect results for the reduced memory usage of PQ. There’s also a reduction to just 18% of the flat search time — something that we can improve even further using IVF later.

Lower recall rates are a major drawback of PQ. This can be counteracted somewhat by using larger  nbits  values at the cost of slower search times and very slow index construction times. However, very high recall is out of reach for both PQ and IVFPQ indexes. If higher recall is required another index should be considered. How does IndexPQ compare to our flat index in terms of memory usage? In[11]:  import os  def get_memory(index):     # write index to file     faiss.write_index(index, './temp.index')     # get file size     file_size = os.path.getsize('./temp.index')     # delete saved index     os.remove('./temp.index')     return file_size  In[12]:  # first we check our Flat index, this should be larger get_memory(l2_index)  Out[12]:  256000045  In[13]:  # now our PQ index get_memory(index)  Out[13]:  4131158  Memory usage using IndexPQ is — put simply — fantastic, with a memory reduction of 98.4%. It is possible to translate some of these preposterous performance benefits into search speeds too by using an IVF+PQ index.

IndexIVFPQ  To speed up our search time we can add another step, using an IVF index, which will act as the initial broad stroke in reducing the scope of vectors in our search. After this, we continue our PQ search as we did before — but with a significantly reduced number of vectors. Thanks to minimizing our search scope, we should find we get vastly improved search speeds. Let’s see how that works. First, we initialize our IVF+PQ index like so:  In[14]:  vecs = faiss.IndexFlatL2(D)  nlist = 2048  # how many Voronoi cells (must be >= k* which is 2**nbits) nbits = 8  # when using IVF+PQ, higher nbits values are not supported index = faiss.IndexIVFPQ(vecs, D, nlist, m, nbits) print(f"{2**nbits=}")  # our value for nlist  Out[14]:  2**nbits=256  We have a new parameter here,  nlist  defines how many Voronoi cells we use to cluster our already quantized PQ vectors (learn more about IndexIVF here). You may be asking, what on earth is a Voronoi cell — what does any of this even mean?

Let’s visualize some 2D ‘PQ vectors’:  2D chart showing our reconstructed ‘PQ’ vectors. However, in reality, we would never use PQ for 2D vectors as there is  simply not enough dimensionality for us to split into subvectors and subquantization.

Let’s add some Voronoi cells:  2D chart showing our quantized ‘PQ’ vectors that have now been assigned to different Voronoi cells via IVF. At a high level, they’re simply a set of partitions.

Similar vectors are assigned to different partitions (or cells), and when it comes to search — we introduce our query vector xq and restrict our search to the nearest cell:  IVF allows us to restrict our search to only vectors that have been assigned nearby cells. The magenta point is our query vector xq.

Now let’s go ahead with our  train  and  search  — and see how our search speed and recall are doing. In[16]:  index.train(xb)  In[17]:  index.add(xb)  In[18]:  In[19]:  dist, I = index.search(xq, k)  %%timeit index.search(xq, k)  Out[19]:  86.3 µs ± 15 µs per loop (mean ± std.

dev. of 7 runs, 10000 loops  each)  In[20]:  sum([1 for i in I[0] if i in l2_I])  Out[20]:  34  A lightning-fast search time of 86.3μs, but the recall has decreased from our IndexPQ significantly (50% to 34%). Given equivalent parameters, both IndexPQ and IndexIVFPQ should be able to attain equal recall performance. The secret to improving our recall, in this case, is bumping up the nprobe  parameter — which tells us how many of the nearest Voronoi cells to include in our search scope. 2D chart showing our quantized ‘PQ’ vectors that have now been assigned to different Voronoi cells via IVF.

At one extreme, we can include all cells by setting nprobe to our nlist  value — this will return the maximum possible recall. Of course, we don’t want to include all cells. It would make our IVF index pointless as we would then not be restricting our search scope (making this equivalent to a flat index).

Instead, we find the lowest  nprobe value that achieves this recall performance. index.nprobe = 2048  # this is searching all Voronoi cells dist, I = index.search(xq, k) sum([1 for i in I[0] if i in l2_I])  index.nprobe = 2 dist, I = index.search(xq, k)sum([1 for i in I[0] if i in l2_I])  index.nprobe = 48 dist, I = index.search(xq, k) sum([1 for i in I[0] if i in l2_I])  In[22]:  Out[22]:  52  In[23]:  Out[23]:  39  In[24]:  Out[24]:  52  With a nprobe of 48, we achieve the best possible recall score of 52% (as demonstrated with  nprobe == 2048 ), while minimizing our search scope (and therefore maximizing search speeds). By adding our IVF step, we’ve dramatically reduced our search time from 1.49ms for IndexPQ to 0.09ms for IndexIVFPQ.

And thanks to our PQ vectors we’ve then paired that with minuscule memory usage that’s 96% lower than the Flat index. All in all, IndexIVFPQ gave us a huge reduction in memory usage — albeit slightly larger than IndexPQ at 9.2MB vs 6.5MB — and lightning- fast search speeds, all while maintaining a reasonable recall of around 50%.

That’s it for this article! We’ve covered the intuition behind product quantization (PQ), and how it manages to compress our index and enable incredibly efficient memory usage. We put together the Faiss IndexPQ implementation and tested search times, recall, and memory usage — then optimized the index even further by pairing it with an IVF index using IndexIVFPQ. FlatL2 PQ IVFPQ  Recall (%)  100  50  52  Speed (ms)  8.26  1.49 0.09  Memory (MB) 256  6.5  9.2  The results of our tests show impressive memory compression and search speeds, with reasonable recall scores. If you’re interested in learning more about the variety of indexes available in search, including more detail on the IVF index, read our article about the best indexes for similarity search. Subscribe for the latest in similarity search! Email address...

Submit  References  [1] H Jégou, et al., Product quantization for nearest neighbor search (2010)  Jupyter Notebooks  Next Chapter: Hierarchical Navigable Small Worlds (HNSW)  Comments Start Discussion  0 replies  What will you build? Upgrade your search or recommendation systems with just a few  lines of code, or contact us for help. Create Account  Pinecone  Pricing  Docs  Learn  Company  Contact  Careers  Get product and article updates  Email address  Get Updates  © Pinecone Systems, Inc. | San Francisco, CA | Terms | Privacy | Product Privacy | Cookies | Trust & Security | System Status Pinecone is a registered trademark of Pinecone Systems, Inc.

03-Locality Sensitive Hashing (LSH): The Illustrated Guide | Pinecone.pdf

Pricing  Docs  Learn  Company  Contact  We're hiring! Log In  Sign Up Free  Locality Sensitive Hashing (LSH): The Illustrated Guide  Locality sensitive hashing (LSH) is a widely popular technique used in approximate nearest neighbor (ANN) search. The solution to efficient similarity search is a profitable one — it is at the core of several billion (and even trillion) dollar companies. Big names like Google, Netflix, Amazon, Spotify, Uber, and countless more rely on similarity search for many of their core functions. Amazon uses similarity search to compare customers, finding new product recommendations based on the purchasing history of their highest-similarity customers. Every time you use Google, you perform a similarity search between your query/search term — and Google’s indexed internet.

If Spotify manages to recommend good music, it’s because their similarity search algorithms are successfully matching you to other customers with a similarly good (or not so good) taste in music. LSH is one of the original techniques for producing high quality search, while maintaining lightning fast search speeds. In this article we will work through the theory behind the algorithm, alongside an easy-to- understand implementation in Python! You can find a video walkthrough of this article here:  Locality Sensitive Hashing (LSH) for Search with Shingling + MinHashing (…  Faiss: The Missing Manual  Chapters:  1. Introduction to Facebook  AI Similarity Search (Faiss)  2. Nearest Neighbor  Indexes for Similarity Search  3. Locality Sensitive  Hashing (LSH): The Illustrated Guide  Search Complexity Locality Sensitive Hashing Shingling, MinHashing, and LSH Band and Hash Testing LSH Further Resources  4. Random Projection for  Locality Sensitive Hashing  5. Product Quantization  6. Hierarchical Navigable Small Worlds (HNSW)  7.

Composite Indexes and the Faiss Index Factory  Share:  Watch on  Search Complexity  Imagine a dataset containing millions or even billions of samples — how can we efficiently compare all of those samples? Even on the best hardware, comparing all pairs is out of the question. This produces an at best complexity of O(n²). Even if comparing a single query against the billions of samples, we still return an at best complexity of O(n). We also need to consider the complexity behind a single similarity calculation — every sample is stored as a vector, often very highly- dimensional vectors — this increases our complexity even further. How can we avoid this?

Is it even possible to perform a search with sub- linear complexity? Yes, it is!

The solution is approximate search. Rather than comparing every vector (exhaustive search) — we can approximate and limit our search scope to only the most relevant vectors. LSH is one algorithm that provides us with those sub-linear search times. In this article, we will introduce LSH and work through the logic behind the magic. Locality Sensitive Hashing  When we consider the complexity of finding similar pairs of vectors, we find that the number of calculations required to compare everything is unmanageably enormous even with reasonably small datasets. Let’s consider a vector index. If we were to introduce just one new vector and attempt to find the closest match — we must compare that vector to every other vector in our database. This gives us a linear time complexity — which cannot scale to fast search in larger datasets. The problem is even worse if we wanted to compare all of those vectors against each other — the optimal approach sorting method to achieve this is at best log-linear time complexity.

So we need a way to reduce the number of comparisons. Ideally, we want only to compare vectors that we believe to be potential matches — or candidate pairs. Locality sensitive hashing (LSH) allows us to do this. LSH consists of a variety of different methods. In this article, we’ll be covering the traditional approach — which consists of multiple steps — shingling, MinHashing, and the final banded LSH function. At its core, the final LSH function allows us to segment and hash the same sample several times. And when we find that a pair of vectors has been hashed to the same value at least once , we tag them as candidate pairs — that is, potential matches. It is a very similar process to that used in Python dictionaries. We have a key-value pair which we feed into the dictionary. The key is processed through the dictionary hash function and mapped to a specific bucket. We then connect the respective value to this bucket.

A typical hash function aims to place different values (no matter how similar) into separate buckets. However, there is a key difference between this type of hash function and that used in LSH.

With dictionaries, our goal is to minimize the chances of multiple key-values being mapped to the same bucket — we minimize collisions.

LSH is almost the opposite. In LSH, we want to maximize collisions — although ideally only for similar inputs. An LSH function aims to place similar values into the same buckets. There is no single approach to hashing in LSH. Indeed, they all share the same ‘bucket similar samples through a hash function’ logic , but they can vary a lot beyond this. The method we have briefly described and will be covering throughout the remainder of this article could be described as the traditional approach, using shingling, MinHashing, and banding. There are several other techniques, such as Random Projection which we cover in another article.

Shingling, MinHashing, and LSH  The LSH approach we’re exploring consists of a three-step process. First, we convert text to sparse vectors using k-shingling (and one-hot encoding), then use minhashing to create ‘signatures’ — which are passed onto our LSH process to weed out candidate pairs. A high-level view of the LSH process we will be working through in this article. We will discuss some of the other LSH methods in future articles. But for now, let’s work through the traditional process in more depth.

k-Shingling  k-Shingling, or simply shingling — is the process of converting a string of text into a set of ‘shingles’. The process is similar to moving a window of length k down our string of text and taking a picture at each step.

We collate all of those pictures to create our set of shingles. k-Shingling consists of moving through a string and adding k characters at a time to a ‘shingle set’. Shingling also removes duplicate items (hence the word ‘set’).

We can create a simple k-shingling function in Python like so:  a = "flying fish flew by the space station" b = "we will not allow you to bring your pet armadillo along" c = "he figured a few sticks of dynamite were easier than a fishing pole to catch fish"  In[1]:  In[2]:  In[3]:  def shingle(text: str, k: int):     shingle_set = []     for i in range(len(text) - k+1):         shingle_set.append(text[i:i+k])     return set(shingle_set)  a = shingle(a, k) b = shingle(b, k) c = shingle(c, k) print(a)  Out[3]:  {'y ', 'pa', 'ng', 'yi', 'st', 'sp', 'ew', 'ce', 'th', 'sh', 'fe',  'e ', 'ta', 'ﬂ', ' b', 'in', 'w ', ' s', ' t', 'he', ' f', 'ti',  'ﬁ', 'is', 'on', 'ly', 'g ', 'at', 'by', 'h ', 'ac', 'io'}  And with this, we have our shingles. Next, we create our sparse vectors.

To do this, we first need to union all of our sets to create one big set containing all of the shingles across all of our sets — we call this the vocabulary (or vocab). All of our shingled sets are merged to create our vocab. We use this vocab to create our sparse vector representations of each set.

All we do is create an empty vector full of zeros and the same length as our vocab — then, we look at which shingles appear in our set. To create our one-hot encoding our single shingle set is matched up to our vocab which indicates where in our zero vector we should place ones (we use a shingle-to-index dictionary in our code). For every shingle that appears, we identify the position of that shingle in our vocab and set the respective position in our new zero-vector to 1. Some of you may recognize this as one-hot encoding.

Minhashing  Minhashing is the next step in our process, allowing us to convert our sparse vectors into dense vectors. Now, as a pre-warning — this part of the process can seem confusing initially — but it’s very simple once you get it.

We have our sparse vectors, and what we do is randomly generate one minhash function for every position in our signature (e.g., the dense vector). So, if we wanted to create a dense vector/signature of 20 numbers — we would use 20 minhash functions. Now, those MinHash functions are simply a randomized order of numbers — and we count from 1 to the final number (which is len(vocab)). Because the order of these numbers has been randomized, we may find that number *1 *is in position 57 (for example) of our randomized MinHash function. 2.

Loop through this randomized MinHash vector (starting at 1), and match the index of each value to the equivalent values in the sparse vector a_1hot. If we find a 1 — that index is our signature value.

print(f"7 -> {hash_ex.index(7)}"). # note that value 7 can be found at index 1 in hash_ex  Our signature values are created by first taking a randomly permuted count vector (from 1 to len(vocab)+1) and finds the  minimum number that aligns with a 1 in our sparse vector. Above, we’re using a smaller vocab containing six values so we can easily visualize the process. We look at our sparse vector and say, “did this shingle at vocab[1] exist in our set?”. If it did — the sparse vector value will be 1 — in this case, it did not exist (hence the 0 value). So, we move to number 2, identify its position (0) and ask the same question. This time, the answer is yes, and so our minhash output is 2. That’s how we produce one value in our minhash signature. But we need to produce 20 (or more) of these values. So, we assign a different minhash function to each signature position — and repeat the process. Here we using four minhash functions/vectors to create a four-digit signature vector. If you count (from one) in each minhash function, and identify the first value that aligns with a one in the sparse vector — you will get 2412.

At the end of this, we produce our minhash signature — or dense vector. Let’s go ahead and write that in code. We have three steps:  1.

Generate a randomized MinHash vector. **  In[10]:  hash_ex = list(range(1, len(vocab)+1)) print(hash_ex)  # we haven't shuffled yet  Out[10]:  [1, 2, 3, 4, 5 ... 99, 100, 101, 102]  In[11]:  from random import shuffle  shuffle(hash_ex) print(hash_ex)  Out[11]:  [63, 7, 94, 16, 36 ... 6, 55, 80, 56]  We now have a randomized list of integers which we can use in  creating our *hashed* signatures. What we do now is begin counting  from `1` through to `len(vocab) + 1`, extracting the position of  this number in our new `hash_ex` list, like so:  for i in range(1, 5):     print(f"{i} -> {hash_ex.index(i)}")  What we do with this is count up from `1` to `len(vocab) + 1` and  ﬁnd if the resultant `hash_ex.index(i)` position in our one-hot  encoded vectors contains a positive value (`1`) in that position,  like so:  In[14]:  for i in range(1, len(vocab)+1):     idx = hash_ex.index(i)     signature_val = a_1hot[idx]     print(f"{i} -> {idx} -> {signature_val}")     if signature_val == 1:         print('match!') break  In[12]:  Out[12]:  7 -> 1  In[13]:  Out[13]:  1 -> 58 2 -> 19 3 -> 96 4 -> 92  Out[14]:  1 -> 58 -> 0 2 -> 19 -> 0 3 -> 96 -> 0 4 -> 92 -> 0 5 -> 83 -> 0 6 -> 98 -> 1 match! 3.

Build a signature from multiple iterations of 1 and 2 (we’ll formalize the code from above into a few easier to use functions):  def create_hash_func(size: int):     # function for creating the hash vector/function     hash_ex = list(range(1, len(vocab)+1))     shuffle(hash_ex)     return hash_ex  def build_minhash_func(vocab_size: int, nbits: int):     # function for building multiple minhash vectors     hashes = []     for _ in range(nbits):         hashes.append(create_hash_func(vocab_size))     return hashes  # we create 20 minhash vectors minhash_func = build_minhash_func(len(vocab), 20)  In[15]:  In[16]:  def create_hash(vector: list):     # use this function for creating our signatures (eg the matching)     signature = []     for func in minhash_func:         for i in range(1, len(vocab)+1):             idx = func.index(i)             signature_val = vector[idx]             if signature_val == 1:                 signature.append(idx)                 break     return signature  In[17]:  # now create signatures a_sig = create_hash(a_1hot) b_sig = create_hash(b_1hot) c_sig = create_hash(c_1hot)  print(a_sig) print(b_sig)  Out[17]:  [44, 21, 73, 14, 2, 13, 62, 70, 17, 5, 12, 86, 21, 18, 10, 10, 86,  47, 17, 78] [97, 96, 57, 82, 43, 67, 75, 24, 49, 28, 67, 56, 96, 18, 11, 85,  86, 19, 65, 75]  And that is MinHashing — it’s really nothing more complex than that. We’ve taken a sparse vector and compressed it into a more densely packed, 20-number signature. Information Transfer from Sparse to Signature  Is the information truly maintained between our much larger sparse vector and much smaller dense vector?

It’s not easy for us to visually identify a pattern in these new dense vectors — but we can calculate the similarity between vectors. If the information truly has been retained during our downsizing — surely the similarity between vectors will be similar too? Well, we can test that.

We use Jaccard similarity to calculate the similarity between our sentences in shingle format — then repeat for the same vectors in signature format:  def jaccard(a: set, b: set):     return len(a.intersection(b)) / len(a.union(b))  In[16]:  In[17]:  jaccard(a, b), jaccard(set(a_sig), set(b_sig))  Out[17]:  (0.14814814814814814, 0.10344827586206896)  In[18]:  jaccard(a, c), jaccard(set(a_sig), set(c_sig))  Out[18]:  (0.22093023255813954, 0.13793103448275862)  We see pretty close similarity scores for both — so it seems that the information is retained. Let’s try again for b and c:  In[19]:  jaccard(b, c), jaccard(set(b_sig), set(c_sig))  Out[19]:  (0.45652173913043476, 0.34615384615384615)  Here we find much higher similarity, as we would expect — it looks like the similarity information is maintained between our sparse vectors and signatures! So, we’re now fully prepared to move onto the LSH process.

Band and Hash  The final step in identifying similar sentences is the LSH function itself. We will be taking the banding approach to LSH — which we could describe as the traditional method. It will be taking our signatures, hashing segments of each signature, and looking for hash collisions — as we described earlier in the article. A high-level view of the signature-building process.

We take our text, build a shingle set, one-hot encode it using our vocab,  and process it through our minhashing process. Through this method, we produce these vectors of equal length that  Copy link  In[1]:  import requests import pandas as pd import io  url = "https://raw.githubusercontent.com/brmson/dataset-sts/master/data/sts/sick2014/SICK_train.txt"  Through this method, we produce these vectors of equal length that contain positive integer values in the range of 1 → len(vocab) — these are the signatures that we typically input into this LSH algorithm. Now, if we were to hash each of these vectors as a whole, we may struggle to build a hashing function that accurately identifies similarity between them — we don’t require that the full vector is equal, only that parts of it are similar. In most cases, even though parts of two vectors may match perfectly — if the remainder of the vectors are not equal, the function will likely hash them into separate buckets.

We don’t want this. We want signatures that share even some similarity to be hashed into the same bucket , thus being identified as candidate pairs. How it Works  The banding method solves this problem by splitting our vectors into sub-parts called bands b. Then, rather than processing the full vector through our hash function, we pass each band of our vector through a hash function. Imagine we split a 100-dimensionality vector into 20 bands. That gives us 20 opportunities to identify matching sub-vectors between our vectors.

We split our signature into b sub-vectors, each is processed through a hash function (we can use a single hash function, or b  hash functions) and mapped to a hash bucket.

We can now add a more flexible condition — given a collision between any two sub-vectors, we consider the respective full vectors as candidate pairs. We split the signatures into subvectors. Each equivalent subvector across all signatures must be processed through the same  hash function. However, it is not necessary to use different hash functions for each subvector (we can use just one hash  function for them all). Now, only part of the two vectors must match for us to consider them. But of course, this also increases the number of false positives (samples that we mark as candidate matches where they are not similar).

However, we do try to minimize these as far as possible. We can implement a simple version of this. First, we start by splitting our signature vectors a, b, and c:  def split_vector(signature, b):     assert len(signature) % b == 0     r = int(len(signature) / b)     # code splitting signature in b parts     subvecs = []     for i in range(0, len(signature), r):         subvecs.append(signature[i : i+r])     return subvecs  Split into 10 bands, creating rows of `2`  band_a = split_vector(a_sig, 10) band_b = split_vector(b_sig, 10) band_b  band_c = split_vector(c_sig, 10) band_c  In[15]:  In[16]:  Out[16]:  In[17]:  Out[17]:  [[42, 43],  [69, 55],  [29, 96],  [86, 46],  [92, 5],  [72, 65],  [29, 5],  [53, 33],  [40, 94],  [96, 70]]  [[90, 43],  [69, 55],  [4, 101],  [35, 15],  [92, 22],  [18, 65],  [40, 18],  [53, 33],  [40, 94],  [80, 14]]  Then we loop through the lists to identify any matches between sub- vectors. If we find any matches — we take those vectors as candidate pairs. In[18]:  for b_rows, c_rows in zip(band_b, band_c):     if b_rows == c_rows:         print(f"Candidate pair: {b_rows} == {c_rows}")         # we only need one band to match         break  Out[18]:  Candidate pair: [69, 55] == [69, 55]  In[20]:  In[21]:  And let's do the same for **a**.

for a_rows, b_rows in zip(band_a, band_b):     if a_rows == b_rows:         print(f"Candidate pair: {a_rows} == {b_rows}")         # we only need one band to match         break  for a_rows, c_rows in zip(band_a, band_c):     if a_rows == c_rows:         print(f"Candidate pair: {b_rows} == {c_rows}")         # we only need one band to match         break  We find that our two more similar sentences, b, and **c **— are identified as candidate pairs. The less similar of the trio, a — is not identified as a candidate. This is a good result, but if we want to really test LSH, we will need to work with more data. Testing LSH  What we have built thus far is a very inefficient implementation — if you want to implement LSH, this is certainly not the way to do it. Rather, use a library built for similarity search — like Faiss, or a managed solution like Pinecone.

But working through the code like this should — if nothing else — make it clear how LSH works.

However, we will now be replicating this for much more data, so we will rewrite what we have so far using Numpy. The code will function in the same way — and you can find each of the functions (alongside explanations) in this notebook. Getting Data  First, we need to get data.

There is a great repository here that contains several datasets built for similarity search testing. We will be extracting a set of sentences from here. text = requests.get(url).text  data = pd.read_csv(io.StringIO(text), sep='\t') data.head()  Out[1]:     pair_ID                                         sentence_A  \ 0        1  A group of kids is playing in a yard and an ol...    1        2  A group of children is playing in the house an...    2        3  The young boys are playing outdoors and the ma...    3        5  The kids are playing outdoors near a man with ...    4        9  The young boys are playing outdoors and the ma...                                               sentence_B   relatedness_score  \ 0  A group of boys in a yard is playing and a man...                 4.5    1  A group of kids is playing in a yard and an ol...                 3.2    2  The kids are playing outdoors near a man with ...                 4.7    3  A group of kids is playing in a yard and an ol...                 3.4    4  A group of kids is playing in a yard and an ol...                 3.7       entailment_judgment   0             NEUTRAL   1             NEUTRAL   2          ENTAILMENT   3             NEUTRAL   4             NEUTRAL    sentences = data['sentence_A'].tolist() sentences[:3]  In[2]:  Out[2]:  ['A group of kids is playing in a yard and an old man is standing  in the background',  'A group of children is playing in the house and there is no man  standing in the background',  'The young boys are playing outdoors and the man is smiling  nearby']  Shingles  Once we have our data, we can create our one-hot encodings — this time stored as a NumPy array (find full code and functions here). In[4]:  k = 8  # shingle size  # build shingles shingles = [] for sentence in sentences:     shingles.append(build_shingles(sentence, k))  # build vocab vocab = build_vocab(shingles)  # one-hot encode our shingles shingles_1hot = [] for shingle_set in shingles:     shingles_1hot.append(one_hot(shingle_set, vocab)) # stack into single numpy array shingles_1hot = np.stack(shingles_1hot) shingles_1hot.shape  Out[4]:  (4500, 36466)  In[5]:  shingles_1hot[:5]  Out[5]:  array([[0., 0., 0., ..., 0., 0., 0. ],        [0., 0., 0., ..., 0., 0., 0. ],        [0., 0., 0., ..., 0., 0., 0.

],        [0., 0., 0., ..., 0., 0., 0. ],        [0., 0., 0., ..., 0., 0., 0.]]) In[6]:  sum(shingles_1hot[0])  # confirm we have 1s  Out[6]:  73.0  Now we have our one-hot encodings. The shingles_1hot array contains *4500 *sparse vectors, where each vector is of length 36466. MinHashing  As before, we will compress our sparse vectors into dense vector ‘signatures’ with minhashing. Again, we will be using our NumPy implementation, which you can find the full code here.

In[8]:  arr = minhash_arr(vocab, 100)  signatures = []  for vector in shingles_1hot:     signatures.append(get_signature(arr, vector))  # merge signatures into single array signatures = np.stack(signatures) signatures.shape  Out[8]:  (4500, 100)  In[9]:  signatures[0]  Out[9]:  array([  65,  438,  534, 1661, 1116,  200, 1206,  583,  141,  766,    92,          52,    7,  287,  587,   65,  135,  581,  136,  838, 1293,   706,          31,  414,  374,  837,   72, 1271,  872, 1136,  201, 1109,   409,         384,  405,  293,  279,  901,   11,  904, 1480,  763, 1610,   518,         184,  398,  128,   49,  910,  902,  263,   80,  608,   69,   185,        1148, 1004,   90,  547, 1527,  139,  279, 1063,  646,  156,   357,         165,    6,   63,  269,  103,   52,   55,  908,  572,  613,   213,         932,  244,   64,  178,  372,  115,  427,  244,  263,  944,   148,          55,   63,  232, 1266,  371,  289,  107,  413,  563,  613,    65,         188])  We’ve compressed our sparse vectors from a length of 36466 to signatures of length 100. A big difference, but as we demonstrated earlier, this compression technique retains similarity information very well. LSH  Finally, onto the LSH portion. We will use a Python dictionary here to hash and store our candidate pairs — again.

The full code is here. In[11]:  b = 20  lsh = LSH(b)  for signature in signatures:     lsh.add_hash(signature)  In[12]:  lsh.buckets  Out[12]:  [{'65,438,534,1661,1116': [0],   '65,2199,534,806,1481': [1],   '312,331,534,1714,575': [2, 4],   '941,331,534,466,75': [3],   ...   '5342,1310,335,566,211': [1443, 1444],   '1365,722,3656,1857,1023': [1445],   '393,858,2770,1799,772': [1446],   ...}]  It’s important to note that our lsh.buckets variable actually contains a separate dictionary for each band — we do not mix buckets between different bands. We see in our buckets the vector IDs (row numbers) , so all we need to do to extract our candidate pairs is loop through all buckets and extract pairs. In[12]:  candidate_pairs = lsh.check_candidates() len(candidate_pairs)  Out[12]:  7243  In[14]:  list(candidate_pairs)[:5]  Out[14]:  [(1646, 1687), (3234, 3247), (1763, 2235), (2470, 2622), (3877,  3878)]  After identifying our candidate pairs, we would restrict our similarity calculations to those pairs only — we will find that some will be within our similarity threshold, and others will not. The objective here is to restrict our scope and reduce search complexity while still maintaining high accuracy in identifying pairs. We can visualize our performance here by measuring the candidate pair classification (1 or 0) against actual cosine (or Jaccard) similarity. Chart showing the distribution of candidate-pairs (1s) and non-candidates (0s) against the cosine similarity of pair signatures.

Now, this may seem like a strange way to visualize our performance — and you are correct, it is — but we do have a reason. Optimizing the Bands  It is possible to optimize our band value b to shift the similarity threshold of our LSH function. The similarity threshold is the point at which we would like our LSH function to switch from a non-candidate to a candidate pair. We formalize this probability-similarity relationship as so:  Probability (P) of a pair being identified as candidate pairs given a similarity score (s), number of bands (b), and number of rows in each band (r). Now, if we were to visualize this probability-similarity relationship for our current b and r values we should notice a pattern:  Candidate classification (left y-axis) and calculated probability P (right y-axis) against similarity (calculated or normalized cosine similarity). This shows that our calculated probability **P **and similarity s values indicate the general distribution of  candidate/non-candidate pairs.

The b and r values are 20 and 5 respectively. Although the alignment isn’t perfect, we can see a correlation between the theoretical, calculated probability — and the genuine candidate pair results. Now, we can push the probability of returning candidate-pairs at different similarity scores left or right by modifying b:  Calculated probability P against similarity s for different b values.

Note that r will be len(signature) / b (in this case  len(signature) == 100). These are our calculated probability values. If we decided that our previous results where b == 20 required too high a similarity to count pairs as candidate pairs — we would attempt to shift the similarity threshold to the left. Looking at this graph, a b value of 25 looks like it could shift our genuine results just enough. So, let’s visualize our results when using b == 25:  Results for real and simulated results when b == 25 are displayed with blue and magenta. Our previous LSH results (teal) are  displayed for comparison.

Note that this has created more candidate pairs. Because we are now returning more candidate pairs, this will naturally result in more false positives — where we return ‘candidate pair’ for dissimilar vectors. This is an unavoidable consequence of modifying b, which we can visualize as:  Increasing b (shifting left) increases FPs while decreasing FNs.

Great! We’ve built our LSH process from scratch — and even managed to tune our similarity threshold.

That’s everything for this article on the principles of LSH. Not only have we covered LSH, but also shingling and the MinHash function! In practice, we would most likely want to implement LSH using libraries built specifically for similarity search. We will be covering LSH — specifically the random projection method — in much more detail, alongside its implementation in Faiss. However, if you’d prefer a quick rundown of some of the key indexes (and their implementations) in similarity search, we cover them all in our overview of vector indexes. Subscribe for the latest in similarity search! Email address...

Submit  Further Resources  Jupyter Notebooks  J. Ullman et al., Mining of Massive Datasets  Next Chapter: Random Projection for Locality Sensitive Hashing  Comments 2 replies  vvs29 How can you get which values are candidate pairs from the bucket, like the bucket contains the signatures and the candidate pairs are in the form of signatures so i actually do not know which ID should i check 1 reply  Jul '22  jamesbriggs I’m not sure for the LSH index speciﬁcally, but for other indexes there is a get_ids method that you can call on the index that returns a “swig object” that you convert to numpy with faiss.vector_to_array. I can also see here that it is possible to retrieve the data from index.codes for LSH, but I believe this the vector codes themselves (not IDs)  ▶ vvs29  Jul '22  Continue Discussion  What will you build? Upgrade your search or recommendation systems with just a few  lines of code, or contact us for help. Create Account  Pinecone  Pricing  Docs  Learn  Company  Contact  Careers  Get product and article updates  Email address  Get Updates  © Pinecone Systems, Inc. | San Francisco, CA | Terms | Privacy | Product Privacy | Cookies | Trust & Security | System Status Pinecone is a registered trademark of Pinecone Systems, Inc.

02-Nearest Neighbor Indexes for Similarity Search | Pinecone.pdf

Pricing  Docs  Learn  Company  Contact  We're hiring! Log In  Sign Up Free  Nearest Neighbor Indexes for Similarity Search  Faiss: The Missing Manual  Chapters:  1. Introduction to Facebook  AI Similarity Search (Faiss)  2. Nearest Neighbor  Indexes for Similarity Search  Indexes in Search Flat And Accurate Locality Sensitive Hashing Hierarchical Navigable Small World Graphs Inverted File Index  3. Locality Sensitive  Hashing (LSH): The Illustrated Guide  4. Random Projection for  Locality Sensitive Hashing  5. Product Quantization  6. Hierarchical Navigable Small Worlds (HNSW)  7.

Composite Indexes and the Faiss Index Factory  Share:  Vector similarity search is a game-changer in the world of search.

It allows us to efficiently search a huge range of media, from GIFs to articles — with incredible accuracy in sub-second timescales for billion+ size datasets. One of the key components to efficient search is flexibility. And for that we have a wide range of search indexes available to us — there is no ‘one-size-fits-all’ in similarity search. However, this great flexibility produces a question — how do we know which size fits our use case? Which index do we choose? Should we use multiple indexes, or is one enough?

This article will explore the pros and cons of some of the most important indexes — Flat, LSH, HNSW, and IVF. We will learn how we decide which to use and the impact of parameters in each index.

Note: Pinecone lets you add vector search to your production applications without knowing anything about vector indexes. However, we know you like seeing how things work, so enjoy learning about these popular vector index types! Check out the video walkthrough:  Choosing Indexes for Similarity Search (Faiss in Python)  Watch on  Indexes in Search  Before jumping into the different indexes available, let’s take a look at why we care about similarity search — and how we can use indexes for efficient similarity search. Why Similarity Search  Let’s start with the most fundamental question to the relevance of this article — why do we care about similarity search? Similarity search can be used to compare data quickly. Given a query (which could be in any format — text, audio, video, GIFs — you name it), we can use similarity search to return relevant results.

This is key to a huge number of companies and applications spanning across industries. It’s used to identify similar genes in genome databases, deduplication of datasets, or search billions of results to search queries every day. Search seems like an easy process — we take one item and compare it to another. But when we have millions (or even billions) of ‘other’ items to compare against — it begins to get tricky. For search to be useful, it needs to be accurate and fast. And it is this more efficient search that we are interested in. Indexes For Efficient Search  In vector similarity search, we use an index to store vector representations of the data we intend to search. Through either statistical methods or machine learning — we can build vectors that encode useful, meaningful information about our original data.

Using densely encoded vectors, we can show that the equivalent man-King semantic relationship for woman is Queen. We take these ‘meaningful’ vectors and store them inside an index to use for intelligent similarity search.

There are many index solutions available; one, in particular, is called Faiss (Facebook AI Similarity Search). We store our vectors in Faiss and query our new Faiss index using a ‘query’ vector. This query vector is compared to other index vectors to find the nearest matches — typically with Euclidean (L2) or inner-product (IP) metrics. So, with that introduction to the why and how of similarity search. But what is this about Faiss — and choosing the right indexes? Faiss And Indexes  Faiss comes with many different index types — many of which can be mixed and matched to produce multiple layers of indexes. We will be focused on a few indexes that prioritize search speed, quality, or index memory. Now, which one of these indexes we use depends very much on our use case.

We must consider factors such as dataset size, search frequency, or search-quality vs. search-speed. Flat And Accurate  Flat indexes come with perfect search-quality at the cost of slow search speeds. Memory utilization of flat indexes is  reasonable. The very first indexes we should look at are the simplest — flat indexes. Flat indexes are ‘flat’ because we do not modify the vectors that we feed into them. Because there is no approximation or clustering of our vectors — these indexes produce the most accurate results.

We have perfect search quality, but this comes at the cost of significant search times. With flat indexes, we introduce our query vector  xq and compare it against every other full-size vector in our index — calculating the distance to each. With flat indexes, we compare our search query xq to every other vector in the index. After calculating all of these distances, we will return the nearest k of those as our nearest matches. A k-nearest neighbors (kNN) search. Once we have calculated all of the distances, we return the k nearest vectors. When To Use  So when should we use a flat index? Well, when search quality is an unquestionably high priority — and search speed is less important. Search speed can be an irrelevant factor for smaller datasets — especially when using more powerful hardware.

Euclidean (L2) and Inner Product (IP) flat index search times using faiss-cpu on an M1 chip. Both using vector dimensionality  of 100.

IndexFlatIP is shown to be slightly faster than IndexFlatL2. The above chart demonstrates Faiss CPU speeds on an M1-chip. Faiss is optimized to run on GPU at significantly higher speeds when paired with CUDA-enabled GPUs on Linux to improve search times significantly.

In short, use flat indexes when:  Search quality is a very high priority. Search time does not matter OR when using a small index (<10K). Implementing a Flat Index  To initialize a flat index, we need our data, Faiss, and one of the two flat indexes —  IndexFlatL2  if using Euclidean/L2 distance, or IndexFlatIP  if using inner product distance.

First, we need data. We will be using the Sift1M dataset, which we can download and load into a notebook with:  In[1]:  import shutil import urllib.request as request from contextlib import closing  # first we download the Sift1M dataset with closing(request.urlopen('ftp://ftp.irisa.fr/local/texmex/corpus/sift.tar.gz'     with open('sift.tar.gz', 'wb') as f:         shutil.copyfileobj(r, f)  In[2]:  import tarfile  # the download leaves us with a tar.gz file, we unzip it tar = tarfile.open('sift.tar.gz', "r:gz") tar.extractall()  In[3]:  import numpy as np  # now define a function to read the fvecs file format of Sift1M dataset def read_fvecs(fp):     a = np.fromfile(fp, dtype='int32')     d = a[0]     return a.reshape(-1, d + 1)[:, 1:].copy().view('float32')  In[4]:  # data we will search through xb = read_fvecs('sift_base.fvecs')  # 1M samples # also get some query vectors to search with xq = read_fvecs('./sift/sift_query.fvecs') # take just one query (there are many in sift_learn.fvecs) xq = xq[0].reshape(1, xq.shape[1])  In[5]:  xq.shape  Out[5]:  (1, 128)  In[7]:  xb.shape  Out[7]:  (1000000, 128)  In[8]:  xq  Out[8]:  array([[  1.,   3.,  11., 110.,  62.,  22.,   4.,   0.,  43.,   21.,  22.,          18.,   6.,  28.,  64.,   9.,  11.,   1.,   0.,   0.,    1.,  40.,         101.,  21.,  20.,   2.,   4.,   2.,   2.,   9.,  18.,   35.,   1.,           1.,   7.,  25., 108., 116.,  63.,   2.,   0.,   0.,   11.,  74.,          40., 101., 116.,   3.,  33.,   1.,   1.,  11.,  14.,   18., 116.,         116.,  68.,  12.,   5.,   4.,   2.,   2.,   9., 102.,   17.,   3.,          10.,  18.,   8.,  15.,  67.,  63.,  15.,   0.,  14.,  116.,  80.,           0.,   2.,  22.,  96.,  37.,  28.,  88.,  43.,   1.,    4.,  18.,         116.,  51.,   5.,  11.,  32.,  14.,   8.,  23.,  44.,   17.,  12.,           9.,   0.,   0.,  19.,  37.,  85.,  18.,  16., 104.,   22.,   6.,           2.,  26.,  12.,  58.,  67.,  82.,  25.,  12.,   2.,    2.,  25.,          18.,   8.,   2.,  19.,  42.,  48.,  11.

]], dtype=ﬂoat32)  Now we can index our new data using one of our two flat indexes. We saw that IndexFlatIP is slightly faster, so let’s use that. d = 128  # dimensionality of Sift1M data k = 10  # number of nearest neighbors to return  1 2 3 4 5 6  index = faiss.IndexFlatIP(d) index.add(data) D, I = index.search(xq, k)  And for flat indexes, that is all we need to do — there is no training (as we have no parameters to optimize when storing vectors without transformations or clustering). Balancing Search Time  Flat indexes are brilliantly accurate but terribly slow. In similarity search, there is always a trade-off between search-speed and search-quality (accuracy). What we must do is identify where our use-case sweet spot lies.

With flat indexes, we are here:  Flat indexes are 100% search-quality, 0% search-speed. Here we have completely unoptimized search-speeds, which will fit many smaller index use-cases — or scenarios where search-time is irrelevant. But, other use-cases require a better balance speed and quality.

So, how can we make our search faster? There are two primary approaches:  1. Reduce vector size — through dimensionality reduction or reducing  the number of bits representing our vectors values.

2. Reduce search scope — we can do this by clustering or organizing vectors into tree structures based on certain attributes, similarity, or distance — and restricting our search to closest clusters or filter through most similar branches. Using either of these approaches means that we are no longer performing an exhaustive nearest-neighbors search but an approximate nearest-neighbors (ANN) search — as we no longer search the entire, full-resolution dataset. So, what we produce is a more balanced mix that prioritizes both search- speed and search-time:  Often, we will want a more balanced mix of both search-speed and search-quality. Locality Sensitive Hashing  LSH — a wide range of performances heavily dependent on the parameters set.

Good quality results in slower search, and  fast search results in worse quality. Poor performance for high-dimensional data. The ‘half-filled’ segments of the bars  represent the range in performance encountered while modifying index parameters. Locality Sensitive Hashing (LSH) works by grouping vectors into buckets by processing each vector through a hash function that maximizes hashing collisions — rather than minimizing as is usual with hashing functions. What does that mean? Imagine we have a Python dictionary. When we create a new key-value pair in our dictionary, we use a hashing function to hash the key. This hash value of the key determines the ‘bucket’ where we store its respective value:  A typical hash function for a dictionary-like object will attempt to minimize hash collisions, aiming to assign only one value to  each bucket. A Python dictionary is an example of a hash table using a typical hashing function that minimizes hashing collisions, a hashing collision where two different objects (keys) produce the same hash.

In our dictionary, we want to avoid these collisions as it means that we would have multiple objects mapped to a single key — but for LSH, we want to maximize hashing collisions. Why would we want to maximize collisions? Well, for search, we use LSH to group similar objects together. When we introduce a new query object (or vector), our LSH algorithm can be used to find the closest matching groups:  Our hash function for LSH attempts to maximize hash collisions, producing groupings of vectors. Implementing LSH  Implementing our LSH index in Faiss is easy. We initialize a IndexLSH object, using the vector dimensions d and the nbits argument — and add our vectors like so:  1 2 3 4 5 6  nbits = d*4  # resolution of bucketed vectors # initialize index and add vectors index = faiss.IndexLSH(d, nbits) index.add(wb) # and search D, I = index.search(xq, k)  Our  nbits  argument refers to the ‘resolution’ of the hashed vectors. A higher value means greater accuracy at the cost of more memory and slower search speeds. Recall score of IndexLSH with d of 128.

Note that to get higher recall performance, we need to increase the num_bits value  dramatically. For 90% recall we use 64d, which is 64128 = 8192.

Our baseline  IndexFlatIP  index is our 100% recall performance, using  IndexLSH  we can achieve 90% using a very high  nbits value. This is a strong result — 90% of the performance could certainly be a reasonable sacrifice to performance if we get improved search-times.

However, LSH is highly sensitive to the curse of dimensionality when using a larger  d  value we also need to increase  nbits  to maintain search-quality. So our stored vectors become increasingly larger as our original vector dimensionality  d  increases.

This quickly leads to excessive search times:  Search time for IndexLSH with varying nbits values, compared against a flat IP index. Which is mirrored by our index memory size:  Index size for IndexLSH with varying nbits values, compared against a flat IP index. So  IndexLSH  is not suitable if we have large vector dimensionality ( 128  is already too large). Instead, it is best suited to low- dimensionality vectors — and small indexes.

If we find ourselves with large  d  values or large indexes — we avoid LSH completely, instead focusing on our next index, HNSW. Hierarchical Navigable Small World Graphs  HNSW — great search-quality, good search-speed, but substantial index sizes. The ‘half-filled’ segments of the bars  represent the range in performance encountered while modifying index parameters.

Hierarchical Navigable Small World (HNSW) graphs are another, more recent development in search. HNSW-based ANNS consistently top out as the highest performing indexes [1]. HNSW is a further adaption of navigable small world (NSW) graphs — where an NSW graph is a graph structure containing vertices connected by edges to their nearest neighbors. The ‘NSW’ part is due to vertices within these graphs all having a very short average path length to all other vertices within the graph — despite not being directly connected. Using the example of Facebook — in 2016, we could connect every user (a vertex) to their Facebook friends (their nearest neighbors). And despite the 1.59B active users, the average number of steps (or hops) needed to  Copy link  the 1.59B active users, the average number of steps (or hops) needed to traverse the graph from one user to another was just 3.57 [2].

Notice that each point is no more than four hops away from another. Facebook is just one example of high connectivity in vast networks — otherwise known as an NSW graph. At a high level, HNSW graphs are built by taking NSW graphs and breaking them apart into multiple layers.

With each incremental layer eliminating intermediate connections between vertices. With HNSW, we break networks into several layers, which are traversed during the search. For bigger datasets with higher-dimensionality — HNSW graphs are some of the best performing indexes we can use. We’ll be covering using the HNSW index alone, but by layering other quantization steps, we can improve search-times even further. HNSW Implementation  To build and search a flat HNSW index in Faiss, all we need is IndexHNSWFlat :  # set HNSW index parameters M = 64  # number of connections each vertex will have ef_search = 32  # depth of layers explored during search ef_construction = 64  # depth of layers explored during index construction  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  # initialize index (d == 128) index = faiss.IndexHNSWFlat(d, M) # set efConstruction and efSearch parameters index.hnsw.efConstruction = ef_construction index.hnsw.efSearch = ef_search # add data to index index.add(wb)  # search as usual D, I = index.search(wb, k)  Here, we have three key parameters for modifying our index performance.

M — the number of nearest neighbors that each vertex will connect to. efSearch — how many entry points will be explored between layers during the search. efConstruction — how many entry points will be explored when building the index. Each of these parameters can be increased to improve search-quality:  Recall values for different efConstruction, efSearch, and M values on the Sift1M dataset. M  and  efSearch  have a larger impact on search-time — efConstruction  primarily increases index construction time (meaning a slower  index.add ), but at higher  M  values and higher query volume we do see an impact from  efConstruction  on search-time too. Search time for different M and efSearch values on the full Sift1M dataset. HNSW gives us great search-quality at very fast search-speeds — but there’s always a catch — HNSW indexes take up a significant amount of memory.

Using an  M  value of  128  for the Sift1M dataset requires upwards of 1.6GB of memory. Index memory usage for different M values on the Sift1M dataset. However, we can increase our other two parameters —  efSearch  and efConstruction  with no effect on the index memory footprint. So, where RAM is not a limiting factor HNSW is great as a well- balanced index that we can push to focus more towards quality by increasing our three parameters.

We can use the lower set of parameters to balance prioritize a slightly faster search-speed with good search-quality — or we  use the higher set of parameters for slightly slower search-speed with high search-quality. That’s HNSW in Faiss — an incredibly powerful and efficient index.

Now let’s move onto our final index — IVF. Inverted File Index  IVF — great search-quality, good search-speed, and reasonable memory usage.

The ‘half-filled’ segments of the bars  represent the range in performance encountered while modifying index parameters. The Inverted File Index (IVF) index consists of search scope reduction through clustering. It’s a very popular index as it’s easy to use, with high search-quality and reasonable search-speed.

It works on the concept of Voronoi diagrams — also called Dirichlet tessellation (a much cooler name). To understand Voronoi diagrams, we need to imagine our highly- dimensional vectors placed into a 2D space. We then place a few additional points in our 2D space, which will become our ‘cluster’ (Voronoi cells in our case) centroids. We then extend an equal radius out from each of our centroids. At some point, the circumferences of each cell circle will collide with another — creating our cell edges:  How Voronoi cells are constructed — here, we have three centroids, resulting in three Voronoi cells. Each datapoint within a  given cell is then assigned to that respective centroid. Now, every datapoint will be contained within a cell — and be assigned to that respective centroid.

Just as with our other indexes, we introduce a query vector  xq  — this query vector must land within one of our cells, at which point we restrict our search scope to that single cell. But there is a problem if our query vector lands near the edge of a cell — there’s a good chance that its closest other datapoint is contained within a neighboring cell. We call this the edge problem:  Our query vector xq lands on the edge of the magenta cell. Despite being closer to datapoints in the teal cell, we will not  compare these if nprobe == 1 — as this means we would restrict search scope to the magenta cell only. Now, what we can do to mitigate this issue and increase search-quality is increase an index parameter known as the  nprobe  value. With nprobe  we can set the number of cells to search. Increasing nprobe increases our search scope.

IVF Implementation  To implement an IVF index and use it in search, we can use IndexIVFFlat :  1 2 3 4 5 6 7 8 9  nlist = 128  # number of cells/clusters to partition data into  quantizer = faiss.IndexFlatIP(d)  # how the vectors will be stored/compared index = faiss.IndexIVFFlat(quantizer, d, nlist) index.train(data)  # we must train the index to cluster into cells index.add(data)  index.nprobe = 8  # set how many of nearest cells to search D, I = index.search(xq, k)  There are two parameters here that we can adjust. nprobe — the number of cells to search  nlist — the number of cells to create  A higher  nlist  means that we must compare our vector to more centroid vectors — but after selecting the nearest centroid’s cells to search, there will be fewer vectors within each cell. So, increase nlist  to prioritize search-speed.

As for  nprobe , we find the opposite. Increasing  nprobe  increases the search scope — thus prioritizing search-quality. Search-time and recall for IVF using different nprobe and nlist values. In terms of memory,  IndexIVFFlat  is reasonably efficient — and modifying  nprobe  will not affect this. The effect of  nlist  on memory usage is small too — higher  nlist  means a marginally larger memory requirement. Memory usage of the index is affected only by the nlist parameter. However, for our Sift1M dataset, the index size changed  only very slightly. So, we must decide between greater search-quality with  nprobe  and faster search-speed with  nlist . We’ve covered a lot in this article , so let’s wrap everything up with a quick summary of each index’s memory, speed, and search-quality performance. Recall  Notes  Memory (MB)  Query Time (ms)  ~500  ~18  Index  Flat (L2 or IP)  LSH  HNSW  20 - 600  600 - 1600  Good for small datasets or where query time is irrelevant  1.7 - 30  Best for low dimensional data, or small datasets  0.6 - 2.1  Very good for quality, high speed, but large memory usage  1.0  0.4 - 0.85  0.5 - 0.95  0.7 - 0.95  IVF  ~520  1 - 9  Good scalable option. High-quality, at reasonable speed and memory usage  Values displayed here are the range of values experienced during testing of each index on the Sift1M dataset and represent the average results from 20 tests at each parameter setting. Unrealistic parameter settings tested in this article (excessively low/high) have been excluded from this range.

The Sift1M dataset consists of a dimensionality  d  of 128, dataset size of 1M. The above values result from querying for a single vector - returning  k == 10  of the nearest matches. Hardware used  M1 chip with 8-core CPU  8GB unified memory  index_summary.md hosted with ❤ by GitHub  view raw  So we have four indexes, with equally potent pros and cons — depending on the use-case. Hopefully, with this article, you will now be much better prepared to decide which of these indexes best fits your own use case. Beyond these metrics, it is possible to improve memory usage and search-speed even further by adding other quantization or compression steps — but that is for another article. Subscribe for the latest in similarity search! Email address... Submit  References  [1] E Bernhardsson, ANN-benchmarks repo, Github  [2] S Edunov, et al., Three and a half degrees of separation (2016), Facebook Research  All images are by the author except where stated otherwise  Next Chapter: Locality Sensitive Hashing (LSH): The Illustrated Guide  Comments 3 replies  Prabhat How does efConstruction have an impact on search time for IVFHNSW (as mentioned in this description)? I am observing something in my experiments but can’t ﬁgure out why.

Jul '22  jamesbriggs efConstruction primarily effects your build time (eg larger efConstruction == longer build time). It has been some time since working with HNSW so take this with a pinch of salt, different efConstruction values create a more or less optimized graph, so search times could be slower or faster because of that. Generally, greater efConstruction means more optimized graph, and faster search times. But I don’t think there is a perfect correlation.

Jul '22  Jerome Hi guys, regarding the efConstruction parameter, I have a question about the performance graphs shown in the HNSW section. How can M be greater than efConstruction ? In my understanding of the paper algorithms 1 and 2 by Malkov and Yashumin, during the node insertion, the edges are created between the inserted node and the M (or Mmax) nearest neighbors among the efConstruction ones returned for a given layer… So it seems to me that M is always less or equal to efConstruction. Same for the efSearch parameter which is by construction less or equal to the  Jul '22  What will you build? Upgrade your search or recommendation systems with just a few  lines of code, or contact us for help. Create Account  Pinecone  Pricing  Docs  Learn  Company  Contact  Careers  Get product and article updates  Email address  Get Updates  © Pinecone Systems, Inc. | San Francisco, CA | Terms | Privacy | Product Privacy | Cookies | Trust & Security | System Status Pinecone is a registered trademark of Pinecone Systems, Inc.

04-Random Projection for Locality Sensitive Hashing | Pinecone.pdf

Pricing  Docs  Learn  Company  Contact  We're hiring! Log In  Sign Up Free  Faiss: The Missing Manual  Chapters:  1. Introduction to Facebook  AI Similarity Search (Faiss)  2. Nearest Neighbor  Indexes for Similarity Search  3. Locality Sensitive  Hashing (LSH): The Illustrated Guide  4. Random Projection for  Locality Sensitive Hashing  Locality Sensitive Hashing Random Hyperplanes Balancing Quality vs.

Speed LSH in Faiss Where to Use LSH References  5. Product Quantization  6. Hierarchical Navigable Small Worlds (HNSW)  7. Composite Indexes and the Faiss Index Factory  Share:  Random Projection for Locality Sensitive Hashing  SimilaritySearch LSHWithRandomProjection  Locality sensitive hashing (LSH) is a widely popular technique used in approximate similarity search. The solution to efficient similarity search is a profitable one — it is at the core of several billion (and even trillion) dollar companies. The problem with similarity search is scale. Many companies deal with millions-to-billions of data points every single day. Given a billion data points, is it feasible to compare all of them with every search? Further, many companies are not performing single searches — Google deals with more than 3.8 million searches every minute[1].

Billions of data points combined with high-frequency searches are problematic — and we haven’t considered the dimensionality nor the similarity function itself. Clearly, an exhaustive search across all data points is unrealistic for larger datasets. The solution to searching impossibly huge datasets? Approximate search. Rather than exhaustively comparing every pair, we approximate — restricting the search scope only to high probability matches. How LSH Random Projection works in search (+Python)  Watch on  Locality Sensitive Hashing  Locality Sensitive Hashing (LSH) is one of the most popular approximate nearest neighbors search (ANNS) methods.

At its core, it is a hashing function that allows us to group similar items into the same hash buckets. So, given an impossibly huge dataset — we run all of our items through the hashing function, sorting items into buckets. Unlike most hashing functions, which aim to minimize hashing collisions — LSH algorithms aim to maximize hashing collisions.

Two hashing functions, the top (blue) minimizes hashing collisions. The bottom (magenta) maximizes hashing collisions —  LSH aims to maximize collisions between similar items. This result for LSH is that similar vectors produce the same hash value and are bucketed together. In contrast, dissimilar vectors will hopefully not produce the same hash value — being placed in different buckets. Search With LSH  Performing search with LSH consists of three steps:  1.

2. Introduce our query vector (search term). It is hashed using the same  LSH function.

3. Compare our hashed query vector to all other hash buckets via  Hamming distance — identifying the nearest. At a very high level, that is the process of the LSH methodology we will be covering. However, we will explain all of this in much more detail further in the article.

Effects of Approximation  Before diving into the detail of LSH, we should note that grouping vectors into lower resolution hashed vectors also means that our search is not exhaustive (e.g., comparing every vector), so we expect a lower search quality. We compress potentially huge dense vectors into highly compressed, grouped binary vectors.

But, the reason for accepting this lower search quality is the potential for significantly faster search speeds.

Which Method? We’ve been purposely lax on the details here because there are several versions of LSH — each utilizing different hash building and distance/similarity metrics. The two most popular approaches are:  Shingling, MinHashing, and banded LSH (traditional approach)  Random hyperplanes with dot-product and Hamming distance  This article will focus on the random hyperplanes method , which is more commonly used and implemented in various popular libraries such as Faiss. Random Hyperplanes  The random hyperplanes (also called random projection) approach is deceptively simple — although it can be hard to find details on the method. Let’s learn through an example — we will be using the Sift1M dataset throughout our examples, which you can download using this script. Now, given a single query vector  xq  we want to identify the top  k nearest neighbors from the  xb  array. Here we are returning the three nearest neighbors to our query vector xq. Using the random projection method, we will reduce our highly- dimensional vectors into low-dimensionality binary vectors. Once we have these binary vectors, we can measure the distance between them using Hamming distance. Let’s work through that in a little more detail.

Creating Hyperplanes  The hyperplanes in this method are used to split our datapoints and assign a value of 0 for those data points that appear on the negative side of our hyperplane — and a value of 1 for those that appear on the positive side. We assign a value of 1 to vectors on the +ve side of our hyperplane and a value of 0 to vectors on the -ve side of the  hyperplane. To identify which side of the hyperplane our data point is located, all we need is the normal vector of the plane — e.g., a vector perpendicular to the plane. We feed this normal vector (alongside our datapoint vector) into a dot product function. If two vectors share the same direction, the resultant dot product is positive. If they do not share the same direction, it is negative.

Where our hyperplane normal vector produces a +ve dot-product with another vector, we can view that vector as being in  front of the hyperplane. The reverse is true for vectors that produce a -ve dot-product. In the unlikely case of both vectors being perfectly perpendicular (sitting on the hyperplane edge), the dot product is 0 — we will group this in with our negative direction vectors. A single binary value doesn’t tell us much about the similarity of our vectors, but when we begin adding more hyperplanes — the amount of encoded information rapidly increases. We add more hyperplanes to increase the amount of positional information stored in our binary vectors. By projecting our vectors into a lower-dimensional space using these hyperplanes, we produce our new hashed vectors.

In the image above, we have used two hyperplanes, and realistically we will need many more — a property that we define using the  nbits parameter. We will discuss  nbits  in more detail later, but for now, we will use four hyperplanes by setting  nbits = 4 .

Now, let’s create the normal vectors of our hyperplanes in Python. nbits = 4  # number of hyperplanes and binary vals to produce d = 2  # vector dimensions  import numpy as np # create a set of 4 hyperplanes, with 2 dimensions plane_norms = np.random.rand(nbits, d) - .5 plane_norms  Out[2]:  array([[-0.26623211,  0.34055181],        [ 0.3388499 , -0.33368453],        [ 0.34768572, -0.37184437],        [-0.11170635, -0.0242341 ]])  Through  np.random.rand  we create a set of random values in the range 0 → 1.

We then add  -.5  to center our array values around the origin (0, 0). Visualizing these vectors, we see:  The normal vectors that define the positions of our hyperplanes, which are all centered around the origin (0, 0). Hashing Vectors  Now let’s add three vectors — a, b, and c — and work through building our hash values using our four normal vectors and their hyperplanes. a = np.asarray([1, 2]) b = np.asarray([2, 1]) c = np.asarray([3, 1])  # calculate the dot product for each of these a_dot = np.dot(a, plane_norms.T) b_dot = np.dot(b, plane_norms.T) c_dot = np.dot(c, plane_norms.T) a_dot  Out[4]:  array([ 0.41487151, -0.32851916, -0.39600301, -0.16017455])  # we know that a positive dot product == +ve side of hyperplane # and negative dot product == -ve side of hyperplane a_dot = a_dot > 0 b_dot = b_dot > 0 c_dot = c_dot > 0 a_dot  Out[5]:  array([ True, False, False, False])  # convert our boolean arrays to int arrays to make bucketing # easier (although is okay to use boolean for Hamming distance) a_dot = a_dot.astype(int) b_dot = b_dot.astype(int) c_dot = c_dot.astype(int) a_dot  In[1]:  In[2]:  In[3]:  In[4]:  In[5]:  In[6]:  Out[6]:  array([1, 0, 0, 0])  Out[7]:  array([0, 1, 1, 0])  In[7]:  b_dot  In[8]:  c_dot  Out[8]:  array([0, 1, 1, 0])  Visualizing this again, we have our three vectors a, b, and c — alongside our four hyperplanes (perpendicular to their respective normal vectors). Taking the +ve and -ve dot-product values for each gives us:  A zero shows that the vector is behind the plane (-ve dot product), and a one shows that the vector is in front of the plane  (+ve dot product). We combine these to create our binary vectors.

Which produces our hashed vectors. Now, LSH uses these values to create buckets — which will contain some reference back to our vectors (Eg their IDs). Note that we do not store the original vectors in the buckets — which would significantly increase the size of our LSH index. As we will see with implementations such as Faiss — the position/order that we added the vector is usually stored. We will use this same approach in our examples. In[10]:  vectors = [a_dot, b_dot, c_dot] buckets = {} i = 0  for i in range(len(vectors)):     # convert from array to string     hash_str = ''.join(vectors[i].astype(str))     # create bucket if it doesn't exist     if hash_str not in buckets.keys():         buckets[hash_str] = []     # add vector position to bucket     buckets[hash_str].append(i)  print(buckets)  Out[10]:  {'1000': [0], '0110': [1, 2]}  Now that we have bucketed our three vectors, let’s consider the change in the complexity of our search.

Let’s say we introduce a query vector that gets hashed as  0111 . With this vector, we compare it to every bucket in our LSH index — which in this case is only two values —  1000  and  0110 . We then use Hamming distance to find the closest match, and this happens to be 0110 . Hamming distance, there are four mismatches between the first two vectors — resulting in a Hamming distance of four. The  next two contain just one mismatch, giving a Hamming distance of one.

We have taken a linear complexity function, which required us to compute the distance between our query vector and all of the previously indexed vectors — to a sub-linear complexity — as we no longer need to compute the distance for every vector — because they’re grouped into buckets. Now, at the same time, vectors 1 and 2 are both equal to  0110 .

So we cannot possibly find which of those is closest to our query vector. This means there is a degree of search quality being lost — however, this is simply the cost of performing an approximate search.

We trade quality for speed. Balancing Quality vs. Speed  As is often the case in similarity search, a good LSH index requires balancing search quality vs. search speed. We saw in our mini-example that our vectors were not easy to differentiate, because out of a total of three vectors — random projection had hashed two of them to the same binary vector. Now imagine we scale this same ratio to a dataset containing one million vectors.

We introduce our query vector  xq  — hash it and calculate the hamming distance between that ( 0111 ) and our two buckets ( 1000 and  0110 ). Wow, a million sample dataset searched with just two distance calculations? That’s fast.

Unfortunately, we return around 700K samples, all with the same binary vector value of  0110 .

Fast yes, accurate — not at all. Now, in reality, using an  nbits  value of  4  would produce 16 buckets:  # this returns number of binary combos for our nbits val 1 << nbits  In[1]:  nbits = 4  Out[1]:  16  In[2]:  # we can print every possible bucket given our nbits value like so for i in range(1 << nbits):     # get binary representation of integer     b = bin(i)[2:]     # pad zeros to start of binary representtion     b = '0' * (nbits - len(b)) + b     print(b, end=' | ')  Out[2]:  0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 |  1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |   We stuck with the two buckets of  1000  and  0110  solely for dramatic effect. But even with 16 buckets — 1M vectors split into just 16 buckets still produces massively imprecise buckets.

In reality, we use many more hyperplanes — more hyperplanes mean higher resolution binary vectors — producing much more precise representations of our vectors. We control this resolution through hyperplanes with the nbits value. A higher  nbits  value improves search quality by increasing the resolution of hashed vectors. Increasing the nbits parameter increases the number of hyperplanes used to build the binary vector representations. Adding more possible combinations of hash values increases the potential number of buckets , increasing the number of comparisons and, therefore, search time. for nbits in [2, 4, 8, 16]:     print(f"nbits: {nbits}, buckets: {1 << nbits}")  In[1]:  Out[1]:  nbits: 2, buckets: 4 nbits: 4, buckets: 16 nbits: 8, buckets: 256 nbits: 16, buckets: 65536  It’s worth noting that not all buckets will necessarily be used — particularly with higher  nbits  values. We will see through our Faiss implementation that a  nbits  value of  128  or more is completely valid and still faster than using a flat index. There is also this notebook that covers a simple implementation of LSH in Python. LSH in Faiss  We have discussed Faiss before, but let’s briefly recap. Faiss — or Facebook AI Similarity Search — is an open-source framework built for enabling similarity search.

IndexLSH for Fast Similarity Search in Faiss  Watch on  Copy link  Copy link  Faiss has many super-efficient implementations of different indexes that we can use in similarity search. That long list of indexes includes IndexLSH  — an easy-to-use implementation of everything we have covered so far. We initialize our LSH index and add our Sift1M dataset  wb  like so:  In[3]:  import faiss  d = wb.shape[1] nbits = 4  # initialize the index using our vectors dimensionality (128) and nbits index = faiss.IndexLSH(d, nbits) # then add the data index.add(wb)  Once our index is ready, we can begin searching using index.search(xq, k)  — where  xq  is our one-or-more query vectors, and  k  is the number of nearest matches we’d like to return. In[4]:  xq0 = xq[0].reshape(1, d) # we use the search method to find the k nearest vectors D, I = index.search(xq0, k=10) # the indexes of these vectors are returned to I I  Out[4]:  array([[26, 47, 43,  2,  6, 70, 73, 74, 25,  0]])  The  search  method returns two arrays. Index positions  I  (e.g., row numbers from  wb ) of our  k  best matches. And the distances  D between those best matches and our query vector  xq0 .

Measuring Performance  Because we have those index positions in  I , we can retrieve the original vectors from our array  wb . # we can retrieve the original vectors from wb using I wb[I[0]]  array([[31., 15., 47., ...,  0.,  1., 19. ],        [ 0.,  0.,  0., ...,  0., 30., 72. ],        [22., 15., 43., ...,  0.,  0., 12. ],        ...,        [ 6., 15.,  9., ..., 12., 17., 21.

],        [33., 22.,  8., ...,  0., 11., 69. ],        [ 0., 16., 35., ..., 25., 23.,  1. ]], dtype=ﬂoat32)  # and calculate the cosine similarity between these and xq0 cosine_similarity(wb[I[0]], xq0)  In[7]:  Out[7]:  In[8]:  Out[8]:  array([[0.7344476 ],        [0.6316513 ],        [0.6995599 ],        [0.20448919],        [0.3054034 ],        [0.25432232],        [0.30497947],        [0.341374  ],        [0.6914262 ],        [0.26704744]], dtype=ﬂoat32)  And from those original vectors, we see if our LSH index is returning relevant results. We do this by measuring the cosine similarity between our query vector  xq0  and the top  k  matches. There are vectors in this index that should return similarity scores of around 0.8. We’re returning vectors with similarity scores of just 0.2 — why do we see such poor performance? Diagnosing Performance Issues  We know that the  nbits  value controls the number of potential buckets in our index. When initializing this index, we set  nbits == 4 — so all of our vectors must be stored across 4-digit, low-resolution buckets. If we try to cram 1M vectors into just 16 hash buckets, each of those buckets very likely contain 10–100K+ vectors. So, when we hash our search query, it matches one of these 16 buckets perfectly — but the index cannot differentiate between the huge number of vectors crammed into that single bucket — they all have the same hashed vector!

We can confirm this by checking our distances  D :  In[10]:  D  Out[10]:  array([[0., 0., 0., 0., 0., 0., 0., 0., 0., 0. ]], dtype=ﬂoat32)  We return a perfect distance score of zero for every item — but why? Well, we know that the Hamming distance can only be zero for perfect matches — meaning all of these hashed vectors must be identical. If all of these vectors return a perfect match, they must all have the same hash value. Therefore, our index cannot differentiate between them — they all share the same position as far as our LSH index is concerned. Now, if we were to increase  k  until we return a non-zero distance value, we should be able to infer the number of vectors that have been bucketed with this same hash code. Let’s go ahead and try it.

In[5]:  k = 100 xq0 = xq[0].reshape(1, d)  while True:     D, I = index.search(xq0, k=k)     if D.any() != 0:         print(k)         break     k += 100  Out[5]:  172100  In[6]:  D  # we will see both 0s, and 1s  Out[6]:  array([[0., 0., 0., ..., 1., 1., 1. ]], dtype=ﬂoat32)  In[7]:  D[:, 172_039:172_041]  # we see the hash code switch at position 172_039  Out[7]:  array([[0., 1. ]], dtype=ﬂoat32)  A single bucket containing  172_039  vectors. That means that we are choosing our top  k  values at random from those 172K vectors. Clearly, we need to reduce our bucket size.

With 1M samples, which  nbits  value gives us enough buckets for a more sparse distribution of vectors? It’s not possible to calculate the exact distribution, but we can take an average:  for nbits in [2, 4, 8, 16, 24, 32]:     buckets = 1 << nbits     print(f"nbits == {nbits}")     print(f"{wb.shape[0]} / {buckets} = {wb.shape[0]/buckets}")  In[11]:  Out[11]:  nbits == 2 1000000 / 4 = 250000.0 nbits == 4 1000000 / 16 = 62500.0 nbits == 8 1000000 / 256 = 3906.25 nbits == 16 1000000 / 65536 = 15.2587890625 nbits == 24 1000000 / 16777216 = 0.059604644775390625 nbits == 32 1000000 / 4294967296 = 0.00023283064365386963  With an  nbits  value of 16 we’re still getting an average of  15.25 vectors within each bucket — which seems better than it is. We must consider that some buckets will be significantly larger than others, as different regions will contain more vectors than others.

Realistically, the  nbits  values of  24  and  32  may be our tipping point towards genuinely effective bucket sizes. Let’s find the  mean cosine similarity for each of these values. In[11]:  xq0 = xq[0].reshape(1, d) k = 100  for nbits in [2, 4, 8, 16, 24, 32]:     index = faiss.IndexLSH(d, nbits)     index.add(wb)     D, I = index.search(xq0, k=k)     cos = cosine_similarity(wb[I[0]], xq0)     print(np.mean(cos))  Out[11]:  0.5424448 0.560827 0.6372647 0.6676912 0.7162514 0.7048228  It looks like our estimate is correct — the overall similarity for our top 100 vectors experiences a sudden with each nbits increment before leveling off at the  nbits == 24  point.

But what if we run the process with even larger  nbits  values? As we increase vector resolution with nbits, our results will become more precise — here, we can see that a larger nbits value  results in higher cosine similarity in our results.

Here, the results are apparent. A fast increase in similarity as we declutter the LSH buckets — followed by a slower increase in similarity. The latter, slower increase in similarity is thanks to the increasing resolution of our hashed vectors. Our buckets are already very sparse — we have many more potential buckets than we have vectors , so we can find little to no performance increase there. But — we are increasing the resolution and, therefore, the precision of those buckets, so we pull the additional performance from here.

Extracting The Binary Vectors  While investigating our index and the distribution of vectors across our buckets above, we inferred the problem of our bucket sizes. This is useful as we’re using what we have already learned about LSH and can see the effects of the indexes' properties. However, we can take a more direct approach.

Faiss allows us to indirectly view our buckets by extracting the binary vectors representations of  wb . Let’s revert to our  nbits  value of 4 and see what is stored in our LSH index. # extract index binary codes (represented as int) arr = faiss.vector_to_array(index.codes) arr  Out[2]:  array([ 5, 12,  5, ..., 15, 13, 12], dtype=uint8)  # we see that there are 1M of these values, 1 for each vector arr.shape  Out[3]:  (1000000,)  # now translate them into the binary vector format (((arr[:, None] & (1 << np.arange(nbits)))) > 0).astype(int)  In[2]:  In[3]:  In[4]:  Out[4]:  array([[1, 0, 1, 0],        [0, 0, 1, 1],        [1, 0, 1, 0],        ...,        [1, 1, 1, 1],        [1, 0, 1, 1],        [0, 0, 1, 1]])  From this, we can visualize the distribution of vectors across those 16 buckets — showing the most used buckets and a few that are empty. Distribution of vectors in different buckets when nbits == 4. This and our previous logic are all we need to diagnose the aforementioned bucketing issues. Where to Use LSH  While LSH can be a swift index, it is less accurate than a Flat index. Using increasingly larger portions of our Sift1M dataset, the best recall score was achieved using an  nbits  value of  768  (better recall is possible at excessive search times). Recall against the number of indexed vectors. The recall is measured as the % of matches with exhaustive search results  (using IndexFlatL2).

Although it’s worth noting that using an  nbits  value of  768  only returns marginally faster results than if using a flat index. Search time as a factor of search time for IndexFlatL2 at different index sizes and using various nbits values. More realistic recall rates — while maintaining a reasonable speed increase — are closer to 40%.

However, varying dataset sizes and dimensionality can make a huge difference. An increase in dimensionality means a higher  nbits  value must be used to maintain accuracy, but this can still enable faster search speeds. It is simply a case of finding the right balance for each use-case and dataset. Now, of course, there are many options out there for vector similarity search. Flat indexes and LSH are just two of many options — and choosing the right index is a mix of experimentation and know-how. As always, similarity search is a balancing act between different indexes and parameters to find the best solutions for our use-cases. We’ve covered a lot on LSH in this article. Hopefully, this has helped clear up any confusion on one of the biggest algorithms in the world of search.

LSH is a complex topic, with many different approaches — and even more implementations available across several libraries. Beyond LSH, we have many more algorithms suited for efficient similarity search, such as HNSW, IVF, and PQ. You can learn more in our overview of vector search indexes. Subscribe for updates on similarity search! Email address...

Submit  References  Jupyter Notebooks  [1] Google Searches, Skai.io Blog  Next Chapter: Product Quantization  Comments Start Discussion  0 replies  What will you build? Upgrade your search or recommendation systems with just a few  lines of code, or contact us for help. Create Account  Pinecone  Pricing  Docs  Learn  Company  Contact  Careers  Get product and article updates  Email address  Get Updates  © Pinecone Systems, Inc. | San Francisco, CA | Terms | Privacy | Product Privacy | Cookies | Trust & Security | System Status Pinecone is a registered trademark of Pinecone Systems, Inc.

01-Introduction to Facebook AI Similarity Search (Faiss) | Pinecone.pdf

Pricing  Docs  Learn  Company  Contact  We're hiring! Log In  Sign Up Free  1. Introduction to Facebook  AI Similarity Search (Faiss)  What is it that makes Faiss special? How do we make the best use of this incredible tool?

Introduction to Facebook AI Similarity Search (Faiss)  Facebook AI Similarity Search (Faiss) is one of the most popular implementations of efficient similarity search, but what is it — and how can we use it? Note: Pinecone lets you implement vector search into your applications with just a few API calls, without knowing anything about Faiss. However, you like seeing how things work, so enjoy the guide! Fortunately, it’s a brilliantly simple process to get started with. And in this article, we’ll explore some of the options FAISS provides, how they work, and — most importantly — how Faiss can make our search faster. Check out the video walkthrough here:  Faiss - Introduction to Similarity Search  Faiss: The Missing Manual  Chapters:  What is Faiss? Building Some Vectors Plain and Simple IndexFlatL2 Partitioning The Index Quantization  2. Nearest Neighbor  Indexes for Similarity Search  3. Locality Sensitive  Hashing (LSH): The Illustrated Guide  4. Random Projection for  Locality Sensitive Hashing  5.

Product Quantization  6. Hierarchical Navigable Small Worlds (HNSW)  7. Composite Indexes and  res = requests.get('https://raw.githubusercontent.com/brmson/dataset-sts/master/data/sts/sick2014/SICK_train.txt' # create dataframe data = pd.read_csv(StringIO(res.text), sep='\t') data.head()  urls = [     'https://raw.githubusercontent.com/brmson/dataset-sts/master/data/sts/semeval-sts/2012/MSRpar.train.tsv'     'https://raw.githubusercontent.com/brmson/dataset-sts/master/data/sts/semeval-sts/2012/MSRpar.test.tsv'     'https://raw.githubusercontent.com/brmson/dataset-sts/master/data/sts/semeval-sts/2012/OnWN.test.tsv'     'https://raw.githubusercontent.com/brmson/dataset-sts/master/data/sts/semeval-sts/2013/OnWN.test.tsv'     'https://raw.githubusercontent.com/brmson/dataset-sts/master/data/sts/semeval-sts/2014/OnWN.test.tsv'     'https://raw.githubusercontent.com/brmson/dataset-sts/master/data/sts/semeval-sts/2014/images.test.tsv'     'https://raw.githubusercontent.com/brmson/dataset-sts/master/data/sts/semeval-sts/2015/images.test.tsv' ]  # each of these dataset have the same structure, so we loop through each creating our sentences data for url in urls:     res = requests.get(url)     # extract to dataframe     data = pd.read_csv(StringIO(res.text), sep='\t', header=None, error_bad_lines     # add to columns 1 and 2 to sentences list     sentences.extend(data[1].tolist())     sentences.extend(data[2].tolist())  Watch on  What is Faiss? Before we get started with any code, many of you will be asking — what is Faiss? Faiss is a library — developed by Facebook AI — that enables efficient similarity search.

So, given a set of vectors, we can index them using Faiss — then using another vector (the query vector), we search for the most similar vectors within the index. Now, Faiss not only allows us to build an index and search — but it also speeds up search times to ludicrous performance levels — something we will explore throughout this article. Building Some Vectors  The first thing we need is data, we’ll be concatenating several datasets from this semantic test similarity hub repo.

We will download each dataset, and extract the relevant text columns into a single list. In[1]:  import requests from io import StringIO import pandas as pd  The ﬁrst dataset is in a slightly different format:     pair_ID                                         sentence_A  \ 0        1  A group of kids is playing in a yard and an ol...    1        2  A group of children is playing in the house an...    2        3  The young boys are playing outdoors and the ma...    3        5  The kids are playing outdoors near a man with ...    4        9  The young boys are playing outdoors and the ma...                                               sentence_B   relatedness_score  \ 0  A group of boys in a yard is playing and a man...                 4.5    1  A group of kids is playing in a yard and an ol...                 3.2    2  The kids are playing outdoors near a man with ...                 4.7    3  A group of kids is playing in a yard and an ol...                 3.4    4  A group of kids is playing in a yard and an ol...                 3.7       entailment_judgment   0             NEUTRAL   1             NEUTRAL   2          ENTAILMENT   3             NEUTRAL   4             NEUTRAL    # we take all samples from both sentence A and B sentences = data['sentence_A'].tolist() sentences[:5]  ['A group of kids is playing in a yard and an old man is standing  in the background',  'A group of children is playing in the house and there is no man  standing in the background',  'The young boys are playing outdoors and the man is smiling  nearby',  'The kids are playing outdoors near a man with a smile',  'The young boys are playing outdoors and the man is smiling  nearby']  # we take all samples from both sentence A and B sentences = data['sentence_A'].tolist() sentence_b = data['sentence_B'].tolist() sentences.extend(sentence_b)  # merge them len(set(sentences))  # together we have ~4.5K unique sentences  Out[6]:  4802  This isn't a particularly large number, so let's pull in a few  more similar datasets. In[4]:  Out[4]:  In[5]:  Out[5]:  In[6]:  In[7]:  In[8]:  Out[8]:  b'Skipping line 191: expected 3 ﬁelds, saw 4\nSkipping line 206:  expected 3 ﬁelds, saw 4\nSkipping line 295: expected 3 ﬁelds, saw  4\nSkipping line 695: expected 3 ﬁelds, saw 4\nSkipping line 699:  expected 3 ﬁelds, saw 4\n' b'Skipping line 104: expected 3 ﬁelds, saw 4\nSkipping line 181:  expected 3 ﬁelds, saw 4\nSkipping line 317: expected 3 ﬁelds, saw  4\nSkipping line 412: expected 3 ﬁelds, saw 5\nSkipping line 508:  expected 3 ﬁelds, saw 4\n'  In[9]:  len(set(sentences))  Out[9]:  14505  Next, we remove any duplicates, leaving us with 14.5K unique sentences.

Finally, we build our dense vector representations of each sentence using the sentence-BERT library. # remove duplicates and NaN sentences = [word for word in list(set(sentences)) if type(word) is  In[6]:  In[7]:  from sentence_transformers import SentenceTransformer # initialize sentence transformer model model = SentenceTransformer('bert-base-nli-mean-tokens') # create sentence embeddings sentence_embeddings = model.encode(sentences) sentence_embeddings.shape  Out[7]:  (14504, 768)  Now, building these sentence embeddings can take some time — so feel free to download them directly from here (you can use this script to load them into Python).

Plain and Simple  We’ll start simple. First, we need to set up Faiss. Now, if you’re on Linux — you’re in luck — Faiss comes with built-in GPU optimization for any CUDA-enabled Linux machine. MacOS or Windows?

Well, we’re less lucky. (Don’t worry, it’s still ludicrously fast)  So, CUDA-enabled Linux users, type  conda install -c pytorch faiss-gpu . Everyone else,  conda install -c pytorch faiss-cpu . If you don’t want to use  conda  there are alternative installation instructions here. Once we have Faiss installed we can open Python and build our first, plain and simple index with  IndexFlatL2 . IndexFlatL2  IndexFlatL2  measures the L2 (or Euclidean) distance between all given points between our query vector, and the vectors loaded into the index. It’s simple, very accurate, but not too fast.

L2 distance calculation between a query vector xq and our indexed vectors (shown as y)  In Python, we would initialize our  IndexFlatL2  index with our vector dimensionality ( 768  — the output size of our sentence embeddings) like so:  In[8]:  import faiss  In[9]:  d = sentence_embeddings.shape[1] d  Out[9]:  768  In[10]:  index = faiss.IndexFlatL2(d)  In[11]:  index.is_trained  Out[11]:  True  Often, we’ll be using indexes that require us to train them before loading in our data. We can check whether an index needs to be trained using the  is_trained  method. IndexFlatL2  is not an index that requires training, so we should return  False .

Once ready, we load our embeddings and query like so:  In[5]:  index.add(sentence_embeddings)  In[6]:  index.ntotal  Out[6]:  14504  In[7]:  In[8]:  In[9]:  Out[9]:  Then search given a query `xq` and number of nearest neigbors to  return `k`. k = 4 xq = model.encode(["Someone sprints with a football"])  %%time D, I = index.search(xq, k)  # search print(I)  Out[8]:  [[4586 10252 12465  190]] CPU times: user 27.9 ms, sys: 29.5 ms, total: 57.4 ms Wall time: 28.9 ms  Here we're returning indices `4586`, `10252`, `12465`, and `190`,  which returns:  data['sentence_A'].iloc[[4586, 10252, 12465, 190]]  4586    A group of football players is running in the ﬁeld 10252    A group of people playing football is running past the  person 12465      Two groups of people are playing football 190    A football player is running past an ofﬁcial Name: sentence_A, dtype: object  Which returns the top  k  vectors closest to our query vector  xq  as 7460 ,  10940 ,  3781 , and  5747 . Clearly, these are all great matches — all including either people running with a football or in the context of a football match.

Now, if we’d rather extract the numerical vectors from Faiss, we can do that too. In[9]:  # we have 4 vectors to return (k) - so we initialize a zero array to hold them vecs = np.zeros((k, d))  Copy link  # then iterate through each ID from I and add the reconstructed vector to our zero-array for i, val in enumerate(I[0].tolist()):     vecs[i, :] = index.reconstruct(val)  In[10]:  vecs.shape  Out[10]:  (4, 768)  In[11]:  vecs[0][:100]  Out[11]:  array([ 0.01627046,  0.22325929, -0.15037425, -0.30747262,  -0.27122435,        -0.10593167, -0.0646093 ,  0.04738174, -0.73349041,  -0.37657705,        -0.76762843,  0.16902871,  0.53107643,  0.51176691,   1.14415848,        -0.08562929, -0.67240077, -0.96637076,  0.02545463,  -0.21559823,        -1.25656605, -0.82982153, -0.09825023, -0.21850856,   0.50610232,         0.10527933,  0.50396878,  0.65242976, -1.39458692,   0.6584745 ,        -0.21525341, -0.22487433,  0.81818348,  0.084643  ,  -0.76141697,        -0.28928292, -0.09825806, -0.73046201,  0.07855812,  -0.84354657,        -0.59242058,  0.77471375, -1.20920527, -0.22757971,  -1.30733597,        -0.23081468, -1.31322539,  0.01629073, -0.97285444,   0.19308169,         0.47424558,  1.18920875, -1.96741307, -0.70061135,  -0.29638717,         0.60533702,  0.62407452, -0.70340395, -0.86754197,   0.17673187,        -0.1917053 , -0.02951987,  0.22623563, -0.16695444,  -0.80402541,        -0.45918915,  0.69675523, -0.24928184, -1.01478696,  -0.921745  ,        -0.33842632, -0.39296737, -0.83734828, -0.11479235,   0.46049669,        -1.4521122 ,  0.60310453,  0.38696304, -0.04061254,   0.00453161,         0.24117804,  0.05396278,  0.07506453,  1.05115867,   0.12383959,        -0.71281093,  0.11722917,  0.52238214, -0.04581215,   0.26827109,         0.8598538 , -0.3566995 , -0.64667088, -0.5435797 ,  -0.0431047 ,         0.95139188, -0.15605772, -0.49625337, -0.11140176,   0.15610115])  Speed  Using the  IndexFlatL2  index alone is computationally expensive, it doesn’t scale well. When using this index, we are performing an exhaustive search — meaning we compare our query vector  xq  to every other vector in our index, in our case that is 14.5K L2-distance calculations for every search. Imagine the speed of our search for datasets containing 1M, 1B, or even more vectors — and when we include several query vectors?

Milliseconds taken to return a result (y-axis) / number of vectors in the index (x-axis) — relying solely on IndexFlatL2 quickly  becomes slow  Our index quickly becomes too slow to be useful, so we need to do something different.

Partitioning The Index  Faiss allows us to add multiple steps that can optimize our search using many different methods. A popular approach is to partition the index into Voronoi cells. We can imagine our vectors as each being contained within a Voronoi cell — when we introduce a new query vector, we first  measure its distance between centroids, then restrict our search scope to that centroid’s cell. Using this method, we would take a query vector  xq , identify the cell it belongs to, and then use our  IndexFlatL2  (or another metric) to search between the query vector and all other vectors belonging to that specific cell. So, we are reducing the scope of our search, producing an approximate answer, rather than exact (as produced through exhaustive search). To implement this, we first initialize our index using  IndexFlatL2  — but this time, we are using the L2 index as a quantizer step — which we feed into the partitioning  IndexIVFFlat  index. In[12]:  nlist = 50  # how many cells quantizer = faiss.IndexFlatL2(d) index = faiss.IndexIVFFlat(quantizer, d, nlist)  Here we’ve added a new parameter  nlist . We use  nlist  to specify how many partitions (Voronoi cells) we’d like our index to have.

Now, when we built the previous  IndexFlatL2 -only index, we didn’t need to train the index as no grouping/transformations were required to build the index. Because we added clustering with  IndexIVFFlat , this is no longer the case. So, what we do now is train our index on our data — which we must do before adding any data to the index. In[13]:  index.is_trained  Out[13]:  False  In[14]:  Out[14]:  True  In[15]:  Out[15]:  14504  index.train(sentence_embeddings) index.is_trained  # check if index is now trained  index.add(sentence_embeddings) index.ntotal  # number of embeddings indexed  Now that our index is trained, we add our data just as we did before. Let’s search again using the same indexed sentence embeddings and the same query vector  xq . In[15]:  %%time D, I = index.search(xq, k)  # search print(I)  Out[15]:  [[ 7460 10940  3781  5747]] CPU times: user 3.83 ms, sys: 3.25 ms, total: 7.08 ms Wall time: 2.15 ms  The search time has clearly decreased, in this case, we don’t find any difference between results returned by our exhaustive search, and this approximate search. But, often this can be the case. If approximate search with  IndexIVFFlat  returns suboptimal results, we can improve accuracy by increasing the search scope. We do this by increasing the  nprobe  attribute value — which defines how many nearby cells to search.

Searching the single closest cell when nprobe == 1 (left), and searching the eight closest cells when nprobe == 8 (right)  We can implement this change easily. We can increase the number of nearby cells to search too with  `nprobe`. index.nprobe = 10  In[16]:  In[17]:  %%time D, I = index.search(xq, k)  # search print(I)  Out[17]:  [[ 7460 10940  3781  5747]] CPU times: user 5.29 ms, sys: 2.7 ms, total: 7.99 ms Wall time: 1.54 ms  Now, because we’re searching a larger scope by increasing the nprobe  value, we will see the search speed increase too. Query time / number of vectors for the IVFFlat index with different nprobe values — 1, 5, 10, and 20  Although, even with the larger  nprobe  value we still see much faster responses than we returned with our  IndexFlatL2 -only index. Vector Reconstruction  If we go ahead and attempt to use index.reconstruct(<vector_idx>)  again, we will return a RuntimeError  as there is no direct mapping between the original vectors and their index position, due to the addition of the IVF step.

So, if we’d like to reconstruct the vectors, we must first create these direct mappings using  index.make_direct_map() . index.make_direct_map()  index.reconstruct(7460)[:100]  In[19]:  In[20]:  Out[20]:  array([ 0.01627046,  0.22325929, -0.15037425, -0.30747262,  -0.27122435,        -0.10593167, -0.0646093 ,  0.04738174, -0.7334904 ,  -0.37657705,        -0.76762843,  0.16902871,  0.53107643,  0.5117669 ,   1.1441585 ,        -0.08562929, -0.6724008 , -0.96637076,  0.02545463,  -0.21559823,        -1.256566  , -0.8298215 , -0.09825023, -0.21850856,   0.5061023 ,         0.10527933,  0.5039688 ,  0.65242976, -1.3945869 ,   0.6584745 ,        -0.21525341, -0.22487433,  0.8181835 ,  0.084643  ,  -0.761417  ,        -0.28928292, -0.09825806, -0.730462  ,  0.07855812,  -0.84354657,        -0.5924206 ,  0.77471375, -1.2092053 , -0.22757971,  -1.307336  ,        -0.23081468, -1.3132254 ,  0.01629073, -0.97285444,   0.19308169,         0.47424558,  1.1892087 , -1.9674131 , -0.70061135,  -0.29638717,         0.605337  ,  0.6240745 , -0.70340395, -0.86754197,   0.17673187,        -0.1917053 , -0.02951987,  0.22623563, -0.16695444,  -0.8040254 ,        -0.45918915,  0.69675523, -0.24928184, -1.014787  ,  -0.921745  ,        -0.33842632, -0.39296737, -0.8373483 , -0.11479235,   0.4604967 ,        -1.4521122 ,  0.60310453,  0.38696304, -0.04061254,   0.00453161,         0.24117804,  0.05396278,  0.07506453,  1.0511587 ,   0.12383959,        -0.71281093,  0.11722917,  0.52238214, -0.04581215,   0.2682711 ,         0.8598538 , -0.3566995 , -0.6466709 , -0.5435797 ,  -0.0431047 ,         0.9513919 , -0.15605772, -0.49625337, -0.11140176,   0.15610115],       dtype=ﬂoat32)  And from there we are able to reconstruct our vectors just as we did before. Quantization  We have one more key optimization to cover. All of our indexes so far have stored our vectors as full (eg  Flat ) vectors. Now, in very large datasets this can quickly become a problem.

Fortunately, Faiss comes with the ability to compress our vectors using Product Quantization (PQ). But, what is PQ?

Well, we can view it as an additional approximation step with a similar outcome to our use of IVF. Where IVF allowed us to approximate by reducing the scope of our search, PQ approximates the distance/similarity calculation instead. PQ achieves this approximated similarity operation by compressing the  vectors themselves, which consists of three steps. Three steps of product quantization  1. We split the original vector into several subvectors. 2. For each set of subvectors, we perform a clustering operation —  creating multiple centroids for each sub-vector set.

3. In our vector of sub-vectors, we replace each sub-vector with the ID  of it’s nearest set-specific centroid. To implement all of this, we use the IndexIVFPQ index — we’ll also need to  train  the index before adding our embeddings. In[21]:  m = 8  # number of centroid IDs in final compressed vectors bits = 8 # number of bits in each centroid  quantizer = faiss.IndexFlatL2(d)  # we keep the same L2 distance flat index index = faiss.IndexIVFPQ(quantizer, d, nlist, m, bits)   `train` the index.

In[22]:  index.is_trained  Out[22]:  False  In[23]:  index.train(sentence_embeddings)  And `add` our vectors. In[23]:  index.add(sentence_embeddings)  And now we’re ready to begin searching using our new index. index.nprobe = 10  # align to previous IndexIVFFlat nprobe value  In[24]:  In[25]:  %%time D, I = index.search(xq, k) print(I)  Out[25]:  [[ 5013 10940  7460  5370]] CPU times: user 3.04 ms, sys: 2.18 ms, total: 5.22 ms Wall time: 1.33 ms  Speed or Accuracy? Through adding PQ we’ve reduced our IVF search time from ~7.5ms to ~5ms, a small difference on a dataset of this size — but when scaled up this becomes significant quickly. However, we should also take note of the slightly different results being returned.

Beforehand, with our exhaustive L2 search, we were returning 7460 ,  10940 ,  3781 , and  5747 . Now, we see a slightly different order of results — and two different IDs,  5013  and  5370 . Both of our speed optimization operations, IVF and PQ, come at the cost of accuracy.

Now, if we print out these results we will still find that each item is relevant:  [f'{i}: {sentences[i]}' for i in I[0]]  In[26]:  Out[26]:  ['5013: A group of football players running down the ﬁeld. ',  '10940: A group of people playing football is running in the  ﬁeld',  '7460: A group of football players is running in the ﬁeld',  '5370: A football player is running past an ofﬁcial carrying a  football']  So, although we might not get the perfect result, we still get close — and thanks to the approximations, we get a much faster response. Query time / number of vectors for our three indexes  And, as shown in the graph above, the difference in query times become increasingly relevant as our index size increases.

That’s it for this article! We’ve covered the essentials to getting started with building high-performance indexes for search in Faiss. Clearly, a lot can be done using  IndexFlatL2 ,  IndexIVFFlat , and  IndexIVFPQ  — and each has many parameters that can be fine- tuned to our specific accuracy/speed requirements.

And as shown, we can produce some truly impressive results, at lightning-fast speeds very easily thanks to Faiss. Want to run Faiss in production? Pinecone provides vector similarity search that’s production-ready, scalable, and fully managed. Next Chapter: Nearest Neighbor Indexes for Similarity Search  Comments 1 reply  suraj  Continue Discussion  Now, because we’re searching a larger scope by increasing the nprobe value, we will see the search speed increase too. Do we see the search speed increase too, or the search time?

Nov '22  What will you build? Upgrade your search or recommendation systems with just a few  lines of code, or contact us for help. Create Account  Pricing  Docs  Learn  Company  Contact  Careers  © Pinecone Systems, Inc. | San Francisco, CA | Terms | Privacy | Product Privacy | Cookies | Trust & Security | System Status Pinecone is a registered trademark of Pinecone Systems, Inc.  Get product and article updates  Email address  Get Updates