Working with subsets

[FlorianWilhelm]

First of all, thanks for providing such a useful piece of software, I find it especially useful when dealing with embeddings. I was wondering if I can somehow define at query time a subset of items that should be considered when calculating the kNN.

Let's assume I want to build some kind of search application that besides some user provided filters also considers the preferences I have collected about the user in form of an user embedding. I could for instance use ElasticSearch to retrieve a list of feasible item ids fulfilling the user's filter criteria. Now I want to find the kNN given the user's embedding in my index of all documents but restricted to the subset of feasible items which I retrieved before.

Another possibility to solve this would be if you allow me to add metadata when adding an item to the annoy index. With an additionally provided filter clause annoy could then only consider the item vectors having the defined metadata when calculating the kNN.

How is Spotify solving this problem, anyhow? Do you have an extended version of annoy?

[erikbern]

Sorry – none of these things are easy to support using Annoy

[a1k0n]

Effectively you have to ask for a bunch of extra items, and then filter them down using your external metadata. AFAIK this is still the same Annoy used internally at Spotify -- in that case it's usually an item blacklist (e.g. stuff the user is already quite familiar with).

If you already have a full subset of feasible items wouldn't it make sense to just exhaustively rank them and use a top-k heap instead of Annoy?

[FlorianWilhelm]

Thanks for the fast reply.

@a1k0n: Exactly, but if the subset is still quite large, exhaustively ranking them might be too expensive. Let's say I want to recommend a new song to the user from the rock genre since that's what the user selected.

First using Annoy to retrieve candidates and filter them down afterwards could also result in having an empty result set and does not feel right in a way, but maybe that's the best workaround for now.

[erikbern]

I'm going to close this issue as a "won't fix" – feel free to continue the discussion, but I don't think it's something Annoy will ever support. It's just not within the small scope of Annoy to support it.

[a1k0n]

Ah, I see. Yeah, that sort of thing would have to be engineered in concert with the ANN indexing scheme and vastly complicate the file format.

One feature which might improve this situation is if Annoy had an iterator API; instead of asking for a certain number of items, you would just iterate the stream of potentially all items, ranked. Then you'd just walk the iterator, checking your metadata for each match -- if this were implemented internally in annoy, that's what it would be doing anyway. This is slightly problematic though because it's not clear how search_k would fit into this.

Or, if you have a small number of tags, make separate indexes for each tag? Doesn't help if you want exactly K items matching a union or intersection query though; you'll have to ask for extra items then too.

[erikbern]

It might be possible to make the results iterable in Annoy, but it seems pretty hard unfortunately

[FlorianWilhelm]

@a1k0n that really sounds like a good idea. An iterator that just provides me with as many neighbours as I want would solve my problem and seems not be out of scope for Annoy.

[a1k0n]

The major issue with that is that the iterator won't be guaranteed to return results in order of best match (since it's an approximate nearest neighbor search), and it will require O(k log k) memory for k results as it needs to de-duplicate them. Overall that's not too bad, I guess, but it won't be as clean to use as the existing API -- if you want to get results as good as the normal API call, you have to iterate quite a bit further than the number of results you actually want and discard the worst matches.

[erikbern]

yes correct @a1k0n – it's also nontrivial to implement since it has to permeate through the C bindings into the C++ module