DeDrift: Robust Similarity Search under Content Drift

We introduce two real-world datasets to serve as a basis for the drift analysis. In principle, most content collected over several years exhibits some form of drift. For the dataset collection, the constraints are (1) the content should be collected over a long time period (2) the volume should be large enough that statistical trends become apparent (3) the data source should be homogeneous so that other sources of noise are minimized (4) of course, timestamps should be available, either for the data acquisition or the moment the data is uploaded.

The VideoAds dataset contains “semantic”¹¹1We call “semantic” embeddings that are intended for input to classifiers. In contrast, copy detection embeddings identify lower-level features useful for image matching [36]. embeddings extracted from ads videos published on a large social media website between October $2020$ and October $2022$. The ads are of professional and non-professional quality, published by individuals, small and large businesses. They were clipped to be of maximum $30$ seconds in length. The video encoder for the video ads consisted of a RegNetY [38] frame encoder followed by a Linformer [43] temporal pooling layer which were trained using MoCo [23], resulting in one embedding per video. The dataset contains $86M$ L2-normalized embeddings in $512$ dimensions.

The YFCC dataset [42] contains 100M images and videos from the Yahoo Flickr photo sharing site. Compared to typical user-generated content sites, Flickr images are of relatively good quality because uploads are limited and users are mostly pro or semi-pro photographers. We filter out videos, broken dates and dummy images of uniform color, leaving $84M$ usable images spanning $7$ years, from January 2007 to December 2013. As a feature extractor, we use a pretrained DINO [11] model with ViT-S/16 backbone that outputs unnormalized 384-dimensional vectors. As DINO embeddings have been developed for use as k-NN classifiers, their L2 distances are semantically meaningful.

Before evaluations, we apply a random rotation to all embeddings and uniformly quantize them to $8$ bits to make them less bulky. These operations have almost no impact on neighborhood relations. We do not apply dimensionality reduction methods, e.g., PCA, since it can be considered as a part of the indexing method and explored separately.

First, we depict daily and monthly traffic for both datasets in Figure 3. For VideoAds, the traffic is lower during weekends and slightly increases over $2$ years. For YFCC, the traffic is higher on weekends than on weekdays. This pattern is due to the professional vs. personal nature of the data.

Over the years, the amount of content also grows for both datasets, following the organic growth of online traffic. Interestingly, for YFCC, we observe minimum traffic in January and maximum in July. In the following, we use subsampling to cancel the statistical effect of data volume. Unless stated, we use a monthly granularity because this is the typical scale at which drift occurs.

We start the analysis of temporal distribution drift by visualizing pairwise similarities between months $i$ and $j$. For each month, we sample a random set $\Phi_{i}=\{\phi_{i}^{1},..,\phi_{i}^{n}\}$ of $\lvert\Phi_{i}\rvert{=}10^{5}$ embeddings. Then, we compute the similarity between $\Phi_{i}$ and $\Phi_{j}$ by averaging nearest-neighbor distances:

where $L{=}100$ and $\mathrm{NN}_{\ell}(x,\Phi)$ is the $\ell$-th nearest neighbor of $x$ in $\Phi$. Note that the similarity is asymmetric: $S(\Phi_{i},\Phi_{j}){\neq}S(\Phi_{j},\Phi_{i})$ in general. Figure 4 shows the similarity matrices for VideoAds and YFCC datasets. The analysis with daily and weekly granularities is in Appendix A.

We observe that the ads data changes over time but does not have noticeable patterns. YFCC content drifts over years and has a strong seasonal dependency. Figure 2 presents images from YFCC for different seasons²²2 The images for the month $i$ were selected as follows: a quantizer of size $K=4096$ is trained on $\Phi_{0}$. Vectors from $\Phi_{i}$ and $\Phi_{i-3}$ are assigned to the $K$ centroids independently. We visualize six random images from one of the top-8 clusters where the size ratio between assignment $i$ over assignment $i{-}3$ is the largest. Out of these 8, we select one representative cluster for visualization. the seasonal pattern is caused by images of outdoor sceneries (e.g., snow and foliage), seasonal activities (e.g., yachting) or holidays (e.g., Halloween and Christmas). Appendix B studies the impact of these monthly similarity patterns on the distribution of quantization assignments.

In this experiment, we investigate the distribution of the nearest neighbors results over predefined time periods. We consider queries $\Phi_{i}$ for month $i$ and search exact top-k (k${=}10$) results in $\Phi_{i-1}\cup...\cup\Phi_{i-m}$ ($m{=}12$ for VideoAds and $m{=}36$ for YFCC). Figure 5 shows how many of the $\lvert\Phi_{i}\rvert{\times}k$ nearest neighbors come from each of the $m$ previous months for a few settings of the reference month $i$. We observe that recent content occurs more often in the results for both datasets. Also, for YFCC, there is a clear seasonal trend, i.e. content from the same season in years before is more likely to be returned. This hints at a drift because if the vectors were temporally i.i.d. search results would be equally likely to come from all previous $m$ months.

The evaluation protocol follows a common use case, where the most recent content is used as query data against a backlog of older content.

Over time, the index content is updated using a sliding window with a time step 1 month: at each month, we remove the data for the oldest month and insert the data for the next month. The queries are a random subset of 10,000 vectors for the month ${j+m}$. This setting mimics the real-world setting when queries come after the index is constructed.

In this section, we investigate the robustness of static indexes of the IVF family. Graph-based indexes [46, 20] are not in the scope of this study because they don’t scale as well to billion-scale datasets. The components of an IVF index are (1) the codec that determines how the vectors are encoded for in-memory storage (2) the coarse quantizer that determines how the database vectors are clustered.

Table 2 reports the 10-recall@10 for various DCS budgets representing different operating points. We experiment with different index settings for VideoAds and YFCC, due to their size difference. The content drift has a significant impact in these experiments. We investigate the effect of different window sizes $m$ in Appendix C.

For billion-scale datasets, the vectors stored in the IVF are compressed with codecs, see Section 4.2. However, DeDrift-Split needs to access all original embeddings (e.g. from external storage). Besides, DeDrift-Lazy needs to update centroids using the original vectors. Reconstructed vectors could be used but this significantly degrades the performance of the DeDrift variants (see Appendix H). A workaround for DeDrift-Lazy is to store just a subsampled set of training vectors. There is no such workaround for the other methods: they must store the entire database, which is an operational constraint.

First, we consider DeDrift on IVF methods with uncompressed embeddings. We consider the quantizer is updated every 1, 2, 3 or 6 months to see how long it can be frozen without perceptible loss in performance.

Along with the recall, we measure the average index update time. The IVF contain $K=16384$ centroids for VideoAds and $K=4096$ for YFCC (accounting to the different numbers of vectors within $m{=}3$ months).

Figure 6 shows that DeDrift-Split improves the search performance especially for low DCS budgets, while it is $160{\times}$ (resp. $250{\times}$) more efficient than the index reconstruction (Full) on YFCC (resp. VideoAds). DeDrift-Lazy significantly outperforms DeDrift-Split on both datasets and all DCS budgets, and is still $70{\times}$ (YFCC) and $170{\times}$ (VideoAds) faster than Full. DeDrift-Hybrid further improves the DeDrift-Lazy performance for low DCS.

Overall, DeDrift almost reaches Full on YFCC and significantly reduces the gap between Full and None on VideoAds. e.g., on YFCC, the proposed method provides $5.4\%$, and $1.3\%$ gains for $6000$, and $30000$ DCS budgets, respectively. DeDrift is about two orders of magnitude cheaper than the full index reconstruction.

In Appendix I, we evaluate Full with evolving k-means [9] which adapts the k-means algorithm to the drift. This provides slightly higher recall on both datasets. However, the update costs are similar to the full index reconstruction.

Hyperparameters. We vary crucial parameters for the DeDrift variants. For DeDrift-Split, we consider $k{=}8$ and $k{=}64$ clusters for the YFCC and VideoAds datasets, respectively. Higher $k$ values usually lead to slightly better recall rates at the cost of noticeably higher index update costs. DeDrift-Lazy performs a single centroid update at a time. Appendix D shows that more training iterations tend to degrade the performance. We hypothesize that further training moves the centroids too far away from the vectors already stored to represent them accurately.

We investigate the index robustness to outlier content that occasionally occurs in real-world settings. When starting experiments on the YFCC dataset, we observed bursts of images of uniform color. It turns out these are placeholders for removed images. For the previous experiments, we removed these in the cleanup phase.

To assess DeDrift’s robustness, we add these images back to the YFCC dataset and repeat the experiments from Section 6.1. Table 3 shows results for September 2012 (month with the largest None-Full gap): DeDrift-Lazy significantly degrades compared to all methods, including no reindexing (None). In contrast, DeDrift-Split and DeDrift-Hybrid prevent the performance drop, Hybrid is comparable to the full index update (Full). This shows DeDrift-Split makes indexes robust to abnormal traffic.

We evaluate indexes with PQ compression. We consider OPQ [21] with $32$ bytes per vector. We evaluate two settings: quantize either original embeddings (direct encoding) or their residuals w.r.t. the nearest centroid in the coarse quantizer (residual encoding). Results for the VideoAds dataset are in Table 4 (see Appendix F for YFCC).

The “residual encoding” is more sensitive to the content drift. Notably, DeDrift-Lazy demonstrates significant improvements over no reindexing: $+3.7\%$ and $+1.4\%$ absolute for $6000$ and $30000$ DCS budgets, respectively. DeDrift-Split also outperforms None but the gains are less pronounced compared to DeDrift-Lazy. DeDrift-Hybrid does not boost DeDrift-Lazy further in most cases.

Discussion. DeDrift significantly reduces the gap between full index reconstruction and doing nothing. DeDrift-Lazy is a key component that brings the most value. We consider it as the primary technique. DeDrift-Hybrid demonstrates that DeDrift-Split can be complementary to DeDrift-Lazy and boost the index performance for low DCS budgets even further. Moreover, the Split variant offers a level of robustness against sudden changes in the dataset distribution.