Hi,

at first thanks for this great library. It works great.

My question refers to missing values in feature vectors. Say, we have used a set of N d-dimensional vectors to create the classifier. Is it possible to query neighbours if our query vector has less than d dimension, e.g. a missing values in one or more dimensions?

Thanks in advance & Best, Max

I downloaded hnswlib package to my env but I am constantly getting an error about AttributeError Traceback (most recent call last) in 1 # Declaring index ----> 2 p = hnswlib.Index(space = 'cosine', dim = EMBEDDING_SIZE) # possible options are l2, cosine or ip

AttributeError: module 'hnswlib' has no attribute 'Index'

Changes

• Index class

  • Static factory methods createFromIndex and createFromParams for Index construction from another Index object or Index parameter tuple, respectively
  • Method getIndexParams serializes Index object. Returns a tuple with Index parameters.
  • Method getAnnData returns a tuple with hnsw-specific parameters. Copy of appr_alg->data_level0_memory_ and appr_alg->linkLists_ are returned as py::array_t<char> objects to avoid additional copying from python side

• Python bindings for Index class

  • Index serialization is implemented with py::pickle definition from pybind11
  • Bind Index.__init__ to static factory methods createFromIndex and createFromParams
  • Expose parameters of the hnsw index as read-only properties in python:
    • space_name, dim, max_elements, element_count, ef_construction, M, num_threads, ef
  • And, two properties that support read and write:
    • ef, num_threads

• Updated API documentation and the first python example in README.md

• New test in python_bindings/tests/bindings_test_pickle.py.

  • Verifies that results of knn_query match results from copies of the same index. Index objects are copied using round-trip pickling.
  • Verify that knn_query gives recall of (almost) 100% for k=25 using three spaces. Brute-force search is used to return ground-truth labels for the randomly generated items.
  • Create separate test for each space
  • Sample test output:

> python3 -m unittest  tests/bindings_test_pickle.py -k Inner
Running pickle tests for <hnswlib.Index(space='ip', dim=48)>
Warning: 1 labels are missing from ann results (k=25, err_thresh=5)
Warning: 1 labels are missing from ann results (k=25, err_thresh=5)
 ... 
Warning: 16 ann distance values are different from brute-force values (total # of values=5000, dists_thresh=50)

.
----------------------------------------------------------------------
Ran 1 test in 19.057s

OK

Closes: https://github.com/nmslib/hnswlib/issues/269 https://github.com/nmslib/hnswlib/issues/177

hnswlib does not use the recommended packaging approach for pybind11. https://pybind11.readthedocs.io/en/stable/compiling.html#setup-helpers-pep518

The pyproject.toml file can specify the requirements necessary for the build backend (setuptools in this case) that are installed before the actual build takes place.

This should also make it easier to start packaging wheels etc if this project moves to a more modern packaging approach.

The error also occurs when running the example code of hnswlib. It seems it is correlated with the system eviroment, but i can not figure it out. Same code runs well on another machine. The error occurs when running this code line:

p.init_index(max_elements = num_elements, ef_construction = 200, M = 16)

I reinstall unbuntu system and hnsw, and it runs into core dump when import hnswlib ...

Any hint or suggestions here?

Fixes https://github.com/nmslib/hnswlib/issues/366

Summary of the change

An optional filtering function can be specified as a template parameter that determines if a given ID should be picked. The default is a function that allows all labels via areturn true -- this will be optimised away by the compiler, so there will be no extra cost for those who don't provide a filtering function.

The use of a templated filter function also ensures that the filtering logic can be entirely inlined by the compiler, and is an implementation detail, instead of forcing a std::set<> of allowed IDs as discussed in #366.

I've added a test that asserts on both the brute force and hnsw implementations. Verified that existing search knn tests pass.

I have created a matrix with 300 dimensions x 70,000 documents (L2 normalized Latent Semantic Vectors). With this data set using M of 300 and efConstruction of 400, I get 99.671% accuracy on retrieving the top 300 items with efSearch of 400. efSearch = 100, I get 82%.

NOTE: using HNSW and "consinesimil" when building the index.

With an M value of 96, and all other parameters the same I get an accuracy of 80.03% for efSearch of 400 and %80.8 for an efSearch value of 1600.

ISSUES:

1. When I increase the # of items to 6,000,000 my results are terrible, even with large values of M (300 or more). Exactly the same kind of data, just a lot more of it.
2. The guidance for setting M and efConstruction size (or just overiding maxM0) is very minimal but seems to suggest that the M value should not need to be so large. I am guessing that the issue is due to having a very large number of similar documents.

Is there better guidance on setting these values or do I need to know the inrinsic amount of similarity in the data collection to put together "optimal" settings? I was thining of doing a random sample of data and get some real measurements and then use that to predict the best parameters.

Any help would be greatly appreciated.

Mike

Hi yurymalkov,

I'm sorry to disturb you again. I have a question about the recall performance evaluation in sift_1b.cpp. In sift_1b.cpp, the number of returned sample for each query is 1, then for the samples at top K (top@K) in the ground truth, if the returned sample is in the samples at top K, it counts 1. I think there is another method which is more appropriate than this. This method is as follows:

The number of retrieved samples for each query is K (top@K), and for the sample at top 1 (top@1) in the ground truth, we check whether it (the sample of ground truth at top 1) in the top@K of retrieved samples. If true, it counts 1.

I think this evaluation is better than the method adopted in sift_1b.cpp. Taking face retrieval as example, we want to get high recall rate. If the same face doesn't recall at top of 10, we can set the number of retrieved samples to big, such as top@50.

How do you think about the evaluation method in the sift_1b.cpp and the method I show it on above?

Looking forward to your reply.

Currently SIMD (SSE or AVX) is used for the cases when dimension is multiple of 4 or 16, while when dimension size is not strictly equal to multiple of 4 or 16 a slower non-vectorized method is used.

To improve performnance for these cases new methods are added: L2SqrSIMD(4|16)ExtResidual - it relies on existing L2SqrSIMD(4|16)Ext to compute up to *4 and *16 dimensions and finishes residual computation by non-vectorized method L2Sqr.

Summary of the change

Expose filtering functionality introduced in #402 in Python API. Changes are kept to a minimum, only HNSW index is implemented and not brute force.

For a discussion of the interface design see here.

Preliminary performance characteristics for filtering (not strictly related to the changes):

| filter | queries per second | | ----------- | ----------- | | 0.1 | 4241.43 | | 0.2 | 5993.89 | | 0.3 | 8232.54 | | 0.4 | 10688.06 | | 0.5 | 11677.54 | | 0.6 | 13242.56 | | 0.7 | 14520.50 | | 0.8 | 14659.25 | | 0.9 | 14932.67 | | none | 503578.34 |

Here filter denotes the fraction of elements the query was restricted to. none denotes that no filtering has been applied.

As per the above table, there is a threshold below which exact ANN is probably preferable.

The following error occurs when trying to pip install hnswlib: clang: error: the clang compiler does not support '-march=native'

The command: clang -cc1 --help | grep march Returns nothing.

Mac no longer has "-march=native" option.

This PR modifies setup.py to not include that option for mac.

void getNeighborsByHeuristic2(
            std::priority_queue<std::pair<dist_t, tableint>, std::vector<std::pair<dist_t, tableint>>, CompareByFirst> &top_candidates,
            const size_t M)
        {
            if (top_candidates.size() < M)
            {
                return;
            }

            std::priority_queue<std::pair<dist_t, tableint>> queue_closest;
            std::vector<std::pair<dist_t, tableint>> return_list;
            while (top_candidates.size() > 0)
            {
                queue_closest.emplace(-top_candidates.top().first, top_candidates.top().second);
                top_candidates.pop();
            }

            while (queue_closest.size())
            {
                if (return_list.size() >= M)
                    break;
                std::pair<dist_t, tableint> curent_pair = queue_closest.top();
                dist_t dist_to_query = -curent_pair.first; 
                queue_closest.pop();
                bool good = true;

                for (std::pair<dist_t, tableint> second_pair : return_list)
                {
                    dist_t curdist =
                        fstdistfunc_(getDataByInternalId(second_pair.second),
                                     getDataByInternalId(curent_pair.second),
                                     dist_func_param_);
                    ;
                    if (curdist < dist_to_query) # FLIP THE INEQUALITY HERE
                    {
                        good = false;
                        break;
                    }
                }
                if (good)
                {
                    return_list.push_back(curent_pair);
                }
            }

Say the distance function is inner product. curdist will be a similarity between the neighbours. dist_to_query is a similarity between the current node and the query.

In the code below,

if (curdist < dist_to_query) # FLIP THE INEQUALITY HERE
{
    good = false;
    break;
}

When heuristically choosing the neighbours, you should only keep the representational nodes. However, this code is removing the nodes that are more similar to the query than their neighbours are similar to each other when you should the other way around. After several tests, I could confirm that flipping the inequality significantly boosts the accuracy of this algorithm.

I use ParallelFor as https://github.com/nmslib/hnswlib/blob/7cc0ecbd43723418f43b8e73a46debbbc3940346/python_bindings/bindings.cpp#L239

// c++ code, add 10000 points, addPoint cost 7580ms
// compile flags:  -std=c++11 -g -pipe -W -Wall -fPIC -pthread -Ofast -fwrapv
int d = 256;
hnswlib::labeltype n = 10000;
   
std::vector<float> data(n * d);
std::mt19937 rng;
rng.seed(47);
std::uniform_real_distribution<> distrib;

for (hnswlib::labeltype i = 0; i < n * d; ++i) {
    data[i] = distrib(rng);
}

hnswlib::L2Space space(d);
hnswlib::AlgorithmInterface<float>* alg_hnsw = new hnswlib::HierarchicalNSW<float>(&space, 2 * n);
int num_threads = std::thread::hardware_concurrency();
ParallelFor(0, n, num_threads, [&](size_t row, size_t threadId) {
                    alg_hnsw->addPoint((void *) data.data() + d * row, (size_t) row);
});

# python code, add 10000 points, add_items cost 310ms
import numpy as np
import hnswlib
import time
dim = 256
num_elements = 10000
data = np.float32(np.random.random((num_elements, dim)))
ids = np.arange(num_elements)
p = hnswlib.Index(space = 'ip', dim = dim)
p.init_index(max_elements = num_elements, ef_construction = 200, M = 16)
start=time.time();p.add_items(data, ids);end=time.time();

Is there anything i missed in c++ code? Why c++ is mush slower?

https://github.com/nmslib/hnswlib/blob/443d667478fddf1e13f2e06b1da4e1ec3a9fe716/hnswlib/hnswalg.h#L267

“ || has_deletions == false”

There is a problem with this judgment condition, which will cause the loop to exit early .

Hello, everyone,

Some labels are duplicate in our case. We add labels by multi-thread. I found thread may lock the same mutex two times in one addPoint which lead to deadlock. The first time to lock mutex at here: https://github.com/nmslib/hnswlib/blob/master/hnswlib/hnswalg.h#L1021 The second time to lock the same mutex at here: https://github.com/nmslib/hnswlib/blob/master/hnswlib/hnswalg.h#L185