[
https://issues.apache.org/jira/browse/LUCENE-9136?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17037325#comment-17037325
]
Julie Tibshirani commented on LUCENE-9136:
------------------------------------------
Hello [~irvingzhang], to me this looks like a really interesting direction! We
also found in our research that k-means clustering (IVFFlat) could achieve high
recall with a relatively low number of distance computations. It performs well
compared to KD-trees and LSH, although it tends to require more distance
computations than HNSW. A nice property of the approach is that it's based on a
classic algorithm, k-means -- it is easy to understand, and has few tuning
parameters.
I wonder if this clustering-based approach could fit more closely in the
current search framework. In the current prototype, we keep all the cluster
information on-heap. We could instead try storing each cluster as its own
'term' with a postings list. The kNN query would then be modelled as an 'OR'
over these terms.
A major concern about clustering-based approaches is the high indexing cost.
K-means is a heavy operation in itself. And even if we only use subsample of
documents during k-means, we must compare each indexed document to all
centroids to assign it to the right cluster. With the heuristic of using
sqrt(n) centroids, this could give poor scaling behavior at index time. A
couple thoughts on this point:
* FAISS helps address this concern by using an ANN algorithm to do the cluster
assignment. In particular, it provides an option to use k-means clustering
(IVFFlat), but do the cluster assignment using HNSW:
https://github.com/facebookresearch/faiss/wiki/Guidelines-to-choose-an-index#how-big-is-the-dataset.
This seemed like a potentially interesting direction.
* There could also be ways to streamline the k-means step. I experimented with
FAISS's implementation of IVFFlat, and found that I could run very few k-means
iterations, but still achieve similar performance. Here are some results on a
dataset of ~1.2 million GloVe word vectors, using sqrt(n) centroids. The cell
values represent recall for a kNN search with k=10:
*{{approach 10 probes 20 probes 100 probes 200 probes}}*
{{random centroids 0.578 0.68 0.902 0.961}}
{{k-means, 1 iter 0.729 0.821 0.961 0.987}}
{{k-means, 2 iters 0.775 0.854 0.968 0.989}}
{{k-means, 20 iters 0.806 0.875 0.972 0.991}}
> Introduce IVFFlat to Lucene for ANN similarity search
> -----------------------------------------------------
>
> Key: LUCENE-9136
> URL: https://issues.apache.org/jira/browse/LUCENE-9136
> Project: Lucene - Core
> Issue Type: New Feature
> Reporter: Xin-Chun Zhang
> Priority: Major
> Attachments: 1581409981369-9dea4099-4e41-4431-8f45-a3bb8cac46c0.png
>
>
> Representation learning (RL) has been an established discipline in the
> machine learning space for decades but it draws tremendous attention lately
> with the emergence of deep learning. The central problem of RL is to
> determine an optimal representation of the input data. By embedding the data
> into a high dimensional vector, the vector retrieval (VR) method is then
> applied to search the relevant items.
> With the rapid development of RL over the past few years, the technique has
> been used extensively in industry from online advertising to computer vision
> and speech recognition. There exist many open source implementations of VR
> algorithms, such as Facebook's FAISS and Microsoft's SPTAG, providing various
> choices for potential users. However, the aforementioned implementations are
> all written in C++, and no plan for supporting Java interface, making it hard
> to be integrated in Java projects or those who are not familier with C/C++
> [[https://github.com/facebookresearch/faiss/issues/105]].
> The algorithms for vector retrieval can be roughly classified into four
> categories,
> # Tree-base algorithms, such as KD-tree;
> # Hashing methods, such as LSH (Local Sensitive Hashing);
> # Product quantization based algorithms, such as IVFFlat;
> # Graph-base algorithms, such as HNSW, SSG, NSG;
> where IVFFlat and HNSW are the most popular ones among all the VR algorithms.
> IVFFlat is better for high-precision applications such as face recognition,
> while HNSW performs better in general scenarios including recommendation and
> personalized advertisement. *The recall ratio of IVFFlat could be gradually
> increased by adjusting the query parameter (nprobe), while it's hard for HNSW
> to improve its accuracy*. In theory, IVFFlat could achieve 100% recall ratio.
> Recently, the implementation of HNSW (Hierarchical Navigable Small World,
> LUCENE-9004) for Lucene, has made great progress. The issue draws attention
> of those who are interested in Lucene or hope to use HNSW with Solr/Lucene.
> As an alternative for solving ANN similarity search problems, IVFFlat is also
> very popular with many users and supporters. Compared with HNSW, IVFFlat has
> smaller index size but requires k-means clustering, while HNSW is faster in
> query (no training required) but requires extra storage for saving graphs
> [indexing 1M
> vectors|[https://github.com/facebookresearch/faiss/wiki/Indexing-1M-vectors]].
> Another advantage is that IVFFlat can be faster and more accurate when
> enables GPU parallel computing (current not support in Java). Both algorithms
> have their merits and demerits. Since HNSW is now under development, it may
> be better to provide both implementations (HNSW && IVFFlat) for potential
> users who are faced with very different scenarios and want to more choices.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
