# Fast PQ
FastPQ is a lightweight Python Vector Database specifically designed to offer high performance and be easy to read.
The main ingredient is an optimized implementation of 4bit Product Quantization (PQ) which enables fast approximate distance computations, 50 times faster than NumPy/BLAS.
<p align="center">
(Performance tradeoff on <a href="http://ann-benchmarks.com/glove-100-angular_10_angular.html">ANN Benchmarks</a>. Up and to the right is better.)
</p>
## Features
FastPQ is a very lightweight index, much smaller than the dataset itself.
It is also quick to build, requiring only a single pass of sklearn's KMeans over the dataset.
## Example
Let's generate some random data
```python
import numpy as np
X = np.random.rand(10000, 128)
queries = np.random.rand(100, 128)
```
We can use the `FastPQ` class to quantize the data and perform nearest neighbor search.
```python
from fast_pq import FastPQ
# Initialize PQ with 64 columns of 2 dimensions each
pq = FastPQ(dims_per_block=2)
X_compressed = pq.fit_transform(X)
# Compute exact k-nearest neighbors, accelerated by PQ
for q in queries:
distance_table = pq.distance_table(q)
est8 = distance_table.estimate_distances(X_compressed)
print("Probably nearest neighbor:", est8.argmin())
```
This will return the 10 nearest neighbors for each query, as well as the distances to those neighbors.
Note that we want a quite low `dims_per_block` compared to other Product Quantization methods, since we only use 4 bits per block.
This again can be attributed to the SSE instructions only allowing 4 bit table lookups.
We can use the `IVF` class to perform approximate nearest neighbor search with Inverted File Indexing.
```python
from fast_pq import IVF
ivf = IVF("euclidean", n_clusters=100).fit(X).build(X)
neighbors = ivf.query(queries, k=10, n_probes=10)
```
This will perform approximate nearest neighbor search using Inverted File Indexing, with 10 probes for each query. Note that we first have to call the `fit` method to build the codebook, and then the `build` method to populate the inverted file.
See also `examples/` for more detailed examples of usage.
## Installing
You need to build `fast_pq` before you can run it, as it contains Cython code.
The easiest way to do this is to simply run
```bash
$ pip install .
```
To test it we can run an example:
```bash
$ python -m examples.example
n=16000, d=128, queries=1000, dims_per_block=2
Sampling
Computing true neighbours
Fitting PQ
Querying
Median place of true nearest neighbor: 1.0
90% quantile: 19.0
Queries/second: 7101.262693814528
Total time spent on preprocess: 0.09025406837463379
Total time spent on search: 0.05056595802307129
Scipy speed for comparison: 2.249645948410034
```
In this example Fast PQ is about 16 times faster than optmized scipy/numpy.
The reason is that Fast PQ uses a trick called [Accelerated Nearest Neighbor Search with Qick ADC](https://dl.acm.org/doi/abs/10.1145/3078971.3078992)
with which SIMD instructions are used to perform 16 inner product operations in a single instruction.
### Developing
If you are helping develop fast_pq, and need to test a change to the Cython code, you can rebuild it with
```bash
$ python setup.py build_ext --inplace
```
## Class Overview
The project consists of two main classes: IVF and FastPQ. The IVF class is used to build an IVF index with cluster centers, fit a product quantizer on the data, and perform queries on the index. The FastPQ class is used to create a product quantizer that can quickly transform data and compute distance tables.
IVF: This class is responsible for creating an IVF index using clustering (either Euclidean or angular) and FastPQ for quantization. It provides methods to fit the index on data, build the index with quantized data, and query the index for nearest neighbors.
Main methods:
- **fit**: Fit the IVF index on the given data by finding cluster centers and fitting the product quantizer.
- **build**: Build the IVF index by assigning data points to their nearest clusters and applying the product quantizer transformation.
- **query**: Query the IVF index to find the k nearest neighbors for a given query point.
FastPQ: This class implements a fast product quantization method using k-means clustering with 16 clusters. It provides methods for fitting the quantizer on data, transforming data using the quantizer, and computing distance tables for a given query.
It has three main methods:
- **fit**: Fit the FastPQ model on the given data by applying k-means clustering on each block of dimensions.
- **transform**: Compress the given data using the FastPQ model.
- **distance_table**: Compute a distance table for the given query vector using the FastPQ model. See below.
DistanceTable: This class is initialized by calling the distance_table method on FastPQ with a *query point*. The distance table provides methods to estimate distances between query and data points, as well as find the top nearest neighbors. It has two methods:
- **estimate_distances**: Estimate the distance from the *query point* to a set of quantized (PQ transformed) data points.
- **top**: Finds the *k* data points nearest to the query, given both quantized and raw data points. The method works in two passes: First *3k* or so nearest points, according to the quantized data, are retrieved. Then the raw data is used to rescore and return the best *k* points among those.
## Benchmarking
To benchmark on the GloVe dataset, first download and preprocess it using
```
examples/glove/prepare-dataset.sh
```
Then run
```
$ python3 -m examples.bench examples/glove/dataset/glove.twitter.27B.100d.npy --metric angular
Loading and shuffling...
num_points=1183514, num_dims=100, num_queries=10000, dims_per_block=2, num_clusters=1087
...
Querying
Recall10@10: 0.37403000000000003
Queries/second: 4727.144941521318
Recall10@10: 0.5021399999999999
Queries/second: 3965.6137940410995
...
```
Raw data
{
"_id": null,
"home_page": "",
"name": "fast-pq",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "nns,approximate nearest neighbor search",
"author": "",
"author_email": "Thomas Dybdahl Ahle <lobais@gmail.com>",
"download_url": "https://files.pythonhosted.org/packages/d0/cb/9eab0a1e26b16ec668070ba79226f1dad68943076f81568024c790e76358/fast_pq-0.3.tar.gz",
"platform": null,
"description": "# Fast PQ\nFastPQ is a lightweight Python Vector Database specifically designed to offer high performance and be easy to read.\nThe main ingredient is an optimized implementation of 4bit Product Quantization (PQ) which enables fast approximate distance computations, 50 times faster than NumPy/BLAS.\n\n\n\n<p align=\"center\">\n(Performance tradeoff on <a href=\"http://ann-benchmarks.com/glove-100-angular_10_angular.html\">ANN Benchmarks</a>. Up and to the right is better.)\n</p>\n\n## Features\n\nFastPQ is a very lightweight index, much smaller than the dataset itself.\nIt is also quick to build, requiring only a single pass of sklearn's KMeans over the dataset.\n\n## Example\n\nLet's generate some random data\n\n```python\nimport numpy as np\nX = np.random.rand(10000, 128)\nqueries = np.random.rand(100, 128)\n```\n\nWe can use the `FastPQ` class to quantize the data and perform nearest neighbor search.\n\n```python\nfrom fast_pq import FastPQ\n# Initialize PQ with 64 columns of 2 dimensions each\npq = FastPQ(dims_per_block=2)\nX_compressed = pq.fit_transform(X)\n\n# Compute exact k-nearest neighbors, accelerated by PQ\nfor q in queries:\n distance_table = pq.distance_table(q)\n est8 = distance_table.estimate_distances(X_compressed)\n print(\"Probably nearest neighbor:\", est8.argmin())\n\n```\n\nThis will return the 10 nearest neighbors for each query, as well as the distances to those neighbors.\nNote that we want a quite low `dims_per_block` compared to other Product Quantization methods, since we only use 4 bits per block.\nThis again can be attributed to the SSE instructions only allowing 4 bit table lookups.\n\nWe can use the `IVF` class to perform approximate nearest neighbor search with Inverted File Indexing.\n\n```python\nfrom fast_pq import IVF\nivf = IVF(\"euclidean\", n_clusters=100).fit(X).build(X)\nneighbors = ivf.query(queries, k=10, n_probes=10)\n```\n\nThis will perform approximate nearest neighbor search using Inverted File Indexing, with 10 probes for each query. Note that we first have to call the `fit` method to build the codebook, and then the `build` method to populate the inverted file.\n\nSee also `examples/` for more detailed examples of usage.\n\n## Installing\n\nYou need to build `fast_pq` before you can run it, as it contains Cython code.\nThe easiest way to do this is to simply run\n\n```bash\n$ pip install .\n```\n\nTo test it we can run an example:\n\n```bash\n$ python -m examples.example\nn=16000, d=128, queries=1000, dims_per_block=2\nSampling\nComputing true neighbours\nFitting PQ\nQuerying\n\nMedian place of true nearest neighbor: 1.0\n90% quantile: 19.0\nQueries/second: 7101.262693814528\n\nTotal time spent on preprocess: 0.09025406837463379\nTotal time spent on search: 0.05056595802307129\nScipy speed for comparison: 2.249645948410034\n```\n\nIn this example Fast PQ is about 16 times faster than optmized scipy/numpy.\nThe reason is that Fast PQ uses a trick called [Accelerated Nearest Neighbor Search with Qick ADC](https://dl.acm.org/doi/abs/10.1145/3078971.3078992)\nwith which SIMD instructions are used to perform 16 inner product operations in a single instruction.\n\n### Developing\nIf you are helping develop fast_pq, and need to test a change to the Cython code, you can rebuild it with\n```bash\n$ python setup.py build_ext --inplace\n```\n\n## Class Overview\n\nThe project consists of two main classes: IVF and FastPQ. The IVF class is used to build an IVF index with cluster centers, fit a product quantizer on the data, and perform queries on the index. The FastPQ class is used to create a product quantizer that can quickly transform data and compute distance tables.\n\nIVF: This class is responsible for creating an IVF index using clustering (either Euclidean or angular) and FastPQ for quantization. It provides methods to fit the index on data, build the index with quantized data, and query the index for nearest neighbors.\nMain methods:\n\n - **fit**: Fit the IVF index on the given data by finding cluster centers and fitting the product quantizer.\n - **build**: Build the IVF index by assigning data points to their nearest clusters and applying the product quantizer transformation.\n - **query**: Query the IVF index to find the k nearest neighbors for a given query point.\n\nFastPQ: This class implements a fast product quantization method using k-means clustering with 16 clusters. It provides methods for fitting the quantizer on data, transforming data using the quantizer, and computing distance tables for a given query.\nIt has three main methods:\n\n - **fit**: Fit the FastPQ model on the given data by applying k-means clustering on each block of dimensions.\n - **transform**: Compress the given data using the FastPQ model.\n - **distance_table**: Compute a distance table for the given query vector using the FastPQ model. See below.\n \nDistanceTable: This class is initialized by calling the distance_table method on FastPQ with a *query point*. The distance table provides methods to estimate distances between query and data points, as well as find the top nearest neighbors. It has two methods:\n\n - **estimate_distances**: Estimate the distance from the *query point* to a set of quantized (PQ transformed) data points.\n\n - **top**: Finds the *k* data points nearest to the query, given both quantized and raw data points. The method works in two passes: First *3k* or so nearest points, according to the quantized data, are retrieved. Then the raw data is used to rescore and return the best *k* points among those.\n\n## Benchmarking\nTo benchmark on the GloVe dataset, first download and preprocess it using\n```\nexamples/glove/prepare-dataset.sh\n```\nThen run\n```\n$ python3 -m examples.bench examples/glove/dataset/glove.twitter.27B.100d.npy --metric angular\nLoading and shuffling...\nnum_points=1183514, num_dims=100, num_queries=10000, dims_per_block=2, num_clusters=1087\n...\nQuerying\nRecall10@10: 0.37403000000000003\nQueries/second: 4727.144941521318\nRecall10@10: 0.5021399999999999\nQueries/second: 3965.6137940410995\n...\n```\n",
"bugtrack_url": null,
"license": "AGPL-3.0-or-later",
"summary": "Approximate Nearest Neighbors in Python.",
"version": "0.3",
"split_keywords": [
"nns",
"approximate nearest neighbor search"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "c8299cd164210582cb26411ea5f7da9d3a9538e388f603ecc22a95896446cec5",
"md5": "f369ed6ccc08037b1b1bd63b628962f2",
"sha256": "613f5f368fdad782e3b15f203d0e31f602d6f2fae53af04ddf4aa45c726f1337"
},
"downloads": -1,
"filename": "fast_pq-0.3-cp311-cp311-macosx_13_0_x86_64.whl",
"has_sig": false,
"md5_digest": "f369ed6ccc08037b1b1bd63b628962f2",
"packagetype": "bdist_wheel",
"python_version": "cp311",
"requires_python": null,
"size": 209983,
"upload_time": "2023-04-19T19:28:58",
"upload_time_iso_8601": "2023-04-19T19:28:58.874390Z",
"url": "https://files.pythonhosted.org/packages/c8/29/9cd164210582cb26411ea5f7da9d3a9538e388f603ecc22a95896446cec5/fast_pq-0.3-cp311-cp311-macosx_13_0_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "d0cb9eab0a1e26b16ec668070ba79226f1dad68943076f81568024c790e76358",
"md5": "46629a029bf2c93261b376a3a4f1668c",
"sha256": "7ccf6f50c3978e3d7a69fd41f50659e258a8701932e2339fdda9de57fea72617"
},
"downloads": -1,
"filename": "fast_pq-0.3.tar.gz",
"has_sig": false,
"md5_digest": "46629a029bf2c93261b376a3a4f1668c",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 139622,
"upload_time": "2023-04-19T19:29:04",
"upload_time_iso_8601": "2023-04-19T19:29:04.237769Z",
"url": "https://files.pythonhosted.org/packages/d0/cb/9eab0a1e26b16ec668070ba79226f1dad68943076f81568024c790e76358/fast_pq-0.3.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-04-19 19:29:04",
"github": false,
"gitlab": false,
"bitbucket": false,
"lcname": "fast-pq"
}
JSON