Mailing List Archive: Need for multiple entry points in HnswGraphSearcher?

Need for multiple entry points in HnswGraphSearcher?

Feb 19, 2022, 6:58 AM

Post #1 of 3 (291 views)

Hi folks-

I've been poking around some of the HNSW code out of curiosity and I
noticed that the HnswGraphSearcher#searchLevel methods accept an array
of entry point nodes (int[] eps), but as far as I can tell, only one
entry point is every provided (from both HnswGraphSearcher and
HnswGraphBuilder). Is there actually a use-case for executing a search
using multiple entry points? I ask purely out of curiosity and trying
to build up my own understanding in this space.

I tried searching the dev list and Jira issues for anywhere this might
have been discussed and came up empty, but apologies if there's a
thread about this somewhere I missed.

Cheers,
-Greg

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org

Re: Need for multiple entry points in HnswGraphSearcher? [ In reply to ]

mayya.sharipova at elastic

Feb 21, 2022, 1:19 AM

Post #2 of 3 (291 views)

Permalink

Hello Greg,
This code is a close implementation of the original HNSW paper
<https://arxiv.org/abs/1603.09320>.

Multiple entry points in HnswGraphSearcher are used during a graph
construction in HnswGraphBuilder for levels <= nodeLevel.
In this case the number of entry points is equal to beamWidth.
Closest neighbors found the previous layer are used as entry points for the
current layer.

I hope this answers your question.

On Sat, Feb 19, 2022 at 3:59 PM Greg Miller <gsmiller@gmail.com> wrote:

> Hi folks-
>
> I've been poking around some of the HNSW code out of curiosity and I
> noticed that the HnswGraphSearcher#searchLevel methods accept an array
> of entry point nodes (int[] eps), but as far as I can tell, only one
> entry point is every provided (from both HnswGraphSearcher and
> HnswGraphBuilder). Is there actually a use-case for executing a search
> using multiple entry points? I ask purely out of curiosity and trying
> to build up my own understanding in this space.
>
> I tried searching the dev list and Jira issues for anywhere this might
> have been discussed and came up empty, but apologies if there's a
> thread about this somewhere I missed.
>
> Cheers,
> -Greg
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: dev-help@lucene.apache.org
>
>

Re: Need for multiple entry points in HnswGraphSearcher? [ In reply to ]

gsmiller at gmail

Feb 21, 2022, 6:30 AM

Post #3 of 3 (291 views)

Permalink

Ah, thanks Mayya. I'd overlooked this one line of code:
https://github.com/apache/lucene/blob/main/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java#L160

That makes sense. Thanks again for the explanation!

Cheers,
-Greg

On Mon, Feb 21, 2022 at 1:19 AM Mayya Sharipova
<mayya.sharipova@elastic.co.invalid> wrote:
>
> Hello Greg,
> This code is a close implementation of the original HNSW paper.
>
> Multiple entry points in HnswGraphSearcher are used during a graph construction in HnswGraphBuilder for levels <= nodeLevel.
> In this case the number of entry points is equal to beamWidth.
> Closest neighbors found the previous layer are used as entry points for the current layer.
>
> I hope this answers your question.
>
>
>
> On Sat, Feb 19, 2022 at 3:59 PM Greg Miller <gsmiller@gmail.com> wrote:
>>
>> Hi folks-
>>
>> I've been poking around some of the HNSW code out of curiosity and I
>> noticed that the HnswGraphSearcher#searchLevel methods accept an array
>> of entry point nodes (int[] eps), but as far as I can tell, only one
>> entry point is every provided (from both HnswGraphSearcher and
>> HnswGraphBuilder). Is there actually a use-case for executing a search
>> using multiple entry points? I ask purely out of curiosity and trying
>> to build up my own understanding in this space.
>>
>> I tried searching the dev list and Jira issues for anywhere this might
>> have been discussed and came up empty, but apologies if there's a
>> thread about this somewhere I missed.
>>
>> Cheers,
>> -Greg
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
>> For additional commands, e-mail: dev-help@lucene.apache.org
>>

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org