Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection

Near neighbor (NN) search is a fundamental problem in machine learning, computer vision, image analysis and recommender systems. Consider a database $\mathcal{D}$ of $N$ vectors given as $\{\boldsymbol{f_{1}},\boldsymbol{f_{2}},\cdots,\boldsymbol{f_{N}}\}$ where each $\boldsymbol{f_{i}}\in\mathbb{R}^{d}$. Given a query vector $\boldsymbol{q}\in\mathbb{R}^{d}$, our aim is to determine all those vectors in $\mathcal{D}$ such that $\textrm{sim}(\boldsymbol{q},\boldsymbol{f_{i}})\geq\rho$, where $\textrm{sim}(.,.)$ denotes some similarity measure, and $\rho$ denotes some threshold on sim. This is called a similarity measure based NN query. Another variant is the $K$ nearest neighbor (KNN) search where the aim is to find the $K$ most similar neighbors to $\boldsymbol{q}$.

A significant portion of the literature on NN search focusses on approximate methods, often resulting in less than perfect recall rates, i.e. many database images that are similar to the query image are not retrieved. This deficiency renders them unsuitable for applications requiring high recall, such as plagiarism detection. In such scenarios, the query vectors, such as images or music files, are compared to an existing database of similar entities, and all vectors exhibiting high similarity with the query need to be retrieved for plagiarism assessment. The failure to retrieve a near neighbor could potentially lead to unfair evaluation of submissions to photography or music competitions, or online forums.

In our technique, a pool of high-dimensional vectors is created by simply adding together the participating vectors, which may for example be (vectorized) images or features extracted from them. Consider a query vector $\boldsymbol{q}\in\mathbb{R}^{d}$ and the database $\mathcal{D}$ consisting of $\{\boldsymbol{f_{1}},\boldsymbol{f_{2}},\cdots,\boldsymbol{f_{N}}\}$ where each $\boldsymbol{f_{i}}\in\mathbb{R}^{d}$. Throughout this paper, we consider the similarity measure $\textrm{sim}(\boldsymbol{q},\boldsymbol{f_{i}})\triangleq\boldsymbol{q}^{t}\boldsymbol{f_{i}}$. For simplicity, we consider the query vector $\boldsymbol{q}$ as well as the vectors in $\mathcal{D}$ to be element-wise non-negative. This constraint is satisfied by images or their features based on ReLU or softmax non-linearities (see the end of this section for a method to handle negative-valued descriptors). We also consider that the vectors in question have unit magnitude, without any loss of generality. Due to this, $\boldsymbol{q}^{t}\boldsymbol{f_{i}}$ acts as a cosine similarity measure.

Our aim is to retrieve all ‘defective’ members of $\mathcal{D}$, i.e. each member $\boldsymbol{f_{i}}$ for which $\boldsymbol{q}^{t}\boldsymbol{f_{i}}\geq\rho$, where $\rho$ is some pre-specified threshold. With this aim in mind, we aim to efficiently prune away any vector $\boldsymbol{f_{i}}$ from $\mathcal{D}$ for which it is impossible to have $\boldsymbol{q}^{t}\boldsymbol{f_{i}}\geq\rho$. Vector pooling using summations proves to be beneficial for this purpose. Consider the toy example of a pool $\boldsymbol{y}=\boldsymbol{f_{1}}+\boldsymbol{f_{2}}+\boldsymbol{f_{3}}+\boldsymbol{f_{4}}$. If $\boldsymbol{q}^{t}\boldsymbol{y}<\rho$ (i.e. the pooled result is negative), then one can clearly conclude that $\boldsymbol{q}^{t}\boldsymbol{f_{i}}<\rho$ for each $i\in\{1,2,3,4\}$. However if $\boldsymbol{q}^{t}\boldsymbol{y}\geq\rho$, i.e. it yields a positive result, then we need to do further work to identify the defective members (if any). For this, we split the original pool and create two pools $\boldsymbol{y_{1}}$ and $\boldsymbol{y_{2}}$, each with approximately half the number of members of the original pool. We recursively compute $\boldsymbol{q}^{t}\boldsymbol{y_{2}}$, and then obtain $\boldsymbol{q}^{t}\boldsymbol{y_{1}}=\boldsymbol{q}^{t}\boldsymbol{y}-\boldsymbol{q}^{t}\boldsymbol{y_{2}}$ (where both $\boldsymbol{q}^{t}\boldsymbol{y}$ and $\boldsymbol{q}^{t}\boldsymbol{y_{2}}$ have already been computed earlier, and hence $\boldsymbol{q}^{t}\boldsymbol{y_{1}}$ is directly obtained from the difference between them). Thereafter, we proceed in a similar fashion for both branches.

We now consider the case of searching within the entire database $\mathcal{D}$ defined earlier. We initiate this recursive process with a pool $\boldsymbol{y_{0}}$ that is obtained from the summation of all $N$ vectors. If $\boldsymbol{y_{0}}$ yields a positive result, we test the query vector with two pools: $\boldsymbol{y_{11}}$ obtained from a summation of vectors $\boldsymbol{f_{1}}$ through to $\boldsymbol{f_{\lfloor N/2\rfloor}}$, and $\boldsymbol{y_{12}}$ obtained from a summation of vectors $\boldsymbol{f_{\lfloor N/2\rfloor+1}}$ through to $\boldsymbol{f_{N}}$. If $\boldsymbol{y_{11}}$ tests negative, then all its members are declared negative and no further tests are required on its members, which greatly reduces the total number of tests. If $\boldsymbol{y_{11}}$ tests positive, then it is split into two pools $\boldsymbol{y_{21}},\boldsymbol{y_{22}}$ with roughly equal number of members. Tests are carried out further on these two pools recursively. The same treatment is accorded to $\boldsymbol{y_{12}}$, which would be split into pools $\boldsymbol{y_{23}},\boldsymbol{y_{24}}$ if it were to test positive. This recursive process stops when the pools obtained after splitting contain just a single vector each, in which case each such single vector is tested against $\boldsymbol{q}$. Clearly, the depth of this recursive process is $\lceil\log_{2}N\rceil$ given $N$ vectors in $\mathcal{D}$. This procedure is called binary splitting, and it is a multi-round adaptive group testing approach, applied here to NN search. For efficiency of implementation, it is important to be able to create the different pools such as $\boldsymbol{y_{0}},\boldsymbol{y_{11}},\boldsymbol{y_{12}},\boldsymbol{y_{21}},\boldsymbol{y_{22}},\boldsymbol{y_{23}},\boldsymbol{y_{24}}$, etc., efficiently. For this purpose, we maintain cumulative sums of the following form in memory:

The cumulative sums are useful for efficient creation of various pools. They are created purely offline, independent of any query vector. The pools are created using simple vector difference operations, given these cumulative sums. For example, notice that $\boldsymbol{y_{0}}=\boldsymbol{\widetilde{f}_{N}},\boldsymbol{y_{11}}=\boldsymbol{\widetilde{f}_{\lfloor N/2\rfloor}}$ and $\boldsymbol{y_{12}}=\boldsymbol{\widetilde{f}_{N}}-\boldsymbol{\widetilde{f}_{\lfloor N/2\rfloor}}$. The overall binary splitting procedure is presented in Alg. 1 (a schematic diagram is provided in [13]). For the sake of greater efficiency, it is implemented non-recursively using a simple stack data structure.

This binary splitting approach is quite different from Dorfman’s algorithm [21], which performs individual testing in the second round. Our approach is more similar to Hwang’s generalized binary splitting approach, a GT procedure which was proposed in [29] (see also [8], Alg. 1.1 of [14]). However compared to Hwang’s technique, our approach allows for creation of all pools either in a purely offline manner or with simple updates involving a single vector-subtraction operation (for example, $\boldsymbol{y_{12}}=\boldsymbol{\widetilde{f}_{N}}-\boldsymbol{\widetilde{f}_{\lfloor N/2\rfloor}}$ in the earlier example). On the other hand, the method in [29] detects defectives one at a time, after going through all $\log_{2}N$ levels of recursion. Once a defective item is detected, it is discarded and all pools are created again. The entire set of $\log_{2}N$ levels of recursion are again executed. This process is repeated until all defectives have been detected and discarded one at a time. The method from [29] is computationally inefficient for high-dimensional NN search, as the pools must be created afresh for each level of recursion. This is because if a vector at index $i$ is discarded, all cumulative sums from index $i+1$ to $N$ need to be updated. Such updates are not required in our method. We also emphasize that the techniques in [21, 14, 29, 33] have all been applied only for binary GT and not for NN search (see the beginning of Sec. 5 for an important difference between binary GT and NN search). The binary splitting procedure saves on a large number of tests because in high dimensional search, we observe that most vectors in $\mathcal{D}$ are dissimilar to a given query vector $\boldsymbol{q}$, as will be demonstrated in Sec. 4. After the first round where pool $\boldsymbol{y_{0}}$ is created, all other pools are essentially created randomly (since the initial arrangement of the vectors in $\mathcal{D}$ is random). As a result, across the different rounds, many pools test negative and are dropped out, especially in later rounds. In particular, we note that there is no loss of accuracy in this method, although we save on the number of tests by a factor more than ten on some large datasets (as will be shown in Sec. 4).

GT algorithms of different flavors have been applied to the NN search problem in [41, 31, 22]. A detailed description of these techniques is presented in the supplemental material at [13, Sec. 2]. Compared to these three afore-mentioned techniques, our method is exact, with the same accuracy as exhaustive search. The methods [41, 31, 22] require choice of various hyper-parameters ($R$, the number of backpropagation steps, for [41]; sparse coding parameters in [31]; bloom filter and hash function parameters ($B,R,m,L$) in [22] – see [13, Sec. 2]) for which there is no clear data-driven selection procedure. Our method, however, requires no parameter tuning. In experiments, we have observed a speed up of more than ten-fold in querying time with our method as compared to exhaustive search on some datasets. Like [41], and unlike [22, 31], our method does have a large memory requirement, as we require all pools to be in memory. Some techniques such as [22] require the nearest neighbors to be significantly more similar than all other members of $\mathcal{D}$ (let us call this condition $\mathscr{C}1$). Our method does not have such a requirement. However, our method will perform more efficiently for queries for which a large number of similarity values turn out to be small, and only a minority are above the threshold $\rho$ (let us call this condition $\mathscr{C}2$). In our experimental study on diverse datasets, we have observed that $\mathscr{C}2$ is true always. On the other hand, $\mathscr{C}1$ does not hold true in a large number of cases, as also reported in [22, Sec. 5.3].

In this section, we present experimental results conducted in two settings: (i) Non-streaming setting with a static database, and (ii) Streaming setting with incremental additions of new vectors to the database. In both the settings, we tested our algorithms on the following publicly available image datasets, of which the first two are widely used in retrieval and NN search problems: (i) MIRFLICKR, a set of 1 million (1M) images from the MIRFLICKR dataset (subset of images from Flickr) available at [11], with an additional 6K images from the Paris dataset available at [12], as followed in [41]; (ii) ImageNet, a set of 1M images used in the ImageNet Object Localization Challenge, available at [2]; (iii) IMDB-Wiki, a set of all 500K images from the IMDB-Wiki face image dataset from [9]; (iv) InstaCities, a set of 1M images of 10 large cities [10]. Although, we have worked with image datasets, our method is equally applicable to any other modalities such as speech, genomics, etc.

In the following, we denote a query image by $\boldsymbol{I_{q}}$. For every dataset containing images $\{\boldsymbol{I_{i}}\}_{i=1}^{N}$, feature vectors $\{\boldsymbol{f_{i}}\}_{i=1}^{N}$ were extracted as follows: First, each image $\boldsymbol{I_{i}}$ was passed through the popular VGGNet [42] (as its features are known to be useful for building good perceptual metrics [44]) to obtain intermediate feature vector $\boldsymbol{f^{\prime}_{i}}$. Second, a softmax-based feature vector $\boldsymbol{f_{i}}$ of dimension $d=1000$, corresponding to the 1000 classes in ImageNet, was extracted further from the VGGNet output vector $\boldsymbol{f^{\prime}_{i}}$. In our experiments, we observed that the softmax-based features yielded superior retrieval recall (defined as # points retrieved belonging to the same class as the query point / # points of the same class as the query point) as compared to the baseline VGGNet features, with exhaustive search on different datasets (see [13, Table 1] for more details), even on those datasets which are different from ImageNet. Higher recall is particularly beneficial for NN search application in scenarios such as image plagiarism detection. The feature vectors were all non-negative and were subsequently unit-normalized. For every dataset, NN search was carried out using different methods (see below) on the same unit-normalized feature vectors extracted from 10,000 query images. That is, the aim was to efficiently identify those indices $i\in\{1,2,...,N\}$ for which the dot products between $\boldsymbol{q}$ (the feature vector of query image $\boldsymbol{I_{q}}$) and $\boldsymbol{f_{i}}$ (both feature vectors unit-normalized) exceeded some specified threshold $\rho$. For all datasets, the intrinsic dimensionality was computed using the number of singular values of the $d\times N$ data matrix that accounted for 99% of its Frobenius norm. The intrinsic dimensionality for all datasets was more than 200 (for $d=1000$).

Our binary splitting approach, using pool creation with summation (Our-Sum) and element-wise maximum (Our-Max), was compared to the following recent and popular techniques: (i) Exhaustive search (Exh) through the entire database, for every query image; (ii) The recent GT-based technique from [22], known as Flinng (Filters to Identify Near-Neighbor Groups), using code from [3]; (iii) The popular randomized KD-tree and K-means based technique Flann for approximate NN search [37], using code from [7] with default parameters; (iv) The Falconn technique from [15] which uses multi-probe LSH, using the code from [4]; (v) Falconn++ [39], an enhanced version of Falconn which filters out potentially distant points from any hash bucket before querying using code from [5]; (vi) Ivf, the speedy inverted multi-index technique implemented in the highly popular Faiss library from Meta/Facebook [1, 16]; (vii) Hnsw, a graph-based technique also used in [1]; (viii) The Scann library [6, 26] which implements an anisotropic vector quantization (KMeans) algorithm. Our methods have no hyperparameters, but for all competing methods, results are reported by tuning hyperparameters so as to maximize the recall (defined below) – see [13, Sec. 5] for more details.

We did not compare with the GT-based techniques from [41] and [31] as we could not find full publicly available implementations for these. Moreover, the technique from [22] is claimed to outperform those in [41] and [31]. We did implement the algorithm from [41], but it yielded significantly large query times. This may be due to subtle implementation differences in the way image lists are re-ranked in each of the $R$ iterations of their algorithm (see Sec. 3). In any case, our method produces 100% recall and precision, unlike [41, 31].

The only update required to Our-Sum for insertion of $n_{s}$ new points will be to produce $n_{s}$ extra cumulative sums as in Eqn. 1 for a cost of $O(dn_{s})$. For comparison, we have selected only those algorithms that include methods for the addition of new points without necessitating the rebuilding of the entire index from scratch. These include Exh, Ivf, Hnsw and Flann-R. Table 2 reports the initial Index Build Time (IBT) for 80% of the database, Mean Insertion Time (MIT) for new points, besides MQT, MP and MR.

For the problem of binary GT, different variants of the binary splitting approach have been shown to require just $s\log_{2}N+O(s)$ or $s\log_{2}(N/s)+O(s)$ tests, depending on some implementation details [14, Theorems 1.2 and 1.3]. Here $s$ stands for the number of defectives out of $N$. However in binary GT, a positive result on a pool necessarily implies that at least one of the participants was defective. In our application for NN search, a pool $\boldsymbol{y}$ can produce $\boldsymbol{q}^{t}\boldsymbol{y}\geq\rho$ for query vector $\boldsymbol{q}$, even if none of the vectors that contributed to $\boldsymbol{y}$ produce a dot product with $\boldsymbol{q}$ that exceeds or equals $\rho$. Due to this important difference, the analysis from [14] does not apply in our situation. Furthermore, it is difficult to pin down a precise deterministic number of tests in our technique. Instead, we resort to a distributional assumption on each dot product $\boldsymbol{q}^{t}\boldsymbol{f_{i}}$. We assume that these dot products are independently distributed as per a truncated normalized exponential (TNE) distribution:

This distribution is obtained by truncating the well-known exponential distribution to the $[0,1]$ range and normalizing it so that it integrates to one. Larger the value of $\lambda$, the more rapid is the ‘decay’ in the probability of dot product values from 0 towards 1. Our empirical studies show that for softmax features, this is a reasonable model for dot product values commonly encountered in queries in image retrieval, as can be seen in Fig. 1 for all datasets we experimented with. Also, the best-fit $\lambda$ values for MIRFLICKR, ImageNet, IMDB-Wiki and InstaCities are respectively $34,57,10,30$. The TNE model fit may not be perfect, but less than perfect adherence to the TNE model does not change the key message that will be conveyed in this section.

Our aim now is to determine the probability that a pool $\boldsymbol{y}$ with some $L$ participating vectors will produce a dot product value $\boldsymbol{q}^{t}\boldsymbol{y}$ below a threshold $\rho$. Note again that such a pool will get pruned away in binary splitting, and therefore we would like this probability to be high. Now, the $L$ individual dot-products (of $\boldsymbol{q}$ with vectors that contributed to $\boldsymbol{y}$) are independent and they are all distributed as per the TNE from Eqn. 2. The mean and variance of a TNE variable with parameter $\lambda$ are respectively given by $\left(1/\lambda+1/(1-e^{\lambda})\right)$ and $\left(1/\lambda^{2}-e^{\lambda}/(e^{\lambda}-1)^{2}\right)$. We now apply the central limit theorem (CLT), due to which we can conclude that $\boldsymbol{q}^{t}\boldsymbol{y}$ is (approximately) Gaussian distributed with a mean $\mu\triangleq L\left(1/\lambda+1/(1-e^{\lambda})\right)$ and variance $\sigma^{2}\triangleq L\left(1/\lambda^{2}-e^{\lambda}/(e^{\lambda}-1)^{2}\right)$. With this, we can easily compute $P(\boldsymbol{q}^{t}\boldsymbol{y}\leq\rho)$ given a value of $L$ and $\rho$. Our numerical experiments, illustrated in Fig. 3 of [13], reveal that this probability increases with $\lambda$ and decreases as $L$ increases. This tallies with intuition, and supports the hypothesis that a larger number of pools will be pruned away in a given round if there is more rapid decrease in the probability of dot product values from 0 to 1.

We are now equipped to determine the expected number of tests (dot products) to be computed per query, given such a TNE distribution for the dot products. Given a value of $\rho$, let us denote the probability that a pool with $L$ participants will get pruned away, by $p_{L}(\rho)$. For Our-Sum, for any $L\geq 6$, the probability $p_{L}(\rho)$ is computed using the TNE and CLT based method described earlier. For $L<6$, the Gaussian distribution can be replaced by a truncated Erlang distribution, as the sum of independent exponential random variables follows an Erlang distribution. Even in this case, $P(\boldsymbol{q}^{t}\boldsymbol{y}\leq\rho)$ increases with $\lambda$ and decreases with $L$.

In round 1, there is only one pool and it contains all $N$ vectors. It will get pruned away with probability $p_{N}(\rho)$, for a given fixed threshold $\rho$ and fixed $\lambda$. The expected number of pools in round 2 will be $Q_{2}\triangleq 2(1-p_{N}(\rho))$, each of which will be pruned away with probability $p_{N/2}(\rho)$. The factor 2 is because each pool gets split into two before sending it to the next round of binary splitting. The expected number of pools in round 3 will be $Q_{3}\triangleq 2(1-p_{N/2}(\rho))Q_{2}$. Likewise, in the $k$th round, the expected number of pools is $Q_{k}=2(1-p_{N/2^{k-2}}(\rho))Q_{k-1}$. Hence the expected number of tests per query in our approach will be given by:

as there are at most $\lceil\log_{2}N+1\rceil$ rounds. The factor $\frac{1}{2}$ is due to the fact that the number of tests (i.e. dot product computations) is always half the number of pools (see second para. of Sec. 2). The value of $E(\rho)$ decreases with $\lambda$ as $p_{N}(\rho),p_{N/2}(\rho),...,p_{N/2^{k-2}}(\rho)$ all increase with $\lambda$. A similar analysis for Our-Max is presented in [13, Sec. 4].

Our theoretical analysis depends on $\lambda$, but note that our algorithm is completely agnostic to $\lambda$ and does not use it in any manner. For values of $\rho\in\{0.7,0.8,0.9\}$, we compared the theoretically predicted average number of dot products ($E(\rho)$) to the experimentally observed number for all datasets. These are presented in Tab. 3, where we observe that for MIRFLICKR, ImageNet and InstaCities, the theoretical number for Our-Sum is generally greater than the empirical one. This is because the dot products for these datasets decay slightly faster than what is predicted by a TNE distribution, as can be seen in Fig. 1. Conversely, for IMDB-Wiki, the theoretical number for Our-Sum is less than the empirical one because the dot products decay slower for this dataset than what is predicted by a TNE distribution. For Our-Max, the difference between empirical and theoretical values is larger, as explain in [13].

We have presented a simple and intuitive multi-round group testing approach for range-based near neighbor search. Our method outperforms exhaustive search by a large factor in terms of query time without losing accuracy, on datasets where query vectors are dissimilar to the vast majority of vectors in the gallery. The larger the percentage of dissimilar vectors, the greater is the speedup our algorithm will produce. Our technique has no tunable parameters. It is also easily applicable to situations where new vectors are dynamically added to an existing gallery, without requiring any expensive updates. Apart from this, our technique also has advantages in terms of accuracy of query results (especially recall) over many recent, state of the art methods. A significant limitation of our method is that it currently only supports cosine distances and is applicable only to databases with a sharp decay in feature similarity distribution, as in the case with softmax features. At present, a pool may produce a large dot product value with a query vector, even though many or even all the members of the pool are dissimilar to the query vector. Developing techniques to reduce the frequency of such situations, possibly using various LSH techniques, as well as testing on billion-scale datasets, are important avenues for future work. The implementation of our algorithms can be found at https://github.com/Harsh-Sensei/GroupTestingNN.

This supplemental material contains the following:

1. 1.

   A figure showing the negative logarithm of the normalized histograms of dot products between feature vectors of query images and those of all gallery images from each of the four datasets we experimented with in the main paper. These are shown in Fig. 3. Compare with Fig. 2 of the main paper where normalized histograms are shown.

2. 2.

   A comparison of the techniques Our-Sum and Our-Max proposed in this paper to recent group testing based NN search methods such as [22, 41, 31] is presented in Sec. 8.

3. 3.

   A discussion regarding the limitation of using the recent advances in the compressed sensing literature to the NN search problem is presented in Sec. 9.

4. 4.

   Statistics for the average number of points pruned away in each round of binary splitting in our method on each of the four databases, are presented in Fig. 4 for Our-Sum and Fig. 5 for Our-Max. Notice that for both the proposed algorithms (Our-Sum and Our-Max) there is nearly no pruning encountered during the initial rounds. But as the adaptive tests continue, negative tests are encountered in further rounds, and hence pools get pruned away. Surprisingly, most negative tests for Our-Max are encountered in the last round in contrast to that for Our-Sum.

5. 5.

   Our numerical experiments, illustrated in Fig. 6 reveal that $P(\boldsymbol{q}^{t}\boldsymbol{y}\leq\rho)$ increases with $\lambda$ and decreases as $L$ increases. This tallies with intuition, and supports the hypothesis that a larger number of pools will be pruned away in a given round if there is more rapid decrease in the probability of dot product values from 0 to 1.

6. 6.

   A theoretical analysis of the Our-Max algorithm is presented in Sec. 10.

7. 7.

   The hyper-parameters for various competing algorithms are presented in Sec. 11.

8. 8.

   Details of augmentation to images for generating queries in a streaming setting are presented in Sec. 12 and Fig. 8.

9. 9.

   A comparison of softmax features (on top of VGGNet features) versus VGGNet features in terms of retrieval precision and retrieval recall is presented in Table 4 and Sec. 13.

10. 10.

    Experiments with a low similarity value, i.e. $\rho$ (=0.3), and experiments on a dataset with 12-million points are presented in Sec.  14.

The oldest work on GT for NN search was presented in [41]. In this method, the original data vectors are represented as a matrix $\boldsymbol{F}\in\mathbb{R}^{N\times d}$. The pools are represented as a matrix $\boldsymbol{Y}\in\mathbb{R}^{m\times d}$ obtained by pre-multiplying $\boldsymbol{F}$ by a randomly generated balanced binary matrix $\boldsymbol{A}$ of size $m\times N$ where $m<N$. Given a query vector $\boldsymbol{q}$, its similarity with the $j$th pool is computed, yielding a score $v_{yj}=\boldsymbol{q}^{t}\boldsymbol{Y^{j}}$, where $\boldsymbol{Y^{j}}$ is the $j$th group vector (and the $j$th row of $\boldsymbol{Y}$). This is repeated for every $j\in[m]$. Let $\mathcal{P}_{i}$ be the set of pools in which the $i$th vector, i.e. $\boldsymbol{f_{i}}$, belongs. Then, a likelihood score $L_{i}\triangleq\sum_{j\in\mathcal{P}_{i}}v_{yj}$ is computed for every vector. The vector from $\boldsymbol{F}$ with the largest likelihood score (denote this vector by $\boldsymbol{f_{k0}}$) is considered to be one of the nearest neighbors of $\boldsymbol{q}$. Next, the value $\boldsymbol{q}^{t}\boldsymbol{f_{k0}}$ is computed and the pool-level similarity scores for all pools containing $\boldsymbol{f_{k0}}$ are updated to yield new scores of the form $v_{yj}=v_{yj}-\boldsymbol{q}^{t}\boldsymbol{f_{k0}}$. Thereafter, all likelihood scores are updated. This process is called back-propagation in [41]. Again, the vector from $\boldsymbol{F}$ with the highest likelihood is identified and this procedure is repeated some $R$ times, and finally a sort operation is performed in order to rank them. In [41], it is argued that the time complexity of this procedure is $O(d(m+R))$. However, this is an approximate search method, and there is no guarantee that the $R$ neighbors thus derived will indeed be the nearest ones. As a result, a large number of false positives may be generated by this method.

The work in [31] clusters the collection $\mathcal{D}$ into disjoint groups such that the members of a group are as orthogonal to each other as possible. As a result, the similarity measure $\boldsymbol{q}^{t}\boldsymbol{y_{j}}$ between $\boldsymbol{q}$ and a group vector $\boldsymbol{y_{j}}$ is almost completely dominated by the similarity between $\boldsymbol{q}$ and exactly one member of the group. A careful sparse coding and decoder correction step is also used, and the sparsity of the codes plays a key role in the speedup achieved by this method. However, this method is again an approximate method and heavily relies on the near-orthogonality of each group.

The work in [22] randomly distributes the collection $\mathcal{D}$ of $N$ vectors over some $B$ cells. This is independently repeated $R$ times, creating a grid of $B\times R$ cells. Within each cell, we have a collection of participating members $M_{r,b}$ and a corresponding group test $C_{r,b}$. The group test is essentially a binary classifier which determines whether $M_{r,b}$ contains at least one member which is similar to the query vector $\boldsymbol{q}$. This is an approximate query, with a true positive rate $p$ and false positive rate $q$. It is implemented via a distance-sensitive bloom filter [17, 32], which allows for very fast querying. The bloom filter is constructed with $m$ binary arrays, with some $L$ concatenated hash functions used in each array. For all positive tests $C_{r,b}$, a union set of all their members is computed. This is repeated $R$ times to create $R$ candidate sets, and the intersection of these $R$ sets is created. Each union can contain many false positives, but this intersection filters out non-members effectively. Precise bounds on $p,q$ are derived in [22], and the time complexity of a single query is proved to be $O(N^{1/2+\gamma}\log^{3}N)$ where $\gamma\triangleq\log s_{|K|}/(\log s_{|K|+1}-\log s_{|K|})$ where $s_{|K|}$ stands for the similarity between $\boldsymbol{q}$ and the $K$th most similar vector in $\mathcal{D}$. The query time is provably sub-linear for queries for which $\gamma<1/2$. This is obeyed in data which are distributed as per a Gaussian mixture model with components that have well spread out mean vectors and with smaller variances. But for many distributions, this condition could be violated, leading to arbitrarily high query times in the worst case. This method, too, produces a large number of false negatives and false positives.

Compared to these three afore-mentioned techniques, our method is exact, with the same accuracy as exhaustive search. The methods [41, 31, 22] require hyper-parameters ($R$ for [41], sparse coding parameters in [31], $B,R,m,L$ in [22]) for which there is no clear data-driven selection procedure. Our method, however, requires no parameter tuning. In experiments, we have observed a speed up of more than ten-fold in querying time with our method as compared to exhaustive search on some datasets. Like [41], and unlike [22, 31], our method does have a large memory requirement, as we require all pools to be in memory. Some techniques such as [22] require the nearest neighbors to be significantly more similar than all other members of $\mathcal{D}$ (let us call this condition $\mathscr{C}1$). Our method does not have such a requirement. However, our method will perform more efficiently for queries for which a large number of similarity values turn out to be small, and only a minority are above the threshold $\rho$ (let us call this condition $\mathscr{C}2$). In our experimental study on diverse datasets, we have observed that $\mathscr{C}2$ is true always. On the other hand, $\mathscr{C}1$ does not hold true in a large number of cases, as also reported in [22, Sec. 5.3].

Sec. 3 of the main paper describes three recent papers [41, 31, 22] which apply the principles of group testing to near neighbor search, and compares them to our technique. In this section, we describe our attempts to apply the latest developments from the compressed sensing (CS) literature to this problem. Note that CS and GT are allied problems, and hence it makes sense to comment on the application of CS to near neighbor search.

Consider that the original data vectors are represented as a matrix $\boldsymbol{F}\in\mathbb{R}^{N\times d}$. The pools are represented as a matrix $\boldsymbol{Y}\in\mathbb{R}^{m\times d}$ obtained by pre-multiplying $\boldsymbol{F}$ by a randomly generated balanced binary matrix $\boldsymbol{A}$ of size $m\times N$ where $m<N$. We considered the relation $\boldsymbol{v_{y}}=\boldsymbol{Av_{x}}$, where $\boldsymbol{v_{y}}\in\mathbb{R}^{m}$ contains the dot products of the query vector $\boldsymbol{q}$ with each of the pool vectors in $\boldsymbol{Y}\in\mathbb{R}^{m\times d}$, i.e. $\boldsymbol{v_{y}}=\boldsymbol{Yq}$. Likewise $\boldsymbol{v_{x}}\in\mathbb{R}^{N}$ contains the dot products of the query vector $\boldsymbol{q}$ with each of the vectors in the collection $\mathcal{D}$, i.e. $\boldsymbol{v_{x}}=\boldsymbol{Fq}$. The aim is to efficiently recover the largest elements of $\boldsymbol{v_{x}}$ from $\boldsymbol{A},\boldsymbol{v_{y}}$. Since algorithms such as Lasso [28] are of an iterative nature, we considered efficient non-iterative algorithms from the recent literature for recovery of nearly sparse vectors [43, Alg. 8.3]. These are called expander recovery algorithms. Theorem 8.4 of [43] guarantees recovery of the $k$ largest elements of $\boldsymbol{v_{x}}$ using this algorithm, but the bounds on the recovery error are too high to be useful, i.e. $\|\boldsymbol{v^{(k)}_{x}}-\boldsymbol{v_{x,est}}\|_{\infty}\leq\delta\triangleq\|\boldsymbol{v_{x}}-\boldsymbol{v^{(k)}_{x}}\|_{1}$. Here, the vector $\boldsymbol{v^{(k)}_{x}}$ is constructed as follows: the $k$ largest elements of $\boldsymbol{v_{x}}$ are copied into $\boldsymbol{v^{(k)}_{x}}$ at the corresponding indices, and all other elements of $\boldsymbol{v^{(k)}_{x}}$ are set to 0. Clearly, for most situations, $\delta$ will be too large to be useful. Indeed, in some of our numerical simulations, we observed $\delta$ to be several times larger than the sum of the $k$ largest elements of $\boldsymbol{v_{x}}$, due to which Alg. 8.3 from [43] is rendered ineffective for our application. Moreover, for Theorem 8.4 of [43] to hold true, the matrix $\boldsymbol{A}$ requires each item in $\mathcal{D}$ to participate in a very large number of pools, rendering the procedure inefficient for our application. Given these restrictive conditions, we did not continue with this approach.

In Sec. 4 of the main paper, we have presented a theoretical analysis of the expected number of dot product computations required for Our-Sum, which is the binary splitting procedure using summations for pool creation. A similar analysis for estimating the number of dot products required for Our-Max using solely the distribution assumption on dot products (truncated normalized exponential or TNE) is challenging. Consider a pool vector $\boldsymbol{y}=\sum_{i=1}^{K}\boldsymbol{f_{i}}$ created by the summation of $K$ participating vectors $\{\boldsymbol{f_{i}}\}_{i=1}^{K}$. In Our-Sum, the dot product between the query vector $\boldsymbol{q}$ and the pool vector $\boldsymbol{y}$ is exactly equal to the sum of the dot products between $\boldsymbol{q}$ and individual members of the pool. Hence an analysis via the central limit theorem or the truncated Erlang distribution is possible, as explained in Sec. 5 of the main paper. For Our-Max, the pool vector $\boldsymbol{y}$ is constructed in the following manner: $\forall j\in\{1,2,...,d\},y_{j}=\textrm{max}_{i\in\{1,2,...,K\}}f_{i,j}$ where $f_{i,j}$ stands for the $j$th element of vector $\boldsymbol{f_{i}}$. The dot product $\boldsymbol{q}^{t}\boldsymbol{y}$ is an upper bound on $\textrm{max}_{{}_{i\in\{1,2,...,K\}}}\boldsymbol{q}^{t}\boldsymbol{f_{i}}$ (assuming that all values in $\boldsymbol{q}$ and in each $\boldsymbol{f_{i}}$ are non-negative). One can of course use the TNE assumption of the individual dot products $\boldsymbol{q}^{t}\boldsymbol{f_{i}}$ and use analytical expressions for the maximum of TNE random variables. However the fact that $\boldsymbol{q}^{t}\boldsymbol{y}$ is an upper bound on $\textrm{max}_{{}_{i\in\{1,2,...,K\}}}\boldsymbol{q}^{t}\boldsymbol{f_{i}}$ complicates the analysis as compared to the case with Our-Sum. Hence, it is difficult to determine an expected number of dot-products per query for Our-Max, but it is possible to determine an upper bound on this quantity. This can be done as described below.

Let $X_{i}\triangleq\boldsymbol{q}^{t}\boldsymbol{f_{i}}$. Let $D_{P}$ denote the similarity of the query vector $\boldsymbol{q}$ with the pool vector $\boldsymbol{y}$, and let $P$ denote the set of vectors that participated in that pool. We can bound $D_{P}$ with a constant $c$ such that $D_{P}\leq c\cdot\text{max}_{i\in P}(X_{i})$ (see later in this section regarding the value of $c$). Let $n:=|P|$. Then using this bound, we have the following relation:

where the last inequality is based on order statistics, and where $F_{X}(.)$ denotes the CDF of the TNE. From the main paper, recall that $Q_{k}$ stands for the expected number of pools in round $k$. Using the recursive relation for $Q_{k}$ in terms of $Q_{k-1}$, we have the following:

Using this, an upper bound on $E(\rho)$ can be obtained in the following manner:

Notice there is no $\frac{1}{2}$ factor (in contrast to $E(\rho)$ for Our-Sum) here. This is because even after splitting, the similarity needs to be calculated for both the divided pools unlike in the Our-sum algorithm. The constant $c$ can be theoretically as large as the dimension of the dataset (that is, $d=1000$ for the datasets used here), giving a very loose upper bound. However, in order to obtain a sharper upper bound, we find the distribution of $c$ for each pool in a given dataset and use the 90 percentile value (denoted by $c_{90}$) to evaluate the bound. Details for this are provided next.

In order to arrive at comparable values of precision and recall of other algorithms as compared to our proposed algorithms, we performed experiments with many hyper-parameters for each algorithm. Below are the hyper-parameters we used for various experiments with the competing methods. Note that in order to select the set of hyperparameters for each algorithm, we chose the one which gives high recall without significantly increasing time. So there can be other hyperparameter sets for an algorithm with higher recall but at the cost of disproportionate increase in query time. Both streaming and non-streaming setting uses the same set of hyperparameters for each algorithm, except Flann-R (details mentioned below).

1. 1.

   Flinng [22]: For each dataset, we ran this code with different hyper-parameters $B\in\{2^{12},2^{13},\cdots,2^{18},2^{19}\}$, $m\in\{2^{2},2^{3},\cdots,2^{10}\}$, $R\in\{2,3,4\},L=14$ as recommended in the suppl. mat. of [22] (see Sec. 3 of the main paper for their precise meaning) and chose the result that yielded the best recall.

2. 2.

   Falconn [15]: Number of tables = $\{100,150,200,250,300\}$, Number of probes = $\{40,50,70,100\}$. Parameters used for reporting : (250, 70) respectively

3. 3.

   Ivf from the Faiss package [1, 16]: Number of lists = $\{32,64,128\}$, Number of probes = $\{2,16\}$. Parameters used for reporting : (32, 16) respectively

4. 4.

   Hsnw from the Faiss package [1]: $M=32$, Efconstruction = $\{32,64\}$, Efsearch = $\{2\}\times\text{Number of neighbors to retrieve}$, i.e. $K$. Parameters used for reporting : (32, 2) respectively

5. 5.

   Scann [6, 26]: Number of leaves = $\{1,2\}\times\sqrt{\text{Number of elements in the dataset}}$, Number of leaves to search = $\{1/2,1/4,1/8\}\times\text{Number of leaves}$, Reorder number of neighbors = $\{4,8,16\}\times K$. Parameters used for reporting : (2, 1/4, 16) respectively

6. 6.

   Flann [37, 7]: We used AutotunedIndexParams with high target precision (0.85) and other parameters set to their default values. For IMDB-Wiki dataset, we used KDTreeIndexParams(32), for building the index with 32 parallel kd-trees and SearchParams(128) during search phase. This was done because AutotunedIndexParams took long time to build index (more than 20 hours) on IMDB-Wiki dataset. For streaming setting, due to excess time taken by AutotunedIndexParams (leading to high Index Build Time), we used KDTreeIndexParams(16), for building the index with 16 parallel kd-trees and SearchParams(256).

7. 7.

   Falconn++ [5, 39]: We used the parameters suggested in examples of Falconn++, with number of random vectors = 256, number of tables = 350, $\alpha=0.01$, Index Probes (iProbes) = 4, Query Probes (qProbes) = $\textrm{min}(40k,2\cdot\textrm{max}(k\text{ among all queries})$. But we have different values of $k$ for each query which can be as large as $N/10$. Hence, in order to prevent qProbes from exceeding the size of dataset, we cap it to $2\cdot\textrm{max}(k\text{ among all queries})$).

In order to create queries suitable for the streaming environment for plagiarism detection, images from the database underwent specially tailored augmentations. The augmentations included artifacts that are somewhat subtle and which do not alter the image content very signficantly, but are designed to trick the detection system: Gaussian blur (with kernel size 3$\times$3), color jitter (in hue, saturation and value), horizontal flip, downscaling of images and image rotation (by 3 degrees). Figure 8 shows an example of these augmentations.

In this section, we provide a comparison between features extracted from penultimate layer of VGG16 (4096 dimensional) and the features extracted after the last layer (i.e. after applying the softmax functions leading to a 1000 dimensional feature vector as there are 1000 classes involved). For comparison, we use a setting akin to [35], in which database images which are similar to a given query image are retrieved. However, instead of retrieving a fixed number of images ($k$), we have performed range-based retrieval with different similarity thresholds ($\rho=\{0.6,0.7,0.8,0.9\}$) on ImageNet [2], ImageDBCaltech (Caltech101) [23] and ImageDBCorel [38]. Table 4 shows the retrieval recall and retrieval precision values for the aforementioned datasets. Note that we define retrieval precision = # (images retrieved belonging to the same class as the query image) / # (images retrieved), and retrieval recall = # (images retrieved belonging to the same class as the query image) / # (images in the database having the same class as the query image). Note that the retrieval precision and retrieval recall as defined here pertain to identification of the class labels. These are different from the precision and recall reported in the main paper, which are based on near neighbors retrieved by a possibly approximate near neighbor search algorithm, in comparison to an exhaustive nearest neighbor search. Note that though the main algorithm proposed by our paper is fully accurate, the other algorithms we have compared to (i.e., [22, 4, 37]) perform only approximate near neighbor search. Observe from Table 4 that the recall rates for penultimate features noticeably lag behind those of softmax features, indicating that softmax features are better suited for plagiarism detection and other applications requiring high recall.

Here we present results on two experiments with a static database: (i) One on retrieval with low similarity values, i.e. $\rho=0.3$, and (ii) One on the complete ImageNet Database containing 12 million data-points. These results are reported in Table 5.