Replace slow brute force algo (sklearn) by a direct, fast BLAS call.

Make sure you have a fast BLAS installed -- a recent ATLAS, or OpenBlas, Intel's MKL, Apple's Accelerate etc. This can make a huge difference in performance.

PR not tested at all. @erikbern can you run it on the AWS machine? I just wrote the code, I didn't get a chance to run it (install assumes Debian). Sorry for any typos.

I've added FALCONN (http://falconn-lib.org/) tuned for the GloVe dataset.

Here are the results for GloVe on the dedicated c4.2xlarge instance: https://gitlab.com/ilyaraz/experiments/blob/master/glove_results/ec2_flat.txt (other numbers are taken from the upstream of ann-benchmarks).

Here is the comparison of Annoy vs. FALCONN in one point on the same instance (to make sure that the numbers from the above make sense): http://pastebin.com/gpDVFQhm

Hi Erik,

as discussed our changes in one very big pull request. A concise description of our work:

• Moved the algorithm wrappers out of main.py and into separate files (see the ann_benchmarks/algorithms/ folder)
• Added support for datasets containing different kinds of data point (see ann_benchmarks/data.py)
• Added support for algorithm implementations running in external processes (see ann_benchmarks/algorithms/subprocess.py), the protocol directory, and the wrappers provided for annoy-hamming, dolphinn, and MIH in the install directory
• Broke up the results files and created a directory hierarchy for them (see ann_benchmarks/results.py)
• Made the results files store the complete results rather than precomputed quality metrics
• Added an interactive HTML5 plot generator (see createwebsite.py)
• Added new datasets (see install/data-*.sh)
• Added new quality metrics (see ann_benchmarks/plotting/results.py)
• Added new algorithms (see install/lib-*.sh)

The only core change that we have done is how we handle the ThreadPool in case of running the benchmark without the --single flag that forces single-core, single-thread. In our code, the query time of each query is recorded, while the the current ann-benchmarks records the time needed to answer all the queries "once". Our behavior is that"multi-threading" makes the experiments run faster, but the results we get are (almost) identical to when you run in a single-threaded mode. We also added support for a batch mode, in which the algorithm takes care of handling all the queries and might use multi-threading, up for it to decide. The batch mode was in particular needed for the FAISS GPU integration.

The following image shows a comparison between single-core/single-thread (annoy), threadpool with a single time measurement (annoy-pool), and threadpool with individual query time measurements (annoy-pool-query-based). We clearly see a difference between the single/individual run, but they keep the actual performance shape for the algorithm. The threadpool with a single measurement at the beginning and end seems to have a lot of overhead for the management included, only at very high recall we see a speedup that we would expect from parallelizing queries.

Looking forward to your thoughts!

After #92 I was interested to see how ONNG actually performs, and it performs quite well! (Much better than their other variant.) Find the updated result plot files in the PR and on http://ann-benchmarks.com.

One problem with the plot script in this situation: The change done to PANNG in algos.yaml by https://github.com/erikbern/ann-benchmarks/commit/0b50eb2f149bd0dee343d8c8274b2d3b8d7827b8 made the PANNG result files inaccessible to plot.py, since their names changed. I dislike this tight connection between the algos.yaml file and the result files. The plotting done in create_website.py just enumerates all result files and plots them, which is much more robust. Maybe we should update plot.py to use the same approach?

Hello! I've tried installing dependencies under Python 3.7.10 and got the following output. What Python version is supported / recommended?

    Running setup.py install for numpy ... error
    ERROR: Command errored out with exit status 1:
     command: /Users/dmitrykan/project/ann-benchmarks/venv/bin/python -u -c 'import io, os, sys, setuptools, tokenize; sys.argv[0] = '"'"'/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/setup.py'"'"'; __file__='"'"'/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/setup.py'"'"';f = getattr(tokenize, '"'"'open'"'"', open)(__file__) if os.path.exists(__file__) else io.StringIO('"'"'from setuptools import setup; setup()'"'"');code = f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' install --record /private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-record-wrmxmqjz/install-record.txt --single-version-externally-managed --compile --install-headers /Users/dmitrykan/project/ann-benchmarks/venv/include/site/python3.7/numpy
         cwd: /private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/
    Complete output (195 lines):
    Running from numpy source directory.
    
    Note: if you need reliable uninstall behavior, then install
    with pip instead of using `setup.py install`:
    
      - `pip install .`       (from a git repo or downloaded source
                               release)
      - `pip install numpy`   (last NumPy release on PyPi)
    
    
    blas_opt_info:
    blas_mkl_info:
      libraries mkl_rt not found in ['/Users/dmitrykan/project/ann-benchmarks/venv/lib', '/usr/local/lib', '/usr/lib']
      NOT AVAILABLE
    
    blis_info:
      libraries blis not found in ['/Users/dmitrykan/project/ann-benchmarks/venv/lib', '/usr/local/lib', '/usr/lib']
      NOT AVAILABLE
    
    openblas_info:
      libraries openblas not found in ['/Users/dmitrykan/project/ann-benchmarks/venv/lib', '/usr/local/lib', '/usr/lib']
      NOT AVAILABLE
    
    atlas_3_10_blas_threads_info:
    Setting PTATLAS=ATLAS
      libraries tatlas not found in ['/Users/dmitrykan/project/ann-benchmarks/venv/lib', '/usr/local/lib', '/usr/lib']
      NOT AVAILABLE
    
    atlas_3_10_blas_info:
      libraries satlas not found in ['/Users/dmitrykan/project/ann-benchmarks/venv/lib', '/usr/local/lib', '/usr/lib']
      NOT AVAILABLE
    
    atlas_blas_threads_info:
    Setting PTATLAS=ATLAS
      libraries ptf77blas,ptcblas,atlas not found in ['/Users/dmitrykan/project/ann-benchmarks/venv/lib', '/usr/local/lib', '/usr/lib']
      NOT AVAILABLE
    
    atlas_blas_info:
      libraries f77blas,cblas,atlas not found in ['/Users/dmitrykan/project/ann-benchmarks/venv/lib', '/usr/local/lib', '/usr/lib']
      NOT AVAILABLE
    
      FOUND:
        extra_compile_args = ['-msse3', '-I/System/Library/Frameworks/vecLib.framework/Headers']
        extra_link_args = ['-Wl,-framework', '-Wl,Accelerate']
        define_macros = [('NO_ATLAS_INFO', 3), ('HAVE_CBLAS', None)]
    
    /bin/sh: svnversion: command not found
    non-existing path in 'numpy/distutils': 'site.cfg'
    /bin/sh: svnversion: command not found
    F2PY Version 2
    lapack_opt_info:
    lapack_mkl_info:
      libraries mkl_rt not found in ['/Users/dmitrykan/project/ann-benchmarks/venv/lib', '/usr/local/lib', '/usr/lib']
      NOT AVAILABLE
    
    openblas_lapack_info:
      libraries openblas not found in ['/Users/dmitrykan/project/ann-benchmarks/venv/lib', '/usr/local/lib', '/usr/lib']
      NOT AVAILABLE
    
    atlas_3_10_threads_info:
    Setting PTATLAS=ATLAS
      libraries tatlas,tatlas not found in /Users/dmitrykan/project/ann-benchmarks/venv/lib
      libraries lapack_atlas not found in /Users/dmitrykan/project/ann-benchmarks/venv/lib
      libraries tatlas,tatlas not found in /usr/local/lib
      libraries lapack_atlas not found in /usr/local/lib
      libraries tatlas,tatlas not found in /usr/lib
      libraries lapack_atlas not found in /usr/lib
    <class 'numpy.distutils.system_info.atlas_3_10_threads_info'>
      NOT AVAILABLE
    
    atlas_3_10_info:
      libraries satlas,satlas not found in /Users/dmitrykan/project/ann-benchmarks/venv/lib
      libraries lapack_atlas not found in /Users/dmitrykan/project/ann-benchmarks/venv/lib
      libraries satlas,satlas not found in /usr/local/lib
      libraries lapack_atlas not found in /usr/local/lib
      libraries satlas,satlas not found in /usr/lib
      libraries lapack_atlas not found in /usr/lib
    <class 'numpy.distutils.system_info.atlas_3_10_info'>
      NOT AVAILABLE
    
    atlas_threads_info:
    Setting PTATLAS=ATLAS
      libraries ptf77blas,ptcblas,atlas not found in /Users/dmitrykan/project/ann-benchmarks/venv/lib
      libraries lapack_atlas not found in /Users/dmitrykan/project/ann-benchmarks/venv/lib
      libraries ptf77blas,ptcblas,atlas not found in /usr/local/lib
      libraries lapack_atlas not found in /usr/local/lib
      libraries ptf77blas,ptcblas,atlas not found in /usr/lib
      libraries lapack_atlas not found in /usr/lib
    <class 'numpy.distutils.system_info.atlas_threads_info'>
      NOT AVAILABLE
    
    atlas_info:
      libraries f77blas,cblas,atlas not found in /Users/dmitrykan/project/ann-benchmarks/venv/lib
      libraries lapack_atlas not found in /Users/dmitrykan/project/ann-benchmarks/venv/lib
      libraries f77blas,cblas,atlas not found in /usr/local/lib
      libraries lapack_atlas not found in /usr/local/lib
      libraries f77blas,cblas,atlas not found in /usr/lib
      libraries lapack_atlas not found in /usr/lib
    <class 'numpy.distutils.system_info.atlas_info'>
      NOT AVAILABLE
    
      FOUND:
        extra_compile_args = ['-msse3']
        extra_link_args = ['-Wl,-framework', '-Wl,Accelerate']
        define_macros = [('NO_ATLAS_INFO', 3), ('HAVE_CBLAS', None)]
    
    /usr/local/Cellar/[email protected]/3.7.10_2/Frameworks/Python.framework/Versions/3.7/lib/python3.7/distutils/dist.py:274: UserWarning: Unknown distribution option: 'define_macros'
      warnings.warn(msg)
    running install
    running build
    running config_cc
    unifing config_cc, config, build_clib, build_ext, build commands --compiler options
    running config_fc
    unifing config_fc, config, build_clib, build_ext, build commands --fcompiler options
    running build_src
    build_src
    building py_modules sources
    creating build
    creating build/src.macosx-11-x86_64-3.7
    creating build/src.macosx-11-x86_64-3.7/numpy
    creating build/src.macosx-11-x86_64-3.7/numpy/distutils
    building library "npymath" sources
    customize Gnu95FCompiler
    Found executable /usr/local/bin/gfortran
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/setup.py", line 392, in <module>
        setup_package()
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/setup.py", line 384, in setup_package
        setup(**metadata)
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/core.py", line 169, in setup
        return old_setup(**new_attr)
      File "/Users/dmitrykan/project/ann-benchmarks/venv/lib/python3.7/site-packages/setuptools/__init__.py", line 153, in setup
        return distutils.core.setup(**attrs)
      File "/usr/local/Cellar/[email protected]/3.7.10_2/Frameworks/Python.framework/Versions/3.7/lib/python3.7/distutils/core.py", line 148, in setup
        dist.run_commands()
      File "/usr/local/Cellar/[email protected]/3.7.10_2/Frameworks/Python.framework/Versions/3.7/lib/python3.7/distutils/dist.py", line 966, in run_commands
        self.run_command(cmd)
      File "/usr/local/Cellar/[email protected]/3.7.10_2/Frameworks/Python.framework/Versions/3.7/lib/python3.7/distutils/dist.py", line 985, in run_command
        cmd_obj.run()
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/command/install.py", line 62, in run
        r = self.setuptools_run()
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/command/install.py", line 36, in setuptools_run
        return distutils_install.run(self)
      File "/usr/local/Cellar/[email protected]/3.7.10_2/Frameworks/Python.framework/Versions/3.7/lib/python3.7/distutils/command/install.py", line 545, in run
        self.run_command('build')
      File "/usr/local/Cellar/[email protected]/3.7.10_2/Frameworks/Python.framework/Versions/3.7/lib/python3.7/distutils/cmd.py", line 313, in run_command
        self.distribution.run_command(command)
      File "/usr/local/Cellar/[email protected]/3.7.10_2/Frameworks/Python.framework/Versions/3.7/lib/python3.7/distutils/dist.py", line 985, in run_command
        cmd_obj.run()
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/command/build.py", line 47, in run
        old_build.run(self)
      File "/usr/local/Cellar/[email protected]/3.7.10_2/Frameworks/Python.framework/Versions/3.7/lib/python3.7/distutils/command/build.py", line 135, in run
        self.run_command(cmd_name)
      File "/usr/local/Cellar/[email protected]/3.7.10_2/Frameworks/Python.framework/Versions/3.7/lib/python3.7/distutils/cmd.py", line 313, in run_command
        self.distribution.run_command(command)
      File "/usr/local/Cellar/[email protected]/3.7.10_2/Frameworks/Python.framework/Versions/3.7/lib/python3.7/distutils/dist.py", line 985, in run_command
        cmd_obj.run()
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/command/build_src.py", line 148, in run
        self.build_sources()
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/command/build_src.py", line 159, in build_sources
        self.build_library_sources(*libname_info)
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/command/build_src.py", line 294, in build_library_sources
        sources = self.generate_sources(sources, (lib_name, build_info))
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/command/build_src.py", line 377, in generate_sources
        source = func(extension, build_dir)
      File "numpy/core/setup.py", line 672, in get_mathlib_info
        st = config_cmd.try_link('int main(void) { return 0;}')
      File "/usr/local/Cellar/[email protected]/3.7.10_2/Frameworks/Python.framework/Versions/3.7/lib/python3.7/distutils/command/config.py", line 243, in try_link
        self._check_compiler()
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/command/config.py", line 81, in _check_compiler
        c_compiler=self.compiler)
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/fcompiler/__init__.py", line 842, in new_fcompiler
        c_compiler=c_compiler)
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/fcompiler/__init__.py", line 816, in get_default_fcompiler
        c_compiler=c_compiler)
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/fcompiler/__init__.py", line 765, in _find_existing_fcompiler
        c.customize(dist)
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/fcompiler/__init__.py", line 521, in customize
        linker_so_flags = self.flag_vars.linker_so
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/environment.py", line 39, in __getattr__
        return self._get_var(name, conf_desc)
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/environment.py", line 53, in _get_var
        var = self._hook_handler(name, hook)
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/fcompiler/__init__.py", line 700, in _environment_hook
        return hook()
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/fcompiler/gnu.py", line 309, in get_flags_linker_so
        flags = GnuFCompiler.get_flags_linker_so(self)
      File "/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/numpy/distutils/fcompiler/gnu.py", line 138, in get_flags_linker_so
        os.environ['MACOSX_DEPLOYMENT_TARGET'] = target
      File "/usr/local/Cellar/[email protected]/3.7.10_2/Frameworks/Python.framework/Versions/3.7/lib/python3.7/os.py", line 686, in __setitem__
        value = self.encodevalue(value)
      File "/usr/local/Cellar/[email protected]/3.7.10_2/Frameworks/Python.framework/Versions/3.7/lib/python3.7/os.py", line 756, in encode
        raise TypeError("str expected, not %s" % type(value).__name__)
    TypeError: str expected, not int
    ----------------------------------------
ERROR: Command errored out with exit status 1: /Users/dmitrykan/project/ann-benchmarks/venv/bin/python -u -c 'import io, os, sys, setuptools, tokenize; sys.argv[0] = '"'"'/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/setup.py'"'"'; __file__='"'"'/private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-install-l_rkp2wp/numpy_7ba5c87712f044d5af4cf340e9f6bc24/setup.py'"'"';f = getattr(tokenize, '"'"'open'"'"', open)(__file__) if os.path.exists(__file__) else io.StringIO('"'"'from setuptools import setup; setup()'"'"');code = f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' install --record /private/var/folders/2l/f04dpd917vx50cyl8fftcxzr0000gn/T/pip-record-wrmxmqjz/install-record.txt --single-version-externally-managed --compile --install-headers /Users/dmitrykan/project/ann-benchmarks/venv/include/site/python3.7/numpy Check the logs for full command output.

Leo (@searchivarius) and I have added a new algorithm (Hierarchical NSW, HNSW) and updated the parameters and performance of the SW-graph algorithm (both from nmslib). Results of comparison to FALCONN and Annoy on the same amazon instance are attached below. Comparison on a Xeon E5-4650 v2 machine can be found in the HNSW preprint http://arxiv.org/abs/1603.09320 Note that SW-graph and HNSW indexes are now saved and reused later to strongly reduce the testing time.

As an addition, we have increased the number of queries to 10K (5K might be also OK), see Leo's comments below:

Eric is most welcome to use any other random_state.

Last time, Leo was testing using random_state==1 However, it is best to use a new random seed for each major re-evaluation, that we test on a truly bind data.

Increasing the number of queries or changing the seed, won't make truly weak methods much faster. However, in my experience, this can easily result in 10-30% changes in performance. This may affect relative performance of methods with similar performance.

Adding Open Distro Elasticsearch KNN plugin support by borrowing on the ES setup from elasticsearch and elastiknn. Below is a comparison on fashion-mnist between this opendistroknn and elastiknn, where opnedistroknn has ~3X better queries/s at comparable recall.

I changed two things in NearPy. The really awful thing was, that no UniqueFilter was used by default. That caused the same indexed vector to be multiple times in the search candidate set. After computing the distance to the query vector and sorting with respect to that, in many cases this caused the cropped N=10 nearest neighbour set to contain the same vector multiple times. Also distance computation was more expensive because of the duplicates. The other thing is that I now store normalized vectors in the index which speeds up distance computation a lot.

Both changes are released via pypi in NearPy 0.2.2

I also ran your benchmark code with a reduced dataset to look for good parameters.

This example with just 50000 vectors shows that the above fixes helped a lot so far. Especially the missing UniqueFilter created an upper bound on the accuracy before.

This commit adds support for reconfiguring an already-built data structure with new query parameters, making it possible to reuse one to perform many different experiments. (This was discussed in issue #41.)

A bit janky, since (a) Milvus is a server process, so I hacked a hacky entrypoint file to run a daemon (b) was impossible building it from source, but I realized I can just copy the relevant binaries from the "official" dockerfile and it seems to work

Running some benchmarks now, will see what we get

• A command line argument "--algo" is added so one can run only one algorithm instead of all.
• Updated kgraph configuration for two dataset separately.

The All-Nearest-Neighbors problem (All-NN) asks us to find all pairs of nearest neighbors in a set of n points in d-dimensions. Classically, there is a deterministic O(n log n) algorithm, as well as stochastic O(n sqrt(n)) algorithm.

I would like to test the All-NN performance of algorithms like Faiss. According to a google insider, the closed version of faiss does have a mode that solve All-NN. However, I don't know if the public version does.

I suspect it may, and I suspect that ann-benchmarks has a mode that can effectively test All-NN performance via its batch mode. However I don't understand the terminology well enough to determine of batch mode is equivalent to solving All-NN. Can it?

The repo is on Ubuntu 18 and Python 3.6.

I'm having trouble upgrading the Elastiknn benchmarks because the latest Elasticseach Ubuntu installer relies on some things that don't seem to be in Ubuntu 18. I've also jumped through some hoops with Python, e.g., intentionally installing older versions of scipy for compat w/ 3.6.

Any reason not to upgrade? Any dragons to be aware of in case I take a first pass at it?

Would it be in the spirit of this benchmarks to add a second benchmark category for ANN in conjunction with categorial filters?

Most real-world applications of ANN will required category filtering e.g. when searching for cloths in an e-commerce scenario via ANN one might filter by gender (categorial) or availability (categorial).

There are several software products which allow combining ANN and category filters e.g. Apache Solr, Elasticsearch, Vertex AI Matching Engine, weaviate, qdrant. However, they mainly differ to this benchmarks in that they are managed services or just services but not embeddable libraries.

In addition to recall vs. queries per second there should be a view which filters to a fraction of the date vs. recall vs. queries per second. For the proprietary managed services, also a cost dimension might be useful.

I have found the following blog articles covering the topic:

• https://blog.vasnetsov.com/posts/categorical-hnsw/
• https://towardsdatascience.com/effects-of-filtered-hnsw-searches-on-recall-and-latency-434becf8041c
• https://towardsdatascience.com/using-approximate-nearest-neighbor-search-in-real-world-applications-a75c351445d

Given that this would be very useful for practical implementations but also the fact that it significantly complicates the benchmarks I would be interested in your opinion and/or how I could help with it. Also I would be great to know if someone has already done such benchmarks.

I was wondering if there is a way of defining what is a “reasonable” relative error, something similar to recall 0.9, 0.95, 0.99. Furthermore, how much is this metric is effected by the distance metric? If you have any experience with this metric I’ll be happy to here about it. Thanks in advance, Guy

This was recently released in Elasticsearch 8.0+ and the API is documented here

Elasticsearch is distinct in both implementation and product from OpenSearch (Amazon maintained fork), and I expect that the two APIs will have different results. Both are HNSW based.

Thanks for maintaining this repo!