search

erikbern / ann-benchmarks

Benchmarks of approximate nearest neighbor libraries in Python
http://ann-benchmarks.com
MIT License
4.86k stars 729 forks source link

Which libraries support incremental item additions? #36

Open alexklibisz opened 6 years ago

alexklibisz commented 6 years ago

Thanks for putting this project together. Is there any way a table or small list could be included to describe which libraries support incremental item additions? I imagine for many this is an important criteria in real-time or near-real-time applications where new content is continuously added and needs to be indexed for look-ups.

erikbern commented 6 years ago

i don't think any of them do, unfortunately :(

aaalgo commented 6 years ago

Last time I checked (many years ago), FLANN's C++ API supported insertion. In theory it's also easy for all LSH-based methods to support insertion. The Python API might not have such functionality exposed though.

alexklibisz commented 6 years ago

@aaalgo Yes from the FLANN website:

(14 December 2012) Version 1.8.0 is out bringing incremental addition/removal of points to/from indexes

Though I'm still trying to figure out how to leverage this via Python.

alexklibisz commented 6 years ago

@erikbern Do you have any recommendations for "online" NN-search from your experience? One approach I'm considering is to maintain an indexed lookup (e.g. Annoy) for the majority of my items as well as a brute-force lookup (e.g. sklearn) for the newest items. Then at some threshold, rebuild the index to include the newest points.

erikbern commented 6 years ago

I don't have any great recommendations, but your idea makes sense though. You could even formalize it and have indexes that have size even powers of two, and any time you have two indexes of the same size, you merge them. That would give you log(n) amortized runtime, although worst case is linear.

yurymalkov commented 6 years ago

@alexklibisz Both hnsw and sw-graph are built incrementally, and thus naturally support incremental item addition. Hovewer, nmslib does not have a python interface for that, only c++.

@erikbern @alexklibisz I think you are talking about Bentley-Saxe method. http://www.sciencedirect.com/science/article/pii/S030643791300104X

erikbern commented 6 years ago

@yurymalkov yeah i've never heard of it, but think that's what i meant. basically play 2048 with the indexes :)

alexklibisz commented 6 years ago

For anyone interested, I built a project that supports the feature from my original question on top of Elasticsearch: https://github.com/alexklibisz/elastik-nearest-neighbors

yurymalkov commented 6 years ago

@alexklibisz Cool @erikbern There are now several algorithms that support updates: flann, hnswlib, faiss (batched updates). Probably, this should be noted in readme somehow.