# A Novel Approach to Incremental Diffusion for Continuous Dataset Updates in Image Retrieval
## 6 Complexity Analysis  
In this section, we discuss the computational complexity to give a quantitative comparison in terms of efficiency between our proposed method and previous ones. Specifically, we mainly compare two typical diffusion approaches, namely online diffusion [4] and offline diffusion [5]. Here, online and offline are delimited by the start of the search.  
As pointed out by [5], the downside of online diffusion is that it requires graph construction for every query image during runtime. Apart from the cost of the nearest neighbor search, the graph construction itself costs \(\mathcal{O}(LK)\) time, where \(L\) is the number of gallery images to be considered and \(K\) is the maximum number of nearest neighbors to whom each node can be connected. In addition, the time complexity of the random walk process implemented by an early-terminated conjugate gradient (CG) is \(\mathcal{O}(LK\tau)\), supposing CG is iterated for \(\tau\) times on average. In contrast to online diffusion, offline diffusion makes the graph construction and the random walk independent of the query and moves these steps offline. As a result, the online computational cost of offline diffusion is trivial. Our proposed method inherits this advantage and takes one step further: the cost to obtain \(\mathbf{S}_{cq}\) in Equation (13) is linear to the number of anchors and thus is much less than the cost to obtain \(\mathbf{S}_{gt}\) in Equation (7).  
Although the offline computation does not affect the efficiency at runtime, we also discuss it for those whom it may concern. Similar to online diffusion, the overall time complexity of offline diffusion is \(\mathcal{O}(nK\tau)\), including the cost of the graph construction and random walk. In our proposed method, the cost of the counterpart is \(\mathcal{O}(kK\tau)\), as we diffuse over the anchor graph. Since the number of anchors is much smaller than the number of gallery images, i.e., \(k\ll n\), our proposed method is faster in terms of diffusion. However, the proposed method requires two additional operations: K-Means clustering and local anchor embedding. We adopt the recent K-Means implementation [23], which is sufficiently efficient for our tasks. We do not discuss its complexity, which is beyond the scope of this work. The main computational burden comes from the local anchor embedding (LAE). According to [17], the time complexity of LAE is \(\mathcal{O}(nks)\). Its cost is non-trivial given a large size of the gallery set.  
We now discuss the computational cost when new data are added to the gallery. Since there is no pre-computation in online diffusion, it does not require any additional operations to process the new data. On the other hand, the offline diffusion pre-computes the inverse of the Laplacian for the entire gallery. Therefore, once the underlying dataset changes, we have to reconstruct the graph to update the inverse of the Laplacian. This cost involves the graph construction for the updated gallery and the random walk process. Supposing the size of new data is \(\Delta n\), the overall time complexity is \(\mathcal{O}((n+\Delta n)K\tau)\), which is not trivial considering the size of gallery \(n\) is usually very large. To circumvents this inefficiency, our proposed method utilizes local anchor embedding to approximate new data by pre-defined anchors. Such a process costs \(\mathcal{O}(\Delta nks)\), where \(k\) is the number of anchors and \(s\) is the maximum number of nearest anchors used to approximate the data point.