<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Search In Practice- Approximate Nearest Neighbors 🔎
Step1:  Motivation 🎇
Used to find similar entries
Recommendation systems
Search engines
Spell checking
Many more
Nearest Neighbors
Our Dataset 💾
Use the movielens dataset 
Contains 100k rows with X dimentions
Step2:  Strategies for Exact Nearest Neighbors 🧠
Exhaustive Search
Step3:  But It’s Not All Rainbows And Unicorns 🦄
Most modern-day applications have massive datasets with high dimensionality.
Linear scan will take a while. 
Additional constraints such as reasonable memory consumption and/or low latency.
The only method guaranting exact nearest neighbor is exhaustive search
Approximate Nearest Neighbors’ Motivation 🎇
Enable fast searches
While controling Memory, Precision, and Performance  tradeoffs 
Can do full calculation after entries being fetched
Strategies for approximate nearest neighbors 🧠
Vector Transformation — applied on vector before they are indexed.
amongst them there is dimensionality reduction and vector rotation.
Vector Encoding — applied on vectors in order to construct the actual index for search.
amongst these there are data structure-based techniques like Trees, LSH and Quantization a technique to encode the vector to a much more compact form.
None Exhaustive Search Component — applied on vectors in order to avoid exhaustive search. 
amongst these techniques there are Inverted Files and Neighborhood Graphs
None Exhaustive Search Component IVF
We can avoid the exhaustive search 
Partition our dataset in such a way that on search, we only query relevant partitions.
Most datasets are actually multi-modal
Dividing the dataset up this way reduce accuracy 
You can search for multiple partitions 
Time/accuracy tradeoff sweet spot.
Step4:  Vector Encoding using Product Quantization
reduce the size of the dataset by replacing every vector with a leaner approximated representation of the vectors 
Give similar vectors to the same representation.
This can be done by clustering similar vectors and represent each of those as the centroid
We can use k-means again
This will allow us to represent each vector in a much more efficient way log(k) bit per vector since each vector can be represented in the label of the centroid.
In our example, each vector is represented by one of the centroids. 
since we have 2042 centroids we can represent each vector with 11 bits, as opposed to 4096 ( 1024*32 ).
This amazing compaction comes with a great cost 
we lose accuracy as we now cant separate the original vector from the centroid.
to increase the accuracy of our vectors we need to increase drastically the number of centroids
makes regurlar Quantization phase infeasible in practice.
Gave birth to Product Quantization 
We can increase the number of centroids by dividing each vector into many vectors and run our quantizer on all of these.
In our example, each vector is represented by 8 sub-vectors which can be represented by one of the centroids. 
Since we have 256 centroids we can represent each matrix in 1 byte
Making vector representation 8byte only as oppose to 4096 ( 1024*32 ).
Although it increases the size of the vector a bit compared to the regular quantizer, it’s still O(log(k)) and allows us to increase the accuracy drastically and still work in practice.
Unfortunately in terms of search, even though we can calculate the distances in more efficiently using table look-ups and some addition. We are still going to do an exhaustive search.
    In our example, this means that this means building a table of subvector distances with 256 rows (one for each centroid) and 8 columns (one for each subvector). Remember that each database vector is now just a sequence of 8 centroid ids.
The exact nearest neighb
<ASSISTANT_TASK:>
Python Code:
# Additional Resources 📚
Explanation: Search In Practice- Approximate Nearest Neighbors 🔎
End of explanation
import pickle
import faiss
def load_data():
    with open('movies.pickle', 'rb') as f:
        data = pickle.load(f)
    return data
data = load_data()
vectors = data["vector"]
names = data["name"]
data
faiss.MatrixStats(vectors).comments.split("\n")
Explanation: Motivation 🎇
Used to find similar entries
Recommendation systems
Search engines
Spell checking
Many more
Nearest Neighbors
Our Dataset 💾
Use the movielens dataset 
Contains 100k rows with X dimentions
End of explanation
index = faiss.IndexFlatL2(vectors.shape[1])
index.add(vectors)
search_vector = vectors[90:91]
distances, indices = index.search(search_vector, 10)
print(f"The most similar movies to {names[90]} are:\n")
print([names[i] for i in indices[0]])
Explanation: Strategies for Exact Nearest Neighbors 🧠
Exhaustive Search: Comparing each point to every other point, which will require Linear query time (the size of the dataset and the dimention ).
knn -> O(Nlogk)
The Grid Trick: subdividing the space to a Grid, which will require exponential space/time (in the dimensionality of the dataset).
kd trees
quad-trees
metric trees
logn query time and n^(d/2) space
Since we are speaking on high dimension datasets the grid trick is impractical.
Exhaustive Search Using Faiss
Support comparision using matrix multiplication or using loops
Support multiple metrics
Running as a batch
Support GPU / CPU
Cache Friendly
A typical operation in IndexFlatL2 is to exhaustively compare a set of nq query vectors and a set of nb database vectors in dimension d (then select the top-k smallest vectors).
Faiss has two implementations of this operation:
direct implementation that loops over nq, nb and the dimension of the vectors.
an implementation that uses the decomposition d(x, y) = ||x||^2 + ||y||^2 - 2 * <x, y>. This is faster because the most expensive operation in O(nq * nb * d) can be handed over to BLAS that normally does this efficiently.
We use implementation 1 when nq < 20, and implementation 2 otherwise. The threshold 20 can be adjusted via global variable faiss::distance_compute_blas_threshold (accessible in Python via faiss.cvar.distance_compute_blas_threshold).
Note that solution 2 may be less stable numerically than 1 for vectors of very different magnitudes, see discussion in issue #297.
Faiss provides low-level functions to do the brute-force search in this context.
The functions take a matrix of database vectors and a matrix of query vectors and return the k-nearest neighbors and their distances.
End of explanation
quantizer = faiss.IndexFlatL2(vectors.shape[1])
index = faiss.IndexIVFFlat(quantizer, 
                           vectors.shape[1], 
                           100,             # number_of_partition,
                           8)               # search_in_x_partitions
index.train(vectors)
index.add(vectors)
search_vector = vectors[90:91]
distances, indices = index.search(search_vector, 10)
print(f"The most similar movies to {names[90]} are:\n")
print([names[i] for i in indices[0]])
Explanation: But It’s Not All Rainbows And Unicorns 🦄
Most modern-day applications have massive datasets with high dimensionality.
Linear scan will take a while. 
Additional constraints such as reasonable memory consumption and/or low latency.
The only method guaranting exact nearest neighbor is exhaustive search
Approximate Nearest Neighbors’ Motivation 🎇
Enable fast searches
While controling Memory, Precision, and Performance  tradeoffs 
Can do full calculation after entries being fetched
Strategies for approximate nearest neighbors 🧠
Vector Transformation — applied on vector before they are indexed.
amongst them there is dimensionality reduction and vector rotation.
Vector Encoding — applied on vectors in order to construct the actual index for search.
amongst these there are data structure-based techniques like Trees, LSH and Quantization a technique to encode the vector to a much more compact form.
None Exhaustive Search Component — applied on vectors in order to avoid exhaustive search. 
amongst these techniques there are Inverted Files and Neighborhood Graphs
None Exhaustive Search Component IVF
We can avoid the exhaustive search 
Partition our dataset in such a way that on search, we only query relevant partitions.
Most datasets are actually multi-modal
Dividing the dataset up this way reduce accuracy 
You can search for multiple partitions 
Time/accuracy tradeoff sweet spot.
End of explanation
quantizer = faiss.IndexFlatL2(vectors.shape[1])
index = faiss.IndexIVFPQ(quantizer, 
                         vectors.shape[1], 
                         100,             # number_of_partition,
                         8,               # search_in_x_partitions, 
                         8)               # subvector_size
index.train(vectors)
index.add(vectors)
search_vector = vectors[90:91]
distances, indices = index.search(search_vector, 10)
print(f"The most similar movies to {names[90]} are:\n")
print([names[i] for i in indices[0]])
Explanation: Vector Encoding using Product Quantization
reduce the size of the dataset by replacing every vector with a leaner approximated representation of the vectors 
Give similar vectors to the same representation.
This can be done by clustering similar vectors and represent each of those as the centroid
We can use k-means again
This will allow us to represent each vector in a much more efficient way log(k) bit per vector since each vector can be represented in the label of the centroid.
In our example, each vector is represented by one of the centroids. 
since we have 2042 centroids we can represent each vector with 11 bits, as opposed to 4096 ( 1024*32 ).
This amazing compaction comes with a great cost 
we lose accuracy as we now cant separate the original vector from the centroid.
to increase the accuracy of our vectors we need to increase drastically the number of centroids
makes regurlar Quantization phase infeasible in practice.
Gave birth to Product Quantization 
We can increase the number of centroids by dividing each vector into many vectors and run our quantizer on all of these.
In our example, each vector is represented by 8 sub-vectors which can be represented by one of the centroids. 
Since we have 256 centroids we can represent each matrix in 1 byte
Making vector representation 8byte only as oppose to 4096 ( 1024*32 ).
Although it increases the size of the vector a bit compared to the regular quantizer, it’s still O(log(k)) and allows us to increase the accuracy drastically and still work in practice.
Unfortunately in terms of search, even though we can calculate the distances in more efficiently using table look-ups and some addition. We are still going to do an exhaustive search.
    In our example, this means that this means building a table of subvector distances with 256 rows (one for each centroid) and 8 columns (one for each subvector). Remember that each database vector is now just a sequence of 8 centroid ids.
The exact nearest neighb
End of explanation
<END_TASK>