Approximate nearest neighbor (ANN) search on high-dimensional vector data is core functionality in an increasing number of real-world applications. However, most existing methods only focus on accelerating search by means of indexing that assumes that the data is static. The few methods capable of contending with dynamic data often face challenges such as decreased query accuracy following updates and low update efficiency. In this study, we propose Wolverine, the first proposal that, to our knowledge, enables efficient monotonic search path repair, thereby solving the graph-based ANN index update problem. Wolverine repairs disrupted monotonic search paths by adding in-edges to the out-neighbors of a point to be deleted. To improve efficiency, Wolverine+ restricts the search space to be within the 2-hop neighbors of the point to be deleted. In addition, Wolverine++ employs a sophisticated candidate selection policy to find high-quality candidates in the reduced search space, simultaneously improving accuracy and efficiency. An experimental study on 9 real-world datasets demonstrates that Wolverine is capable of accelerating the deletion throughput by up to 11X and achieving more stable recall during updates compared to the state-of-the-art dynamic ANN search method.

Subsequence anomaly detection for time series is a crucial problem in various real-world applications. However, existing methods proposed so far design the anomaly score functions solely based on either local neighborhood or global patterns, leading to unsatisfactory detection accuracy. In addition, these methods either cannot adapt, or yield insufficient accuracy and efficiency in streaming scenario. Therefore, we propose Sirloin, an accurate and efficient streaming time series subsequence anomaly detection framework. First, Sirloin proposes a glance and focus anomaly score function that takes both global and local information into consideration, contributing to an accurate anomaly detection. Second, Sirloin dynamically maintains an inverted file index and product quantization codebooks to index and compress the subsequences, hence is able to cope with the time series evolution and to process streaming batches efficiently. In addition, a dual index optimization strategy is put forward that further improves the efficiency. An experimental study in 11 different datasets from 5 domains offers insight into the performance of Sirloin, showing that it improves throughput on average 4x and enhances accuracy 58.02% compared to the state-of-the-art streaming method.

Approximate nearest neighbor (ANN) search in high-dimensional space plays an essential role in a variety of real-world applications. A well-known solution to ANN search, inverted file product quantization (IVFPQ) adopts inverted files to avoid exhaustive examination and compresses vectors using product quantization to reduce the space overhead. However, existing implementations use the same fixed probing cardinality (i.e., the number of cells to probe) setting for all queries, which leads to too many or too few cell examinations, thus increasing the average query latency or reducing the recall. To achieve a better trade-off between latency and accuracy, we enable probing cardinality estimation for high-dimensional ANN search by using deep learning techniques. We develop HBK-means, a hierarchical balanced clustering algorithm that reduces the data distribution imbalance of cells to enable a better estimation. Next, we develop PCE-Net, an encoder-decoder based neural network for estimating query-dependent minimum probing cardinality. In addition, we introduce two query optimization strategies: lower bound sorting based pruning (LBS-Pruning) and early termination (ET), to further reduce query latency. Extensive experiments with real-world data offer evidence that the proposed solution is capable of achieving better performance than IVFPQ and its variants.