Graph edit distance (GED) is a general and versatile measure of graph similarity. Many combinatorial algorithms have been proposed for computing exact GED, but they suffer from the high computational cost due to the NP-hardness of GED computation. To address this challenge, approximate GED computation techniques have been extensively studied. These techniques are generally twofold: early work is based on combinatorial algorithms that restrict search space for efficient computation, while more recent approaches employ machine learning techniques to estimate GED. Although learning-based approaches generally achieve higher estimation accuracy than combinatorial approximations, they often rely on smoothed node embeddings to model node-to-node interactions, which may limit their ability to capture fine-grained structural differences. To alleviate this limitation, we exploit the insight that sequential variations in node interactions across GNN layers exhibit informative patterns. In this paper, we design a novel neural model, Grasp, that learns to extract and leverage these patterns to predict pairwise node matching probabilities and their associated costs. By aggregating these estimates from the perspectives of both input graphs, Grasp effectively and accurately computes an approximate GED. Experimental results on real-world datasets demonstrate that Grasp significantly improves estimation accuracy over existing approximate methods.

Large scale machine learning (ML) and deep learning (DL) platforms face challenges when integrated with deduplication enabled storage clusters. In the quest to achieve smart and efficient storage utilization, removal of duplicate data introduces bottlenecks, since deduplication alters the I/O transaction layout of the storage system. Therefore, it is critical to address such deduplication overhead for acceleration of ML/DL computation in deduplication storage. Existing state of the art ML/DL storage solutions such as Alluxio and AutoCache adopt non deduplication-aware caching mechanisms, which lacks the much needed performance boost when adopted in deduplication enabled ML/DL clusters. In this paper, we introduceRedup, which eliminates the performance drop caused by enabling deduplication in ML/DL storage clusters. At the core, is aRedupCaching Manager (RDCM), composed of a 2-tier deduplication layout-aware caching mechanism. The RDCM provides an abstraction of the underlying deduplication storage layout to ML/DL applications and provisions a decoupled acceleration of object reconstruction during ML/DL read operations. OurRedupevaluation shows negligible performance drop in ML/DL training performances as compared to a cluster without deduplication, whilst significantly outperforming Alluxio and AutoCache in terms of various performance metrics.

Graph similarity search is to retrieve all graphs from a graph database whose graph edit distance (GED) to a query graph is within a given threshold. As GED computation is NP-hard, existing solutions adopt the filtering-and-verification framework, where the main focus is on the filtering phase to reduce the number of GED verifications. However, existing filtering techniques have inherently limited filtering capabilities, and suffer from a large number of GED verifications. To address the problem, in this paper, we propose a fundamentally different approach that utilizes pre-computed GEDs between data graphs in the filtering phase. Based on the approach, we develop a novel search framework Nass, which substantially reduces the verification workload. Because the efficiency of GED computation is essential in GED pre-computation, not to mention the verification of candidate graphs, we also propose an efficient GED computation algorithm as a part of Nass. We conduct extensive experiments on real datasets, and show Nass significantly outperforms the state-of-the art solutions.

Recent advances in DNA sequencing have enabled a flood of sequencing-based applications for studying biology and medicine. A key requirement of these applications is to rapidly and accurately map DNA subsequences to a reference genome. This DNA subsequence mapping problem shares core technical challenges with the similarity query processing problem studied in the database research literature. To solve this problem, existing techniques first extract signatures from a query, then retrieve candidate mapping positions from an index using the extracted signatures, and finally verify the candidate positions. The efficiency of these techniques depends critically on signatures selected from queries, while signature selection relies on an indexing scheme of a reference genome. The q-gram inverted indexing, one of the most widely used indexing schemes, can discover candidate positions quickly, but has the limitation that signatures of queries are restricted to fixed-length q-grams. To address the problem, we propose a flexible way to generate variable-length signatures using a fixed-length q-gram index. The proposed technique groups a few q-grams into a variable-length signature, and generates candidate positions for the variable-length signature using the inverted lists of the q-grams. We also propose a novel dynamic programming algorithm to balance between the filtering power of signatures and the overhead of generating candidate positions for the signatures. Through extensive experiments on both simulated and real genomic data, we show that our technique substantially improves the performance of read mapping in terms of both mapping speed and accuracy.

BACKGROUND: Next-generation sequencing (NGS) enables rapid production of billions of bases at a relatively low cost. Mapping reads from next-generation sequencers to a given reference genome is an important first step in many sequencing applications. Popular read mappers, such as Bowtie and BWA, are optimized to return top one or a few candidate locations of each read. However, identifying all mapping locations of each read, instead of just one or a few, is also important in some sequencing applications such as ChIP-seq for discovering binding sites in repeat regions, and RNA-seq for transcript abundance estimation. RESULTS: Here we present Hobbes2, a software package designed for fast and accurate alignment of NGS reads and specialized in identifying all mapping locations of each read. Hobbes2 efficiently identifies all mapping locations of reads using a novel technique that utilizes additional prefix q-grams to improve filtering. We extensively compare Hobbes2 with state-of-the-art read mappers, and show that Hobbes2 can be an order of magnitude faster than other read mappers while consuming less memory space and achieving similar accuracy. CONCLUSIONS: We propose Hobbes2 to improve the accuracy of read mapping, specialized in identifying all mapping locations of each read. Hobbes2 is implemented in C++, and the source code is freely available for download at http://hobbes.ics.uci.edu.

Similarity searches are essential in many applications including data cleaning and near duplicate detection. Many similarity search algorithms first generate candidate records, and then identify true matches among them. A major focus of those algorithms has been on how to reduce the number of candidate records in the early stage of similarity query processing. One of the most commonly used techniques to reduce the candidate size is the prefix filtering principle, which exploits the document frequency ordering of tokens. In this paper, we propose a novel partitioning technique that considers multiple token orderings based on token co-occurrence statistics. Experimental results show that the proposed technique is effective in reducing the number of candidate records and as a result improves the performance of existing algorithms significantly.