当前位置：网站首页>Hnsw introduction and some reference articles in lucene9

Hnsw introduction and some reference articles in lucene9

2022-07-03 07:30:00 【chuanyangwang】

Read a text HNSW The context of algorithm theory _u011233351 The blog of -CSDN Blog _hnsw Algorithm HNSW Algorithm ----Hierarchcal Navigable Small World graphs, The first contributor ：Y.Malkov( Russia ) One . Background introduction It has always been a headache to do efficient similarity search in the vast data stream . such as , I'm searching for dogs app I read an article on , The recommender system should push the article closest to this article for me , All articles in the database are represented by vectors , So the problem we have to solve is “ Find the vector corresponding to this article ...https://blog.csdn.net/u011233351/article/details/85116719

NSW Search for ：

K-NNSearch(object q, integer:m, k)
 Definition ：TreeSet[object] tempRes, candidates, visitedset, result
for(i=0;i<m;i++) do:
     Pick one at random entry point  Put in candidates in 
    tempRes = null
    repeat:
         stay candidates Select distance from q Some recent c
         take c from candidates Delete in 
         If c Than all in result The elements in are all separated q far 
             then break repeat
        for e: c.friends
             If e be not in visitedSet Middle principle 
                 hold e Join in visitedSet, candidates, tempRes
            
    end repeat
     hold tempRes Add result in 
    
end for
 from result Before returning in k results

NSW Of Insert ：

Nearest_Neighbor_Insert(object:new_object, integer:f,w)
    SET[object]: neighbors = k-NNSearch(new_object, w, f)
    for(i = 0; i<f; i++) do:
        neighbors[i].connect(new_object)
        new_object.connect(neighbors[i])

Lucene in hsnw The index structure of is as follows

 Meta data and index part:
 +--------------------------------------------------+
 | meta data                                        |
 +--------+-----------------------------------------+
 | doc id | offset to first friend list for the doc |
 +--------+-----------------------------------------+
 | doc id | offset to first friend list for the doc |
 +--------+-----------------------------------------+
 |              ......                              |
 +--------+-----------------------------------------+

 Graph data part:
 +-------------------------+---------------------------+---------+-------------------------+
 | friends list at layer N | friends list at layer N-1 |  ...... | friends list at level 0 | <- friends lists for doc 0
 +-------------------------+---------------------------+---------+-------------------------+
 | friends list at layer N | friends list at layer N-1 |  ...... | friends list at level 0 | <- friends lists for doc 1
 +-------------------------+---------------------------+---------+-------------------------+
 |                            ......                                                       | <- and so on
 +-----------------------------------------------------------------------------------------+

 Vector data part:
 +----------------------+
 | encoded vector value | <- vector value for doc 0
 +----------------------+
 | encoded vector value | <- vector value for doc 1
 +----------------------+
 |   ......             | <- and so on
 +----------------------+

The logic of writing indexes

org.apache.lucene.codecs.lucene90.Lucene90HnswVectorsWriter#writeField

1. Write vector

2. Write graph

3. Write meta

  @Override
  public void writeField(FieldInfo fieldInfo, VectorValues vectors) throws IOException {
    long pos = vectorData.getFilePointer();
    // write floats aligned at 4 bytes. This will not survive CFS, but it shows a small benefit when
    // CFS is not used, eg for larger indexes
    long padding = (4 - (pos & 0x3)) & 0x3;
    long vectorDataOffset = pos + padding;
    for (int i = 0; i < padding; i++) {
      vectorData.writeByte((byte) 0);
    }
    // TODO - use a better data structure; a bitset? DocsWithFieldSet is p.p. in o.a.l.index
    int[] docIds = new int[vectors.size()];
    int count = 0;
    for (int docV = vectors.nextDoc(); docV != NO_MORE_DOCS; docV = vectors.nextDoc(), count++) {
      // write vector
      writeVectorValue(vectors);
      docIds[count] = docV;
    }
    // count may be < vectors.size() e,g, if some documents were deleted
    long[] offsets = new long[count];
    long vectorDataLength = vectorData.getFilePointer() - vectorDataOffset;
    long vectorIndexOffset = vectorIndex.getFilePointer();
    if (vectors instanceof RandomAccessVectorValuesProducer) {
      writeGraph(
          vectorIndex,
          (RandomAccessVectorValuesProducer) vectors,
          fieldInfo.getVectorSimilarityFunction(),
          vectorIndexOffset,
          offsets,
          count,
          maxConn,
          beamWidth);
    } else {
      throw new IllegalArgumentException(
          "Indexing an HNSW graph requires a random access vector values, got " + vectors);
    }
    long vectorIndexLength = vectorIndex.getFilePointer() - vectorIndexOffset;
    writeMeta(
        fieldInfo,
        vectorDataOffset,
        vectorDataLength,
        vectorIndexOffset,
        vectorIndexLength,
        count,
        docIds);
    writeGraphOffsets(meta, offsets);
  }

HNSW Introduce – d0evi1 The blog of http://d0evi1.com/hnsw/