Link Search Menu Expand Document

Performance

Elastiknn is benchmarked on a subset of datasets from the popular ann-benchmarks project.

Method

For each dataset, run a grid-search over mappings and compatible queries. Report the pareto frontier for recall and queries/second. Present the mapping and query used for each point on the pareto frontier. Partition these results by the number of shards in the index, which controls parallelism at query time. Currently, all datasets are indexed with exactly one shard (i.e. no parallelism), merged into a single segment, with zero replicas.

Each run uses a single-node Elasticsearch cluster with an 8GB heap, G1 garbage collection, tmpfs storage (for faster indexing, has minimal effect on queries), running on C5.4XLarge EC2 instances in an AWS EKS cluster.

Work In Progress

  1. Results for the remaining ann-benchmarks datasets.
  2. Results for multiple shards and possibly multiple nodes (i.e. quantify effects of scaling out).
  3. Results for larger datasets, e.g. Deep1B and Amazon reviews image vectors.

Caveats

If you need high-throughput nearest neighbor search for batch jobs, there are many faster methods. When comparing Elastiknn performance to these methods, consider the following:

  1. Elastiknn executes entirely in the Elasticsearch JVM and is implemented with existing Elasticsearch and Lucene primitives. Many other methods use C and C++, which are generally faster than the JVM for pure number crunching tasks.
  2. Elastiknn issues an HTTP request for every query, since a KNN query is just a standard Elasticsearch query. Most other methods operate without network I/O.
  3. Elastiknn stores vectors on disk and uses zero caching beyond the caching that Lucene already implements. Most other methods operate entirely in memory.
  4. Elastiknn scales horizontally out-of-the-box by adding shards to an Elasticsearch index. Query latency typically scales inversely with the number of shards, i.e., queries on an index with two shards will be 2x faster than an index with one shard. Few other methods are this simple to parallelize.

Results

  1. Annb Fashion Mnist
    1. Single Shard
  2. Annb Sift
    1. Single Shard

Annb Fashion Mnist

Single Shard

Exact 100

Recall Q/S Mapping Query
1 8 {“dims”: 784} {“model”: “exact”, “similarity”: “l2”}

LSH 100

Recall Q/S Mapping Query
1 70 {“L”: 125, “dims”: 784, “k”: 3, “model”: “lsh”, “similarity”: “l2”, “w”: 7} {“candidates”: 1000, “model”: “lsh”, “probes”: 9, “similarity”: “l2”}
0.99 112 {“L”: 75, “dims”: 784, “k”: 3, “model”: “lsh”, “similarity”: “l2”, “w”: 7} {“candidates”: 1000, “model”: “lsh”, “probes”: 9, “similarity”: “l2”}
0.98 127 {“L”: 125, “dims”: 784, “k”: 3, “model”: “lsh”, “similarity”: “l2”, “w”: 6} {“candidates”: 1000, “model”: “lsh”, “probes”: 4, “similarity”: “l2”}
0.97 138 {“L”: 100, “dims”: 784, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 7} {“candidates”: 1000, “model”: “lsh”, “probes”: 6, “similarity”: “l2”}
0.96 150 {“L”: 50, “dims”: 784, “k”: 3, “model”: “lsh”, “similarity”: “l2”, “w”: 6} {“candidates”: 1000, “model”: “lsh”, “probes”: 10, “similarity”: “l2”}
0.95 160 {“L”: 50, “dims”: 784, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 7} {“candidates”: 1000, “model”: “lsh”, “probes”: 10, “similarity”: “l2”}
0.94 165 {“L”: 50, “dims”: 784, “k”: 3, “model”: “lsh”, “similarity”: “l2”, “w”: 6} {“candidates”: 1000, “model”: “lsh”, “probes”: 6, “similarity”: “l2”}
0.93 177 {“L”: 50, “dims”: 784, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 7} {“candidates”: 1000, “model”: “lsh”, “probes”: 7, “similarity”: “l2”}
0.92 178 {“L”: 50, “dims”: 784, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 7} {“candidates”: 1000, “model”: “lsh”, “probes”: 6, “similarity”: “l2”}
0.91 180 {“L”: 50, “dims”: 784, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 7} {“candidates”: 1000, “model”: “lsh”, “probes”: 5, “similarity”: “l2”}
0.89 191 {“L”: 50, “dims”: 784, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 7} {“candidates”: 1000, “model”: “lsh”, “probes”: 4, “similarity”: “l2”}
0.84 194 {“L”: 50, “dims”: 784, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 6} {“candidates”: 1000, “model”: “lsh”, “probes”: 4, “similarity”: “l2”}
0.81 195 {“L”: 50, “dims”: 784, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 6} {“candidates”: 1000, “model”: “lsh”, “probes”: 3, “similarity”: “l2”}
0.74 196 {“L”: 50, “dims”: 784, “k”: 3, “model”: “lsh”, “similarity”: “l2”, “w”: 3} {“candidates”: 1000, “model”: “lsh”, “probes”: 8, “similarity”: “l2”}
0.63 198 {“L”: 50, “dims”: 784, “k”: 3, “model”: “lsh”, “similarity”: “l2”, “w”: 3} {“candidates”: 1000, “model”: “lsh”, “probes”: 4, “similarity”: “l2”}
0.44 204 {“L”: 50, “dims”: 784, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 3} {“candidates”: 1000, “model”: “lsh”, “probes”: 5, “similarity”: “l2”}
0.42 207 {“L”: 50, “dims”: 784, “k”: 2, “model”: “lsh”, “similarity”: “l2”, “w”: 1} {“candidates”: 1000, “model”: “lsh”, “probes”: 8, “similarity”: “l2”}
0.39 208 {“L”: 50, “dims”: 784, “k”: 2, “model”: “lsh”, “similarity”: “l2”, “w”: 1} {“candidates”: 1000, “model”: “lsh”, “probes”: 5, “similarity”: “l2”}
0.35 212 {“L”: 50, “dims”: 784, “k”: 2, “model”: “lsh”, “similarity”: “l2”, “w”: 1} {“candidates”: 1000, “model”: “lsh”, “probes”: 4, “similarity”: “l2”}

Annb Sift

Single Shard

Exact 100

Recall Q/S Mapping Query
1 3 {“dims”: 128} {“model”: “exact”, “similarity”: “l2”}

LSH 100

Recall Q/S Mapping Query
1 6 {“L”: 75, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 3} {“candidates”: 10000, “model”: “lsh”, “probes”: 6, “similarity”: “l2”}
0.99 9 {“L”: 75, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 3} {“candidates”: 10000, “model”: “lsh”, “probes”: 3, “similarity”: “l2”}
0.98 13 {“L”: 50, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 3} {“candidates”: 10000, “model”: “lsh”, “probes”: 3, “similarity”: “l2”}
0.96 16 {“L”: 100, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 3} {“candidates”: 10000, “model”: “lsh”, “probes”: 0, “similarity”: “l2”}
0.93 24 {“L”: 75, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 3} {“candidates”: 10000, “model”: “lsh”, “probes”: 0, “similarity”: “l2”}
0.89 35 {“L”: 100, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 1} {“candidates”: 10000, “model”: “lsh”, “probes”: 9, “similarity”: “l2”}
0.84 43 {“L”: 100, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 1} {“candidates”: 10000, “model”: “lsh”, “probes”: 6, “similarity”: “l2”}
0.78 50 {“L”: 75, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 1} {“candidates”: 10000, “model”: “lsh”, “probes”: 6, “similarity”: “l2”}
0.75 55 {“L”: 50, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 1} {“candidates”: 10000, “model”: “lsh”, “probes”: 9, “similarity”: “l2”}
0.71 57 {“L”: 75, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 1} {“candidates”: 5000, “model”: “lsh”, “probes”: 6, “similarity”: “l2”}
0.68 58 {“L”: 50, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 1} {“candidates”: 5000, “model”: “lsh”, “probes”: 9, “similarity”: “l2”}
0.67 63 {“L”: 50, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 1} {“candidates”: 10000, “model”: “lsh”, “probes”: 6, “similarity”: “l2”}
0.6 71 {“L”: 50, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 1} {“candidates”: 5000, “model”: “lsh”, “probes”: 6, “similarity”: “l2”}
0.58 72 {“L”: 75, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 1} {“candidates”: 5000, “model”: “lsh”, “probes”: 3, “similarity”: “l2”}
0.47 87 {“L”: 50, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 1} {“candidates”: 5000, “model”: “lsh”, “probes”: 3, “similarity”: “l2”}
0.35 97 {“L”: 100, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 1} {“candidates”: 5000, “model”: “lsh”, “probes”: 0, “similarity”: “l2”}
0.31 103 {“L”: 75, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 1} {“candidates”: 5000, “model”: “lsh”, “probes”: 0, “similarity”: “l2”}
0.23 104 {“L”: 50, “dims”: 128, “k”: 4, “model”: “lsh”, “similarity”: “l2”, “w”: 1} {“candidates”: 5000, “model”: “lsh”, “probes”: 0, “similarity”: “l2”}