Set similarity search, as a foundational operation in data processing with diverse applications in different domains, has been extensively studied. However, in the era of big data where sets sizes and quantities are rapidly increasing, set similarity search suffers from significant computational and storage overheads. Additionally, traditional approaches struggle to universally address the search problem across different similarity measures and query types. To tackle these challenges, AI techniques, with their powerful learning capabilities, may provide a viable solution. In this paper, we first propose a multi-task representation learning approach with box embeddings that accurately simulates different similarity measures simultaneously by estimating the overlap and union relationships between set pairs in latent box space. Based on the compressed representations of sets, we then introduce a universal search approach designed to answer various set similarity queries with parallel implementation. Extensive experiments conducted on real-world datasets demonstrate the universality, accuracy and efficiency of the proposed approach, showing that it outperforms competing methods. For reproduction, we release our source code on https://github.com/yangzhong901/MTBUS.

Recent advances in machine learning, particularly in Natural Language Processing (NLP), have produced powerful models trained on vast datasets. However, these models risk leaking sensitive information, raising privacy concerns. In response, regulatory measures such as the European Union's General Data Protection Regulation (GDPR) have driven increasing interest in Machine Unlearning techniques, which enable models to selectively forget specific data entries. Early unlearning approaches primarily relied on pre-processing methods, while more recent research has shifted towards training-based solutions. Despite their effectiveness, a key limitation persists: most methods require access to original training data, which is often unavailable. Additionally, directly applying unlearning techniques bears the cost of undermining the model's expressive capabilities. To address these challenges, we introduce the Iterative Contrastive Unlearning (ICU) framework, which consists of three core components: A Knowledge Unlearning Induction module designed to target specific knowledge for removal using an unlearning loss; A Contrastive Learning Enhancement module to preserve the model's expressive capabilities against the pure unlearning goal; And an Iterative Unlearning Refinement module that dynamically adjusts the unlearning process through ongoing evaluation and updates. Experimental results demonstrate the efficacy of our ICU method in unlearning sensitive information while maintaining the model's overall performance, offering a promising solution for privacy-conscious machine learning applications.

Graph Edit Distance (GED) is a widely recognized metric for measuring graph similarity, yet its NP-complete nature poses challenges for fast and accurate computation. This paper introduces FGWAlign, an Optimal Transport (OT)-based approach for graph alignment and GED computation. We take the first step to theoretically demonstrate and that computing GED can be transformed into optimizing a particular OT variant—the Fused Gromov-Wasserstein distance. Tailored to the GED problem structure, we further implement three key enhancements to the standard FGW solver: (1) a random exploration scheme to better locate the global optimum, (2) a diverse projection strategy for post-processing the transportation plan to escape local optima, and (3) a novel extension to accommodate multi-relational graphs with edge labels. With O (| V || E |) time complexity and O (| V | 2 ) space complexity, where | V | and | E | are the maximum number of nodes and edges between the two compared graphs, FGWAlign achieves a superior balance of efficiency, accuracy, and scalability. Empirical results show that, compared with 12 representative GED computation methods across different categories on 4 real-world graph datasets, FGWAlign reduces computation errors by over 80% and achieves 15–60× speedup. It also demonstrates promising resutls on downstream applications including labeled graph alignment and graph-level anomaly detection, highlighting its versatility. FGWAlign opens up promising avenues for future applications in graph data management.

The maximum inner product search (MIPS) problem in high-dimensional vector spaces has various applications, primarily driven by the success of deep neural network-based embedding models. Existing MIPS methods designed for dense vectors using approximate techniques like locality-sensitive hashing (LSH) have been well studied, but they are not efficient and effective for searching sparse vectors due to the near-orthogonality among the sparse vectors. The solutions to MIPS over sparse vectors rely heavily on inverted lists, resulting in poor query efficiency, particularly when dealing with large-scale sparse datasets. In this paper, we introduce SOSIA, a novel framework specifically tailored to address these limitations. To handle sparsity, we propose the SOS transformation, which converts sparse vectors into a binary space while providing an unbiased estimator of the inner product between any two vectors. Additionally, we develop a minHash-based index to enhance query efficiency. We provide a theoretical analysis on the query quality of SOSIA and present extensive experiments on real-world sparse datasets to validate its effectiveness. The experimental results demonstrate its superior performance in terms of query efficiency and accuracy compared to existing methods.

The constantly increasing scale of graphs leads to higher costs in terms of data storage and computation. Consequently, there is a growing trend of outsourcing and analyzing graphs in clouds. As there is a concern that cloud servers may extract sensitive information from these graphs, the graphs being outsourced must be pre-anonymized, leading to increased space consumption and degraded graph query processing efficiency. Previous work has attempted to address this issue by outsourcing a compacted anonymized graph to the cloud. However, the solution typically focuses on a specific type of query, such as a subgraph query, and cannot adequately accommodate real-life scenarios where multiple applications often work concurrently on the same graph. In this paper, we propose a generic framework called FRESH to handle various graph queries efficiently within a single outsourced graph. To reduce the size of the outsourced graph, we developed a novel graph contraction scheme that transforms a big graph into a compact one while preserving graph privacy. To showcase the adaptability of classical graph query algorithms (e.g., subgraph query, triangle counting, and shortest distance query), we demonstrate their successful execution on the same compact graph created through our contraction scheme. We further extend our framework by incorporating optimizations that significantly improve query processing efficiency. Extensive experimental results demonstrate the superiority of FRESH over traditional techniques.

In this paper, we revisit the problem of the current routing system in terms of prediction scalability and routing result optimality. Specifically, the current traffic prediction models are not suitable for large urban networks due to the incomplete information of traffic conditions. Besides, existing routing systems can only plan the routes based on the past traffic conditions and struggle to update the optimal route for vehicles in real-time. As a result, the actual route taken by vehicles is different from the ground-truth optimal path. Therefore, we propose a Just-In-Time Predictive Route Planning framework to tackle these two problems. Firstly, we propose a Travel Time Constrained Top-$k^{n}$Shortest Path algorithm which pre-computes a set of candidate paths with several switch points. This empowers vehicles to continuously have the opportunity to switch to better paths taking into account real-time traffic condition changes. Moreover, we present a query-driven prediction paradigm with ellipse-based searching space estimation, along with an efficient multi-queries handling mechanism. This not only allows for targeted traffic prediction by prioritizing regions with valuable yet outdated traffic information, but also provides optimal results for multiple queries based on real-time traffic evolution. Evaluations on two real-life road networks demonstrate the effectiveness and efficiency of our framework and methods.

With an exponentially growing number of graphs from disparate repositories, there is a strong need to analyze a graph database containing an extensive collection of small- or medium-sized data graphs (eg chemical compounds). Although subgraph enumeration and subgraph mining have been proposed to bring insights into a graph database by a set of subgraph structures, they often end up with similar or homogenous topologies, which is undesirable in many graph applications. To address this limitation, we propose theTop-k Edge-Diversified Patterns Discovery problemto retrieve a set of subgraphs that cover the maximum number of edges in a database. To efficiently process such query, we present a generic and extensible framework called$\textsc {Ted}^+$which achieves a guaranteed approximation ratio to the optimal result. Three optimization strategies are further developed to improve the performance, and a lightweight version calledTedLiteis designed for even larger graph databases. Experimental studies on real-world datasets demonstrate the superiority of$\textsc {Ted}^+$to traditional techniques.

The protocols that satisfy Local Differential Privacy (LDP) enable untrusted third parties to collect aggregate information about a population without disclosing each user's privacy. In particular, each user locally encodes and perturbs his private data before sending it to the data collector, who aggregates and estimates the statistics about the population based on the collected perturbed values from individuals. Owing to their growing importance, LDP protocols have been widely studied and deployed in real-world scenarios (eg Chrome and Windows). However, as data poisoning attacks may be injected by attackers who introduce many fake users, the utility of the statistics is heavily poisoned. In this paper, we present a generic and extensible framework called LDPGuard to address the problem. LDPGuard provides effective defenses against data poisoning attacks to LDP protocols for frequency estimation, a basic query of most data analytics tasks. In particular, it first precisely estimates the percentage of fake users and then provides adversarial schemes to defend against particular data poisoning attacks. Experimental study on real-world and synthetic datasets demonstrates the superiority of LDPGuard compared to existing techniques.

Locality-sensitive hashing (LSH) is a promising family of methods for the high-dimensional approximate nearest neighbor (ANN) search problem due to its sub-linear query time and strong theoretical guarantee. Existing LSH methods either suffer from large index sizes and hash boundary problems, or incur a linear cost for high-quality candidate identification. This dilemma is addressed in a novel method called DB-LSH proposed in this paper. It organizes the projected spaces with multi-dimensional indexes instead of fixed-width hash buckets, which significantly reduces space costs. High-quality candidates can be generated efficiently by dynamically constructing query-based hypercubic buckets with the required widths through index-based window queries. A novel incremental search strategy called DBI-LSH is also developed to further boost the query performance, which incrementally accesses the next best point for higher accuracy and efficiency. Considering the intermediate query information of each query, DBA-LSH is designed to adaptively tune termination conditions without scarifying the success probability. Our theoretical analysis proves that DB-LSH has a smaller query cost than the existing work while DBA-LSH and DBI-LSH have lower expected query costs than DB-LSH. An extensive range of experiments on real-world data show the superiority of our approaches over the state-of-the-art methods in both efficiency and accuracy.

Visual Graph Query Interfaces (VQIs) empower non-programmers to query graph data by constructing visual queries intuitively. Devising efficient technologies in Graph Query Engines (GQEs) for interactive search and exploration has also been studied for years. However, these two vibrant scientific fields are traditionally independent of each other, causing a vast barrier for users who wish to explore the full-stack operations of graph querying. In this demonstration, we propose a novel VQI system built upon Neo4j called VisualNeo that facilities an efficient subgraph query in large graph databases. VisualNeo inherits several advanced features from recent advanced VQIs, which include the data-driven gui design and canned pattern generation. Additionally, it embodies a database manager module in order that users can connect to generic Neo4j databases. It performs query processing through the Neo4j driver and provides an aesthetic query result exploration.

The approximate nearest neighbor (ANN) search in high-dimensional spaces is a fundamental but computationally very expensive problem. Many methods have been designed for solving the ANN problem, such as LSH-based methods and graph-based methods. The LSH-based methods can be costly to reach high query quality due to the hash-boundary issues, while the graph-based methods can achieve better query performance by greedy expansion in an approximate proximity graph (APG). However, the construction cost of these APGs can be one or two orders of magnitude higher than that for building hash-based indexes. In addition, they fail short in incrementally maintaining APGs as the underlying dataset evolves. In this paper, we propose a novel approach named LSH-APG to build APGs and facilitate fast ANN search using a lightweight LSH framework. LSH-APG builds an APG via consecutively inserting points based on their nearest neighbor relationship with an efficient and accurate LSH-based search strategy. A high-quality entry point selection technique and an LSH-based pruning condition are developed to accelerate index construction and query processing by reducing the number of points to be accessed during the search. LSH-APG supports fast maintenance of APGs in lieu of building them from scratch as dataset evolves. Its maintenance cost and query cost for a point is proven to be less affected by dataset cardinality. Extensive experiments on real-world and synthetic datasets demonstrate that LSH-APG incurs significantly less construction cost but achieves better query performance than existing graph-based methods.

Maximum inner product search (MIPS) in high-dimensional spaces has wide applications but is computationally expensive due to the curse of dimensionality. Existing studies employ asymmetric transformations that reduce the MIPS problem to a nearest neighbor search (NNS) problem, which can be solved using locality-sensitive hashing (LSH). However, these studies usually maintain multiple hash tables and locally examine them one by one, which may cause additional costs on probing unnecessary points. In addition, LSH is applied without taking into account the properties of the inner product. In this paper, we develop a fast search framework FARGO for MIPS on large-scale, high-dimensional data. We propose a global multi-probing (GMP) strategy that exploits the properties of the inner product to globally examine high quality candidates. In addition, we develop two optimization techniques. First, different with existing transformations that introduce either distortion errors or data distribution imbalances, we design a novel transformation, called random XBOX transformation, that avoids the negative effects of data distribution imbalances. Second, we propose a global adaptive early termination condition that finds results quickly and offers theoretical guarantees. We conduct extensive experiments with real-world data that offer evidence that FARGO is capable of outperforming existing proposals in terms of both accuracy and efficiency.

Indexing is an effective way to support efficient query processing in large databases. Recently the concept oflearned index, which replaces or complements traditional index structures with machine learning models, has been actively explored to reduce storage and search costs. However, accurate and efficient similarity query processing in high-dimensional metric spaces remains to be an open challenge. In this paper, we propose a novel indexing approach called LIMS that uses data clustering, pivot-based data transformation techniques and learned indexes to support efficient similarity query processing in metric spaces. In LIMS, the underlying data is partitioned into clusters such that each cluster follows a relatively uniform data distribution. Data redistribution is achieved by utilizing a small number of pivots for each cluster. Similar data are mapped into compact regions and the mapped values are totally ordinal. Machine learning models are developed to approximate the position of each data record on disk. Efficient algorithms are designed for processing range queries and nearest neighbor queries based on LIMS, and for index maintenance with dynamic updates. Extensive experiments on real-world and synthetic datasets demonstrate the superiority of LIMS compared with traditional indexes and state-of-the-art learned indexes.

Among many solutions to the high-dimensional approximate nearest neighbor (ANN) search problem, locality sensitive hashing (LSH) is known for its sub-linear query time and robust theoretical guarantee on query accuracy. Traditional LSH methods can generate a small number of candidates quickly from hash tables but suffer from large index sizes and hash boundary problems. Recent studies to address these issues often incur extra overhead to identify eligible candidates or remove false positives, making query time no longer sub-linear. To address this dilemma, in this paper we propose a novel LSH scheme called DB-LSH which supports efficient ANN search for large high-dimensional datasets. It organizes the projected spaces with multi-dimensional indexes rather than using fixed-width hash buckets. Our approach can significantly reduce the space cost by avoiding the need to maintain many hash tables for different bucket sizes. During the query phase of DB-LSH, a small number of high-quality candidates can be generated efficiently by dynamically constructing query-based hypercubic buckets with the required widths through index-based window queries. For a dataset of$n$d-dimensional points with approximation ratio$c$, our rigorous theoretical analysis shows that DB-LSH achieves a smaller query cost$O(n^{\rho}d\log n)$, where$\rho^{\ast}$is bounded by$1/c^{\alpha}$versus a bound of$1/c$in the existing work. An extensive range of experiments on real-world data demonstrate the superiority of DB-LSH over state-of-the-art methods on both efficiency and accuracy.

Exploratory search is a search paradigm that plays a vital role in databases, data mining, and information retrieval to assist users to get familiar with the underlying databases. It supports iterative query formulation to explore the data space. Despite its growing importance, exploratory search on graph-structured data has not received adequate attention in the literature. In this paper, we demonstrate a novel system called Vincent that facilitates an efficient exploratory subgraph search in a graph database containing a large collection of small or medium-sized graphs. By automatically generating the content for panels in GUI and diversified patterns from databases and providing a visual result explorer, Vincent supports data-driven visual query formulation, incremental subgraph processing, and efficient query result summarization.

Trajectory similarity computation is a fundamental component in a variety of real-world applications, such as ridesharing, road planning, and transportation optimization. Recent advances in mobile devices have enabled an unprecedented increase in the amount of available trajectory data such that efficient query processing can no longer be supported by a single machine. As a result, means of performing distributed in-memory trajectory similarity search are called for. However, existing distributed proposals either suffer from computing resource waste or are unable to support the range of similarity measures that are being used. We propose a distributed in-memory management framework called REPOSE for processing top-k trajectory similarity queries on Spark. We develop a reference point trie (RP-Trie) index to organize trajectory data for local search. In addition, we design a novel heterogeneous global partitioning strategy to eliminate load imbalance in distributed settings. We report on extensive experiments with real-world data that offer insight into the performance of the solution, and show that the solution is capable of outperforming the state-of-the-art proposals.

The set similarity join (SSJ) is core functionality in a range of applications, including data cleaning, near-duplicate object detection, and data integration. Threshold-based SSJ queries return all pairs of sets with similarity no smaller than a given threshold. As results, and their utility, are very sensitive to the choice of threshold value, it is a problem that it is difficult to choose such an appropriate value. Doing so requires prior knowledge of the data, which users often do not have. To avoid this problem, we propose a solution to the top-k overlap set similarity join (TkOSSJ) that returns k pairs of sets with the highest overlap similarities. The state-of-the-art solution disregards the effect of the so-called step size, which is the number of elements accessed in each iteration of the algorithm. This affects its performance negatively. To address this issue, we first propose an algorithm that uses a fixed step size, thus taking advantage of the benefits of a large step size, and then we present an adaptive step size algorithm that is capable of automatically adjusting the step size, thus reducing redundant computations. An extensive empirical study offers insight into the new algorithms and indicates that they are capable of outperforming the state-of-the-art method on real, large-scale data sets.

Nearest neighbor (NN) search in high-dimensional spaces is inherently computationally expensive due to the curse of dimensionality. As a well-known solution to approximate NN search, locality-sensitive hashing (LSH) is able to answer c-approximate NN ( c -ANN) queries in sublinear time with constant probability. Existing LSH methods focus mainly on building hash bucket based indexing such that the candidate points can be retrieved quickly. However, existing coarse-grained structures fail to offer accurate distance estimation for candidate points, which translates into additional computational overhead when having to examine unnecessary points. This in turn reduces the performance of query processing. In contrast, we propose a fast and accurate LSH framework, called PM-LSH, that aims to compute the c -ANN query on large- scale, high-dimensional datasets. First, we adopt a simple yet effective PM-tree to index the data points. Second, we develop a tunable confidence interval to achieve accurate distance estimation and guarantee high result quality. Third, we propose an efficient algorithm on top of the PM-tree to improve the performance of computing c -ANN queries. Extensive experiments with real-world data offer evidence that PM-LSH is capable of outperforming existing proposals with respect to both efficiency and accuracy.