mayya-sharipova commented on a change in pull request #608: URL: https://github.com/apache/lucene/pull/608#discussion_r790163536
########## File path: lucene/backward-codecs/src/test/org/apache/lucene/backward_codecs/lucene90/Lucene90HnswRWGraph.java ########## @@ -0,0 +1,215 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.lucene.backward_codecs.lucene90; + +import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.List; +import java.util.SplittableRandom; +import org.apache.lucene.index.KnnGraphValues; +import org.apache.lucene.index.RandomAccessVectorValues; +import org.apache.lucene.index.VectorSimilarityFunction; +import org.apache.lucene.util.Bits; +import org.apache.lucene.util.SparseFixedBitSet; +import org.apache.lucene.util.hnsw.BoundsChecker; +import org.apache.lucene.util.hnsw.NeighborArray; +import org.apache.lucene.util.hnsw.NeighborQueue; + +/** + * Navigable Small-world graph. Provides efficient approximate nearest neighbor search for high + * dimensional vectors. See <a href="https://doi.org/10.1016/j.is.2013.10.006";>Approximate nearest + * neighbor algorithm based on navigable small world graphs [2014]</a> and <a + * href="https://arxiv.org/abs/1603.09320";>this paper [2018]</a> for details. + * + * <p>The nomenclature is a bit different here from what's used in those papers: + * + * <h2>Hyperparameters</h2> + * + * <ul> + * <li><code>numSeed</code> is the equivalent of <code>m</code> in the 2012 paper; it controls the + * number of random entry points to sample. + * <li><code>beamWidth</code> in {@link Lucene90HnswGraphBuilder} has the same meaning as <code> + * efConst + * </code> in the 2016 paper. It is the number of nearest neighbor candidates to track while + * searching the graph for each newly inserted node. + * <li><code>maxConn</code> has the same meaning as <code>M</code> in the later paper; it controls + * how many of the <code>efConst</code> neighbors are connected to the new node + * </ul> + * + * <p>Note: The graph may be searched by multiple threads concurrently, but updates are not + * thread-safe. Also note: there is no notion of deletions. Document searching built on top of this + * must do its own deletion-filtering. + */ +public final class Lucene90HnswRWGraph extends KnnGraphValues { Review comment: Good idea, addressed in 770c1ff239a5509087c203fd1fa3a3f83f0ce93f -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
