jtibshirani commented on a change in pull request #608: URL: https://github.com/apache/lucene/pull/608#discussion_r787201469
########## 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: I think for simplicity we could just have one class `Lucene90HnswGraph` that performs both reading and writing. There isn't a risk of users accidentally writing to the 90 codec since we disallow that in `Lucene90HnswVectorsFormat`. It would mean that a little bit of test-only logic lives in the main module, but that seems okay to me. ########## File path: lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/Lucene90HnswVectorsFormat.java ########## @@ -77,26 +77,33 @@ static final int VERSION_START = 0; static final int VERSION_CURRENT = VERSION_START; + /** Default number of maximum connections per node */ public static final int DEFAULT_MAX_CONN = 16; + /** + * Default number of the size the size of the queue maintained while searching and the number of Review comment: Nice :) ########## File path: lucene/core/src/java/org/apache/lucene/codecs/lucene91/Lucene91HnswVectorsFormat.java ########## @@ -0,0 +1,144 @@ +/* + * 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.codecs.lucene91; + +import java.io.IOException; +import org.apache.lucene.codecs.KnnVectorsFormat; +import org.apache.lucene.codecs.KnnVectorsReader; +import org.apache.lucene.codecs.KnnVectorsWriter; +import org.apache.lucene.index.SegmentReadState; +import org.apache.lucene.index.SegmentWriteState; +import org.apache.lucene.util.hnsw.HnswGraph; + +/** + * Lucene 9.0 vector format, which encodes numeric vector values and an optional associated graph + * connecting the documents having values. The graph is used to power HNSW search. The format + * consists of three files: + * + * <h2>.vec (vector data) file</h2> + * + * <p>This file stores all the floating-point vector data ordered by field, document ordinal, and + * vector dimension. The floats are stored in little-endian byte order. + * + * <h2>.vex (vector index)</h2> + * + * <p>Stores graphs connecting the documents for each field organized as a list of nodes' neighbours + * as following: + * + * <ul> + * <li>For each level: + * <ul> + * <li>For each node: + * <ul> + * <li><b>[int32]</b> the number of neighbor nodes + * <li><b>array[int32]</b> the neighbor ordinals + * <li><b>array[int32]</b> padding from empty integers if the number of neighbors less + * than the maximum number of connections (maxConn). Padding is equal to + * ((maxConn-the number of neighbours) * 4) bytes. + * </ul> + * </ul> + * </ul> + * + * <h2>.vem (vector metadata) file</h2> + * + * <p>For each field: + * + * <ul> + * <li><b>[int32]</b> field number + * <li><b>[int32]</b> vector similarity function ordinal + * <li><b>[vlong]</b> offset to this field's vectors in the .vec file + * <li><b>[vlong]</b> length of this field's vectors, in bytes + * <li><b>[vlong]</b> offset to this field's index in the .vex file + * <li><b>[vlong]</b> length of this field's index data, in bytes + * <li><b>[int]</b> dimension of this field's vectors + * <li><b>[int]</b> the number of documents having values for this field + * <li><b>array[vint]</b> the docids of documents having vectors, in order + * <li><b>[int]</b> the maximum number of connections (neigbours) that each node can have + * <li><b>[int]</b> number of levels in the graph + * <li>Graph nodes by level. For each level + * <ul> + * <li><b>[int]</b> the number of nodes on this level + * <li><b>array[vint]</b> for levels greater than 0 list of nodes on this level, stored as + * the the level 0th nodes ordinals. + * </ul> + * </ul> + * + * @lucene.experimental + */ +public final class Lucene91HnswVectorsFormat extends KnnVectorsFormat { + + static final String META_CODEC_NAME = "Lucene91HnswVectorsFormatMeta"; + static final String VECTOR_DATA_CODEC_NAME = "Lucene91HnswVectorsFormatData"; + static final String VECTOR_INDEX_CODEC_NAME = "Lucene91HnswVectorsFormatIndex"; + static final String META_EXTENSION = "vem"; + static final String VECTOR_DATA_EXTENSION = "vec"; + static final String VECTOR_INDEX_EXTENSION = "vex"; + + static final int VERSION_START = 0; + static final int VERSION_CURRENT = VERSION_START; + + /** Default number of maximum connections per node */ + public static final int DEFAULT_MAX_CONN = 16; + /** + * Default number of the size the size of the queue maintained while searching during a graph Review comment: Typo: "the size the size" ########## File path: lucene/core/src/java/org/apache/lucene/codecs/lucene90/package-info.java ########## @@ -180,9 +180,6 @@ * of files, recording dimensionally indexed fields, to enable fast numeric range filtering * and large numeric values like BigInteger and BigDecimal (1D) and geographic shape * intersection (2D, 3D). - * <li>{@link org.apache.lucene.codecs.lucene90.Lucene90HnswVectorsFormat Vector values}. The Review comment: I think we could just move this javadoc to `org.apache.lucene.backward_codecs.lucene90.package-info.java`? Or we could delete it... I don't see detailed package-info for other old codecs like lucene86. ########## File path: lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/Lucene90HnswVectorsFormat.java ########## @@ -77,26 +77,33 @@ static final int VERSION_START = 0; static final int VERSION_CURRENT = VERSION_START; + /** Default number of maximum connections per node */ public static final int DEFAULT_MAX_CONN = 16; + /** + * Default number of the size the size of the queue maintained while searching and the number of + * random entry points to sample during a graph construction. + */ public static final int DEFAULT_BEAM_WIDTH = 100; /** * Controls how many of the nearest neighbor candidates are connected to the new node. Defaults to * {@link Lucene90HnswVectorsFormat#DEFAULT_MAX_CONN}. See {@link HnswGraph} for more details. */ - private final int maxConn; + final int maxConn; Review comment: These could be `protected` ########## File path: lucene/core/src/java/org/apache/lucene/util/hnsw/BoundsChecker.java ########## @@ -17,62 +17,74 @@ package org.apache.lucene.util.hnsw; -abstract class BoundsChecker { +/** + * A helper class for an hnsw graph that serves as a comparator of the currently set bound value + * with a new value. + */ +public abstract class BoundsChecker { Review comment: I see we're sharing some classes between `Lucene90HnswGraph` and `HnswGraph`. We usually try to keep the logic separate (and not make utility classes public?) but it seems like an okay compromise here. -- 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]
