{'fraction_non_alphanumeric': 0.03872288656122964, 'fraction_numerical': 0.016676063024836058, 'mean_word_length': 4.478218465539662, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Proximity Graph Maintenance for Fast Online Nearest Neighbor Search

Approximate Nearest Neighbor (ANN) search is a fundamental technique for (e.g.,) the deployment of recommender systems. Recent studies bring proximity graph-based methods into practitioners' attention -- proximity graph-based methods outperform other solutions such as quantization, hashing, and tree-based ANN algorithm families. In current recommendation systems, data point insertions, deletions, and queries are streamed into the system in an online fashion as users and items change dynamically. As proximity graphs are constructed incrementally by inserting data points as new vertices into the graph, online insertions and queries are well-supported in proximity graph. However, a data point deletion incurs removing a vertex from the proximity graph index, while no proper graph index updating mechanisms are discussed in previous studies. To tackle the challenge, we propose an incremental proximity graph maintenance (IPGM) algorithm for online ANN. IPGM supports both vertex deletion and insertion on proximity graphs. Given a vertex deletion request, we thoroughly investigate solutions to update the connections of the vertex. The proposed updating scheme eliminates the performance drop in online ANN methods on proximity graphs, making the algorithm suitable for practical systems.


Introduction
Approximate Nearest Neighbor (ANN) search is a fundamental problem with wide applications in recommendation systems, search engine, and advertising (Pazzani and Billsus, 2007;Vanderkam et al., 2013;Xu et al., 2018b;Fan et al., 2019;Tan et al., 2020bTan et al., , 2021bYu et al., 2022). Given a query vector q and a dataset D, the goal of ANN search is to find a vector p ∈ D that minimizes metric distance f (p, q) with sub-linear time complexity. Here, f represents a distance measure, e.g., Euclidean distance, cosine, Jaccard, GMM (generalized min-max) (Li, 2018) etc. The research on ANN dated back to the early days of computer science, i.e., KD-tree algorithms (Friedman et al., 1975(Friedman et al., , 1977. Even recently, tree-based methods are still active research topics (Lin et al., 1994;Berchtold et al., 1996;Zezula et al., 1998;Sakurai et al., 2000;Ram and Sinha, 2019). Another popular line of research on ANN is based on hashing, including random sampling, (Gaussian and non-Gaussian) random projections, minwise hashing, consistent weighted sampling, extremal process, etc. (Broder, 1997;Broder et al., 1998;Indyk and Motwani, 1998;Gionis et al., 1999;Charikar, 2002;Datar et al., 2004;Li and Church, 2005;Weiss et al., 2008;Shrivastava and Li, 2012;Wei et al., 2014;Liong et al., 2015;Gao et al., 2015;Shen et al., 2015;Li and Zhang, 2017;Li, 2019;Li et al., 2021). Quantization-based ANN methods are also commonly used (Jégou et al., 2011a;Ge et al., 2013;Zhang et al., 2014;André et al., 2015;. In this paper, we focus on graph-based ANN methods (Paredes and Chávez, 2005;Hajebi et al., 2011;Malkov et al., 2014;Morozov and Babenko, 2018;Fu et al., 2019;Malkov and Yashunin, 2020;Zhao et al., 2020;Tan et al., 2021a), which have successfully demonstrates their impressive empirical performance. Graph-based ANN search methods share the spirits with idea of six degrees of separation (Karinthy, 1929;Guare, 1990;Kleinberg, 2000). The general paradigm of these methods can be summarized as two steps: First, we index the dataset as a proximity graph G, where every vertex represents a data vector and every edge connects two "close" vertices. Then, we walk on G towards the query q to obtain its nearest neighbors: we maintain a priority queue that stores the searching vertex candidates. In each search step, we extract the vertex that is closest to q from the priority queue and push all unvisited neighbors of the vertex into the priority queue for the future search steps. The proximity graph indexing is constructed in a bootstrap manner. We insert data vectors as new vertices incrementally. Each time a new vertex is inserted, we query on the existing graph index to obtain its nearest neighbors from the priority queue and create edges between them.
However, graph-based methods do not support ANN search in online settings due to the lack of vertices update mechanism. In real-world applications, the online ANN search means that the dataset D is updated by deletion and insertion for a period of time. For instance, in sponsored search systems for online advertising, the deep Click-Through Rate (CTR) prediction models (Dave and Varma, 2010;Fan et al., 2019;Yu et al., 2022) learn user vectors and Ad vectors and measure them by cosine distance to predict the final CTR. Given a user vector, ANN search is applied to retrieve ad vectors that minimize their cosine similarity. Due to the dynamic changes of sponsored items over time, the online Ads systems will update the ad vectors by deleting the expired Ads and inserting the recently arrived Ads. In these settings, although the incremental vertex insertion construction algorithm of graph-based algorithm can handle the upcoming Ads vectors, there is no specialized design for removing expired vertices on graph. If we preserve the vertices of expired Ads on the graph, the search precision and efficiency will drop because a branch of time is wasted in visiting and ranking useless vertices. If we remove these vertices as well as their edges, the connectivity of the graph will be broken, which will also cause inefficiency in the search phase. There are few literatures on the graph-based online ANN search approaches. Therefore, when graph-based methods are deployed in online systems, a periodical reconstruction of indexing graph is inevitable. As re-indexing the large scale datasets scales as O(n log(n)) (Malkov et al., 2014), which increases the computation and memory cost for online services.
To address those challenges, this paper studies online ANN search with graph-based indexing methods. We imitate the real-world settings by incrementally performing insertion and deletion in given ANN search vector sets. To dynamically handle the changes in data distribution, we propose an incremental proximity graph maintenance (IPGM) algorithm that supports online insertion and deletion of vertices on graph, which enables the indices update when the distribution of data is evolving periodically.
Summary of main contributions: Firstly, we formally define the proximity graph maintenance problem and theoretically prove the feasibility of incremental updates on proximity graphs. Then, we propose an online graph maintenance framework and 4 novel proximity graph update strategies that maintain proximity graph properties when deleting vertices. Massive experimental evaluations on public datasets confirm the effectiveness-our recommend global reconnection algorithm outperform the reconstruction baseline in query processing speed by a maximum factor of 18.8%.

Graph-based ANN Search
Graph-based ANN search methods (Paredes and Chávez, 2005;Hajebi et al., 2011;Malkov et al., 2014;Morozov and Babenko, 2018;Fu et al., 2019;Malkov and Yashunin, 2020;Zhao et al., 2020;Tan et al., 2021a) have received considerable research attention. Most ANN search scenarios studied by these papers are static. In the experiments section, the graph-based methods are compared with other ANN search methods on a fixed dataset such as Sift (Jégou et al., 2011a) or Glove (Pennington et al., 2014). In recommendations systems, one of the core tasks is: given a user embedding, to find relevant item embeddings. This is usually realized by learning an auxiliary data structure concurrently with learning item embeddings (Zhu et al., 2018Zhuo et al., 2020;Gao et al., 2020;Yu et al., 2022). (Tan et al., 2020a(Tan et al., , 2021b discover that graph-based ANN techniques can be leveraged on complex neural network similarity measure, i.e., user-item matching score, to efficiently retrieve recommendation candidates. However, in current ANN applications like feed-in Ads recommendation (Fan et al., 2019), the distribution of dataset (e.g., product vectors) changes over time due to the activation and expiration of products. Few works addressed this problem except Singh et al. (2021). Therefore, modification to graphbased methods for online manner is essential for filling their gap with practical usage. However, as the insertion or deletion of vertex on graph breaks its topology, direct modification of graph-based methods for online manner is challenging due to the unaffordable computational cost.

Online ANN Search
Besides graph-based ANN methods, some ANN methodologies can be modified for online settings, such as hashing methods and quantization methods. However, their shortcomings lie in the lower speed during the search phase. Ghashami and Abdullah (2015); Leng et al. (2015); Cakir et al. (2017) modify the supervised hashing algorithms to accommodate the sequential inputs. These online hashing models achieve promising results in handling sequential input vectors. However, these online hashing requires expensive and infeasible labeling for each data vectors in real-world systems. Meanwhile, these online learning paradigms do not support the expired data vectors removal.
For quantization methods, the main challenge is to update the codebook according to the change of data distribution in database. In online settings, the changes in the distribution in database require expensive re-computation of codebook and codewords. To tackle this issue, Xu et al. (2018a) propose a PQ approach that supports data insertion and deletion by updating the codebook without changing the codewords of existing vectors in the database. This online PQ method achieves promising results in sliding window settings.

Problem Statement
Formally, the ANN search problem is defined as follows: Problem 1 (ANN Search). given a dataset D and a query vector q in Euclidean space R d we aim at efficiently computing (1) Here, we discuss metric similarity such as f (x, q) = − x − q , which minimizes the Euclidean distance, or f (x, q) = x T q x q , which maximizes the cosine similarity. In most real-world datasets, linear scan is infeasible to solve this problem because |D| d. To remedy this issue, we index D as a proximity graph G = (D, E), where each vertex represents a x i ∈ D and each pair (x i , x j ) indicates the connection between vertices. Given each q, we find the solution of Eq. (1) by walking on G. As a walking path only covers a fraction of vertices on G, the speed for solving Eq. (1) is accelerated at the expense of precision.
For metric similarities that satisfy triangle inequality, an efficient proximity graph G usually approximates Delaunay graph, which is defined by Voronoi cells.
Definition 1. For fixed x i ∈ D ⊂ R d and a given function f , the Voronoi cells R i is defined as Voronoi cells determine the solution of Eq. (1). We observe that, x j ∈ arg max x i ∈D f (x i , q) if and only if q ∈ R j . The Delaunay graph is the dual diagram of Voronoi cells, which is given by the following definition.
Definition 2. For fixed function f and dataset D ⊂ R d , and given Voronoi cells R i , i = 1, 2, . . . , n w.r.t. f and D, the Delaunay graph of D is an undirected graph G with vertices {x i ∈ D}, and the For graph-based ANN search problem, the guarantee of finding the optimal solution for Eq. (1) on Delaunay graph is given in Theorem 1, with proof provided in Morozov and Babenko (2018).
Theorem 1. For given metric similarity f , we assume for any dataset D, each the Voronoi cell R i is a connected. Let G = (D, E) be the Delaunay graph w.r.t. the Voronoi cells. Then for any q ∈ R d , greedy search on Delaunay graph returns the solution of (1). In other words, let For large scale dataset, the computation cost of constructing and storing both Voronoi cells and Delaunay graph are unaffordable. The performance of proximity graphs in ANN search depends on their approximation to Delaunay graph.
In this work, we discuss the maintenance of G in online settings, where the ANN search problem becomes: . . , T }, and a query vector q in Euclidean space R d we aim at efficiently computing Here, D i ∩ D i+1 = ∅ indicates the possibility of data insertion and deletion in each step. Start from proximity graph G 1 that approximates Delaunay graph of D 1 , our goal is to develop a proximity graph maintenance algorithm update(G,

Incremental Proximity Graph
We first theoretically prove that deletion a vertex on Delaunay Graph only requires update of the removed vertex's neighbors' connections. Based on this insight, we propose a high-level incremental proximity graph maintenance framework for online update settings.

Theoretical Analysis
In this section, we prove that we only require to update the edges of the deleted vertex's neighbors to maintain the properties of Delaunay graph-the incremental graph maintenance is feasible in online settings. Given the Delaunay graph G of vertices S, suppose we remove an vertex x 0 from S, and 1. suppose x ∈ D is not a neighbor of x 0 in G, then the neighbors of x in the new Delaunay graph (corresponding to S\{x 0 }) remains the same as the ones in the old G.
2. suppose x ∈ D is a neighbor of x 0 in G, then it's incident edges except {x, x 0 } remains existing in the Delaunay graph.
These properties are rigorously stated in the following theorem. Given a graph G, G is a Delaunay graph or contains Delaunay graph as subgraph, we demonstrate that 1. If a vertex x i is removed from G, G still contains a Delaunay graph if we update the connections of N (x i ).
2. If a vertex x i is inserted to G, G still contains a Delaunay graph if we set up N (x i ).
Theorem 2. Let f be continuous function such that for any datasets, every Voronoi cell is nonempty and connected. Let G and G be the Delaunay graphs corresponding to data points D = {x 0 , . . . , x n } and D = {x 1 , . . . , x n } = D\{x 0 }. Let N (x i , G) and N (x i , G ) be the set of neighbors of x i on graph G and G respectively, then (a) for all removing x 0 and its the incident edges from G, the resulting graph is a subgraph of G .
Proof. (a) We consider two cases. Firstly is connected, there exists a path c : [0, 1] → R x i (D ) connecting q and q . Considering the function we have By continuity of f and intermediate value theorem, there exists t * ∈ [0, 1] such that g(t * ) = 0.
It was demonstrated in Navarro (2002) that greed search on proximity graph is guaranteed to find the exact nearest neighbor for every given query. However, it is computationally infeasible to build exact Delaunay Graph in high-dimensional data because the number of edges grows exponentially as the scale of dataset increases (Beaumont et al., 2007). A typical solution towards this issue is to approximate Delaunay Graph and trade accuracy for significant efficiency improvements. Practical applications employ the proximity graph as an approximation of the Delaunay graph. Therefore, we focus on the incremental maintenance on proximity graphs in this paper.

High-Level Proximity Graph Maintenance
In this section, we introduce our high-level incremental proximity graph maintenance algorithm (Algorithm 3).
In each state of the workload, we approximate the Delaunay Graph via a directed proximity graph, where each vertex have edges pointed to its neighbors, namely out-neighbors. We use W o i is the type of the operations-namely query, insert, or delete-and x i is the corresponding vectors.
Query. Querying operation is performed by executing the greedy search on the proximity graph G. The algorithm for greedy search is present in Algorithm 1. Given a query vector q and a graph G, the algorithm first chooses a vertex x s randomly on G. Starting from x s , q walks on G. During the walking, we preserve a priority queue where the vertex that maximizes the measurement function f is on top of the queue. For every visited vertex x, we push its out-neighbors in the queue after calculating their similarity with q.
Algorithm 1: GREEDY-SEARCH(G, q, k, Y ) 1: Input: graph G = (D, E), query vector q, candidate size k, removed vertices Y . 2: Initialize the priority queue by random sampling, S ← top-k vectors in S that has the largest value of − x − q . We place them in a descending order. 7: end if 8: while ∃x ∈ D unvisited and S do 9: Mark S as visited.

11:
if |S| > k then 12: S ← top-k vectors in S that has the largest value of − x − q . We place them in a descending order. if o i = query then 5:

9:
for z ∈ N do 10: Add edges (x i , z) to G and (z, x i ) to G .
Insertion. When o i is inserted, we perform a greedy search on G to obtain x i 's Top-K neighbors (same as in the query phase). We then extract the vertex from the queue as the start point for next search step. When the walking stops, we select the Top-K vertices in the queue to return. The next step is to select the Top-K neighbors of x i found on G and set connections in G and G . Here we adapt the edge selection algorithm (Malkov et al., 2014) (Algorithm 2). After the selection, x i 's outgoing vertices are its nearest neighbors in diverse directions.
Deletion. If o i is delete and x i ∈ G, we start the vertex deletion and graph update process. For every expired vertex x i , we first obtain its incoming vertices on G, by the prepared reversed graph G . Let N (x i ) be the in-neighbors of vertex x i (the vertices that points to x i in G). DELETE-UPDATE-EDGES updates the edges of N (x i ) to maintain the proximity graphthe nearest neighbors can be retrieved from the updated graph by the greedy searching algorithm. Besides, the reverse graph G is updated according to G.
A sub-optimal updating algorithm reduces the connectivity of the proximity graph and hence the greedy searching cannot locate accurate nearest neighbors. In the online settings, the deletion operation is called regularly in the workload-the disadvantage of sub-optimal updating algorithms are magnified. Therefore, we delve into the design and implementation of the DELETE-UPDATE-EDGES algorithm in the following paper.

DELETE-UPDATE-EDGES Algorithms
We investigate online proximity graph deletion algorithms in this section. We begin with straightforward solutions and then keep refining the update algorithm step by step.

Pure Delete
The most straightforward delete operations for proximity graph update is to remove the vertex as well as its connections. Here we demonstrate our pure deletion algorithm in Algorithm 4 and Figure 1 (b). Given a deleted vertex x i , we first obtain its out-neighbors and in-neighbors. For each out-neighbor x j , we remove edge (x i , x j ) on proximity graph G and (x j , x i ) on the reverse proximity graph G . For each in-neighbor x k , we remove edge (x k , x i ) on proximity graph G and Algorithm 4: PURE-DELETE(x i , G, G , f, d) 1: Input: deleted vertex x i , proximity graph G and its reverse graph G , measurement function f , maximum outgoing degree of graph d.
Remove (x k , x i ) in G and (x i , x k ) in G 9: end for 10: Output: G, G .
(x i , x k ) on the reverse proximity graph G . Pure deletion breaks the connectivity of the proximity graph, which may lead to the fail of greedy search as the path towards the exact nearest neighbors are blocked.

Vertex Masking
To tackle the preserve the connectivity challenge in the Pure Deletion method, one straightforward solution is to mask the deleted vertices as "deleted" and push it into Y in Algorithm 1. When we perform a greedy searching, the "deleted" vertices are still visited. However, we do not push the "deleted" vertices into the result priority queue-the visited "deleted" vertices are not counted as top-K candidates. The connections of the vertices in the graph are unchanged. We illustrate this method in Figure 1 (c).
One advantage of the masking method is that the connectivity of the original proximity graph is preserved and the expired vertices are still useful for guiding the greedy search. However, the disadvantages are still obvious. First, after masking, the search space for each query is large and unnecessary. The visit to expired vertices slows down the greedy search speed. Second, as all expired vertices are still stored, space grows continuously as the stream performs, which may cause inevitable memory issues.

Local Reconnect
To remedy the connectivity of the proximity graph while reducing the useless visit in the search phase, another solution is to reset local connections between the in-neighbors and out-neighbors of deleted vertex. The local reconnect algorithm is presented in Algorithm 5 and Figure 1 (d). For each expired vertex x i , we first acquire its in-neighbors N (x i ) from G and out-neighbors N (x i ) from G. Then, for each in-neighbor x j , we remove the edge from x j to x i in G and G . The last step is to select the most diverse vertex z for x j from N (x i ) and set out-going links from x j to z.
The idea of local reconnect is to compensate an edge for the in-neighbors of deleted vertex. According to the nearest neighbor expansion, the out-neighbors of expired vertex x i may be the neighbors of x j ∈ N (x i ). However, as the proximity graph is an approximation to real Delaunay Graph, out-neighbors of x i may not be x i 's exact nearest neighbors. Therefore, the compensated edge may still not be good.
Algorithm 5: LOCAL-RECONNECT(x i , G, G , f, d) 1: Input: deleted vertex x i , proximity graph G and its reverse graph G , measurement function f , maximum outgoing degree of graph d.
Add edges (x j , z) to G and (z, x j ) to G 10: end if 11: end for 12: Output: G, G .
Algorithm 6: GLOBAL-RECONNECT(x i , G, G , k, f, d) 1: Input: deleted vertex x i , proximity graph G and its reverse graph G , priority queue length k, measurement function f , out-neighbor degree threshold d.
for z ∈ N do 8: Add edges (x j , z) to G and (z, x j ) to G .

Global Reconnect
To compensate the in-neighbors of deleted vertices with better edges, we propose a global reconnection algorithm for proximity graph update. The algorithm is presented in Algorithm 6 and Figure 1 (e). For each expired vertex x i , we first acquire its in-neighbors N (x i ) from G and out-neighbors N (x i ) from G. After that, for every element x j in N (x i ), we perform greedy search to obtain its nearest neighbors C on graph G. Then we use SELECT-NEIGHBORS function to select the vertices set N from Z to fit the regulation for graph degree d. Finally, we remove all the previous connections of x j and reset edges by vertices in N .
The general idea behind this deletion method is to treat each in-neighbor x j of the expired vertex as a new vertex and reset x j 's connections by re-inserting it on proximity graph. In this way, x j has an opportunity to improve its connection by re-selecting vertices globally, Therefore, the proximity graph may become a better approximation to Delaunay Graph. The disadvantage is the updating time cost. however, it can be amortized by the number of query operations. In real-world recommendation systems or search engine, the number of queries(users) may be much larger than the number of data(Ads, items) and one query may occur in high frequency. Thus, this deletion method may outperform peers in online graph-based ANN search.

Experiments
The objective of the experimental evaluation is to investigate the performance of our update algorithms on real datasets. The performance includes both the quality and efficiency of the retrieving top-K candidates and the execution time for indexing and searching. Specifically, we target to answer the following questions: • Does the proposed global reconnect algorithm improve the performance of the proximity graph?
How does it compare with other graph update algorithms?
• Does the proposed global reconnect algorithm robust to different update patterns? How is the proposed algorithm and baselines perform in different update patterns?
• Does the proposed global reconnect algorithm reduce the total execution time for insertion, deletion, and query?
Implementation. We implement the update algorithms as a C++11 prototype and compile the code with g++-5.4.0 and "O3" optimization. The implementation in Zhao et al. (2020) is employed as the proximity graph searching algorithm. The code contains special functions to harness detailed profiling data.
Hardware System. We execute the experiments on a single node server. The server has one Intel(R) Core(TM) i7-5960X CPU @ 3.00GHz (64 bit). It has 8 cores 16 threads, and 32 GB memory. Ubuntu 16.04.4 64-bit is the operating system.
Retrieval Recall. In this paper, we use recall to measure the quality of search, which is defined as the ratio of retrieved correct items over the total correct items. The increase in recall relates to higher quality.
Data. We use 4 real ANN benchmark datasets for experiments: SIFT (Jégou et al., 2011b), GloVe200 (Pennington et al., 2014), NYTimes (Dua and Graff, 2017) and GIST (Sandhawalia and Jégou, 2010). The dimension of vectors in these datasets are 128,200,256 and 960. The NYTimes contains 280, 000 vectors while others contain 1, 000, 000 vectors. We have a diverge distribution of the datasets-GloVe200 and NYTimes are more skewed compare to others.
Workload. For each of the 4 ANN datasets, we build 10 step workloads. Given the base set, each step of the workload removes a set with 10,000 vectors and then digests an set with 10,000 vectors. After that, a query set of 10,000 vectors are fed for top-K ANN search. In this case, the size for base set in NYTimes is 180,000 while other sets are 900,000.
We consider two update patterns in the experiments: (a) Random updates: we permute the whole data set before partition. Each vector of base, delete, insert and query set is randomly selected from the original dataset. (b) Cluster updates: we perform 10 class K-means clustering on the whole dataset. Then we place the clusters in a sequence and build base, delete and insert sets in the order of this sequence. Therefore, each step we remove several clusters of vectors on graph. And then insert several clusters.
Methods. The 4 proposed algorithms are abbreviated as PURE, MASK, LOCAL and GLOBAL. We also include ReBuild, which reconstructs the whole graph in each update batch before query.

Query Time
In this section, we present the query efficiency for our proposed algorithms and baseline. In Figure 2 and Figure 3, we plot relative queries processed per second (QPS) versus the query batches of workloads from 3 ANN datasets. The queries processed per second (QPS) versus the query batches of workloads of GIST dataset is also presented at Figure 3. In each workload, we follow the pattern described above. Here the relative QPS is the result of real QPS divided by the QPS of ReBuild algorithm in 0.8 Top-10, Top-20 or Top-100 recall.

Random updates
The results in Figure 2 demonstrate that global reconnect achieves superior performance than other delete-update-edge algorithms. For each dataset, the QPSes of different methods start at the same point in query batch 0, which means that they have the same performance when doing ANN search on the base set without an update. Then, as the batch increases, we observe that our global reconnect algorithm has higher QPS than other incremental update methods. In SIFT dataset, the global reconnect algorithm even outperforms reconstruct graph in QPS at 0.8 Top-10 recall. The same phenomenon also happens in GloVe200 dataset and GIST dataset. For baseline methods, local reconnect achieves the best performance. Pure deletion algorithm has a QPS drop as batch increases, which means the proximity graph becomes inefficiency due to the broken of connectivity. The vertex mask method achieves the lowest QPS in every batch, illustrating that unnecessary visits of expired vertices significantly influence the performance of ANN search on proximity graph.

Clustered updates
The results in Figure 3 demonstrates the superior performance of global reconnect algorithm in workloads with clustered updates. Similar to Figure 2, global reconnect achieves the best QPS in each batch at 0.8 Top-10, Top-20 or Top-100 recall. In the clustered updates settings, we delete some vectors and their nearest neighbors in each update step. Therefore, for vectors located near to these clusters, a large fraction of their nearest neighbors are also deleted. To update their connections, it requires global search on graph to find new nearest neighbors.
Different from random updates, in clustered updates, we observe that our global reconnect algorithm outperforms graph reconstruction in almost all scenarios. Since the graph is constructed incrementally-new edges of an inserted vertex are connected based on the existing vertices, those edges do not accurately reveal the exact nearest neighbors. Our global reconnect algorithm updates edges based on the entire graph. The edges in the graph are refined during the updates-thus, a better performance than the reconstruction is observed.

Overall Execution Time
To evaluate the execution time of our proposed global reconnect algorithm and other baselines, we plot the accumulated time versus the number of operations. The accumulated time grows as the number of operations increases. Lower plot in the figure represents less workload execution time and better performance. In this experiments, we consider two major characteristics of real-world scenarios. First, embedding vectors of different usernames, are a much larger group than the online product embeddings. Therefore, the number of queries may be greater or equal to the number of vectors in database. Second, one single user may look for products several times within an hour. Thus, one query vector may be executed hundreds of times. Combining this two features, we modify the original workload for SIFT. Given 900k base vectors, in every step of the workload, we remove 10k vectors and insert the same amount of vectors, but query with 200k, 1 million or 20 million vectors. The query set is obtained by duplicating original 10k query set. Plots for these 3 workloads corresponds to sub-figures from left to right in Figure 4. In Figure 4 on the left, we show that if we query 200k vectors per batch. Graph reconstruction has the highest time cost because the time cost introduced by reset all vertices on graph. Then, the vertex masking is also time inefficient. Although it deletes vertices in the fastest way, the significant QPS drop in query phase makes it time-consuming. The global reconnect, local reconnect and pure deletion have similar total execution time. Global reconnect and local reconnect have higher execution time due to the cost introduced by reconnection. Then, as the number of queries per batch increases, we observe that our global reconnect algorithm achieves the lowest total execution time.
This phenomenon validates the assumption that the updating time cost can be amortized by the time saved by efficient ANN search. The same compensation effect is also observed in graph reconstruction and local reconnect. As the number of queries increases each batch, the total execution time of graph reconstruction outperforms vertex masking and becomes closer to pure deletion. The performance of local reconnect also improves as the margin between it and pure deletion increases when we have more queries. Therefore, in real-world applications that require online ANN search. Given the large amount of query requests, the proposed IPGM framework outperforms static proximity graph based methods due to the advantages taken in each search phase. Meanwhile, IPGM reduces the latency of data deletion by avoiding reindexing the whole dataset as a graph in each step.

Further Discussions
• To obtain a level of recall at 0.8, the proposed global reconnect algorithm improves the performance of incremental proximity graph in online ANN search by a factor of 10.6% on average. In some scenarios, global reconnect algorithm also outperforms graph reconstruction by a maximum factor of 18.8%.
• The proposed global reconnect algorithm is robust to random update pattern and clustered update pattern. In clustered update when we delete a vector and its nearest neighbors together, the global reconnect algorithm is a better way to maintain a good approximation to Delaunay Graph.
• Our proposed global reconnect algorithm reduces the total execution time when the number of queries increases. In real-world settings where the number of queries and data vectors are at the same level, our method has the fastest execution time compared to other methods.

Conclusion
Graph-based ANN search methods index the dataset as proximity graph and has shown superiority over other ANN search approaches. However, the inefficiency of proximity graph against incremental data vector insertion and deletion prevents it to be used in large-scale online ANN search. This paper presents a proximity graph maintenance algorithm for online ANN search. We define the incremental proximity graph update problem formally and give theoretical proofs to demonstrate the feasibility of incremental vertex insertion and deletion on the proximity graph. We propose 4 proximity graph update algorithms to preserve the advantages of proximity graph in ANN search when vertices are removed from the graph in different patterns. The experiments on 4 public ANN datasets show that our proposed algorithms outperform the reconstruction baseline by a maximum factor of 18.8%. The proposed updating scheme eliminates the performance drop in online ANN methods on proximity graphs, which enables the deployment in real-world search engines and recommendation systems.