一种新的基于递归分解的图可达性查询算法

针对现实中许多超大规模图可达性查询的问题,提出了一种新的基于递归分解的算法,即将原图递归分解成一系列生成树和剩余图两类子图,并通过分别查询这两类子图来减少查询开销.相比于区间标记、链分解、2-hop标签和路径树等传统算法,该算法不仅空间开销更小,且时间复杂度更低.仿真实验表明,该算法对处理大规模有向图可达性问题上存储规模更小且查询效率更高.     

Answering pattern match queries in large graph databases via graph embedding

The growing popularity of graph databases has generated interesting data management problems, such as subgraph search, shortest path query, reachability verification, and pattern matching. Among these, a pattern match query is more flexible compared with a subgraph search and more informative compared with a shortest path or a reachability query. In this paper, we address distance-based pattern match queries over a large data graph G. Due to the huge search space, we adopt a filter-and-refine framework to answer a pattern match query over a large graph. We first find a set of candidate matches by a graph embedding technique and then evaluate these to find the exact matches. Extensive experiments confirm the superiority of our method.     

SPARQL graph pattern rewriting for OWL-DL inference queries

This paper focuses on the issue of OWL-DL ontology queries implemented in SPARQL. Currently, ontology repositories construct inference ontology models, and match SPARQL queries to the models, to derive inference results. Because an inference model uses much more storage space than the original model, and cannot be reused as inference requirements vary, this method is not suitable for large-scale deployment. To solve this problem, this paper proposes a novel method that passes rewritten SPARQL queries to the original ontology model, to retrieve inference results. We define OWL-DL inference rules and apply them to rewriting Graph Patterns in queries. The paper classifies the inference rules and discusses how these rules affect query rewriting. To illustrate the advantages of our proposal, we present a prototype system based on Jena, and address query optimization, to eliminate the disadvantages of augmented query sentences. We perform a set of query tests and compare the results with related works. The results show that the proposed method results in significantly improved query efficiency, without compromising completeness or soundness.

Efficient guided symbolic reachability using reachability expressions

Asynchronous systems consist of a set of transitions which are non-deterministically chosen and executed. We present a theory of guiding symbolic reachability in such systems by scheduling clusters of transitions. A theory of reachability expressions which specify the schedules is presented. This theory allows proving equivalence of different schedules which may have radically different performance in BDD-based search. We present experimental evidence to show that optimized reachability expressions give rise to significant performance advantages. The profiling is carried out in the NuSMV framework using examples from discrete timed automata and circuits with delays. A variant tool called NuSMVDP has been developed for interpreting reachability expressions to carry out the experiments.     

Efficient processing of k-hop reachability queries

We study the problem of answering k -hop reachability queries in a directed graph, i.e., whether there exists a directed path of length $k$ , from a source query vertex to a target query vertex in the input graph. The problem of $k$ -hop reachability is a general problem of the classic reachability (where $k=\infty $ ). Existing indexes for processing classic reachability queries, as well as for processing shortest path distance queries, are not applicable or not efficient for processing $k$ -hop reachability queries. We propose an efficient index for processing $k$ -hop reachability queries. Our experimental results on a wide range of real datasets show that our method is efficient and scalable in terms of both index construction and query processing.     

Efficient processing of label-constraint reachability queries in large graphs

In this paper, we study a variant of reachability queries, called label-constraint reachability (LCR) queries. Specifically, given a label set S and two vertices u₁ and u₂ in a large directed graph G, we check the existence of a directed path from u₁ to u₂, where edge labels along the path are a subset of S. We propose the path-label transitive closure method to answer LCR queries. Specifically, we t4ransform an edge-labeled directed graph into an augmented DAG by replacing the maximal strongly connected components as bipartite graphs. We also propose a Dijkstra-like algorithm to compute path-label transitive closure by re-defining the “distance” of a path. Comparing with the existing solutions, we prove that our method is optimal in terms of the search space. Furthermore, we propose a simple yet effective partition-based framework (local path-label transitive closure+online traversal) to answer LCR queries in large graphs. We prove that finding the optimal graph partition to minimize query processing cost is a NP-hard problem. Therefore, we propose a sampling-based solution to find the sub-optimal partition. Moreover, we address the index maintenance issues to answer LCR queries over the dynamic graphs. Extensive experiments confirm the superiority of our method.     

Parallel processing of graph reachability in databases

In this paper we consider parallel processing of a graph represented by a database relation, and we achieved two objectives. First, we propose a methodology for analyzing the speedup of a parallel processing strategy with the purpose of selecting at runtime one of several candidate strategies, depending on the hardware architecture and the input graph. Second, we study the single-source reachability problem, namely the problem of computing the set of nodes reachable from a given node in a directed graph. We propose several parallel strategies for solving this problem, and we analyze their performance using our new methodology. The analysis is confirmed experimentally in a UNIX-Ethernet environment. We also extend the results to the transitive closure problem.A preliminary shortened version of this paper has appeared inPDIS. See Ref. 1.This author's work was supported in part by NSF Grant 90-03341.This author's work was supported in part by the Natural Sciences and Engineering Research Council of Canada.This author's work was supported in part by NSF Grant 90-03341.     

From regular expressions to smaller NFAs

Several methods have been developed to construct λ-free automata that represent a regular expression. Among the most widely known are the position automaton (Glushkov), the partial derivatives automaton (Antimirov) and the follow automaton (Ilie and Yu). All these automata can be obtained with quadratic time complexity, thus, the comparison criterion is usually the size of the resulting automaton. The methods that obtain the smallest automata (although, for general expressions, they are not comparable), are the follow and the partial derivatives methods. In this paper, we propose another method to obtain a λ-free automaton from a regular expression. The number of states of the automata we obtain is bounded above by the size of both the partial derivatives automaton and of the follow automaton. Our algorithm also runs with the same time complexity of these methods.     

有向无环图上k步可达查询优化算法

k步可达查询用于在给定的有向无环图（DAG）中回答两点之间是否存在长度不超过k的路径。针对现有方法的索引规模大、查询处理效率低的问题,提出一种基于部分点的双向最短路径索引来提升索引的可达信息覆盖率,并提出一组优化规则来减小索引规模;然后提出基于简化图的正反互逆拓扑索引来加速回答不可达查询;最后提出远距离优先的双向遍历策略来提高查询处理的效率。基于21个真实数据集（如引用网络、社交网络等）的实验结果表明,相比已有的高效方法PLL及BFSI-B,所提出的算法具有更小的索引规模和更快的查询响应速度。     

Answering reachability queries with ordered label constraints over labeled graphs

Reachability query plays a vital role in many graph analysis tasks. Previous researches proposed many methods to efficiently answer reachability queries between vertex pairs. Since many real graphs are labeled graph, it highly demands Label-Constrained Reachability (LCR) query in which constraint includes a set of labels besides vertex pairs. Recent researches proposed several methods for answering some LCR queries which require appearance of some labels specified in constraints in the path. Besides that constraint may be a label set, query constraint may be ordered labels, namely OLCR (Ordered-Label-Constrained Reachability) queries which retrieve paths matching a sequence of labels. Currently, no solutions are available for OLCR. Here, we propose DHL, a novel bloom filter based indexing technique for answering OLCR queries. DHL can be used to check reachability between vertex pairs. If the answers are not no, then constrained DFS is performed. So, we employ DHL followed by performing constrained DFS to answer OLCR queries. We show that DHL has a bounded false positive rate, and it’s powerful in saving indexing time and space. Extensive experiments on 10 real-life graphs and 12 synthetic graphs demonstrate that DHL achieves about 4.8–22.5 times smaller index space and 4.6–114 times less index construction time than two state-of-art techniques for LCR queries, while achieving comparable query response time. The results also show that our algorithm can answer OLCR queries effectively.     

Duration-constrained regular expressions

This paper investigates the logic-automata-connection for Duration Calculus. It has been frequently observed that Duration Calculus with linear duration terms comes close to being a logic of linear hybrid automata. We attempt to make this relation precise by constructing Kleene-connection between duration-constrained regular expressions and a subclass of linear hybrid automata called loop-reset automata in which any variable tested in a loop is reset in the same loop. The formalism of duration-constrained regular expressions is an extension of regular expressions with duration constraints, which are essentially formulas of Duration Calculus without negation, yet extended by a Kleene-star operator. In this paper, we show that this formalism is equivalent in expressive power to loop-reset automata by providing a translation procedure from expressions to automata and vice verse.Received June 1999Accepted in revised form September 2003 by M. R. Hansen and C. B. Jones     

Synchronized regular expressions

Text manipulation is one of the most common tasks for everyone using a computer. The increasing number of textual information in electronic format that every computer user collects everyday also increases the need of more powerful tools to interact with texts. Indeed, much work has been done to provide simple and versatile tools that can be useful for the most common text manipulation tasks. Regular Expressions (RE), introduced by Kleene, are well known in the formal language theory. RE have been extended in various ways, depending on the application of interest. In almost all the implementations of RE search algorithms (e.g. the egrep [15] UNIX command, or the Perl [20] language pattern matching constructs) we find backreferences, i.e. expressions that make reference to the string matched by a previous subexpression. Generally speaking, it seems that all kinds of synchronizations between subexpressions in a RE can be very useful when interacting with texts. In this paper we introduce the Synchronized Regular Expressions (SRE) as an extension of the Regular Expressions. We use SRE to present a formal study of the already known backreferences extension, and of a new extension proposed by us, which we call the synchronized exponents. Moreover, since we are dealing with formalisms that should have a practical utility and be used in real applications, we have the problem of how to present SRE to the final users. Therefore, in this paper we also propose a user-friendly syntax for SRE to be used in implementations of SRE-powered search algorithms. Received: 30 July 2001 / 16 May 2002 This research has been partially supported by MURST project TOSCA.     

NIDS中正则表达式数量限定符的电路设计与实现

针对网络入侵检测系统(NIDS)中复杂正则表达式匹配的数量限定符进行了硬件设计和实现。经过对这3种限定符匹配原理的分析,改变了以往的直接复制多个重复单元的实现方法,设计了一套完整的优化的数量限定符FPGA实现电路。实验测试结果表明,本设计每个非元字符平均大约需要0.92个逻辑单元,系统可以达到1.2 Gb/s的吞吐能力。     

Graph expressions and graph rewritings

We define an algebraic structure for the set of finite graphs, a notion of graph expression for defining them, and a complete set of equational rules for manipulating graph expressions. (By agraph we mean an oriented hypergraph, the hyperedges of which are labeled with symbols from a fixed finite ranked alphabet and that is equipped with a finite sequence of distinguished vertices). The notion of a context-free graph grammar is introduced (based on the substitution of a graph for a hyperedge in a graph). The notion of an equational set of graphs follows in a standard way from the algebraic structure. As in the case of context-free languages, a set of graphs is contextfree iff it is equational. By working at the level of expressions, we derive from the algebraic formalism a notion of graph rewriting which is as powerful as the usual one (based on a categorical approach) introduced by Ehrig, Pfender, and Schneider.This work has been supported by the PRC Mathématiques et Informatique. Reprints can be requested from B. Courcelle by electronic mail at the following address (UUCP network): mcvax!inria!geocub!courcell.