-
Notifications
You must be signed in to change notification settings - Fork 11
Time Series Graphs
Yogesh Simmhan edited this page Aug 13, 2016
·
6 revisions
- Presented by Abhilash
- Frame is a snapshot. Points to next snapshot, and all vertices and edges in the same frame.
- Vertices and edges modeled as nodes in Neo4J
- Newo4J relations between edge, its source and sink vertex.
- Temporal indexing: Tree to help identify the snapshots within a given time range.
- Types of queries
- Snapshots in a time range satisfying a graph property
- Return all vertices that matches a given predicate in a given snapshot
- Return a subgraph BFS
- TODO:
- Additional reading: Data and query model for TS graphs, Timeseries in Titan [AS]
- Presented by Abhilash
- Space: Node, neighbor, graph, size
- Time: Point, interval
- Snapshot over time. Key-Val pairs for vertices and edges. Different schemas for different vertices/edges.
- Node-centric model.
- Temporal node with many time-specific states for a given vertex.
- Set of temporal nodes: Temporal nodes within same interval.
- Temporal Subgraph
- Dimensions for filtering (Cube)
- Node (select), Attribute (Filter), Time (Timeslice)
- Map operation can be applied on temporal node, or a snapshot of the node. one result for template or one result per snapsoht.
- Evolution, ...
- Presented by Abhilash
- Approaches to temporal graph: Copy creates snapshot at each interval, Log of deltas, Copy+Log keeps snapshots and deltas between them
- Delta is a change to a graph component. Sum of deltas: take latest of overlapping vertices, union of non-overlapping; difference, intersection, union;
- For each timespan, one graph forms the reference static graph for partitioning, e.g. median time, union-max, union mean.
- Store versions of a partition, for a timespan, as a binary tree having original graph and deltas between parent and children to build different snapshots. Leaves of tree are snapshots. Inter-snapshot deltas also stored between leaves.
- Reconstruct a node or a partition for a given timepoint from the tree.
- Version chain for a given node: list of all partitions and event lists