zilliztech / bbann Goto Github PK

Block-based Approximate Nearest Neighbor

License: MIT License

CMake 0.68% C++ 85.71% Shell 5.97% Python 7.64%

bbann's Introduction

Block-based Approximate Nearest Neighbor (BBAnn)

BBAnn is an algorithm optimized for SSD storage. It organizes data so that they are aligned with SSD block size.

The source code is mainly located in include and src folders. By running scripts under python directory, it will create docker image, install python library bound with pybind11 and then run the framework.

Prerequisites

CMake >= 3.10
gcc >= 6.1
AIO
Docker

Get Started

git clone --recurse-submodules https://github.com/zilliztech/BBAnn.git
cd BBAnn/python

# Run knn search
sudo ./run_framework.sh

# Run range search
sudo ./run_range_search.sh

To run a dataset other than random-xs and random-range-xs, you first need to prepare the dataset

cd BBAnn/benchmark
sudo python3 create_dataset.py --dataset [dataset_name]
cd ../python

# Change dataset name
vi run_framework.sh 

sudo ./run_framework.sh

The parameters for datasets are located in python/bbann-algo.yaml.

bbann's People

Contributors

Stargazers

Watchers

Forkers

cqy123456 wxyucs longjiquan hannankan guoxiangzhou reus1 pwzxxm heaoxiang1012 whutbd foxspy songlinlife jonathanjia1

bbann's Issues

等宽直方图等高直方图

Polish Script

Breakdown Experiment: Read Vector File + Compute Distance

ETA: 09.23 16:00

分桶比较

add histogram of cluster size
nprobe as x axis

https://gitee.com/bianzheng123/nips-competition/tree/master/dataset-partition

https://docs.qq.com/doc/DWWVTSUdvZEhudGVN

Some compilation warnings are on

For example:
https://github.com/shengjun1985/BigAnn/blob/master/include/pq/pq_residual.h#L96

update script and log reader

need to add unit test

Build: NUMA-aware

https://zilliverse.feishu.cn/docs/doccnE0osweJwlzmtM0DoDwUl7b#PNdSfm
Build Machine is a NUMA

If build time too long, then make build code NUMA-aware.

Check Early Termination on Search

distance(q, 10-th NN) v.s. centrods distances => distribution
x: nprobe, y procentage of hits

Graph Partition instead of kmeans in the bottom level

Integrate this lib: https://github.com/KaHIP/KaHIP

Check here for the function signature:
https://github.com/PwzXxm/BigAnn/blob/e0524635d7e6c3041b8bd667fdc03a459708047f/include/ivf/clustering.h#L525

centroids: the centroids of the vectors after clustering
assign: the assignment (the corresponding cluster id or bucket id) of vectors in x_in ,
dists: the distance to the centroids

Add commit to this branch:
https://github.com/PwzXxm/BigAnn/tree/graph-partition

zilliz@vm1:~$ uname -a
Linux vm1 5.4.0-1055-azure #57~18.04.1-Ubuntu SMP Fri Jul 16 19:40:19 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux

Linux Kernel 5.4.0 liburing is supported.

norm bias revision

add 10M, 100M
remove irrelevant py code

CMake & Script

https://github.com/PwzXxm/BigAnn/blob/master/CMakeLists.txt#L24

build & release
assert flag
add more script
update README
Early Input Sanitizer
- check if index foler is there: clean up it if exists?
- check e.g.: if d & m == 0