Symmetric searchable encryption (SSE) for geo-textual data has attracted significant attention. However, existing schemes rely on task-specific, incompatible indices for isolated specific secure queries (e.g., range or k-nearest neighbor spatial-keyword queries), limiting practicality due to prohibitive multi-index overhead. To address this, we propose RISK, a model for rich spatial-keyword queries on encrypted geo-textual data. In a textual-first-then-spatial manner, RISK is built on a novel k-nearest neighbor quadtree (kQ-tree) that embeds representative and regional nearest neighbors, with the kQ-tree further encrypted using standard cryptographic tools (e.g., keyed hash functions and symmetric encryption). Overall, RISK seamlessly supports both secure range and k-nearest neighbor queries, is provably secure under IND-CKA2 model, and extensible to multi-party scenarios and dynamic updates. Experiments on three real-world and one synthetic datasets show that RISK outperforms state-of-the-art methods by at least 0.5 and 4 orders of magnitude in response time for 1% range queries and 10-nearest neighbor queries, respectively.

Approximate nearest neighbor (ANN) searches are commonly employed in various machine learning applications, such as recommendation systems, but traditional ANN searches typically involve only a single reference vector in a query. To broaden the capabilities of ANN search and support multi-reference-vector queries, thereby enabling a wider range of machine learning applications, we introduce all/any-k ANN search. They aim to find vectors that are similar to all or any of the multi-reference vectors in a query, respectively. To effectively and efficiently support all/any-k ANN search, we first propose distance metrics to evaluate the ranking of vectors among those in the dataset for exact all/any-k NN. Building on this, we introduce search algorithms and prove they can search according to the proposed distance metrics on graph indexes designed for traditional ANN. Additionally, we further introduce two-stage search algorithms for all/any-k ANN search to further enhance their search performance. We conduct extensive experiments on real-world datasets to validate the efficiency and effectiveness of our proposed algorithms compared to existing approaches.

In the era of cloud computing and AI, data owners outsource ubiquitous vectors to the cloud, which furnish approx-imate k-nearest neighbors (k-ANNS) services to users. To protect data privacy against the untrusted server, privacy-preserving k-ANNS (PP-ANNS) on vectors has been a fundamental and urgent problem. However, existing PP-ANNS solutions fall short of meeting the requirements of data privacy, efficiency, accuracy, and minimal user involvement concurrently. To tackle this challenge, we introduce a novel solution that primarily executes PP-ANNS on a single cloud server to avoid the heavy communication overhead between the cloud and the user. To ensure data privacy, we introduce a novel encryption method named distance comparison encryption, facilitating secure, efficient, and exact distance comparisons. To optimize the trade-off between data privacy and search performance, we design a privacy-preserving index that combines the state-of-the-art k-ANNS method with an approximate distance computation method. Then, we devise a search method using a filter-and - refine strategy based on the index. Moreover, we provide the security analysis of our solution and conduct extensive experiments to demonstrate its superiority over existing solutions. Based on our experimental results, our method accelerates PP-ANNS by up to 3 orders of magnitude compared to state-of-the-art methods, while not compromising the accuracy.

Modern database systems rely on workload forecasting to guide performance tuning, resource allocation, and query optimization. However, evolving query patterns and resource demands make accurate workload forecasting increasingly challenging. Most existing methods separately model query and resource behaviors using simple statistics or single-scale forecasting models, thereby ignoring their inherent correlations and leading to inaccurate modeling of real-world workload behaviors. In practice, real-world workloads show that query and resource behaviors are often interdependent and exhibit temporal dynamics. However, most forecasting methods overlook the inherent correlations between query and resource, as well as the temporal patterns across multi-scale resolutions in real workloads. To address these issues, we propose QuadraFormer, an end-to-end forecasting framework that jointly predicts query and resource usage. First, we introduce a unified workload representation that integrates query and resource information into a structured input, enabling joint modeling of workload across variates. Second, we develop an adaptive multi-scale routing mechanism that selects appropriate temporal resolutions to capture periodic patterns and multi-scale variability. Third, we design a novel Quadra-attention mechanism that models both intra- and inter-patch temporal dependencies as well as intra- and inter-dimensional dependencies. Extensive experiments on real-world workloads show that QuadraFormer consistently outperforms competitive baselines, achieving the highest F1 score of 98.38% and accuracy of 86.17%, with F1 improvements of up to 10.28% over the best-performing baseline, while reducing training time by up to 2.16×.

Recent advancements in deep learning, particularly in embedding models, have enabled the effective representation of various data types such as text, images, and audio as vectors, thereby facilitating semantic analysis. A large number of massive vector datasets are maintained in vector databases. Approximate similarity join is a core operation in vector database systems that joins two datasets, and outputs all pairs of vectors from the two datasets, if the distance between such a pair of two vectors is no more than a specified value. Existing approaches for similarity join are selection-based such that they treat each data point in a dataset as an individual query point to search data points by an approximate range query in another dataset. Such methods do not fully capitalize on the inherent properties of the join operation itself. In this paper, we propose a new join algorithm, SimJoin. Our join algorithm aims at boosting join processing efficiency by leveraging relationships between partial join results (e.g., join windows). In brief, our join algorithm accelerates the join processing to process a join window by utilizing the join windows from the processed data points. Then, we discuss optimizing join window order to minimize join costs. In addition, we discuss how to support k -similarity join, and how to maintain proximity graph index based on k-similarity join. Extensive experiments on real-world and synthetic datasets demonstrate the significant performance superiority of our proposed algorithms over existing state-of-the-art methods.

k -ANN search has been extensively studied to find k approximate nearest neighbors for a given query vector in a high-dimensional dataset, where a data item is represented as a vector. As there are many new emerging real-world applications that have categorical/numerical attributes associated with vectors, it is highly needed to support k -ANN search with additional predicates on such attributes. In this paper, we study k -ANN queries, q = (v q , c q ), where v q is a query vector and c q is a predicate on categorical/numerical attributes. Note that the conventional k -ANN search is a k -ANN query when c q = ∅. In the literature, some can support the cases when c q = ∅, some can support the cases when c q is on categorical attributes, and some can support the cases when c q is on numerical attributes. But none of them can support all cases efficiently. In this paper, we propose an all-in-one approach. Our approach supports conventional k -ANN search in the same way as the state-of-the-art approaches, and supports the predicates in a similar or even better way compared to the approaches that are tailored to support either categorical attributes or numerical attributes. We conduct extensive performance studies and confirm the accuracy and the efficiency of our approach in comparison with the state-of-the-art approaches.

Ensuring the ACID properties of transactions is the fundamental functionality of transactional DBMSs. However, through our study on existing solutions on transaction management, we found that transaction implementations in some mainstream databases, such as MySQL, MariaDB and TiDB, may violate what they claim in their documentation, in the form of incorrect database state or query results. Since there is still a lack of efficient and comprehensive testing methods to detect bugs within transaction management implementation for off-the-shelf DBMSs at present, we propose Fucci, a fuzzing framework, to solve the problem. Given a target DBMS, Fucci improves the efficiency of detecting transaction bugs through three key components: Random Conflict Construction (RCC), Multilevel Constraint Solving (MCS), and Experience-driven Automatic Simplification (EAS). RCC addresses the issue of inadequate case validity by ensuring the presence of read-write or write-write conflicts between transactions. MCS enhances the accuracy and efficiency of the transaction oracle by employing an external multi-version control system to solve data visibility. EAS is ultimately adopted to improve the efficiency of simplification and the readability of the identified bug cases. All of the above strategies are tested on commercial databases such as MySQL, MariaDB and TiDB. Accordingly, 6 previously unknown transaction bugs and 14 known duplicate transaction bugs have been newly discovered, most of which have been officially acknowledged.

Proximity graphs (PG) have gained increasing popularity as the state-of-the-art solutions to k -approximate nearest neighbor ( k -ANN) search on high-dimensional data, which serves as a fundamental function in various fields, e.g., retrieval-augmented generation. Although PG-based approaches have the best k -ANN search performance, their index construction cost is superlinear to the number of points. Such superlinear cost substantially limits their scalability in the era of big data. Hence, the goal of this paper is to accelerate the construction of PG-based methods without compromising their k -ANN search performance. To achieve this goal, two mainstream categories of PG are revisited: relative neighborhood graph (RNG) and navigable small world graph (NSWG). By revisiting their construction process, we find the issues of construction efficiency. To address these issues, we propose a new construction framework with a novel pruning strategy for edge selection, which accelerates RNG construction while keeping its k -ANN search performance. Then, we integrate this framework into NSWG construction to enhance both the construction efficiency and k -ANN search performance of NSWG. Extensive experiments are conducted to validate our construction framework for both RNG and NSWG, and that it significantly reduces the PG construction cost, achieving up to 5.6x speedup, while not compromising the k -ANN search performance.

The problem of k -nearest neighbor ( k -NN) search is a fundamental problem to find the exact k nearest neighbor points for a user-given query point q in a d -dimensional large dataset D with n points, and the approximate k -NN ( k -ANN) search problem is to find the approximate k -NN. Both are extensively studied to support real applications. Among all approaches, the graph-based approaches have been seen as the best to support k -NN/ANN in recent studies. The state-of-the-art graph-based approach, τ-MG, finds 1-NN, \(\bar{p}_1\) , over a graph index G τ constructed for D based on a predetermined parameter τ where the distance between \(\bar{p}_1\) and q is less than τ, and finds k -ANN based on the approach taken for 1-NN. There are some main issues in τ-MG and other graph-based approaches. One is that it is difficult to predetermine τ which can ensure to find 1-NN and can do it efficiently. This is because the accuracy/efficiency is related to the size of the graph index G τ constructed. To achieve high accuracy is at the expense of efficiency. In addition, like all the other existing graph-based approaches, it does not have a theoretical guarantee to ensure k -NN for the same reason to use the same graph index, G τ , for both 1-NN and k -NN ( k > 1). In this article, we propose a new graph-based approach for k -NN with a theoretical guarantee. We construct a labeled graph, \(\mathcal {G}\) , and we do not need to predetermine τ. Instead, we find 1-NN over a subgraph, \(\mathcal {G}_{\dot{\tau }}\) , of \(\mathcal {G}\) , virtually constructed in a dynamic manner. Here, \(\dot{\tau }\) we use is query-dependent and can be smaller than τ, and the subgraph \(\mathcal {G}_{\dot{\tau }}\) is smaller than G τ when \(\dot{\tau }= \tau\) . We find k -NN in two phases. In the navigation phase, we find 1-NN, \(\bar{p}_1\) , of q over \(\mathcal {G}_{\dot{\tau }}\) . In the second refinement phase, for k > 1, we explore the neighbors within the vicinity region of \(\bar{p}_1\) in \(\mathcal {G}\) . Based on our solution for k -NN in theory, we propose new algorithms to support k -ANN efficiently in practice. We conduct extensive performance studies and confirm the effectiveness and efficiency of our new approach.

Approximate nearest neighbor (ANN) search in high-dimensional space plays an essential role in many multimedia applications. Recently, product quantization (PQ) based methods for ANN search have attracted enormous attention in the community of computer vision, due to its good balance between accuracy and space requirement. PQ based methods embed a high-dimensional vector into a short binary code (called PQ code), and the squared Euclidean distance is estimated by asymmetric quantizer distance (AQD) with pretty high precision. Thus, ANN search in the original space can be converted to similarity search on AQD using the PQ approach. All existing PQ methods are in-memory solutions, which may not handle massive data if they cannot fit entirely in memory. In this paper, we propose an I/O-efficient PQ based solution for ANN search. We design an index called PQB+-forest to support efficient similarity search on AQD. PQB+-forest first creates a number of partitions of the PQ codes by a coarse quantizer and then builds a B+-tree, called PQB+-tree, for each partition. The search process is greatly expedited by focusing on a few selected partitions that are closest to the query, as well as by the pruning power of PQB+-trees. According to the experiments conducted on two large-scale data sets containing up to 1 billion vectors, our method outperforms its competitors, including the state-of-the-art PQ method and the state-of-the-art LSH methods for ANN search.

Approximate Nearest Neighbor (ANN) search in high dimensional space has become a fundamental paradigm in many applications. Recently, Locality Sensitive Hashing (LSH) and its variants are acknowledged as the most promising solutions to ANN search. However, state-of-the-art LSH approaches suffer from a drawback: accesses to candidate objects require a large number of random I/O operations. In order to guarantee the quality of returned results, sufficient objects should be verified, which would consume enormous I/O cost. To address this issue, we propose a novel method, called SortingKeys-LSH (SK-LSH), which reduces the number of page accesses through locally arranging candidate objects. We firstly define a new measure to evaluate the distance between the compound hash keys of two points. A linear order relationship on the set of compound hash keys is then created, and the corresponding data points can be sorted accordingly. Hence, data points that are close to each other according to the distance measure can be stored locally in an index file. During the ANN search, only a limited number of disk pages among few index files are necessary to be accessed for sufficient candidate generation and verification, which not only significantly reduces the response time but also improves the accuracy of the returned results. Our exhaustive empirical study over several real-world data sets demonstrates the superior efficiency and accuracy of SK-LSH for the ANN search, compared with state-of-the-art methods, including LSB, C2LSH and CK-Means.