Search Results

Subgraph counting is a fundamental problem in understanding and analyzing graph structured data, yet computationally challenging. This calls for an accurate and efficient algorithm for Subgraph Cardinality Estimation, which is to estimate the number of ...

The B-tree and its variants are an indispensable tool for database systems and applications. Hence the efficiency of the B-tree is one of the few critical factors that determine the performance of a database system. In main-memory database ...

• DB+ tree redesigns the node structure of B+ tree for faster branching operation
• Our branching algorithm can be implemented in an O(1) number of instructions
• DB+ tree performs point search 170% faster than pkB-tree.
• DB+ tree ...

Subgraph matching is the problem of searching for all embeddings of a query graph in a data graph, and subgraph query processing (also known as subgraph search) is to find all the data graphs that contain a query graph as subgraphs. Extensive research ...

This article proposes an index key compression scheme based on the notion of distinction bits. It proves that the distinction bits of index keys are sufficient information to determine the sorted order of the index keys. The actual compression ratio may ...

Subgraph query processing (also known as subgraph search) and subgraph matching are fundamental graph problems in many application domains. A lot of efforts have been made to develop practical solutions for these problems. Despite the efforts, ...

Subgraph query processing (also known as subgraph search) and subgraph matching are fundamental graph problems in many application domains. A lot of efforts have been made to develop practical solutions for these problems. Despite the efforts, existing ...

In many real datasets such as social media streams and cyber data sources, graphs change over time through a graph update stream of edge insertions and deletions. Detecting critical patterns in such dynamic graphs plays an important role in various ...

The hierarchical overlap graph (HOG for short) is an overlap encoding graph that efficiently represents overlaps from a given set P of n strings. A previously known algorithm constructs the HOG in time and space, where is the sum of lengths of ...

Supergraph search is one of fundamental graph query processing problems in many application domains. Given a query graph and a set of data graphs, supergraph search is to find all the data graphs contained in the query graph as subgraphs. In existing ...

Cartesian tree matching is the problem of finding all substrings in a given text which have the same Cartesian trees as that of a given pattern. In this paper, we deal with Cartesian tree matching for the case of multiple patterns. We present two ...

Cartesian tree matching is the problem of finding all substrings of a given text which have the same Cartesian trees as that of a given pattern. So far there is one linear-time solution for Cartesian tree matching, which is based on the KMP ...

In Cartesian tree matching, two strings match if the Cartesian trees of the strings are the same. In this paper we define full, initial, and general periods in Cartesian tree matching, and present an O(n) time algorithm for finding all full ...

Subgraph matching (or subgraph isomorphism) is one of the fundamental problems in graph analysis. Extensive research has been done to develop practical solutions for subgraph matching. The state-of-the-art algorithms such as \textsfCFL-Match and \...

In this paper we propose the FM-index of alignment, a compressed index for similar strings with the functionalities of pattern search and random access. For this, we first design a new and improved version of the suffix array of alignment. The FM-index ...

The computing power of graphics processing units GPU has increased rapidly, and there has been extensive research on general-purpose computing on GPU GPGPU for cryptographic algorithms such as RSA, Elliptic Curve Cryptosystem ECC, NTRU, and Advanced ...

We present a new method of deciding the order-isomorphism between two strings.We show that the bad character rule can be applied to the OPPM problem.We present a space-efficient algorithm computing the shift table for text search.We present a linear-...

Business planning as well as analytics on top of large-scale database systems is valuable to decision makers, but planning operations known and implemented so far are very basic. In this paper we propose a new planning operation called interval ...

We introduce a new string matching problem called order-preserving matching on numeric strings, where a pattern matches a text if the text contains a substring of values whose relative orders coincide with those of the pattern. Order-preserving matching ...

Recently, the problem of extending an alignment with k-mismatches and a single gap for pairwise sequence alignment was introduced (Flouri et al., 2011). The authors considered the problem of extending an alignment under the Hamming distance model by ...

The suffix tree of alignment is an index data structure for similar strings. Given an alignment of similar strings, it stores all suffixes of the alignment, called alignment-suffixes . An alignment-suffix represents one suffix of a string or suffixes ...