Real-time analysis of graphs containing temporal information, such as social media streams, Q&A networks, and cyber data sources, plays an important role in various applications. Among them, detecting patterns is one of the fundamental graph analysis problems. In this paper, we study time-constrained continuous subgraph matching, which detects a pattern with a strict partial order on the edge set in real-time whenever a temporal data graph changes over time. We propose a new algorithm based on two novel techniques. First, we introduce a filtering technique called time-constrained matchable edge that uses temporal information for filtering with polynomial space. Second, we develop time-constrained pruning techniques that reduce the search space by pruning some of the parallel edges in backtracking, utilizing temporal information. Extensive experiments on real and synthetic datasets show that our approach outperforms the state-of-the-art algorithm by up to two orders of magnitude in terms of query processing time.

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 application domains such as fraud detection, cyber security, and recommendation systems for social networks. Given a dynamic data graph and a query graph, the continuous subgraph matching problem is to find all positive matches for each edge insertion and all negative matches for each edge deletion. The state-of-the-art algorithm TurboFlux uses a spanning tree of a query graph for filtering. However, using the spanning tree may have a low pruning power because it does not take into account all edges of the query graph. In this paper, we present a symmetric and much faster algorithm SymBi which maintains an auxiliary data structure based on a directed acyclic graph instead of a spanning tree, which maintains the intermediate results of bidirectional dynamic programming between the query graph and the dynamic graph. Extensive experiments with real and synthetic datasets show that SymBi outperforms the state-of-the-art algorithm by up to three orders of magnitude in terms of the elapsed time.

We introduce the two-dimensional rational automata (RA) to recognize languages of pictures, as an extension of the finite automata for strings. A RA processes a picture column by column changing its state. The states are columns of symbols, too. The transition function is realized by a transducer. We prove that RA recognize the family REC of languages recognized by tiling systems. Moreover, RA provide a uniform setting for a lot of important notions, techniques and results presented in the last decades for recognizable two-dimensional languages. The model is also very flexible. In fact, there can be imposed restrictions or added features to easily interesting new classes and examples or to capture known families of languages.

A setX⊆ Σ** of pictures is a code if every picture over Σ is tilable in at most one way with pictures inX. The definition ofstrong prefix codeis introduced. The family of finite strong prefix codes is decidable and it has a polynomial time decoding algorithm. Maximality for finite strong prefix codes is also studied and related to the notion of completeness. We prove that any finite strong prefix code can be embedded in a unique maximal strong prefix code that has minimal size and cardinality. A complete characterization of the structure of maximal finite strong prefix codes completes the paper.

Recognizable two-dimensional languages (REC) are defined by tiling systems that generalize to two dimensions non-deterministic finite automata for strings. We introduce the notion of deterministic tiling system and the corresponding family of languages (DREC) and study its structural and closure properties. Furthermore we show that, in contrast with the one-dimensional case, there exist other classes between deterministic and non-deterministic families that we separate by means of examples and decidability properties.

The purpose of this paper is to investigate about a new notion of finite state recognizability for two-dimensional (picture) languages. This notion takes as starting point the characterization of one-dimensional recognizable languages in terms of local languages and projections. Such notion can be extended in a natural way to the two-dimensional case. We first introduce a notion of local picture language and then we define,a recognizable picture language as a projection of a local picture language. The family of recognizable picture languages is denoted by REC. We study some combinatorial and language-theoretic properties of family REC. In particular we prove some closure properties with respect to different kinds of operations. From this, we derive that some natural families of two-dimensional languages (finite languages, regular languages, locally testable languages) are recognizable. Further we give some necessary conditions for recognizability which provides tools to show that certain languages are not recognizable. Although REC shares several properties of recognizable string languages, however, differently from the case of words, we prove here that REC is not closed under complementation and that the emptyness problem is undecidable for this family of languages. Finally, we report some characterizations of family REC by means of machine-based models and logic-based formalisms.

The purpose of this paper is to propose a new notion of recognizability for picture (two-dimensional) languages extending the characterization of one-dimensional recognizable languages in terms of local languages and alphabetic mappings. We first introduce the family of local picture languages (denoted by LOC) and, in particular, prove the undecidability of the emptiness problem. Then we define the new family of recognizable picture languages (denoted by REC). We study some combinatorial and language theoretic properties of REC such as ambiguity, closure properties or undecidability results. Finally we compare the family REC with the classical families of languages recognized by four-way automata.