mbrette commented on issue #12440: URL: https://github.com/apache/lucene/issues/12440#issuecomment-1702888408
Having a look at the first paper you shared [On the merge of knn graphs](https://arxiv.org/pdf/1908.00814.pdf): they proposed 2 algorithms, the second one is called Joint-merge, and is exactly what we are doing today: add the raw dataset of the second graph into the fully constructed first graph. The first one is called Symmetric Merge, basic idea is: Given 2 graphs, for each node in each graph, remove the lower halves of each neighbor lists. Replace it with random nodes from the other graph. Then apply a NN-Descent algorithm, an older algorithm than HNSW, defined in [Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures](https://www.cs.princeton.edu/cass/papers/www11.pdf). NN-Descent algorithm is an iterative algorithm that converge to an a-knn state. For each node, it compare the node with its neighbors' neighbors (the 2-degree neighbors), and update the neighbor list with the closest ones. Then iterate again over all nodes until some stopping criteria is reached (number of changes in the graph below some threshold). It's worth exploring some variation of this. -- 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: issues-unsubscr...@lucene.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org
