Vector based store and ANN

classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

Vector based store and ANN

Pedram Rezaei

Hi there,

 

Is there a way to store numerical vectors (vector based index) and perform search based on Approximate Nearest Neighbor class of algorithms in Lucene?

 

If not, has there been any interests in the topic so far?

 

Thanks,

 

Pedram

Reply | Threaded
Open this post in threaded view
|

Re: Vector based store and ANN

Adrien Grand
Hi Pedram,

We don't have much in this area, but I'm hearing increasing interest
so it'd be nice to get better there! The closest that we have is this
class that can search for nearest neighbors for a vector of up to 8
dimensions: https://github.com/apache/lucene-solr/blob/master/lucene/sandbox/src/java/org/apache/lucene/document/FloatPointNearestNeighbor.java.

On Wed, Feb 27, 2019 at 1:44 AM Pedram Rezaei
<[hidden email]> wrote:

>
> Hi there,
>
>
>
> Is there a way to store numerical vectors (vector based index) and perform search based on Approximate Nearest Neighbor class of algorithms in Lucene?
>
>
>
> If not, has there been any interests in the topic so far?
>
>
>
> Thanks,
>
>
>
> Pedram



--
Adrien

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: Vector based store and ANN

J. Delgado
Lucene’s scoring function (which I believe is okapi BM25  
https://en.m.wikipedia.org/wiki/Okapi_BM25) is a kind of nearest neighbor using the TF-IDF vector representation of documents and query. Are you interested in ANN to be applied to a different kind of vector representation, say for example Doc2Vec?

On Thu, Feb 28, 2019 at 5:59 AM Adrien Grand <[hidden email]> wrote:
Hi Pedram,

We don't have much in this area, but I'm hearing increasing interest
so it'd be nice to get better there! The closest that we have is this
class that can search for nearest neighbors for a vector of up to 8
dimensions: https://github.com/apache/lucene-solr/blob/master/lucene/sandbox/src/java/org/apache/lucene/document/FloatPointNearestNeighbor.java.

On Wed, Feb 27, 2019 at 1:44 AM Pedram Rezaei
<[hidden email]> wrote:
>
> Hi there,
>
>
>
> Is there a way to store numerical vectors (vector based index) and perform search based on Approximate Nearest Neighbor class of algorithms in Lucene?
>
>
>
> If not, has there been any interests in the topic so far?
>
>
>
> Thanks,
>
>
>
> Pedram



--
Adrien

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

RE: Vector based store and ANN

Pedram Rezaei

Hi there,

 

Thank you for the responses. Yes, we have a few scenarios in mind that can benefit from a vector-based index optimized for ANN searches:

 

  • Advanced, optimized, and high precision visual search: For this to work, we would convert the images to their vector representations and then use algorithms and implementations such as SPTAG, FAISS, and HNSWLIB.
  • Advanced document retrieval: Using a numerical vector representation of a document, we could improve the search result
  • Nearest neighbor queries: discovering the nearest neighbors to a given query could also benefit from these ANN algorithms (although doesn’t necessarily need the vector based index)

 

I would be grateful to hear your thoughts and whether the community is open to a conversation on this topic with my team.

 

Thanks,

 

Pedram

 

From: J. Delgado <[hidden email]>
Sent: Thursday, February 28, 2019 7:38 AM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>
Subject: Re: Vector based store and ANN

 

Lucene’s scoring function (which I believe is okapi BM25  

https://en.m.wikipedia.org/wiki/Okapi_BM25) is a kind of nearest neighbor using the TF-IDF vector representation of documents and query. Are you interested in ANN to be applied to a different kind of vector representation, say for example Doc2Vec?

 

On Thu, Feb 28, 2019 at 5:59 AM Adrien Grand <[hidden email]> wrote:

Hi Pedram,

We don't have much in this area, but I'm hearing increasing interest
so it'd be nice to get better there! The closest that we have is this
class that can search for nearest neighbors for a vector of up to 8
dimensions: https://github.com/apache/lucene-solr/blob/master/lucene/sandbox/src/java/org/apache/lucene/document/FloatPointNearestNeighbor.java.

On Wed, Feb 27, 2019 at 1:44 AM Pedram Rezaei
<[hidden email]> wrote:
>
> Hi there,
>
>
>
> Is there a way to store numerical vectors (vector based index) and perform search based on Approximate Nearest Neighbor class of algorithms in Lucene?
>
>
>
> If not, has there been any interests in the topic so far?
>
>
>
> Thanks,
>
>
>
> Pedram



--
Adrien

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: Vector based store and ANN

david.w.smiley@gmail.com
This presentation by Rene Kriegler at Haystack 2018 was a real eye-opener to me on this subject: https://haystackconf.com/2018/relevance-scoring/. Uses random-projection forests which is a very clever technique.  (CC'ing Rene)

~ David

On Fri, Mar 1, 2019 at 1:30 PM Pedram Rezaei <[hidden email]> wrote:

Hi there,

 

Thank you for the responses. Yes, we have a few scenarios in mind that can benefit from a vector-based index optimized for ANN searches:

 

  • Advanced, optimized, and high precision visual search: For this to work, we would convert the images to their vector representations and then use algorithms and implementations such as SPTAG, FAISS, and HNSWLIB.
  • Advanced document retrieval: Using a numerical vector representation of a document, we could improve the search result
  • Nearest neighbor queries: discovering the nearest neighbors to a given query could also benefit from these ANN algorithms (although doesn’t necessarily need the vector based index)

 

I would be grateful to hear your thoughts and whether the community is open to a conversation on this topic with my team.

 

Thanks,

 

Pedram

 

From: J. Delgado <[hidden email]>
Sent: Thursday, February 28, 2019 7:38 AM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>
Subject: Re: Vector based store and ANN

 

Lucene’s scoring function (which I believe is okapi BM25  

https://en.m.wikipedia.org/wiki/Okapi_BM25) is a kind of nearest neighbor using the TF-IDF vector representation of documents and query. Are you interested in ANN to be applied to a different kind of vector representation, say for example Doc2Vec?

 

On Thu, Feb 28, 2019 at 5:59 AM Adrien Grand <[hidden email]> wrote:

Hi Pedram,

We don't have much in this area, but I'm hearing increasing interest
so it'd be nice to get better there! The closest that we have is this
class that can search for nearest neighbors for a vector of up to 8
dimensions: https://github.com/apache/lucene-solr/blob/master/lucene/sandbox/src/java/org/apache/lucene/document/FloatPointNearestNeighbor.java.

On Wed, Feb 27, 2019 at 1:44 AM Pedram Rezaei
<[hidden email]> wrote:
>
> Hi there,
>
>
>
> Is there a way to store numerical vectors (vector based index) and perform search based on Approximate Nearest Neighbor class of algorithms in Lucene?
>
>
>
> If not, has there been any interests in the topic so far?
>
>
>
> Thanks,
>
>
>
> Pedram



--
Adrien

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

--
Lucene/Solr Search Committer (PMC), Developer, Author, Speaker
Reply | Threaded
Open this post in threaded view
|

RE: Vector based store and ANN

Pedram Rezaei

Thank you for sharing, and it is exciting to see how advanced your thinking is.

 

Yes, the idea is the same idea with an extra step that Rene also seems to elude to here in his comment. Instead of using these types of techniques only at the scoring time, we can use them for information retrieval from the index. This will allow us to, for example, index millions of images and quickly and efficiently lookup the most relevant images.

 

I would love to hear yours and others thoughts on this. I think there is a great opportunity here, but it would need a lot of input and guidance from the experts here.

 

Thank you,

 

Pedram

 

From: David Smiley <[hidden email]>
Sent: Friday, March 1, 2019 12:11 PM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>; René Kriegler <[hidden email]>
Subject: Re: Vector based store and ANN

 

This presentation by Rene Kriegler at Haystack 2018 was a real eye-opener to me on this subject: https://haystackconf.com/2018/relevance-scoring/. Uses random-projection forests which is a very clever technique.  (CC'ing Rene)

 

~ David

On Fri, Mar 1, 2019 at 1:30 PM Pedram Rezaei <[hidden email]> wrote:

Hi there,

 

Thank you for the responses. Yes, we have a few scenarios in mind that can benefit from a vector-based index optimized for ANN searches:

 

  • Advanced, optimized, and high precision visual search: For this to work, we would convert the images to their vector representations and then use algorithms and implementations such as SPTAG, FAISS, and HNSWLIB.
  • Advanced document retrieval: Using a numerical vector representation of a document, we could improve the search result
  • Nearest neighbor queries: discovering the nearest neighbors to a given query could also benefit from these ANN algorithms (although doesn’t necessarily need the vector based index)

 

I would be grateful to hear your thoughts and whether the community is open to a conversation on this topic with my team.

 

Thanks,

 

Pedram

 

From: J. Delgado <[hidden email]>
Sent: Thursday, February 28, 2019 7:38 AM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>
Subject: Re: Vector based store and ANN

 

Lucene’s scoring function (which I believe is okapi BM25  

https://en.m.wikipedia.org/wiki/Okapi_BM25) is a kind of nearest neighbor using the TF-IDF vector representation of documents and query. Are you interested in ANN to be applied to a different kind of vector representation, say for example Doc2Vec?

 

On Thu, Feb 28, 2019 at 5:59 AM Adrien Grand <[hidden email]> wrote:

Hi Pedram,

We don't have much in this area, but I'm hearing increasing interest
so it'd be nice to get better there! The closest that we have is this
class that can search for nearest neighbors for a vector of up to 8
dimensions: https://github.com/apache/lucene-solr/blob/master/lucene/sandbox/src/java/org/apache/lucene/document/FloatPointNearestNeighbor.java.

On Wed, Feb 27, 2019 at 1:44 AM Pedram Rezaei
<[hidden email]> wrote:
>
> Hi there,
>
>
>
> Is there a way to store numerical vectors (vector based index) and perform search based on Approximate Nearest Neighbor class of algorithms in Lucene?
>
>
>
> If not, has there been any interests in the topic so far?
>
>
>
> Thanks,
>
>
>
> Pedram



--
Adrien

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

--

Lucene/Solr Search Committer (PMC), Developer, Author, Speaker

Reply | Threaded
Open this post in threaded view
|

Re: Vector based store and ANN

René Kriegler
Hi there,

Thank you for looping me in. Just a few random thoughts on this topic: 

- I’ve heard ;-) that this ES plugin is fast for vector-based scoring: https://github.com/StaySense/fast-cosine-similarity. The links in the ‘General’ section provide some history. As far as I can see, there is nothing which couldn’t be implemented at Lucene level.

- For retrieval, I think a two-pass approach looks like something worth trying out. First pass: look up documents in a low dimensional space (maybe produced via LSH) and then, in the second pass, calculate vector distances in the high-dimensional space just for the documents that resulted from the first pass. This solution will come with some compromises to make. For example, a higher dimensionality of LSH would increase precision but also produce more hash tokens and make the lookup slower, especially for large indexes.

- Day 2 of Haystack 2019 (https://haystackconf.com/agenda/) will have a talk by Simon Hughes about ’Search with Vectors’. There is a channel on this topic at OpenSource Connections’ search relevance Slack (https://relevancy.slack.com) and Simon has been one of the drivers of the discussion.

Best,
René


On 1 Mar 2019, at 20:51, Pedram Rezaei <[hidden email]> wrote:

Thank you for sharing, and it is exciting to see how advanced your thinking is.
 
Yes, the idea is the same idea with an extra step that Rene also seems to elude to here in his comment. Instead of using these types of techniques only at the scoring time, we can use them for information retrieval from the index. This will allow us to, for example, index millions of images and quickly and efficiently lookup the most relevant images.
 
I would love to hear yours and others thoughts on this. I think there is a great opportunity here, but it would need a lot of input and guidance from the experts here.
 
Thank you,
 
Pedram
 
From: David Smiley <[hidden email]> 
Sent: Friday, March 1, 2019 12:11 PM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>; René Kriegler <[hidden email]>
Subject: Re: Vector based store and ANN
 
This presentation by Rene Kriegler at Haystack 2018 was a real eye-opener to me on this subject: https://haystackconf.com/2018/relevance-scoring/. Uses random-projection forests which is a very clever technique.  (CC'ing Rene)
 

~ David

On Fri, Mar 1, 2019 at 1:30 PM Pedram Rezaei <[hidden email]> wrote:
Hi there,
 
Thank you for the responses. Yes, we have a few scenarios in mind that can benefit from a vector-based index optimized for ANN searches:
 
  • Advanced, optimized, and high precision visual search: For this to work, we would convert the images to their vector representations and then use algorithms and implementations such as SPTAG, FAISS, and HNSWLIB.
  • Advanced document retrieval: Using a numerical vector representation of a document, we could improve the search result
  • Nearest neighbor queries: discovering the nearest neighbors to a given query could also benefit from these ANN algorithms (although doesn’t necessarily need the vector based index)
 
I would be grateful to hear your thoughts and whether the community is open to a conversation on this topic with my team.
 
Thanks,
 
Pedram
 
From: J. Delgado <[hidden email]> 
Sent: Thursday, February 28, 2019 7:38 AM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>
Subject: Re: Vector based store and ANN
 
Lucene’s scoring function (which I believe is okapi BM25  
https://en.m.wikipedia.org/wiki/Okapi_BM25) is a kind of nearest neighbor using the TF-IDF vector representation of documents and query. Are you interested in ANN to be applied to a different kind of vector representation, say for example Doc2Vec?
 
On Thu, Feb 28, 2019 at 5:59 AM Adrien Grand <[hidden email]> wrote:

Hi Pedram,

We don't have much in this area, but I'm hearing increasing interest
so it'd be nice to get better there! The closest that we have is this
class that can search for nearest neighbors for a vector of up to 8
dimensions: https://github.com/apache/lucene-solr/blob/master/lucene/sandbox/src/java/org/apache/lucene/document/FloatPointNearestNeighbor.java.

On Wed, Feb 27, 2019 at 1:44 AM Pedram Rezaei
<[hidden email]> wrote:


>
> Hi there,
>
>
>
> Is there a way to store numerical vectors (vector based index) and perform search based on Approximate Nearest Neighbor class of algorithms in Lucene?
>
>
>
> If not, has there been any interests in the topic so far?
>
>
>
> Thanks,
>
>
>
> Pedram



-- 
Adrien

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

-- 
Lucene/Solr Search Committer (PMC), Developer, Author, Speaker

Reply | Threaded
Open this post in threaded view
|

Re: Vector based store and ANN

J. Delgado
In reply to this post by Pedram Rezaei
Traditional search engines work both as a retrieval engine, with the support of arbitrarily complex BOOLEAN queries and a scoring engine that performs vector-based similarity computations. It works very well for words (terms) because of the clever inverted index and posting list data structures, used to represent a very sparse matrix that associate terms/weights with documents.  I'm not so sure if these core properties of a search engine can be generalized to performing the selection with an ANN algorithm such as LSH and then do a more sophisticated scoring function. Notice that doing nearest neighbor inherently doing a top-k selection.  As stated in Rene's presentation it can work with mages recognition vectors (embeddings) by implementing Random Projection Forest and indexing random projections and defining hyperplanes instead of the full high-dimensional vector, which is an interesting approach. It reminds me of the use of Geohash and Isocrones  in Doordash's search (see https://medium.com/@DoorDash/how-we-designed-road-distances-in-doordash-search-913ef8434099)

I've been working in ML Scoring within search (traditonal ML/Learning to Rank and recently Deep Learning), which has worked well in my previous lives and now at Groupon. See various presentation I have given on the topic since 2015:




Thanks!

-- J

On Fri, Mar 1, 2019 at 12:58 PM Pedram Rezaei <[hidden email]> wrote:

Thank you for sharing, and it is exciting to see how advanced your thinking is.

 

Yes, the idea is the same idea with an extra step that Rene also seems to elude to here in his comment. Instead of using these types of techniques only at the scoring time, we can use them for information retrieval from the index. This will allow us to, for example, index millions of images and quickly and efficiently lookup the most relevant images.

 

I would love to hear yours and others thoughts on this. I think there is a great opportunity here, but it would need a lot of input and guidance from the experts here.

 

Thank you,

 

Pedram

 

From: David Smiley <[hidden email]>
Sent: Friday, March 1, 2019 12:11 PM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>; René Kriegler <[hidden email]>
Subject: Re: Vector based store and ANN

 

This presentation by Rene Kriegler at Haystack 2018 was a real eye-opener to me on this subject: https://haystackconf.com/2018/relevance-scoring/. Uses random-projection forests which is a very clever technique.  (CC'ing Rene)

 

~ David

On Fri, Mar 1, 2019 at 1:30 PM Pedram Rezaei <[hidden email]> wrote:

Hi there,

 

Thank you for the responses. Yes, we have a few scenarios in mind that can benefit from a vector-based index optimized for ANN searches:

 

  • Advanced, optimized, and high precision visual search: For this to work, we would convert the images to their vector representations and then use algorithms and implementations such as SPTAG, FAISS, and HNSWLIB.
  • Advanced document retrieval: Using a numerical vector representation of a document, we could improve the search result
  • Nearest neighbor queries: discovering the nearest neighbors to a given query could also benefit from these ANN algorithms (although doesn’t necessarily need the vector based index)

 

I would be grateful to hear your thoughts and whether the community is open to a conversation on this topic with my team.

 

Thanks,

 

Pedram

 

From: J. Delgado <[hidden email]>
Sent: Thursday, February 28, 2019 7:38 AM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>
Subject: Re: Vector based store and ANN

 

Lucene’s scoring function (which I believe is okapi BM25  

https://en.m.wikipedia.org/wiki/Okapi_BM25) is a kind of nearest neighbor using the TF-IDF vector representation of documents and query. Are you interested in ANN to be applied to a different kind of vector representation, say for example Doc2Vec?

 

On Thu, Feb 28, 2019 at 5:59 AM Adrien Grand <[hidden email]> wrote:

Hi Pedram,

We don't have much in this area, but I'm hearing increasing interest
so it'd be nice to get better there! The closest that we have is this
class that can search for nearest neighbors for a vector of up to 8
dimensions: https://github.com/apache/lucene-solr/blob/master/lucene/sandbox/src/java/org/apache/lucene/document/FloatPointNearestNeighbor.java.

On Wed, Feb 27, 2019 at 1:44 AM Pedram Rezaei
<[hidden email]> wrote:


>
> Hi there,
>
>
>
> Is there a way to store numerical vectors (vector based index) and perform search based on Approximate Nearest Neighbor class of algorithms in Lucene?
>
>
>
> If not, has there been any interests in the topic so far?
>
>
>
> Thanks,
>
>
>
> Pedram



--
Adrien

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

--

Lucene/Solr Search Committer (PMC), Developer, Author, Speaker

Reply | Threaded
Open this post in threaded view
|

RE: Vector based store and ANN

Pedram Rezaei
In reply to this post by René Kriegler

Hi there,

 

Thank you for sharing your thoughts. I am finding them extremely useful and to be honest exciting!

 

Regarding the vector-based scoring, you are 100% correct. There are many ways of having an efficient vector-based similarity scorer implemented on top of an encoded vector stored at the document level in Lucene.

 

As you have rightly pointed out, this in itself might not be sufficient for large indexes. After all, the engine would need to read the vector per document and then calculate similarity.

 

LSH or similar n-pass (n>1) techniques are pretty interesting and certainly can get us closer to using the existing index for lookup. As you rightly point out below, it can come at a cost either to the performance or the precision.

 

I am personally very intrigued by the new generation of vector-based indexes such as Facebook’s FAISS library for similarity search and clustering of dense vectors used as part of larger search offerings. Do you think there might be a world in which Lucene would want to have first-class support for vector-based searches? I think with such a capability, we might open the door for new and innovative ways of information retrieval.

 

I am grateful to you all for your insights and this fascinating discussion!

 

Pedram

 

P.S. How do I join https://relevancy.slack.com?

 

From: René Kriegler <[hidden email]>
Sent: Friday, March 1, 2019 3:24 PM
To: Pedram Rezaei <[hidden email]>
Cc: [hidden email]; Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>
Subject: Re: Vector based store and ANN

 

Hi there,

 

Thank you for looping me in. Just a few random thoughts on this topic: 

 

- I’ve heard ;-) that this ES plugin is fast for vector-based scoring: https://github.com/StaySense/fast-cosine-similarity. The links in the ‘General’ section provide some history. As far as I can see, there is nothing which couldn’t be implemented at Lucene level.

 

- For retrieval, I think a two-pass approach looks like something worth trying out. First pass: look up documents in a low dimensional space (maybe produced via LSH) and then, in the second pass, calculate vector distances in the high-dimensional space just for the documents that resulted from the first pass. This solution will come with some compromises to make. For example, a higher dimensionality of LSH would increase precision but also produce more hash tokens and make the lookup slower, especially for large indexes.

 

- Day 2 of Haystack 2019 (https://haystackconf.com/agenda/) will have a talk by Simon Hughes about ’Search with Vectors’. There is a channel on this topic at OpenSource Connections’ search relevance Slack (https://relevancy.slack.com) and Simon has been one of the drivers of the discussion.

 

Best,

René

 



On 1 Mar 2019, at 20:51, Pedram Rezaei <[hidden email]> wrote:

 

Thank you for sharing, and it is exciting to see how advanced your thinking is.

 

Yes, the idea is the same idea with an extra step that Rene also seems to elude to here in his comment. Instead of using these types of techniques only at the scoring time, we can use them for information retrieval from the index. This will allow us to, for example, index millions of images and quickly and efficiently lookup the most relevant images.

 

I would love to hear yours and others thoughts on this. I think there is a great opportunity here, but it would need a lot of input and guidance from the experts here.

 

Thank you,

 

Pedram

 

From: David Smiley <[hidden email]> 
Sent: Friday, March 1, 2019 12:11 PM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>; René Kriegler <[hidden email]>
Subject: Re: Vector based store and ANN

 

This presentation by Rene Kriegler at Haystack 2018 was a real eye-opener to me on this subject: https://haystackconf.com/2018/relevance-scoring/. Uses random-projection forests which is a very clever technique.  (CC'ing Rene)

 

~ David

On Fri, Mar 1, 2019 at 1:30 PM Pedram Rezaei <[hidden email]> wrote:

Hi there,

 

Thank you for the responses. Yes, we have a few scenarios in mind that can benefit from a vector-based index optimized for ANN searches:

 

  • Advanced, optimized, and high precision visual search: For this to work, we would convert the images to their vector representations and then use algorithms and implementations such as SPTAG, FAISS, and HNSWLIB.
  • Advanced document retrieval: Using a numerical vector representation of a document, we could improve the search result
  • Nearest neighbor queries: discovering the nearest neighbors to a given query could also benefit from these ANN algorithms (although doesn’t necessarily need the vector based index)

 

I would be grateful to hear your thoughts and whether the community is open to a conversation on this topic with my team.

 

Thanks,

 

Pedram

 

From: J. Delgado <[hidden email]> 
Sent: Thursday, February 28, 2019 7:38 AM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>
Subject: Re: Vector based store and ANN

 

Lucene’s scoring function (which I believe is okapi BM25  

https://en.m.wikipedia.org/wiki/Okapi_BM25) is a kind of nearest neighbor using the TF-IDF vector representation of documents and query. Are you interested in ANN to be applied to a different kind of vector representation, say for example Doc2Vec?

 

On Thu, Feb 28, 2019 at 5:59 AM Adrien Grand <[hidden email]> wrote:

Hi Pedram,

We don't have much in this area, but I'm hearing increasing interest
so it'd be nice to get better there! The closest that we have is this
class that can search for nearest neighbors for a vector of up to 8
dimensions: https://github.com/apache/lucene-solr/blob/master/lucene/sandbox/src/java/org/apache/lucene/document/FloatPointNearestNeighbor.java.

On Wed, Feb 27, 2019 at 1:44 AM Pedram Rezaei
<[hidden email]> wrote:
>
> Hi there,
>
>
>
> Is there a way to store numerical vectors (vector based index) and perform search based on Approximate Nearest Neighbor class of algorithms in Lucene?
>
>
>
> If not, has there been any interests in the topic so far?
>
>
>
> Thanks,
>
>
>
> Pedram



-- 
Adrien

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

-- 

Lucene/Solr Search Committer (PMC), Developer, Author, Speaker

 

Reply | Threaded
Open this post in threaded view
|

Re: Vector based store and ANN

J. Delgado

On Fri, Mar 1, 2019 at 4:23 PM Pedram Rezaei <[hidden email]> wrote:

Hi there,

 

Thank you for sharing your thoughts. I am finding them extremely useful and to be honest exciting!

 

Regarding the vector-based scoring, you are 100% correct. There are many ways of having an efficient vector-based similarity scorer implemented on top of an encoded vector stored at the document level in Lucene.

 

As you have rightly pointed out, this in itself might not be sufficient for large indexes. After all, the engine would need to read the vector per document and then calculate similarity.

 

LSH or similar n-pass (n>1) techniques are pretty interesting and certainly can get us closer to using the existing index for lookup. As you rightly point out below, it can come at a cost either to the performance or the precision.

 

I am personally very intrigued by the new generation of vector-based indexes such as Facebook’s FAISS library for similarity search and clustering of dense vectors used as part of larger search offerings. Do you think there might be a world in which Lucene would want to have first-class support for vector-based searches? I think with such a capability, we might open the door for new and innovative ways of information retrieval.

 

I am grateful to you all for your insights and this fascinating discussion!

 

Pedram

 

P.S. How do I join https://relevancy.slack.com?

 

From: René Kriegler <[hidden email]>
Sent: Friday, March 1, 2019 3:24 PM
To: Pedram Rezaei <[hidden email]>
Cc: [hidden email]; Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>
Subject: Re: Vector based store and ANN

 

Hi there,

 

Thank you for looping me in. Just a few random thoughts on this topic: 

 

- I’ve heard ;-) that this ES plugin is fast for vector-based scoring: https://github.com/StaySense/fast-cosine-similarity. The links in the ‘General’ section provide some history. As far as I can see, there is nothing which couldn’t be implemented at Lucene level.

 

- For retrieval, I think a two-pass approach looks like something worth trying out. First pass: look up documents in a low dimensional space (maybe produced via LSH) and then, in the second pass, calculate vector distances in the high-dimensional space just for the documents that resulted from the first pass. This solution will come with some compromises to make. For example, a higher dimensionality of LSH would increase precision but also produce more hash tokens and make the lookup slower, especially for large indexes.

 

- Day 2 of Haystack 2019 (https://haystackconf.com/agenda/) will have a talk by Simon Hughes about ’Search with Vectors’. There is a channel on this topic at OpenSource Connections’ search relevance Slack (https://relevancy.slack.com) and Simon has been one of the drivers of the discussion.

 

Best,

René

 



On 1 Mar 2019, at 20:51, Pedram Rezaei <[hidden email]> wrote:

 

Thank you for sharing, and it is exciting to see how advanced your thinking is.

 

Yes, the idea is the same idea with an extra step that Rene also seems to elude to here in his comment. Instead of using these types of techniques only at the scoring time, we can use them for information retrieval from the index. This will allow us to, for example, index millions of images and quickly and efficiently lookup the most relevant images.

 

I would love to hear yours and others thoughts on this. I think there is a great opportunity here, but it would need a lot of input and guidance from the experts here.

 

Thank you,

 

Pedram

 

From: David Smiley <[hidden email]> 
Sent: Friday, March 1, 2019 12:11 PM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>; René Kriegler <[hidden email]>
Subject: Re: Vector based store and ANN

 

This presentation by Rene Kriegler at Haystack 2018 was a real eye-opener to me on this subject: https://haystackconf.com/2018/relevance-scoring/. Uses random-projection forests which is a very clever technique.  (CC'ing Rene)

 

~ David

On Fri, Mar 1, 2019 at 1:30 PM Pedram Rezaei <[hidden email]> wrote:

Hi there,

 

Thank you for the responses. Yes, we have a few scenarios in mind that can benefit from a vector-based index optimized for ANN searches:

 

  • Advanced, optimized, and high precision visual search: For this to work, we would convert the images to their vector representations and then use algorithms and implementations such as SPTAG, FAISS, and HNSWLIB.
  • Advanced document retrieval: Using a numerical vector representation of a document, we could improve the search result
  • Nearest neighbor queries: discovering the nearest neighbors to a given query could also benefit from these ANN algorithms (although doesn’t necessarily need the vector based index)

 

I would be grateful to hear your thoughts and whether the community is open to a conversation on this topic with my team.

 

Thanks,

 

Pedram

 

From: J. Delgado <[hidden email]> 
Sent: Thursday, February 28, 2019 7:38 AM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>
Subject: Re: Vector based store and ANN

 

Lucene’s scoring function (which I believe is okapi BM25  

https://en.m.wikipedia.org/wiki/Okapi_BM25) is a kind of nearest neighbor using the TF-IDF vector representation of documents and query. Are you interested in ANN to be applied to a different kind of vector representation, say for example Doc2Vec?

 

On Thu, Feb 28, 2019 at 5:59 AM Adrien Grand <[hidden email]> wrote:

Hi Pedram,

We don't have much in this area, but I'm hearing increasing interest
so it'd be nice to get better there! The closest that we have is this
class that can search for nearest neighbors for a vector of up to 8
dimensions: https://github.com/apache/lucene-solr/blob/master/lucene/sandbox/src/java/org/apache/lucene/document/FloatPointNearestNeighbor.java.

On Wed, Feb 27, 2019 at 1:44 AM Pedram Rezaei
<[hidden email]> wrote:
>
> Hi there,
>
>
>
> Is there a way to store numerical vectors (vector based index) and perform search based on Approximate Nearest Neighbor class of algorithms in Lucene?
>
>
>
> If not, has there been any interests in the topic so far?
>
>
>
> Thanks,
>
>
>
> Pedram



-- 
Adrien

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

-- 

Lucene/Solr Search Committer (PMC), Developer, Author, Speaker

 

Reply | Threaded
Open this post in threaded view
|

Re: Vector based store and ANN

René Kriegler
Thanks for the links, Joaquin!

Yet another thought related to an implementation at Lucene level: I wonder how much sense it makes to try to implement a one-approach-fits-all solution for vector-based retrieval. We have different expectations of a solution, depending on aspects such as vector dimensionality, domain (text vs. image recognition vs. …) and retrieval quality priorities (recall vs precision). I think that was also reflected in the Slack discussion. I think it would be very helpful to have real-life vector datasets (labelled for specific retrieval tasks), so that we could benchmarks solutions for retrieval speed and quality metrics. For example, we could easily create synthetic vector datasets for KNN search (which is still a good starting point!) - but using random vectors probably doesn’t reflect the distribution we would normally face in an image search or when searching by word embeddings.

Best,
René


On 2 Mar 2019, at 22:06, J. Delgado <[hidden email]> wrote:


On Fri, Mar 1, 2019 at 4:23 PM Pedram Rezaei <[hidden email]> wrote:

Hi there,

 

Thank you for sharing your thoughts. I am finding them extremely useful and to be honest exciting!

 

Regarding the vector-based scoring, you are 100% correct. There are many ways of having an efficient vector-based similarity scorer implemented on top of an encoded vector stored at the document level in Lucene.

 

As you have rightly pointed out, this in itself might not be sufficient for large indexes. After all, the engine would need to read the vector per document and then calculate similarity.

 

LSH or similar n-pass (n>1) techniques are pretty interesting and certainly can get us closer to using the existing index for lookup. As you rightly point out below, it can come at a cost either to the performance or the precision.

 

I am personally very intrigued by the new generation of vector-based indexes such as Facebook’s FAISS library for similarity search and clustering of dense vectors used as part of larger search offerings. Do you think there might be a world in which Lucene would want to have first-class support for vector-based searches? I think with such a capability, we might open the door for new and innovative ways of information retrieval.

 

I am grateful to you all for your insights and this fascinating discussion!

 

Pedram

 

P.S. How do I join https://relevancy.slack.com?

 

From: René Kriegler <[hidden email]>
Sent: Friday, March 1, 2019 3:24 PM
To: Pedram Rezaei <[hidden email]>
Cc: [hidden email]; Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>
Subject: Re: Vector based store and ANN

 

Hi there,

 

Thank you for looping me in. Just a few random thoughts on this topic: 

 

- I’ve heard ;-) that this ES plugin is fast for vector-based scoring: https://github.com/StaySense/fast-cosine-similarity. The links in the ‘General’ section provide some history. As far as I can see, there is nothing which couldn’t be implemented at Lucene level.

 

- For retrieval, I think a two-pass approach looks like something worth trying out. First pass: look up documents in a low dimensional space (maybe produced via LSH) and then, in the second pass, calculate vector distances in the high-dimensional space just for the documents that resulted from the first pass. This solution will come with some compromises to make. For example, a higher dimensionality of LSH would increase precision but also produce more hash tokens and make the lookup slower, especially for large indexes.

 

- Day 2 of Haystack 2019 (https://haystackconf.com/agenda/) will have a talk by Simon Hughes about ’Search with Vectors’. There is a channel on this topic at OpenSource Connections’ search relevance Slack (https://relevancy.slack.com) and Simon has been one of the drivers of the discussion.

 

Best,

René

 



On 1 Mar 2019, at 20:51, Pedram Rezaei <[hidden email]> wrote:

 

Thank you for sharing, and it is exciting to see how advanced your thinking is.

 

Yes, the idea is the same idea with an extra step that Rene also seems to elude to here in his comment. Instead of using these types of techniques only at the scoring time, we can use them for information retrieval from the index. This will allow us to, for example, index millions of images and quickly and efficiently lookup the most relevant images.

 

I would love to hear yours and others thoughts on this. I think there is a great opportunity here, but it would need a lot of input and guidance from the experts here.

 

Thank you,

 

Pedram

 

From: David Smiley <[hidden email]> 
Sent: Friday, March 1, 2019 12:11 PM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>; René Kriegler <[hidden email]>
Subject: Re: Vector based store and ANN

 

This presentation by Rene Kriegler at Haystack 2018 was a real eye-opener to me on this subject: https://haystackconf.com/2018/relevance-scoring/. Uses random-projection forests which is a very clever technique.  (CC'ing Rene)

 

~ David

On Fri, Mar 1, 2019 at 1:30 PM Pedram Rezaei <[hidden email]> wrote:

Hi there,

 

Thank you for the responses. Yes, we have a few scenarios in mind that can benefit from a vector-based index optimized for ANN searches:

 

  • Advanced, optimized, and high precision visual search: For this to work, we would convert the images to their vector representations and then use algorithms and implementations such as SPTAG, FAISS, and HNSWLIB.
  • Advanced document retrieval: Using a numerical vector representation of a document, we could improve the search result
  • Nearest neighbor queries: discovering the nearest neighbors to a given query could also benefit from these ANN algorithms (although doesn’t necessarily need the vector based index)

 

I would be grateful to hear your thoughts and whether the community is open to a conversation on this topic with my team.

 

Thanks,

 

Pedram

 

From: J. Delgado <[hidden email]> 
Sent: Thursday, February 28, 2019 7:38 AM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>
Subject: Re: Vector based store and ANN

 

Lucene’s scoring function (which I believe is okapi BM25  

https://en.m.wikipedia.org/wiki/Okapi_BM25) is a kind of nearest neighbor using the TF-IDF vector representation of documents and query. Are you interested in ANN to be applied to a different kind of vector representation, say for example Doc2Vec?

 

On Thu, Feb 28, 2019 at 5:59 AM Adrien Grand <[hidden email]> wrote:

Hi Pedram,

We don't have much in this area, but I'm hearing increasing interest
so it'd be nice to get better there! The closest that we have is this
class that can search for nearest neighbors for a vector of up to 8
dimensions: https://github.com/apache/lucene-solr/blob/master/lucene/sandbox/src/java/org/apache/lucene/document/FloatPointNearestNeighbor.java.

On Wed, Feb 27, 2019 at 1:44 AM Pedram Rezaei
<[hidden email]> wrote:
>
> Hi there,
>
>
>
> Is there a way to store numerical vectors (vector based index) and perform search based on Approximate Nearest Neighbor class of algorithms in Lucene?
>
>
>
> If not, has there been any interests in the topic so far?
>
>
>
> Thanks,
>
>
>
> Pedram



-- 
Adrien

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

-- 

Lucene/Solr Search Committer (PMC), Developer, Author, Speaker

 


Reply | Threaded
Open this post in threaded view
|

Re: Vector based store and ANN

Doug Turnbull
In reply to this post by Pedram Rezaei
Hi Pedram (and community)

The invite link for Relevance slack is http://o19s.com/slack ... 

Best!
-Doug

On Fri, Mar 1, 2019 at 7:23 PM Pedram Rezaei <[hidden email]> wrote:

Hi there,

 

Thank you for sharing your thoughts. I am finding them extremely useful and to be honest exciting!

 

Regarding the vector-based scoring, you are 100% correct. There are many ways of having an efficient vector-based similarity scorer implemented on top of an encoded vector stored at the document level in Lucene.

 

As you have rightly pointed out, this in itself might not be sufficient for large indexes. After all, the engine would need to read the vector per document and then calculate similarity.

 

LSH or similar n-pass (n>1) techniques are pretty interesting and certainly can get us closer to using the existing index for lookup. As you rightly point out below, it can come at a cost either to the performance or the precision.

 

I am personally very intrigued by the new generation of vector-based indexes such as Facebook’s FAISS library for similarity search and clustering of dense vectors used as part of larger search offerings. Do you think there might be a world in which Lucene would want to have first-class support for vector-based searches? I think with such a capability, we might open the door for new and innovative ways of information retrieval.

 

I am grateful to you all for your insights and this fascinating discussion!

 

Pedram

 

P.S. How do I join https://relevancy.slack.com?

 

From: René Kriegler <[hidden email]>
Sent: Friday, March 1, 2019 3:24 PM
To: Pedram Rezaei <[hidden email]>
Cc: [hidden email]; Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>
Subject: Re: Vector based store and ANN

 

Hi there,

 

Thank you for looping me in. Just a few random thoughts on this topic: 

 

- I’ve heard ;-) that this ES plugin is fast for vector-based scoring: https://github.com/StaySense/fast-cosine-similarity. The links in the ‘General’ section provide some history. As far as I can see, there is nothing which couldn’t be implemented at Lucene level.

 

- For retrieval, I think a two-pass approach looks like something worth trying out. First pass: look up documents in a low dimensional space (maybe produced via LSH) and then, in the second pass, calculate vector distances in the high-dimensional space just for the documents that resulted from the first pass. This solution will come with some compromises to make. For example, a higher dimensionality of LSH would increase precision but also produce more hash tokens and make the lookup slower, especially for large indexes.

 

- Day 2 of Haystack 2019 (https://haystackconf.com/agenda/) will have a talk by Simon Hughes about ’Search with Vectors’. There is a channel on this topic at OpenSource Connections’ search relevance Slack (https://relevancy.slack.com) and Simon has been one of the drivers of the discussion.

 

Best,

René

 



On 1 Mar 2019, at 20:51, Pedram Rezaei <[hidden email]> wrote:

 

Thank you for sharing, and it is exciting to see how advanced your thinking is.

 

Yes, the idea is the same idea with an extra step that Rene also seems to elude to here in his comment. Instead of using these types of techniques only at the scoring time, we can use them for information retrieval from the index. This will allow us to, for example, index millions of images and quickly and efficiently lookup the most relevant images.

 

I would love to hear yours and others thoughts on this. I think there is a great opportunity here, but it would need a lot of input and guidance from the experts here.

 

Thank you,

 

Pedram

 

From: David Smiley <[hidden email]> 
Sent: Friday, March 1, 2019 12:11 PM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>; René Kriegler <[hidden email]>
Subject: Re: Vector based store and ANN

 

This presentation by Rene Kriegler at Haystack 2018 was a real eye-opener to me on this subject: https://haystackconf.com/2018/relevance-scoring/. Uses random-projection forests which is a very clever technique.  (CC'ing Rene)

 

~ David

On Fri, Mar 1, 2019 at 1:30 PM Pedram Rezaei <[hidden email]> wrote:

Hi there,

 

Thank you for the responses. Yes, we have a few scenarios in mind that can benefit from a vector-based index optimized for ANN searches:

 

  • Advanced, optimized, and high precision visual search: For this to work, we would convert the images to their vector representations and then use algorithms and implementations such as SPTAG, FAISS, and HNSWLIB.
  • Advanced document retrieval: Using a numerical vector representation of a document, we could improve the search result
  • Nearest neighbor queries: discovering the nearest neighbors to a given query could also benefit from these ANN algorithms (although doesn’t necessarily need the vector based index)

 

I would be grateful to hear your thoughts and whether the community is open to a conversation on this topic with my team.

 

Thanks,

 

Pedram

 

From: J. Delgado <[hidden email]> 
Sent: Thursday, February 28, 2019 7:38 AM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>
Subject: Re: Vector based store and ANN

 

Lucene’s scoring function (which I believe is okapi BM25  

https://en.m.wikipedia.org/wiki/Okapi_BM25) is a kind of nearest neighbor using the TF-IDF vector representation of documents and query. Are you interested in ANN to be applied to a different kind of vector representation, say for example Doc2Vec?

 

On Thu, Feb 28, 2019 at 5:59 AM Adrien Grand <[hidden email]> wrote:

Hi Pedram,

We don't have much in this area, but I'm hearing increasing interest
so it'd be nice to get better there! The closest that we have is this
class that can search for nearest neighbors for a vector of up to 8
dimensions: https://github.com/apache/lucene-solr/blob/master/lucene/sandbox/src/java/org/apache/lucene/document/FloatPointNearestNeighbor.java.

On Wed, Feb 27, 2019 at 1:44 AM Pedram Rezaei
<[hidden email]> wrote:
>
> Hi there,
>
>
>
> Is there a way to store numerical vectors (vector based index) and perform search based on Approximate Nearest Neighbor class of algorithms in Lucene?
>
>
>
> If not, has there been any interests in the topic so far?
>
>
>
> Thanks,
>
>
>
> Pedram



-- 
Adrien

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

-- 

Lucene/Solr Search Committer (PMC), Developer, Author, Speaker

 



--
Doug Turnbull | CTO | OpenSource Connections, LLC | 240.476.9983 
Author: Relevant Search
This e-mail and all contents, including attachments, is considered to be Company Confidential unless explicitly stated otherwise, regardless of whether attachments are marked as such.
Reply | Threaded
Open this post in threaded view
|

Re: Vector based store and ANN

Doug Turnbull
In reply to this post by René Kriegler
I'll add that Elasticsearch has a vector scoring (though not filtering/matching) coming in to Elasticsearch mainline by Mayya Sharipova 


It uses doc values to do some reranking using standard similarities. It's a start, hopefully something that can be built upon

Hoping Mayya can be at Haystack... vector filtering/similarities/use cases could even be its own breakout/collaboration session

On Fri, Mar 1, 2019 at 8:59 PM René Kriegler <[hidden email]> wrote:
Hi there,

Thank you for looping me in. Just a few random thoughts on this topic: 

- I’ve heard ;-) that this ES plugin is fast for vector-based scoring: https://github.com/StaySense/fast-cosine-similarity. The links in the ‘General’ section provide some history. As far as I can see, there is nothing which couldn’t be implemented at Lucene level.

- For retrieval, I think a two-pass approach looks like something worth trying out. First pass: look up documents in a low dimensional space (maybe produced via LSH) and then, in the second pass, calculate vector distances in the high-dimensional space just for the documents that resulted from the first pass. This solution will come with some compromises to make. For example, a higher dimensionality of LSH would increase precision but also produce more hash tokens and make the lookup slower, especially for large indexes.

- Day 2 of Haystack 2019 (https://haystackconf.com/agenda/) will have a talk by Simon Hughes about ’Search with Vectors’. There is a channel on this topic at OpenSource Connections’ search relevance Slack (https://relevancy.slack.com) and Simon has been one of the drivers of the discussion.

Best,
René


On 1 Mar 2019, at 20:51, Pedram Rezaei <[hidden email]> wrote:

Thank you for sharing, and it is exciting to see how advanced your thinking is.
 
Yes, the idea is the same idea with an extra step that Rene also seems to elude to here in his comment. Instead of using these types of techniques only at the scoring time, we can use them for information retrieval from the index. This will allow us to, for example, index millions of images and quickly and efficiently lookup the most relevant images.
 
I would love to hear yours and others thoughts on this. I think there is a great opportunity here, but it would need a lot of input and guidance from the experts here.
 
Thank you,
 
Pedram
 
From: David Smiley <[hidden email]> 
Sent: Friday, March 1, 2019 12:11 PM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>; René Kriegler <[hidden email]>
Subject: Re: Vector based store and ANN
 
This presentation by Rene Kriegler at Haystack 2018 was a real eye-opener to me on this subject: https://haystackconf.com/2018/relevance-scoring/. Uses random-projection forests which is a very clever technique.  (CC'ing Rene)
 

~ David

On Fri, Mar 1, 2019 at 1:30 PM Pedram Rezaei <[hidden email]> wrote:
Hi there,
 
Thank you for the responses. Yes, we have a few scenarios in mind that can benefit from a vector-based index optimized for ANN searches:
 
  • Advanced, optimized, and high precision visual search: For this to work, we would convert the images to their vector representations and then use algorithms and implementations such as SPTAG, FAISS, and HNSWLIB.
  • Advanced document retrieval: Using a numerical vector representation of a document, we could improve the search result
  • Nearest neighbor queries: discovering the nearest neighbors to a given query could also benefit from these ANN algorithms (although doesn’t necessarily need the vector based index)
 
I would be grateful to hear your thoughts and whether the community is open to a conversation on this topic with my team.
 
Thanks,
 
Pedram
 
From: J. Delgado <[hidden email]> 
Sent: Thursday, February 28, 2019 7:38 AM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>
Subject: Re: Vector based store and ANN
 
Lucene’s scoring function (which I believe is okapi BM25  
https://en.m.wikipedia.org/wiki/Okapi_BM25) is a kind of nearest neighbor using the TF-IDF vector representation of documents and query. Are you interested in ANN to be applied to a different kind of vector representation, say for example Doc2Vec?
 
On Thu, Feb 28, 2019 at 5:59 AM Adrien Grand <[hidden email]> wrote:

Hi Pedram,

We don't have much in this area, but I'm hearing increasing interest
so it'd be nice to get better there! The closest that we have is this
class that can search for nearest neighbors for a vector of up to 8
dimensions: https://github.com/apache/lucene-solr/blob/master/lucene/sandbox/src/java/org/apache/lucene/document/FloatPointNearestNeighbor.java.

On Wed, Feb 27, 2019 at 1:44 AM Pedram Rezaei
<[hidden email]> wrote:


>
> Hi there,
>
>
>
> Is there a way to store numerical vectors (vector based index) and perform search based on Approximate Nearest Neighbor class of algorithms in Lucene?
>
>
>
> If not, has there been any interests in the topic so far?
>
>
>
> Thanks,
>
>
>
> Pedram



-- 
Adrien

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

-- 
Lucene/Solr Search Committer (PMC), Developer, Author, Speaker



--
Doug Turnbull | CTO | OpenSource Connections, LLC | 240.476.9983 
Author: Relevant Search
This e-mail and all contents, including attachments, is considered to be Company Confidential unless explicitly stated otherwise, regardless of whether attachments are marked as such.
Reply | Threaded
Open this post in threaded view
|

RE: Vector based store and ANN

Pedram Rezaei
In reply to this post by Pedram Rezaei

Merging the threads and pasting all the replies into here and responding to them below:

 

Thank you all for your detailed and thoughtful contributions.

 

Here at Bing, we used to use the coarse approximation nearest neighbor approach (using something similar to the LSH hashing technique) on the inverted index and a finer-grained final rescoring method. However, for Bing, we have seen a visible impact on relevance using ANN. This even applies to smaller indexes with 20M records. We also find that recall varies on LSH on our interested dataset. Hence we adopted KD-tree & RNG which has more stable recall. The algorithm is open sourced here. We have also seen success with HNSW and FAISS.

 

The links provided by Doug and J. are attempting to add vectors to the existing index. These solutions typically inefficient on medium to large size indexes if used for online querying as they tend to behave more like a linear search. The author of EsAknn has also alluded to this on its github page:

 

“If you need to quickly run KNN on an extremely large corpus in an offline job, use one of the libraries from Ann-Benchmarks. If you need KNN in an online setting with support for horizontally-scalable searching and indexing new vectors in near-real-time, consider EsAknn (especially if you already use Elasticsearch).”

 

Using a vector-based index tuned for ANN searches, with an ability to hook in other index formats and algorithms as Rene requested below, we can provide a solution that can, for example, index and serve hundreds of millions of images and offers fast query over those indexes. We use these algorithms and indexes that are referenced above for image and text search. The user can choose the most relevant one or even combine multiple of those before the final scoring.

 

I would love to hear your thoughts on this and see if the community is open to a proposal by Bing on contributing some of its tech to Lucene. We will run the design and the development incrementally with the full input from the community.

 

Thanks,

 

Pedram

 

From: Doug Turnbull <[hidden email]>
Sent: Saturday, March 2, 2019 3:50 PM
To: [hidden email]
Cc: Pedram Rezaei <[hidden email]>; Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>
Subject: Re: Vector based store and ANN

 

I'll add that Elasticsearch has a vector scoring (though not filtering/matching) coming in to Elasticsearch mainline by Mayya Sharipova 

 

https://github.com/elastic/elasticsearch/pull/33022

 

It uses doc values to do some reranking using standard similarities. It's a start, hopefully something that can be built upon

 

Hoping Mayya can be at Haystack... vector filtering/similarities/use cases could even be its own breakout/collaboration session

 

From: René Kriegler <[hidden email]>
Sent: Saturday, March 2, 2019 3:23 PM
To: J. Delgado <[hidden email]>
Cc: [hidden email]; Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>
Subject: Re: Vector based store and ANN

 

Thanks for the links, Joaquin!

 

Yet another thought related to an implementation at Lucene level: I wonder how much sense it makes to try to implement a one-approach-fits-all solution for vector-based retrieval. We have different expectations of a solution, depending on aspects such as vector dimensionality, domain (text vs. image recognition vs. …) and retrieval quality priorities (recall vs precision). I think that was also reflected in the Slack discussion. I think it would be very helpful to have real-life vector datasets (labelled for specific retrieval tasks), so that we could benchmarks solutions for retrieval speed and quality metrics. For example, we could easily create synthetic vector datasets for KNN search (which is still a good starting point!) - but using random vectors probably doesn’t reflect the distribution we would normally face in an image search or when searching by word embeddings.

 

Best,

René

 

On 2 Mar 2019, at 22:06, J. Delgado <[hidden email]> wrote:

 

Apparently, there is already an implementation along the lines discussed here:

 

https://blog.insightdatascience.com/elastik-nearest-neighbors-4b1f6821bd62

https://github.com/alexklibisz/elastik-nearest-neighbors/

 

From: J. Delgado <[hidden email]>
Sent: Friday, March 1, 2019 3:26 PM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>; René Kriegler <[hidden email]>
Subject: Re: Vector based store and ANN

 

Traditional search engines work both as a retrieval engine, with the support of arbitrarily complex BOOLEAN queries and a scoring engine that performs vector-based similarity computations. It works very well for words (terms) because of the clever inverted index and posting list data structures, used to represent a very sparse matrix that associate terms/weights with documents.  I'm not so sure if these core properties of a search engine can be generalized to performing the selection with an ANN algorithm such as LSH and then do a more sophisticated scoring function. Notice that doing nearest neighbor inherently doing a top-k selection.  As stated in Rene's presentation it can work with mages recognition vectors (embeddings) by implementing Random Projection Forest and indexing random projections and defining hyperplanes instead of the full high-dimensional vector, which is an interesting approach. It reminds me of the use of Geohash and Isocrones  in Doordash's search (see https://medium.com/@DoorDash/how-we-designed-road-distances-in-doordash-search-913ef8434099)

 

I've been working in ML Scoring within search (traditonal ML/Learning to Rank and recently Deep Learning), which has worked well in my previous lives and now at Groupon. See various presentation I have given on the topic since 2015:

 

https://www.youtube.com/watch?v=x-tLA8eZs1k

https://www.slideshare.net/SDianaHu/recsys-2015-tutorial-scalable-recommender-systems-where-machine-learning-meets-search

https://www.slideshare.net/bojanbabic/deep-learning-application-within-search-and-ranking-at-groupon

 

 

 

Thanks!

 

-- J

 

From: Pedram Rezaei <[hidden email]>
Sent: Friday, March 1, 2019 4:23 PM
To: René Kriegler <[hidden email]>; [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>
Subject: RE: Vector based store and ANN

 

Hi there,

 

Thank you for sharing your thoughts. I am finding them extremely useful and to be honest exciting!

 

Regarding the vector-based scoring, you are 100% correct. There are many ways of having an efficient vector-based similarity scorer implemented on top of an encoded vector stored at the document level in Lucene.

 

As you have rightly pointed out, this in itself might not be sufficient for large indexes. After all, the engine would need to read the vector per document and then calculate similarity.

 

LSH or similar n-pass (n>1) techniques are pretty interesting and certainly can get us closer to using the existing index for lookup. As you rightly point out below, it can come at a cost either to the performance or the precision.

 

I am personally very intrigued by the new generation of vector-based indexes such as Facebook’s FAISS library for similarity search and clustering of dense vectors used as part of larger search offerings. Do you think there might be a world in which Lucene would want to have first-class support for vector-based searches? I think with such a capability, we might open the door for new and innovative ways of information retrieval.

 

I am grateful to you all for your insights and this fascinating discussion!

 

Pedram

 

P.S. How do I join https://relevancy.slack.com?

 

From: René Kriegler <[hidden email]>
Sent: Friday, March 1, 2019 3:24 PM
To: Pedram Rezaei <[hidden email]>
Cc: [hidden email]; Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>
Subject: Re: Vector based store and ANN

 

Hi there,

 

Thank you for looping me in. Just a few random thoughts on this topic: 

 

- I’ve heard ;-) that this ES plugin is fast for vector-based scoring: https://github.com/StaySense/fast-cosine-similarity. The links in the ‘General’ section provide some history. As far as I can see, there is nothing which couldn’t be implemented at Lucene level.

 

- For retrieval, I think a two-pass approach looks like something worth trying out. First pass: look up documents in a low dimensional space (maybe produced via LSH) and then, in the second pass, calculate vector distances in the high-dimensional space just for the documents that resulted from the first pass. This solution will come with some compromises to make. For example, a higher dimensionality of LSH would increase precision but also produce more hash tokens and make the lookup slower, especially for large indexes.

 

- Day 2 of Haystack 2019 (https://haystackconf.com/agenda/) will have a talk by Simon Hughes about ’Search with Vectors’. There is a channel on this topic at OpenSource Connections’ search relevance Slack (https://relevancy.slack.com) and Simon has been one of the drivers of the discussion.

 

Best,

René

 

 

On 1 Mar 2019, at 20:51, Pedram Rezaei <[hidden email]> wrote:

 

Thank you for sharing, and it is exciting to see how advanced your thinking is.

 

Yes, the idea is the same idea with an extra step that Rene also seems to elude to here in his comment. Instead of using these types of techniques only at the scoring time, we can use them for information retrieval from the index. This will allow us to, for example, index millions of images and quickly and efficiently lookup the most relevant images.

 

I would love to hear yours and others thoughts on this. I think there is a great opportunity here, but it would need a lot of input and guidance from the experts here.

 

Thank you,

 

Pedram

 

From: David Smiley <[hidden email]> 
Sent: Friday, March 1, 2019 12:11 PM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>; Arun Sacheti <[hidden email]>; Kun Wu <[hidden email]>; Junhua Wang <[hidden email]>; Jason Li <[hidden email]>; René Kriegler <[hidden email]>
Subject: Re: Vector based store and ANN

 

This presentation by Rene Kriegler at Haystack 2018 was a real eye-opener to me on this subject: https://haystackconf.com/2018/relevance-scoring/. Uses random-projection forests which is a very clever technique.  (CC'ing Rene)

 

~ David

On Fri, Mar 1, 2019 at 1:30 PM Pedram Rezaei <[hidden email]> wrote:

Hi there,

 

Thank you for the responses. Yes, we have a few scenarios in mind that can benefit from a vector-based index optimized for ANN searches:

 

  • Advanced, optimized, and high precision visual search: For this to work, we would convert the images to their vector representations and then use algorithms and implementations such as SPTAG, FAISS, and HNSWLIB.
  • Advanced document retrieval: Using a numerical vector representation of a document, we could improve the search result
  • Nearest neighbor queries: discovering the nearest neighbors to a given query could also benefit from these ANN algorithms (although doesn’t necessarily need the vector based index)

 

I would be grateful to hear your thoughts and whether the community is open to a conversation on this topic with my team.

 

Thanks,

 

Pedram

 

From: J. Delgado <[hidden email]> 
Sent: Thursday, February 28, 2019 7:38 AM
To: [hidden email]
Cc: Radhakrishnan Srikanth (SRIKANTH) <[hidden email]>
Subject: Re: Vector based store and ANN

 

Lucene’s scoring function (which I believe is okapi BM25  

https://en.m.wikipedia.org/wiki/Okapi_BM25) is a kind of nearest neighbor using the TF-IDF vector representation of documents and query. Are you interested in ANN to be applied to a different kind of vector representation, say for example Doc2Vec?

 

On Thu, Feb 28, 2019 at 5:59 AM Adrien Grand <[hidden email]> wrote:

Hi Pedram,

We don't have much in this area, but I'm hearing increasing interest
so it'd be nice to get better there! The closest that we have is this
class that can search for nearest neighbors for a vector of up to 8
dimensions: https://github.com/apache/lucene-solr/blob/master/lucene/sandbox/src/java/org/apache/lucene/document/FloatPointNearestNeighbor.java.

On Wed, Feb 27, 2019 at 1:44 AM Pedram Rezaei
<[hidden email]> wrote:
>
> Hi there,
>
>
>
> Is there a way to store numerical vectors (vector based index) and perform search based on Approximate Nearest Neighbor class of algorithms in Lucene?
>
>
>
> If not, has there been any interests in the topic so far?
>
>
>
> Thanks,
>
>
>
> Pedram



-- 
Adrien

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

-- 

Lucene/Solr Search Committer (PMC), Developer, Author, Speaker