@maumueller Per our email conversation, can you validate my various code changes to accomodate T3? I've tested locally on 4/6 datasets and it looks good so far.

This is currently how I will likely be instructing T3 participants: https://github.com/harsha-simhadri/big-ann-benchmarks/blob/gw/T3/t3/README.md

Hi, I have a question about using this framework w/ a non-python ANN implementation.

It looks like this is mostly a fork of ann-benchmarks. So the only option for using outside of Python is to hack together a client/server setup, as has been done for a few algos in ann-benchmarks. This obviously handicaps and complicates non-python implementations, as it introduces costs of context-switching, serialization, and data transfer among processes.

I asked and was told early on by project organizers that the big-ann challenge would support non-python implementations:

So I'm wondering if there has been progress here, or any idea of how it might work?

It seems like it wouldn't be terribly difficult to refactor the code so that the containers executed by runner.py can have any entrypoint, e.g., a program in another language. The interface between runner and algorithm would then simply be some standard file format for inputs and nearest neighbor results. If that sounds like a good idea I can try to implement it. Otherwise maybe we can use this ticket for discussing alternatives.

Thanks -Alex

@harsha-simhadri @maumueller @

Per our discussion, here is a new recall-with-ties approach with a bunch of recall related unit tests.

Please review if you get a chance, since it is fairly different from the existing implementation and could really use a second pair of eyes.

Highlights include:

• retains the set intersection method to determine number of recalls, but changes how the true_ids set is presented to it
• basically it groups ids in true_ids by grouping "close" values in true_dists
• "close"ness is determined by the absolute value difference of consecutive distances in true_dists ( treshold is <= 1e-6 )
• it uses the first element in a consecutive group as one of the subtraction operands
• it will also track the tie condition and surfaces the count of queries in query set with the tie condition
• recall_tests.py attempts to provide a comprehensive set of unit tests for both versions of recall (without and with ties)
• there is a run script for these tests ( tests/tests.sh ) which could be incorporated into a github action

Lowlights include:

• admittedly this recall-with-ties implementation could be faster using vectorization
• there are some slow tests in recall_tests.py which may slow down github push validation further if incorporated as-is as a branch push action

Kuaishou Technology Billion-Scale ANN Challenge Track2: A joint team from Kuaishou Technology and Tsinghua University. This is for Track 2. Only optimize search process, currently for three datasets: msturing-1B, bigann-1B, msspacev-1B, it's first commit, there may be some other modifications before deadline.

Thanks @maumueller, @gosha1128 and others for the fruitful discussion over in #20. I think I've arrived at an implementation that could fit the purpose of language-agnostic (big) ANN.

The HttpANN algorithm is designed to make HTTP calls to a server. The server executes all indexing and querying, thus enabling language-agnostic ANN implementations with minimal overhead. The only requirements for the server are:

1. It should implement the JSON-over-HTTP API documented below (copied from httpann.py). Note that this is a 1:1 copy of the BaseANN Python Class API.
2. It should be able to read the vector dataset in the standard binary format used by this competition.

It could in theory even run remotely, although the intended use-case is that the server runs in the same container.

The overhead for data transfer and serialization is minimal. The server only needs to parse the 10k JSON-encoded query vectors and encode the resulting 10k lists of neighbors.

I also included an example implementation which uses scikit-learn. It's too slow for the large datasets, but it works on the smaller random-xs and random-range-xs. So it should be good enough to demonstrate that this algorithm works.

Here is the API that a server must implement:

| Method | Route | Request Body | Expected Status | Response Body | | ------ | -------------------- | ---------------------------------------------------------------------------------------------------------- | --------------- | -------------------------------------------------------------------------- | | POST | /init | dictionary of constructor arguments, e.g., {“metric”: “euclidean”, “dimension”: 99 } | 200 | { } | | POST | /load_index | { "dataset": <dataset name, e.g. "bigann-10m"> } | 200 | { "load_index": } | | POST | /set_query_arguments | dictionary of query arguments | 200 | { } | | POST | /query | { “X”: , “k”: } | 200 | { } | | POST | /range_query | { “X”: , “radius”: } | 200 | { } | | POST | /get_results | { } | 200 | { “get_results”: } | | POST | /get_additional | { } | 200 | { “get_additional”: } | | POST | /get_range_results | { } | 200 | { “get_range_results”: <list of three 1-dimensional lists (lims, I, D)> } |

Added functionality to give credit to tied candidates. This uses the fact that GT file has top 100 NNs computed while k=10 is what is evaluated. So if top 8 through top 15 candidates are tied for a query, we can use GT to credit any entries from there. This will not work if there are more than 100 ties, unless we recompute GT with k>100. Using this function, the difference in recall for msspacev-1B for diskann is as follows

With ties diskann-t2,DiskANN,msspacev-1B,10,873.3891725887347,4128.170671305772,1000000.0,57414268.0,65737.32512600713,132.8194160185564,9124.044242052121,0.9774116523400191 diskann-t2,DiskANN,msspacev-1B,10,815.8064319257669,4391.558241233456,1000000.0,57414268.0,70377.31715901,142.64251603220086,9773.534383954155,0.9786396507026879 diskann-t2,DiskANN,msspacev-1B,10,954.1772918666221,3863.1387024150636,1000000.0,57414268.0,60171.48855815104,122.95968072042571,8459.167928776094,0.9760779096738983 diskann-t2,DiskANN,msspacev-1B,10,1123.4640002144592,3333.160165097558,1000000.0,57414268.0,51104.67980196974,103.29038750170555,7087.164108336744,0.9722915813890026 diskann-t2,DiskANN,msspacev-1B,10,1535.2989986923885,2538.5193682630647,1000000.0,57414268.0,37396.14762264525,73.94146541137945,5179.051030154182,0.9634329376449721 diskann-t2,DiskANN,msspacev-1B,10,1720.4498608048532,2273.3868058398143,1000000.0,57414268.0,33371.6601151868,64.20122117614955,4642.449686178196,0.9587835993996453 diskann-t2,DiskANN,msspacev-1B,10,1233.6608183762005,3069.4611474962476,1000000.0,57414268.0,46539.751562809,93.52844862873516,6449.107449856733,0.9701869286396507 diskann-t2,DiskANN,msspacev-1B,10,1979.1985895820392,2009.0835243553008,1000000.0,57414268.0,29008.846460488112,54.51992086232774,4017.1128735161687,0.9519238641015144 diskann-t2,DiskANN,msspacev-1B,10,1034.378157726947,3598.717198799291,1000000.0,57414268.0,55506.071518532684,113.13927548096602,7694.289875835721,0.9742870787283394 diskann-t2,DiskANN,msspacev-1B,10,1371.7472009562052,2804.5663255560103,1000000.0,57414268.0,41854.846111570834,83.73499113112294,5834.428264428981,0.9675808432255424

Without ties diskann-t2,DiskANN,msspacev-1B,10,873.3891725887347,4128.170671305772,1000000.0,57414268.0,65737.32512600713,132.8194160185564,9124.044242052121,0.914753035884841 diskann-t2,DiskANN,msspacev-1B,10,815.8064319257669,4391.558241233456,1000000.0,57414268.0,70377.31715901,142.64251603220086,9773.534383954155,0.9160526674853322 diskann-t2,DiskANN,msspacev-1B,10,954.1772918666221,3863.1387024150636,1000000.0,57414268.0,60171.48855815104,122.95968072042571,8459.167928776094,0.9133817710465275 diskann-t2,DiskANN,msspacev-1B,10,1123.4640002144592,3333.160165097558,1000000.0,57414268.0,51104.67980196974,103.29038750170555,7087.164108336744,0.9097182425978987 diskann-t2,DiskANN,msspacev-1B,10,1535.2989986923885,2538.5193682630647,1000000.0,57414268.0,37396.14762264525,73.94146541137945,5179.051030154182,0.9009551098376314 diskann-t2,DiskANN,msspacev-1B,10,1720.4498608048532,2273.3868058398143,1000000.0,57414268.0,33371.6601151868,64.20122117614955,4642.449686178196,0.8958520944194296 diskann-t2,DiskANN,msspacev-1B,10,1233.6608183762005,3069.4611474962476,1000000.0,57414268.0,46539.751562809,93.52844862873516,6449.107449856733,0.9076204120616728 diskann-t2,DiskANN,msspacev-1B,10,1979.1985895820392,2009.0835243553008,1000000.0,57414268.0,29008.846460488112,54.51992086232774,4017.1128735161687,0.8887331150225133 diskann-t2,DiskANN,msspacev-1B,10,1034.378157726947,3598.717198799291,1000000.0,57414268.0,55506.071518532684,113.13927548096602,7694.289875835721,0.91110997407559 diskann-t2,DiskANN,msspacev-1B,10,1371.7472009562052,2804.5663255560103,1000000.0,57414268.0,41854.846111570834,83.73499113112294,5834.428264428981,0.9046800382043936

Hello!

Thanks for providing the scripts for running baselines. The following one liner:

python -u track1_baseline_faiss/baseline_faiss.py --dataset bigann-100M \
    --indexkey OPQ64_128,IVF1048576_HNSW32,PQ64x4fsr \
    --maxtrain 100000000 \
    --two_level_clustering \
    --build \
    --add_splits 30 \
    --indexfile data/track1_baseline_faiss/deep-100M.IVF1M_2level_PQ64x4fsr.faissindex \
    --quantizer_efConstruction 200 \
    --quantizer_add_efSearch 80

produces output on F32s_v2 with 64G RAM:

args= Namespace(M0=-1, add_bs=100000, add_splits=30, autotune_max=[], autotune_range=[], basedir=None, build=True, buildthreads=-1, by_residual=-1, clustering_niter=-1, dataset='bigann-100M', indexfile='data/track1_baseline_faiss/deep-100M.IVF1M_2level_PQ64x4fsr.faissindex', indexkey='OPQ64_128,IVF1048576_HNSW32,PQ64x4fsr', inter=True, k=10, maxRAM=-1, maxtrain=100000000, min_test_duration=3.0, n_autotune=500, no_precomputed_tables=False, pairwise_quantization='', parallel_mode=-1, prepare=False, quantizer_add_efSearch=80, quantizer_efConstruction=200, query_bs=-1, radius=96237, search=False, searchparams=['autotune'], searchthreads=-1, stop_at_split=-1, train_on_gpu=False, two_level_clustering=True)
nb processors 32
model name	: Intel(R) Xeon(R) Platinum 8272CL CPU @ 2.60GHz
Dataset BigANNDataset in dimension 128, with distance euclidean, search_type knn, size: Q 10000 B 100000000
build index, key= OPQ64_128,IVF1048576_HNSW32,PQ64x4fsr
Build-time number of threads: 32
metric type 1
Update add-time parameters
   update quantizer efSearch= 16 -> 80
  update quantizer efConstruction= 40 -> 200
getting first 100000000 dataset vectors for training
train, size (100000000, 128)
  Forcing OPQ training PQ to PQ4
  training vector transform
  transform trainset
Killed

Can you please explain what could be wrong? Is the expectation to allocate 10% of data for training?

I cannot reproduce it on h8 or e8 instances, but on f32v2 instances faiss will segfault with some parameter settings. E.g., set up everything to run msturing-1B and carry out

params="
nprobe=128,quantizer_efSearch=128
nprobe=64,quantizer_efSearch=512
nprobe=128,quantizer_efSearch=256
nprobe=128,quantizer_efSearch=512
nprobe=256,quantizer_efSearch=256
nprobe=256,quantizer_efSearch=512
"

python  track1_baseline_faiss/baseline_faiss.py \
           --dataset msturing-1B --indexfile data/msturing-1B.IVF1M_2level_PQ64x4fsr.faissindex \
              --search --searchparams $params

results in

azureuser@test:~/big-ann-benchmarks$ bash test.sh
nb processors 32
model name      : Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz
Dataset MSTuringANNS in dimension 100, with distance euclidean, search_type knn, size: Q 100000 B 1000000000
reading data/msturing-1B.IVF1M_2level_PQ64x4fsr.faissindex
imbalance_factor= 1.5638867719477003
index size on disk:  41360658380
current RSS: 44945760256
precomputed tables size: 0
Search threads: 32
Optimize for intersection @  10
Running evaluation on 6 searchparams
parameters                                   inter@ 10 time(ms/q)   nb distances %quantization #runs
nprobe=128,quantizer_efSearch=128        test.sh: line 12:  8954 Killed                  python track1_baseline_faiss/baseline_faiss.py --dataset msturing-1B --indexfile data/msturing-1B.IVF1M_2level_PQ64x4fsr.faissindex --search --searchparams $params

Any thoughts Matthijs? (Once you are back from vacation)

Hi, I wanted to know are there any plans for adding benchmarks for SCANN? I am not sure if there are benchmarks available for SCANN for large datasets so I was curious on the same. Thanks!

Hi ! Thanks for providing the scripts for evaluating results.

I found that when running python data_export.py --output res.csv, this line of code: power_capture.detect_power_benchmarks(metrics, res) will run out the yield generator res, so the next line: for i, (properties, run) in enumerate(res): don't output anything to be write into res.csv.

I'm still studying the code, and not sure if this is a bug...

@maumueller Alright, I tried the index strategy "OPQ32_128,IVF1048576_HNSW32,PQ32" on SSNPP and got the exception below. Note that I'm now defaulting to CPU on build_index for this dataset since the quantizer class doesn't support range search.

I will next try to set quantizer_on_gpu_add=False and train_on_gpu=False for build_index(). The default was True for both.

... Training PQ slice 30/32 Clustering 65536 points in 4D to 256 clusters, redo 1 times, 25 iterations Preprocessing in 0.00 s Iteration 24 (0.36 s, search 0.32 s): objective=1.11718e+07 imbalance=1.174 nsplit=0 Training PQ slice 31/32 Clustering 65536 points in 4D to 256 clusters, redo 1 times, 25 iterations Preprocessing in 0.00 s Iteration 24 (0.36 s, search 0.32 s): objective=1.12101e+07 imbalance=1.185 nsplit=0 doing polysemous training for PQ IndexIVFPQ::precompute_table: not precomputing table, it would be too big: 34359738368 bytes (max 2147483648) Total train time 14384.034 s ============== SPLIT 0/1 Process Process-1: Traceback (most recent call last): File "/home/george/anaconda3/envs/bigann/lib/python3.8/multiprocessing/process.py", line 315, in _bootstrap self.run() File "/home/george/anaconda3/envs/bigann/lib/python3.8/multiprocessing/process.py", line 108, in run self._target(*self._args, **self._kwargs) File "/home/george/Projects/BigANN/harsha/big-ann-benchmarks/benchmark/main.py", line 45, in run_worker run_no_docker(definition, args.dataset, args.count, File "/home/george/Projects/BigANN/harsha/big-ann-benchmarks/benchmark/runner.py", line 268, in run_no_docker run_from_cmdline(cmd) File "/home/george/Projects/BigANN/harsha/big-ann-benchmarks/benchmark/runner.py", line 182, in run_from_cmdline run(definition, args.dataset, args.count, args.runs, args.rebuild) File "/home/george/Projects/BigANN/harsha/big-ann-benchmarks/benchmark/runner.py", line 76, in run algo.fit(dataset) File "/home/george/Projects/BigANN/harsha/big-ann-benchmarks/benchmark/algorithms/faiss_t3.py", line 274, in fit index = build_index(buildthreads, by_residual, maxtrain, File "/home/george/Projects/BigANN/harsha/big-ann-benchmarks/benchmark/algorithms/faiss_t3.py", line 184, in build_index for xblock, assign in stage2: File "/home/george/Projects/BigANN/harsha/big-ann-benchmarks/benchmark/algorithms/faiss_t3.py", line 46, in rate_limited_iter res = res.get() File "/home/george/anaconda3/envs/bigann/lib/python3.8/multiprocessing/pool.py", line 771, in get raise self._value File "/home/george/anaconda3/envs/bigann/lib/python3.8/multiprocessing/pool.py", line 125, in worker result = (True, func(*args, **kwds)) File "/home/george/Projects/BigANN/harsha/big-ann-benchmarks/benchmark/algorithms/faiss_t3.py", line 39, in next_or_None return next(l) File "/home/george/Projects/BigANN/harsha/big-ann-benchmarks/benchmark/algorithms/faiss_t3.py", line 176, in produce_batches _, assign = quantizer_gpu.search(xblock, 1) File "/home/george/anaconda3/envs/bigann/lib/python3.8/site-packages/faiss/init.py", line 287, in replacement_search assert d == self.d AssertionError

I try to built index database of track-3 follow : python track3_baseline_faiss/gpu_baseline_faiss.py --dataset bigann-1B \ --indexkey IVF1048576,SQ8 \ --train_on_gpu \ --build --quantizer_on_gpu_add --add_splits 30 \ --search \ --searchparams nprobe={1,4,16,64,256} \ --parallel_mode 3 --quantizer_on_gpu_search but failed caused by DRAM 128GB less than base-line 768GB. Someone could provide Track-3 Base-line link , thanks

Couldn't access the slides of talks from track winners. The url like: https://big-ann-benchmarks.com/templates/slides/* e.g. https://big-ann-benchmarks.com/templates/slides/invited-talk-anshu.pptx (just report 404 error)

It feels a bit weird to see a lot of activity on this repo rather than trying to contribute to the original one https://github.com/erikbern/ann-benchmarks

Is the ambition to merge it back into the main repo? Or is this just a short-lived repo anyway?

I'm happy to donate my code to something more neutral (eg we can set up a neutral github.com organzation rather than have the code under my username). Seems like it would be beneficial to to not diverge too far.

(also felt a bit weird that no one told me about this – I found out about it randomly)

@maumueller wdyt?

Dear all,

<tl;dr> Please add your thoughts on the future of this benchmark!

Thank you very much for participating in our NeurIPS'21 competition. The competition will end with an event on Dec 8, and you can find the timeline for this event on https://big-ann-benchmarks.com/. We hope many of you will be able to participate!

The last part of the event will be an open discussion among the participants for future directions of this competition. As organizers we have already identified some points we would like to discuss and potentially include in a future version of the benchmark.

1. Filtered ANNS: can you support ANNS queries which allow filters like date range, author or some combination of attributes. This would look like a simple SQL + ANNS query.

2. Streaming ANNS: Can algorithms be robust to insertions and deletions. Here we have a strong baseline (fresh-diskann: https://arxiv.org/abs/2105.09613)

3. Out of distribution queries: this is already a problem with T2I and we can imagine various variations

4. Better vector compression: Most approaches use some variant of product quantization as vector compression, but can we get more accurate estimation, maybe at the price of more expensive decoding?

Please let us know what you think about these topics, and add your own!

Thanks!

codes for Billion-Scale Approximate Nearest Neighbor Search Challenge T1(re-upload) out team name registered for T1 was Kuaishou Technology Billion-Scale ANN Challenge Track1 kst_ann_t1 is our algorithm name