Summarizing semantic graphs: a survey <s> Quotient graph summaries <s> We present improved partition refinement algorithms for three problems: lexicographic sorting, relational coarsest partition, and double lexical ordering. Our double lexical ordering algorithm uses a new, efficient method for unmerging two sorted sets. <s> BIB001 </s> Summarizing semantic graphs: a survey <s> Quotient graph summaries <s> We present algorithms for computing similarity relations of labeled graphs. Similarity relations have applications for the refinement and verification of reactive systems. For finite graphs, we present an O(mn) algorithm for computing the similarity relation of a graph with n vertices and m edges (assuming m/spl ges/n). For effectively presented infinite graphs, we present a symbolic similarity-checking procedure that terminates if a finite similarity relation exists. We show that 2D rectangular automata, which model discrete reactive systems with continuous environments, define effectively presented infinite graphs with finite similarity relations. It follows that the refinement problem and the /spl forall/CTL* model-checking problem are decidable for 2D rectangular automata. <s> BIB002 </s> Summarizing semantic graphs: a survey <s> Quotient graph summaries <s> In recent years there has been an increased interest in managing data that does not conform to traditional data models, like the relational or object oriented model. The reasons for this non-conformance are diverse. On the one hand, data may not conform to such models at the physical level: it may be stored in data exchange formats, fetched from the Web, or stored as structured files. One the other hand, it may not conform at the logical level: data may have missing attributes, some attributes may be of different types in different data items, there may be heterogeneous collections, or the schema may be too complex or changes too often. The term semistructured data has been used to refer to such data. The semistructured data model consists of an edge-labeled graph, in which nodes correspond to objects and edges to attributes or values. Figure 1 illustrates a semistructured database providing information about a city. <s> BIB003 </s> Summarizing semantic graphs: a survey <s> Quotient graph summaries <s> In this paper, we ask if the traditional relational query acceleration techniques of summary tables and covering indexes have analogs for branching path expression queries over tree- or graph-structured XML data. Our answer is yes --- the forward-and-backward index already proposed in the literature can be viewed as a structure analogous to a summary table or covering index. We also show that it is the smallest such index that covers all branching path expression queries. While this index is very general, our experiments show that it can be so large in practice as to offer little performance improvement over evaluating queries directly on the data. Likening the forward-and-backward index to a covering index on all the attributes of several tables, we devise an index definition scheme to restrict the class of branching path expressions being indexed. The resulting index structures are dramatically smaller and perform better than the full forward-and-backward index for these classes of branching path expressions. This is roughly analogous to the situation in multidimensional or OLAP workloads, in which more highly aggregated summary tables can service a smaller subset of queries but can do so at increased performance. We evaluate the performance of our indexes on both relational decompositions of XML and a native storage technique. As expected, the performance benefit of an index is maximized when the query matches the index definition. <s> BIB004 </s> Summarizing semantic graphs: a survey <s> Quotient graph summaries <s> XML and other semi-structured data may have partially specified or missing schema information, motivating the use of a structural summary which can be automatically computed from the data. These summaries also serve as indices for evaluating the complex path expressions common to XML and semi-structured query languages. However, to answer all path queries accurately, summaries must encode information about long, seldom-queried paths, leading to increased size and complexity with little added value. We introduce the A(k)-indices, a family of approximate structural summaries. They are based on the concept of k-bisimilarity, in which nodes are grouped based on local structure, i.e., the incoming paths of length up to k. The parameter k thus smoothly varies the level of detail (and accuracy) of the A(k)-index. For small values of k, the size of the index is substantially reduced. While smaller, the A(k) index is approximate, and we describe techniques for efficiently extracting exact answers to regular path queries. Our experiments show that, for moderate values of k, path evaluation using the A(k)-index ranges from being very efficient for simple queries to competitive for most complex queries, while using significantly less space than comparable structures. <s> BIB005 </s> Summarizing semantic graphs: a survey <s> Quotient graph summaries <s> To facilitate queries over semi-structured data, various structural summaries have been proposed. Structural summaries are derived directly from the data and serve as indices for evaluating path expressions on semi-structured or XML data. We introduce the D(k) index, an adaptive structural summary for general graph structured documents. Building on previous work, 1-index and A(k) index, the D(k)-index is also based on the concept of bisimilarity. However, as a generalization of the 1-index and A(k)-index, the D(k) index possesses the adaptive ability to adjust its structure according to the current query load. This dynamism also facilitates efficient update algorithms, which are crucial to practical applications of structural indices, but have not been adequately addressed in previous index proposals. Our experiments show that the D(k) index is a more effective structural summary than previous static ones, as a result of its query load sensitivity. In addition, update operations on the D(k) index can be performed more efficiently than on its predecessors. <s> BIB006 </s> Summarizing semantic graphs: a survey <s> Quotient graph summaries <s> As Web applications mature and evolve, the nature of the semistructured data that drives these applications also changes. An important trend is the need for increased flexibility in the structure of Web documents. Hence, applications cannot rely solely on schemas to provide the complex knowledge needed to visualize, use, query and manage documents. Even when XML Web documents are valid with regard to a schema, the actual structure of such documents may exhibit significant variations across collections for several reasons: the schema may be very lax (e.g., RSS feeds), the schema may be large and different subsets of it may be used in different documents (e.g., industry standards like UBL), or open content models may allow arbitrary schemas to be mixed (e.g., RSS extensions like those used for podcasting). For these reasons, many applications that incorporate XPath queries to process a large Web document collection require an understanding of the actual structure present in the collection, and not just the schema. To support modern Web applications, we introduce DescribeX, a powerful framework that is capable of describing complex XML summaries of Web collections. DescribeX supports the construction of heterogenous summaries that can be declaratively defined and refined by means of axis path regular expression (AxPREs). AxPREs provide the flexibility necessary for declaratively defining complex mappings between instance nodes (in the documents) and summary nodes. These mappings are capable of expressing order and cardinality, among other properties, which can significantly help in the understanding of the structure of large collections of XML documents and enhance the performance of Web applications over these collections. DescribeX captures most summary proposals in the literature by providing (for the first time) a common declarative definition for them. Experimental results demonstrate the scalability of DescribeX summary operations (summary creation, as well as refinement and stabilization, two key enablers for tailoring summaries) on multi-gigabyte Web collections. <s> BIB007 </s> Summarizing semantic graphs: a survey <s> Quotient graph summaries <s> In this paper, we present, to our knowledge, the first known I/O efficient solutions for computing the k-bisimulation partition of a massive directed graph, and performing maintenance of such a partition upon updates to the underlying graph. Ubiquitous in the theory and application of graph data, bisimulation is a robust notion of node equivalence which intuitively groups together nodes in a graph which share fundamental structural features. k-bisimulation is the standard variant of bisimulation where the topological features of nodes are only considered within a local neighborhood of radius k > 0. The I/O cost of our partition construction algorithm is bounded by O(k · sort}(|Et|) + k · scan(|Nt|) + sort(|Nt|)), while our maintenance algorithms are bounded by O(k · sort}(|Et|) + k · scan(|Nt|). The space complexity bounds are O(|Nt|+|Et|)$ and O(k · |Nt|+k ·|Et|), resp. Here, |Et| and |Nt| are the number of disk pages occupied by the input graph's edge set and node set, resp., and sort(n) and scan(n) are the cost of sorting and scanning, resp., a file occupying n pages in external memory. Empirical analysis on a variety of massive real-world and synthetic graph datasets shows that our algorithms perform efficiently in practice, scaling gracefully as graphs grow in size. <s> BIB008
Many proposals for indexing graph data are based on establishing some notion of equivalence among graph nodes, and storing the IDs of all nodes as the extent of the summary node. Formally, these correspond to quotient graphs, whose definition we recall below: Prominent node equivalence relations used for graph summarization build on backward, forward, or backwardand-forward bisimulation BIB002 : Forward bisimulation, noted ≈ f , is defined similarly to backward simulation, but considers the outgoing edges of v and v , instead of the incoming ones. Forward and backward Table 1 Graph summaries based on structural quotients We already pointed out that, in Fig. 1 , the graph on the right is homomorphic to that on the left. The former is actually the quotient graph of the latter using ≈ f b . In particular, the classes of ≈ b -equivalent nodes are {1}, {2, 3, 4, 5}, {6, 8, 9}, {7}, those of ≈ f -equivalent nodes are {1}, {2}, {3, 4}, {5, 6, 7, 8, 9}, and those of ≈ f bequivalent nodes are {1}, {2}, {3, 4}, {5}, {6}, {7}, {8, 9}. Finally, we remark that it easily follows from the bisimulation definitions that if v ≈ v , for instance for forward bisimulation, then any label path that can be followed from v in the graph G can also be followed from v in G and the other way around. In other words, the same paths start (respectively, end) in two ≈-equivalent nodes. This condition is hard to meet in graphs that exhibit some structural heterogeneity: in such cases, every node is ≈-equivalent to very few (if any) other nodes. The Template Index (or T-index) BIB003 summary considers that two graph nodes are equivalent if they are backward bisimilar. In particular, in a T-index, nodes represented together need to be reachable by the exact same set of incoming paths. The goal of the T-index is to speed up the evaluation of complex queries of a certain form (or template), such as P.v (all nodes v reachable by a path matching the regular expression P) or v.P.u (all v, u node pairs connected by a path matching P); the proposal generalizes to arbitrary arity queries, although the authors note it is likely to be most useful in the above two simplest forms. The simulation relation between the nodes of a graph G is known to be computable in O(M * log(M)) BIB001 or O(N * M) BIB002 ; the cost drops to linear for acyclic graphs. All these algorithms assume the graph fits in memory. To support efficient processing of graph queries that navigate both forward (in the direction of the graph edges) and backward, Kaushik et al. BIB004 describes the Forward and Backward Index (F&B) which considers two nodes equivalent if they are undistinguishable by any navigation path composed only of forward and backward steps (see Fig. 5 for an example). While this equivalence condition is very powerful, it is rarely satisfied by two nodes, thus the F&B-index is likely to have a large amount of nodes (close to the number of nodes in the original graph), making the manipulation of the F&B-index structure inefficient. To address the problem, the authors note that in practice not any path query is frequently asked by applications; therefore, it suffices to consider F&B equivalence of nodes as being undistinguishable by forward and backward navigation along the paths from a certain set only. Another method proposed in BIB005 BIB006 , in order to make the F&B-index smaller and more manageable, is to consider bisimilarity restricted only to paths of a certain length around the graph nodes (see Fig. 5 for an example). This increases the chances that two nodes be considered equivalent, thus reducing the size of the bisimilarity-based summary. Limited bisimulation summaries like this, can be computed by evaluating structural group-by queries (for k-bounded bisimilarity), respectively, queries derived from the workload of interest (for workload-driven F&B summarization). While the theoretical complexity of such queries is O(M k ), with M the number of edges and k the size of the most complex query involved, efficient graph query processors, with the help of good indexing, achieve much better performance in practice. Consens et al. BIB007 considers the summarization of large Web document collections. While the main structure in this case consists of trees, they may also feature reference edges which turn the dataset into a global graph. The authors build a summary as a collection of regular expression queries, such that the set of results to these queries, together, make up a partition over the set of nodes in all the documents of the input collection. To each such regular expression is associated a set of cardinality statistics, to help application designers chose meaningful queries and inform them on the expected performance which may be reached on those queries. The dominant-cost operation required by this approach is computing simulations among N nodes; summaries can then be refined based on user-specified path queries. Luo et al. BIB008 provides an I/O efficient external memorybased algorithm for constructing the k-bisimulation summary of a disk-resident graph on a single machine, based on several passes of sorting and gradually refining partitions of nodes on disk. The I/O complexity of the algorithm is , where M p , respectively, N p are the numbers of disk pages required to store the graph edges, respectively, graph nodes, while sort(·) and scan(·) quantify the cost of an external sort, respectively, the cost to scan a certain number of pages.