In many applications, entities and their relationships are represented by graphs. Examples include social networks (users and friendship), the WWW (web pages and hyperlinks) and bibliographic networks (authors and co-authorship). In a dynamic world, information changes and so the graphs representing the information evolve with time. For example, a Facebook link between two friends is established, or a hyperlink is added to a web page. We propose that historical graph-structured data be archived for analytical processing. We call a historical evolving graph sequence an EGS. We study the problem of efficient query processing on an EGS, which finds many applications that lead to interesting evolving graph analysis. To solve the problem, we propose a solution framework called FVF and a cluster-based LU decomposition algorithm called CLUDE, which can evaluate queries efficiently to support EGS analysis. The Find-Verify-and-Fix (FVF) framework applies to a wide range of queries. We demonstrate how some important graph measures, including shortest-path distance, closeness centrality and graph centrality, can be efficiently computed from EGSs using FVF. Since an EGS generally contains numerous large graphs, we also discuss several compact storage models that support our FVF framework. Through extensive experiments on both real and synthetic datasets, we show that our FVF framework is highly efficient in EGS query processing. A graph can be conveniently modeled by a matrix from which various quantitative measures are derived like PageRank and SALSA and Personalized PageRank and Random Walk with Restart. To compute these measures, linear systems of the form Ax = b, where A is a matrix that captures a graph's structure, need to be solved. To facilitate solving the linear system, the matrix A is often decomposed into two triangular matrices (L and U). In a dynamic world, the graph that models it changes with time and thus is the matrix A that represents the graph. We consider a sequence of evolving graphs and its associated sequence of evolving matrices. We study how LU-decomposition should be done over the sequence so that (1) the decomposition is efficient and (2) the resulting LU matrices best preserve the sparsity of the matrices A's (i.e., the number of extra non-zero entries introduced in L and U are minimized). We propose a cluster-based algorithm CLUDE for solving the problem. Through an experimental study, we show that CLUDE is about an order of magnitude faster than the traditional incremental update algorithm. The number of extra non-zero entries introduced by CLUDE is also about an order of magnitude fewer than that of the traditional algorithm. CLUDE is thus an efficient algorithm for LU decomposition that produces high-quality LU matrices over an evolving matrix sequence. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

The prevalence of graph-structured data in modern real-world applications has led to a rejuvenation of research on graph data management and analytics. Several database query languages have been proposed for textually querying graph databases. Unfortunately, formulating a graph query using any of these query languages often demands considerable cognitive effort and requires "programming" skill at least similar to programming in SQL. Yet, in a wide spectrum of graph applications consumers need to query graph data but are not proficient query writers. Hence, it is important to devise intuitive techniques that can alleviate the burden of query formulation and thus increase the usability of graph databases. In this dissertation, we take the first step to study the graph query autocompletion problem. We provide techniques that take a user's graph query as input and generate top-k query suggestions as output, to help to alleviate the verbose and error-prone graph query formulation process in a visual environment. Firstly, we study visual query autocompletion for graph databases. Techniques for query autocompletion have been proposed for web search and XML search. However, a corresponding capability for graph query engine is in its infancy. We propose a novel framework for graph query autocompletion (called AutoG). The novelties of AutoG are as follows: First, we formalize query composition that specifies how query suggestions are formed. Second, we propose to increment a query with the logical units called c-prime features, that are (i) frequent subgraphs and (ii) constructed from smaller c-prime features in no more than c ways. Third, we propose algorithms to rank candidate suggestions. Fourth, we propose a novel index called feature DAG (FDAG) to further optimize the ranking. Secondly, we propose user focus-based graph query autocompletion. AutoG provides suggestions that are formed by adding subgraph increments to arbitrary places of an existing user query. However, humans can only interact with a small number of recent software artifacts in hand. Hence, many such suggestions could be irrelevant. We present the GFocus framework that exploits a novel notion of user focus of graph query formulation. Intuitively, the focus is the subgraph that a user is working on. We formulate locality principles to automatically identify and maintain the focus. We propose novel monotone submodular ranking functions for generating popular and comprehensive query suggestions only at the focus. We propose efficient algorithms and an index for ranking the suggestions. Thirdly, we propose graph query autocompletion for large graphs. Graph features that have been exploited in AutoG are either absent or rare in large graphs. To address this, we present Flexible graph query autocompletion for LArge Graphs, called FLAG. We propose wildcard label for query graph and query suggestions. In particular, FLAG allows augmenting users' queries using subgraph increments with wildcard labels, which summarize query suggestions that have similar increment structures but different labels. We propose an efficient ranking algorithm and a novel index, called Suggestion Summarization DAG (SSDAG), to optimize the online suggestion ranking. Detailed problem analysis and extensive experimental studies consistently demonstrate the effectiveness and robustness of our proposed techniques in a broad range of settings.

No abstract available. / Thesis (Ph.D.)-University of KwaZulu-Natal, Westville, 2007.

The object of this paper is to investigate the behavior of some important graph properties and to statistically analyze the execution times of certain graph are the average degree of a vertex, connectivity of a graph, the existence of Hamilton cycles, Euler tours, and bipartitions in graphs. This study is unique in that it is based on statistical rather than deterministic methods.

We introduce a weighted model of random trees and analyze the asymptotic properties of their heights. Our framework encompasses most trees of logarithmic height that were introduced in the context of the analysis of algorithms or combinatorics. This allows us to state a sort of "master theorem" for the height of random trees, that covers binary search trees (Devroye, 1986), random recursive trees (Devroye, 1987; Pittel, 1994), digital search trees (Pittel, 1985), scale-free trees (Pittel, 1994; Barabasi and Albert, 1999), and all polynomial families of increasing trees (Bergeron et al., 1992; Broutin et al., 2006) among others. Other applications include the shape of skinny cells in geometric structures like k-d and relaxed k-d trees. / This new approach sheds new light on the tight relationship between data structures like trees and tries that used to be studied separately. In particular, we show that digital search trees and the tries built from sequences generated by the same memoryless source share the same stable core. This link between digital search trees and tries is at the heart of our analysis of heights of tries. It permits us to derive the height of several species of tries such as the trees introduced by de la Briandais (1959) and the ternary search trees of Bentley and Sedgewick (1997). / The proofs are based on the theory of large deviations. The first order terms of the asymptotic expansions of the heights are geometrically characterized using the Crame'r functions appearing in estimates of the tail probabilities for sums of independent random variables.

No description available.

Petri nets are used as models in the study of networks involving information flows. Petri nets have also turned out to be useful in the study of many asynchronous concurrent systems.In this thesis, the notions of deadlocks, traps, and liveness are considered from a graph theoretic viewpointA characterization of minimal deadlocks and traps in Petri nets is obtained. For the complete Petri nets, alternative characterizations of deadlocks and traps are obtained. Necessary and sufficient conditions are obtained for complete Petri nets to be deadlock free. Similar conditions for trap free complete Petri nets are also determined. / Department of Computer Science

Graph theory is a relatively new way of thinking in mathematics. Graphs can model a number of different problems. Graph theory introduces solutions to many problems which human beings have faced since ancient times.A study of graphs will not be complete without an introduction to both theory and algorithms. Invention of the tools for studying graphs is necessary in order to help people learn the theory and execute the algorithms. The study of graphs itself, by nature, needs graphical representation which can give clearer images for a better understanding. A windowing environment is selected as an instrument for developing a device to study graphs because of its friendly Graphical User Interface. / Department of Computer Science

M.Sc. (Computer Science) / In this thesis a study is made of graphs, graph grammars as well as grammars which represent structures in three dimensions. Structure graphs are defined for the first time in this thesis. The definition thereof is based upon that of ordinary graphs, they differ however in that certain geometric properties are assigned to the arcs of the graphs, Two different types of structure graph grammars are defined. Structure graph grammars derive structure graphs as language. The geometric properties of the structure graphs appear as context's in the grammars. A study is mode of the properties of· the structure graph grammars. A comparison between the two types of grammars is also given. The properties of the languages derived by each are also discussed. Existing computer systems which model chemical processes are also discussed. Finally a discussion is given of a software system which was developed as part of this study.

by Ho Kei Shiu Edward. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1992. / Includes bibliographical references (leaves 199-202). / Acknowledgement / Abstract / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Initial Motivations --- p.1 / Chapter 1.2 --- Objectives of Our Study --- p.2 / Chapter 1.3 --- Outline of the Thesis --- p.3 / Chapter Chapter 2 --- Basics of the Procedure Graph Theory --- p.6 / Chapter 2.1 --- Introducing Procedure Graph Theory --- p.6 / Chapter 2.1.1 --- "Nodes, Arcs and Pseudo-time Labels" --- p.7 / Chapter 2.2 --- Examples --- p.12 / Chapter 2.3 --- Exploring the Meanings of the Pseudo-time Labels --- p.13 / Chapter 2.4 --- Equivalence and Transformation --- p.16 / Chapter 2.4.1 --- Equivalence --- p.16 / Chapter 2.4.2 --- Transmission Track and Causality Preservation --- p.16 / Chapter 2.4.3 --- Transformation --- p.17 / Chapter 2.4.3.1 --- Serial-to-Parallel Transformations (SP) --- p.18 / Chapter 2.4.3.2 --- Parallel-to-Serial Transformations (PS) --- p.20 / Chapter 2.4.3.3 --- Store-Store Cancellations (SSC) --- p.21 / Chapter 2.4.3.4 --- Normalization of Pseudo-time Labels --- p.23 / Chapter 2.4.3.5 --- Boundary Conditions and Multi-level Pseudo-time Labels --- p.24 / Chapter 2.5 --- Procedure Graph Optimizations --- p.28 / Chapter 2.5.1 --- Representing Dependencies --- p.28 / Chapter 2.5.2 --- Eliminating Unnecessary Dependencies --- p.32 / Chapter 2.6 --- Simulation Program --- p.36 / Chapter 2.6.1 --- Preliminary Study Using the Simulation Program --- p.36 / Chapter 2.6.2 --- Economic Factors --- p.37 / Chapter 2.6.3 --- Combinatorial Explosion of Procedure Graphs --- p.38 / Chapter Chapter 3 --- Extending the Procedure Graph Theory --- p.45 / Chapter 3.1 --- The T-Operator and the F-Operator --- p.45 / Chapter 3.2 --- Modifying the Firing Rule --- p.46 / Chapter 3.3 --- Procedure Graph Representation for Different Branch Strategies --- p.49 / Chapter 3.3.1 --- Multiple-Path Execution --- p.49 / Chapter 3.3.2 --- Conditional Execution with Delayed Commitment of Results --- p.51 / Chapter 3.3.3 --- Speculative Execution with Register Backup and Branch Repair --- p.52 / Chapter 3.4 --- Procedure Graph Representation for a Stack --- p.56 / Chapter 3.5 --- Vector Forwarding --- p.58 / Chapter 3.5.1 --- An Example of Vector Chaining in Cray-1 --- p.58 / Chapter 3.5.2 --- "Vector SP, PS and SSC" --- p.59 / Chapter 3.5.3 --- A Note Concerning the Use of Algorithmic Time Labels --- p.61 / Chapter 3.5.4 --- Further Consideration of Vector Forwarding --- p.62 / Chapter Chapter 4 --- Hardware Realization of Procedure Graph Optimizations --- p.64 / Chapter 4.1 --- Node-Oriented Versus Arc-Oriented Representation --- p.64 / Chapter 4.2 --- Backward Pointers Versus Forward Pointers --- p.65 / Chapter 4.3 --- Backward Pointers as Hardware Tags --- p.69 / Chapter 4.4 --- Pointer Algebra --- p.72 / Chapter 4.4.1 --- Serial-to-Parallel Transformations --- p.72 / Chapter 4.4.2 --- Store-Store Cancellations --- p.73 / Chapter 4.4.3 --- Parallel-to-Serial Transformations --- p.74 / Chapter 4.5 --- Drawbacks of Using Backward Pointers --- p.75 / Chapter 4.6 --- Multiple Tags --- p.76 / Chapter Chapter 5 --- A Backward-Pointer Representation Scheme :The T-Architecture --- p.82 / Chapter 5.1 --- The T-Architecture --- p.82 / Chapter 5.2 --- Local Addressing Space Within the CPU --- p.83 / Chapter 5.3 --- Why Reservation Stations --- p.84 / Chapter 5.4 --- Memory Data Forwarding --- p.89 / Chapter 5.4.1 --- The Updating Buffer --- p.90 / Chapter 5.4.2 --- Ordering and Consistency --- p.96 / Chapter 5.4.2.1 --- Store After Store --- p.96 / Chapter 5.4.2.2 --- Store After Load --- p.97 / Chapter 5.5 --- Speculative Execution --- p.97 / Chapter 5.5.1 --- Procedural Dependencies --- p.97 / Chapter 5.5.2 --- Branch Instruction Format --- p.98 / Chapter 5.5.3 --- Branch Prediction --- p.99 / Chapter 5.5.4 --- Branch Instruction Unit --- p.99 / Chapter 5.5.5 --- Register Backups --- p.100 / Chapter 5.5.5.1 --- Branch is Correctly Predicted --- p.101 / Chapter 5.5.5.2 --- Branch Repair --- p.102 / Chapter 5.5.5.3 --- Example --- p.102 / Chapter 5.5.6 --- Total Ordering Memory Stores --- p.110 / Chapter 5.5.7 --- Simplifying the Checkpoint Repair Mechanism --- p.112 / Chapter 5.6 --- A Simulator for the T-Architecture --- p.113 / Chapter 5.6.1 --- Basic Configuration of the Simulator --- p.114 / Chapter 5.6.2 --- Parameters of the Simulator --- p.115 / Chapter 5.6.3 --- Benchmark Programs --- p.116 / Chapter 5.7 --- Experiments --- p.118 / Chapter 5.7.1 --- Experiment1 --- p.119 / Chapter 5.7.2 --- Experiment2 --- p.121 / Chapter 5.7.3 --- Experiment3 --- p.123 / Chapter 5.7.4 --- Experiment4 --- p.127 / Chapter Chapter 6 --- Predictive Procedure Graph Optimizations in the S-Prototype --- p.137 / Chapter 6.1 --- Keys to Higher Performance --- p.138 / Chapter 6.2 --- The Superscalar Approach --- p.139 / Chapter 6.3 --- Processor Architecture of the S-Prototype --- p.139 / Chapter 6.4 --- Design Strategies of the S-Prototype --- p.141 / Chapter 6.4.1 --- Fetching Multiple Instructions --- p.142 / Chapter 6.4.2 --- Handling Procedural Dependencies : Branching Instructions --- p.142 / Chapter 6.4.2.1 --- Branch Unit and Branch Predicting Buffer --- p.143 / Chapter 6.4.2.2 --- Branch Repairing - Recovering Machine State --- p.144 / Chapter 6.4.3 --- Extensive Tagging and Result Forwarding --- p.147 / Chapter 6.4.4 --- Static and Dynamic Data Dependencies --- p.148 / Chapter 6.4.4.1 --- Handling Static Dependencies by using the Multitag Pool --- p.149 / Chapter 6.4.4.2 --- Handling Dynamic Dependencies by using the Reservation Stations --- p.150 / Chapter 6.4.5 --- Extracting Parallelism --- p.152 / Chapter 6.4.5.1 --- Representing Data Dependency in the Multitag Pool --- p.153 / Chapter 6.4.5.2 --- Implementing Transformation Rules --- p.156 / Chapter 6.4.6 --- Out-of-order Issue and Execution --- p.157 / Chapter 6.4.7 --- Memory Accesses --- p.158 / Chapter 6.4.8 --- Bus Contention and Arbitration --- p.160 / Chapter Chapter 7 --- An Attempt To Simulate Procedure Graphs Using Graph Grammar --- p.161 / Chapter 7.1 --- Introducing Graph Grammar --- p.161 / Chapter 7.2 --- Basic Concepts in Sequential Graph Grammar --- p.161 / Chapter 7.2.1 --- Production Rules and Interface Graph --- p.162 / Chapter 7.2.2 --- Gluing Constructions and Pushouts --- p.162 / Chapter 7.2.3 --- Gluing Conditions --- p.163 / Chapter 7.3 --- Initial Considerations to Simulate Procedure Graphs --- p.165 / Chapter 7.4 --- Example --- p.165 / Chapter 7.5 --- Problems Encountered --- p.167 / Chapter 7.6 --- Some Insights into the Unsolved Problem --- p.168 / Chapter 7.7 --- "Parallelism, Concurrency and New Transformation Rules" --- p.171 / Chapter Chapter 8 --- Representing Causality Using Petri Nets --- p.175 / Chapter 8.1 --- Defining Petri Nets --- p.175 / Chapter 8.1.1 --- Petri Nets as a Tool for System Modeling --- p.176 / Chapter 8.1.2 --- The Characteristics of a Petri Net --- p.177 / Chapter 8.1.3 --- Useful Extensions --- p.178 / Chapter 8.2 --- Program Analysis and Modeling Computer Operations --- p.179 / Chapter 8.2.1 --- Representing Causality Relationships --- p.180 / Chapter 8.2.2 --- Representing the Total Ordering of Instructions in a Sequential Program --- p.184 / Chapter 8.3 --- Extending the Model --- p.186 / Chapter 8.4 --- Comparing Procedure Graphs and Petri Nets --- p.188 / Chapter Chapter 9 --- Conclusion and Future Research Directions --- p.190 / Chapter 9.1 --- Formalizing the Procedure Graph Theory --- p.190 / Chapter 9.2 --- Mathematical Properties of Procedure Graphs --- p.191 / Chapter 9.3 --- Register Abuses --- p.192 / Chapter 9.4 --- Hardware Representation of Procedure Graphs --- p.194 / Chapter 9.5 --- Tags Describing Tags --- p.196 / Chapter 9.6 --- Software Optimizations --- p.197 / Chapter 9.7 --- Simulation Programs --- p.198 / References --- p.199