Approximate Nearest Neighbor Search (ANNS) has become a fundamental component in many real-world applications. Among various ANNS algorithms, graph-based methods are state-of-the-art. However, ANNS often suffers from a significant drop in accuracy for certain queries, especially in Out-of-Distribution (OOD) scenarios. To address this issue, a recent approach named RoarGraph constructs a bipartite graph between the base data and historical queries to bridge the gap between two different distributions. However, it suffers from some limitations: (1) Building a bipartite graph between two distributions lacks theoretical support, resulting in the query distribution not being effectively utilized by the graph index. (2) Requires a sufficient number of historical queries before graph construction and suffers from high construction times. (3) When the query workload changes, it requires reconstruction to maintain high search accuracy. In this paper, we first propose Escape Hardness, a metric to evaluate the quality of the graph structure around the query. Then we divide the graph search into two stages and dynamically identify and fix defective graph regions in each stage based on Escape Hardness. (1) From the entry point to the vicinity of the query. We propose R eachability Fix ing (RFix), which enhances the navigability of some key nodes. (2) Searching within the vicinity of the query. We propose N eighboring G raph Defects Fix ing (NGFix) to improve graph connectivity in regions where queries are densely distributed. The results of extensive experiments show that our method outperforms other state-of-the-art methods on real-world datasets, achieving up to 2.25× faster search speed for OOD queries at 99% recall compared with RoarGraph and 6.88× faster speed compared with HNSW. It also accelerates index construction by 2.35-9.02× compared to RoarGraph.

Time series databases play a critical role in large-scale performance monitoring systems. Metrics are required to be observable immediately after being generated to support real-time analysis. However, the commonly used Log-Structured Merge-Tree structure suffers from periodically visible delay spikes when a new segment is created due to the instantaneous index construction pressure.

Commercial search engines generally maintain hundreds of thousands of machines equipped with large sized DRAM which incurs high hardware cost since DRAM is expensive. Recently, NVM Optane SSD has been considered as a promising underlying storage device due to its price advantage and speed advantage. However, to achieve a comparable efficiency performance with in-memory index, applying NVM to both latency and I/O bandwidth critical applications still face non-trivial challenges, because NVM has much lower I/O speed and bandwidth compared to DRAM. In this paper, we propose an NVM SSD-optimized query processing framework, aiming to address both the latency and bandwidth issues of using NVM in search engines. First, we propose a pipelined query processing methodology which significantly reduces the I/O waiting time. Second, we propose a cache-aware query reordering algorithm which enables queries sharing more data to be processed adjacently. Third, we propose a data prefetching mechanism which reduces the extra thread waiting time and improves bandwidth utilization. Moreover, we propose intra-query parallel mechanisms for long-tail queries, including query subtask scheduling, heap concurrent access strategy, query parallelism prediction and adaptive pipelining. Extensive experimental studies show that our framework significantly outperforms the state-of-the-art baselines, which obtains comparable processing latency and throughput with DRAM in both inter-query and intra-query parallel scenarios.

Commercial search engines generally maintain hundreds of thousands of machines equipped with large sized DRAM in order to process huge volume of user queries with fast responsiveness, which incurs high hardware cost since DRAM is very expensive. Recently, NVM Optane SSD has been considered as a promising underlying storage device due to its price advantage over DRAM and speed advantage over traditional slow block devices. However, to achieve a comparable efficiency performance with in-memory index, applying NVM to both latency and I/O bandwidth critical applications such as search engine still faces non-trivial challenges, because NVM has much lower I/O speed and bandwidth compared to DRAM.

Search engines encounter a time vs. space trade-off: search responsiveness (i.e., a short query response time) comes at the cost of increased index storage. We propose a hybrid method which uses both (a) the recently published mapping-matrix-style index BitFunnel (BF) for search efficiency, and (b) the state-of-the-art Partitioned Elias-Fano (PEF) inverted-index compression method. We use this proposed hybrid method to minimize time while satisfying a fixed space constraint, and to minimize space while satisfying a fixed time constraint. Each document is stored using either BF or PEF, and we use a local search strategy to find an approximately optimal BF-PEF partition. Since performing full experiments on each candidate BF-PEF partition is impractically slow, we use a regression model to predict the time and space costs resulting from candidate partitions (space accuracy 97.6%; time accuracy 95.2%). Compared with a hybrid mathematical index (Ottaviano et al., 2015), the time cost is reduced by up to 47% without significantly exceeding its size. Compared with three mathematical encoding methods, the hybrid BF-PEF index allows performing list intersection between around 16% to 76% faster (without significantly increasing the index size). Compared with BF, the index size is reduced by 45% while maintaining an intersection time comparable to that of BF.

Large-scale search engines utilize inverted indexes which store ordered lists of document identifies (docIDs) relevant to query terms, which can be queried thousands of times per second. In order to reduce storage requirements, we propose a dictionary-based compression approach for the recently proposed bitwise data-structure BitFunnel, which makes use of a Bloom filter. Compression is achieved through storing frequently occurring blocks in a dictionary. Infrequently occurring blocks (those which are not represented in the dictionary) are instead referenced using similar blocks that are in the dictionary, introducing additional false positive errors. We further introduce a docID reordering strategy to improve compression. Experimental results indicate an improvement in compression by 27% to 30%, at the expense of increasing the query processing time by 16% to 48% and increasing the false positive rate by around 7.6 to 10.7 percentage points.