Abstract | ||
---|---|---|
Increasingly, enterprises require efficient graph processing capabilities to store and analyze the evolution of the graph topology over time. While a static graph captures information about the connectedness of vertices at a certain point in time, a time-varying graph keeps track of every data manipulation-insertion and removal of a vertex or an edge-performed on the graph and allows detecting topological changes, such as cluster growth and subgraph densification, and discovering behavioral patterns of the connected entities in the graph. Although temporal graph processing has been an active research area in the past decade, most well-known graph algorithms are defined on static graphs only. In this paper we study the problem of graph traversals and reachability in the presence of a temporal dimension and derive three classes of temporal traversals from a set of realistic use cases. We validate our prototypical implementations against two graph processing systems, a columnar graph execution engine and a native graph database management system. Our experimental evaluation on a large real-world graph dataset demonstrates the generality and applicability of our solution and shows the scalability of our proposed temporal traversal operators to different graph sizes. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1007/978-3-319-41576-5_13 | BIOMEDICAL DATA MANAGEMENT AND GRAPH ONLINE QUERYING |
Field | DocType | Volume |
Data mining,Graph,Behavioral pattern,Social connectedness,Tree traversal,Vertex (geometry),Graph traversal,Computer science,Theoretical computer science,Reachability,Topological graph theory | Conference | 9579 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
7 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Max Wildemann | 1 | 0 | 0.34 |
Michael Rudolf | 2 | 0 | 0.34 |
Marcus Paradies | 3 | 82 | 10.36 |