= Time Scale Event Meta Model =
:neo4j-version: 2.0.0-RC1
:author: Kenny Bastani
:twitter: @kennybastani

Recently at the http://www.graphconnect.com/san-francisco[GraphConnect 2013 conference in San Francisco], many questions were asked about how to handle temporal or time-based traversals in a Neo4j graph database.

The goal of this GraphGist is to provide you with a lens to help you see information as simple temporal facts that are captured across space and time.

"Time is a dimension in which events can be ordered from the past through the present into the future." - via http://en.wikipedia.org/wiki/Time[Wikipedia - Time]

image::https://raw.github.com/kbastani/gists/master/meta/time-line.png[Timeline]

Graph databases like Neo4j are not just a traditional data store. Rather, graph databases are an entirely new paradigm that aids a person in capturing meaning from the world as relativistic information described by connected data. 

== What is relativistic information? ==

Relatvistic information is actually meaning. Unconnected data has no meaning. Only when you connect data can you better describe what it actually means.

Observations are made, captured, from a perspective of a position in time and space. A graph is a model of that space.

A graph database provides you a means to model space and see information from the perspective of a point relative to other points. Those points can represent a condition or state of the world.

Consider the example below. 

* Pam met Sally.
* John met Sally.
* Sally met Anne.
* Anne met Pam.

Each point on the graph is from the perspective of a person relative to meeting other people.

image::https://raw.github.com/kbastani/gists/master/meta/event-model-1.png[Event_Model]

The need to understand these nodes temporally, ordered linearly as time-based events, starts with modeling time as a graph.

== What is a time graph? ==

Time is a hierarchical model of categorization that enables the back-referencing or prediction of events on a timeline that moves forward in a single direction.

image::https://raw.github.com/kbastani/gists/master/meta/TSEMM-v1.04.png[Time_Scale_Event_Meta_Model]

In the time scale graph that is modeled above, a shortest path traversal from a blue colored node to the transparent colored node constitutes a unique time identity in bits.

The identity traced by the red path is 0->1->0->1->0->0. The reverse path is 0->0->1->0->1->0 or simply 001010, a unique identity in bits.

//hide
//setup
[source,cypher]
----
CREATE (a:a { key:'a0', tempo:'0' }) 
CREATE (a)<-[:child_of]-(b0:b { key:'b0', tempo:'0' }) 
CREATE (a)<-[:child_of]-(b1:b { key:'b1', tempo:'1' }) 
CREATE b0<-[:child_of]-(c0:c { key:'c0', tempo:'0' }) 
CREATE b0<-[:child_of]-(c1:c { key:'c1', tempo:'1' }) 
CREATE b1<-[:child_of]-(c2:c { key:'c2', tempo:'0' }) 
CREATE b1<-[:child_of]-(c3:c { key:'c3', tempo:'1' }) 
CREATE (d0:d { key:'d0', tempo:'0', interval:'50' }),(d1:d { key:'d1', tempo:'1', interval:'50' }) 
CREATE (d2:d { key:'d2', tempo:'0', interval:'50' }),(d3:d { key:'d3', tempo:'1', interval:'50' }) 
CREATE (d4:d { key:'d4', tempo:'0', interval:'50' }),(d5:d { key:'d5', tempo:'1', interval:'50' }) 
CREATE (d6:d { key:'d6', tempo:'0', interval:'50' }),(d7:d { key:'d7', tempo:'1', interval:'50' }) 
CREATE c0<-[:child_of]-d0, c0<-[:child_of]-d1 
CREATE c1<-[:child_of]-d2, c1<-[:child_of]-d3 
CREATE c2<-[:child_of]-d4, c2<-[:child_of]-d5 
CREATE c3<-[:child_of]-d6, c3<-[:child_of]-d7 
CREATE d0-[:NEXT]->d1-[:NEXT]->d2-[:NEXT]->d3-[:NEXT]->d4-[:NEXT]->d5-[:NEXT]->d6-[:NEXT]->d7 
CREATE (a1:a { key:'a1', tempo:'1' }) 
CREATE (a1)<-[:child_of]-(b2:b { key:'b2', tempo:'0' }) 
CREATE (a1)<-[:child_of]-(b3:b { key:'b3', tempo:'1' }) 
CREATE (z0:z { key: 'z0' , tempo:'0' })<-[:child_of]-(a1) 
CREATE (y0:y { key: 'y0' , tempo:'0' })<-[:child_of]-(z0) 
CREATE (z0)<-[:child_of]-(a) 
CREATE b2<-[:child_of]-(c4:c { key:'c4', tempo:'0' }) 
CREATE b2<-[:child_of]-(c5:c { key:'c5', tempo:'1' }) 
CREATE b3<-[:child_of]-(c6:c { key:'c6', tempo:'0' }) 
CREATE b3<-[:child_of]-(c7:c { key:'c7', tempo:'1' }) 
CREATE (d8:d { key:'d8', tempo:'0', interval:'50' }),(d9:d { key:'d9', tempo:'1', interval:'50' }) 
CREATE (d10:d { key:'d10', tempo:'0', interval:'50' }),(d11:d { key:'d11', tempo:'1', interval:'50' }) 
CREATE (d12:d { key:'d12', tempo:'0', interval:'50' }),(d13:d { key:'d13', tempo:'1', interval:'50' }) 
CREATE (d14:d { key:'d14', tempo:'0', interval:'50' }),(d15:d { key:'d15', tempo:'1', interval:'50' }) 
CREATE c4<-[:child_of]-d8, c4<-[:child_of]-d9 
CREATE c5<-[:child_of]-d10, c5<-[:child_of]-d11 
CREATE c6<-[:child_of]-d12, c6<-[:child_of]-d13 
CREATE c7<-[:child_of]-d14, c7<-[:child_of]-d15 
CREATE d7-[:NEXT]->d8-[:NEXT]->d9-[:NEXT]->d10-[:NEXT]->d11-[:NEXT]->d12-[:NEXT]->d13-[:NEXT]->d14-[:NEXT]->d15 
CREATE (a2:a { key:'a2', tempo:'0' }) 
CREATE (a2)<-[:child_of]-(b4:b { key:'b4', tempo:'0' }) 
CREATE (a2)<-[:child_of]-(b5:b { key:'b5', tempo:'1' }) 
CREATE (z1:z { key: 'z1' , tempo:'1' })<-[:child_of]-(a2) 
CREATE y0<-[:child_of]-z1 
CREATE b4<-[:child_of]-(c8:c { key:'c8', tempo:'0' }) 
CREATE b4<-[:child_of]-(c9:c { key:'c9', tempo:'1' }) 
CREATE b5<-[:child_of]-(c10:c { key:'c10', tempo:'0' }) 
CREATE b5<-[:child_of]-(c11:c { key:'c11', tempo:'1' }) 
CREATE (d16:d { key:'d16', tempo:'0', interval:'50' }),(d17:d { key:'d17', tempo:'1', interval:'50' }) 
CREATE (d18:d { key:'d18', tempo:'0', interval:'50' }),(d19:d { key:'d19', tempo:'1', interval:'50' }) 
CREATE (d20:d { key:'d20', tempo:'0', interval:'50' }),(d21:d { key:'d21', tempo:'1', interval:'50' }) 
CREATE (d22:d { key:'d22', tempo:'0', interval:'50' }),(d23:d { key:'d23', tempo:'1', interval:'50' }) 
CREATE c8<-[:child_of]-d16, c8<-[:child_of]-d17 
CREATE c9<-[:child_of]-d18, c9<-[:child_of]-d19 
CREATE c10<-[:child_of]-d20, c10<-[:child_of]-d21 
CREATE c11<-[:child_of]-d22, c11<-[:child_of]-d23 
CREATE d15-[:NEXT]->d16-[:NEXT]->d17-[:NEXT]->d18-[:NEXT]->d19-[:NEXT]->d20-[:NEXT]->d21-[:NEXT]->d22-[:NEXT]->d23 
CREATE (a3:a { key:'a3', tempo:'1' }) 
CREATE (a3)<-[:child_of]-(b6:b { key:'b6', tempo:'0' }) 
CREATE (a3)<-[:child_of]-(b7:b { key:'b7', tempo:'1' }) 
CREATE (z1)<-[:child_of]-(a3) 
CREATE b6<-[:child_of]-(c12:c { key:'c12', tempo:'0' }) 
CREATE b6<-[:child_of]-(c13:c { key:'c13', tempo:'1' }) 
CREATE b7<-[:child_of]-(c14:c { key:'c14', tempo:'0' }) 
CREATE b7<-[:child_of]-(c15:c { key:'c15', tempo:'1' }) 
CREATE (d24:d { key:'d24', tempo:'0', interval:'50' }),(d25:d { key:'d25', tempo:'1', interval:'50' }) 
CREATE (d26:d { key:'d26', tempo:'0', interval:'50' }),(d27:d { key:'d27', tempo:'1', interval:'50' }) 
CREATE (d28:d { key:'d28', tempo:'0', interval:'50' }),(d29:d { key:'d29', tempo:'1', interval:'50' }) 
CREATE (d30:d { key:'d30', tempo:'0', interval:'50' }),(d31:d { key:'d31', tempo:'1', interval:'50' }) 
CREATE c12<-[:child_of]-d24, c12<-[:child_of]-d25 
CREATE c13<-[:child_of]-d26, c13<-[:child_of]-d27 
CREATE c14<-[:child_of]-d28, c14<-[:child_of]-d29 
CREATE c15<-[:child_of]-d30, c15<-[:child_of]-d31 
CREATE d23-[:NEXT]->d24-[:NEXT]->d25-[:NEXT]->d26-[:NEXT]->d27-[:NEXT]->d28-[:NEXT]->d29-[:NEXT]->d30-[:NEXT]->d31 
CREATE (met0:event:met { key:'met0', verb:'meet', past:'has met', present:'meets', future:'will meet' })-[:event]->d0 
CREATE (met1:event:met { key:'met1', verb:'meet', past:'has met', present:'meets', future:'will meet' })-[:event]->d5 
CREATE (met2:event:met { key:'met2', verb:'meet', past:'has met', present:'meets', future:'will meet' })-[:event]->d9 
CREATE (met3:event:met { key:'met3', verb:'meet', past:'has met', present:'meets', future:'will meet' })-[:event]->d14 
CREATE (person:class { key:'person', plural:'People', singular:'Person' }) 
CREATE (sally:person { key:'person0', name:'Sally' })-[:class_of]->person 
CREATE (anne:person { key:'person1', name:'Anne' })-[:class_of]->person 
CREATE (john:person { key:'person2', name:'John' })-[:class_of]->person 
CREATE (pam:person { key: 'person3' , name:'Pam' })-[:class_of]->person 
CREATE (product:class { key:'product', plural:'Products', singular:'Product' }) 
CREATE (shoe:product:shoes { key:'product0', name:'pair of red heels' })-[:class_of]->product 
CREATE (hat:product:hats { key:'product1', name:'sombrero' })-[:class_of]->product
CREATE (headphone:product:headphones { key:'product1', name:'noise cancelling headphones' })-[:class_of]->product
CREATE (coffeemug:product:coffeemugs { key:'product1', name:'i heart neo4j coffee mug' })-[:class_of]->product
CREATE (view0:event:view { key:'view0', verb:'view', past:'has viewed', present:'is viewing', future:'will view' })-[:event]->d16 
CREATE (view1:event:view { key:'view1', verb:'view', past:'has viewed', present:'is viewing', future:'will view' })-[:event]->d17 
CREATE (view2:event:view { key:'view2', verb:'view', past:'has viewed', present:'is viewing', future:'will view' })-[:event]->d18 
CREATE (view3:event:view { key:'view3', verb:'view', past:'has viewed', present:'is viewing', future:'will view' })-[:event]->d21 
CREATE (view4:event:view { key:'view4', verb:'view', past:'has viewed', present:'is viewing', future:'will view' })-[:event]->d22 
CREATE (view5:event:view { key:'view5', verb:'view', past:'has viewed', present:'is viewing', future:'will view' })-[:event]->d23 
CREATE (buy0:event:buy { key:'buy0', verb:'buy', past:'bought', present:'is buying', future:'will buy' })-[:event]->d19 
CREATE (buy1:event:buy { key:'buy1', verb:'buy', past:'bought', present:'is buying', future:'will buy' })-[:event]->d24 
CREATE anne-[:event]->met0-[:event]->pam 
CREATE pam-[:event]->met1-[:event]->sally 
CREATE sally-[:event]->met2-[:event]->anne 
CREATE john-[:event]->met3-[:event]->sally 
CREATE pam-[:event]->view0-[:event]->shoe
CREATE pam-[:event]->view3-[:event]->headphone
CREATE pam-[:event]->view4-[:event]->coffeemug
CREATE pam-[:event]->buy0-[:event]->shoe 
CREATE sally-[:event]->view1-[:event]->shoe 
CREATE sally-[:event]->view2-[:event]->hat 
CREATE sally-[:event]->buy1-[:event]->hat
CREATE sally-[:event]->view5-[:event]->coffeemug
RETURN *
----

=== Get time identity as shortest path ===

[source,cypher]
----
MATCH p=shortestPath((n1:d)-[:child_of*]->(n2:y)) 
WHERE n1.key = 'd10' 
RETURN extract(n IN nodes(p) | n.key) as Path
----

//graph

//table

=== Get time identity as bit string ===

[source,cypher]
----
MATCH p=shortestPath((n1:d)-[:child_of*]->(n2:y)) 
WHERE n1.key = 'd10' 
RETURN DISTINCT reduce(s = '' , n IN nodes(p)| n.tempo + s) AS TimeIdentity 
ORDER BY TimeIdentity
----

//table

=== Get all time identities as bit strings ===

[source,cypher]
----
MATCH p=shortestPath((n1:d)-[:child_of*]->(n2:y)) 
RETURN DISTINCT reduce(s = '' , n IN nodes(p)| n.tempo + s) AS TimeIdentity 
ORDER BY TimeIdentity
----

//table

One of the most powerful use cases for traversals in a graph database is the need to model the recurrence relations of past events as they relate to future events. 


== What is an event graph? ==

An event is any feature or characteristic that describes the state of the world in the past, present, or future.

Furthermore, an event is described by an arbitrary set of features that generalize on the properties contained across all possible events.

This means that an event is only meaningful by connecting it to data that describes it. By attaching a set of features, represented by nodes in the graph, it is possible to attribute meaning to a set of temporal events.

A feature is further described by an arbitrary set of classes that generalize on its combinatorial or shared characteristics. In other words, two or more features can be grouped into a class that generalizes its characteristics at a group level.

The image below represents a time scale connected to a series of events (met). Events, represented as triangular nodes in the image, are also connected to a hierarchy of features (John, Sally, Pam, Anne) which are then further generalized into classes (Person).

image::https://raw.github.com/kbastani/gists/master/meta/TSEMM-Temporal-Binding.png[Time_Scale_Event_Meta_Model]


=== Get time ordered events where people met other people ===

[source,cypher]
----
MATCH p=(p0:person)-[:event]->(ev)-[:event]->(p1:person)
WITH p, ev
MATCH time_identity = (d0:d)<-[:event]-(ev)
WITH d0, p
MATCH p1=(d0)-[:child_of*]->(y0:y)
RETURN extract(x IN nodes(p)| coalesce(x.name, x.future)) AS Interaction, reduce(s = '' , n IN nodes(p1)| n.tempo + s) AS TimeIdentity
ORDER BY TimeIdentity
----

//table

=== Get time ordered events where people interacted with a product ===

[source,cypher]
----
MATCH p=(p0:person)-[:event]->(ev)-[:event]->(p1:product)
WITH p, ev
MATCH time_identity = (d0:d)<-[:event]-(ev)
WITH d0, p
MATCH p1=(d0)-[:child_of*]->(y0:y)
RETURN extract(x IN nodes(p)| coalesce(x.name, x.future)) AS Interaction, reduce(s = '' , n IN nodes(p1)| n.tempo + s) AS TimeIdentity
ORDER BY TimeIdentity
----

//table


Using this model we can determine how to recommend products or services to a user based on similar patterns of behavior happening over time.

== How do I do recommendations? ==

Graphs allow us to connect the dots in order to find recommendations.

image::https://raw.github.com/kbastani/gists/master/meta/TSEMM-Recommendations.png[Recommendations_Graphs]



=== People who viewed a product  ===

[source,cypher]
----
MATCH p=(p0:person)-[:event]->(ev:view)-[:event]->(p1:product)
WITH p, ev
MATCH time_identity = (d0:d)<-[:event]-(ev)
WITH d0, p
MATCH p1=(d0)-[:child_of*]->(y0:y)
RETURN extract(x IN nodes(p)| coalesce(x.name, x.past)) AS Interaction, reduce(s = '' , n IN nodes(p1)| n.tempo + s) AS TimeIdentity
ORDER BY TimeIdentity
----

//table

=== People who viewed X also viewed Y ===

Let's find products that other people viewed who also viewed the product named 'pair of red heels'.

[source,cypher]
----
MATCH p=(p0:person)-[:event]->(ev:view)-[:event]->(p1:product) 
WITH p0, p1 
WHERE p1.name = 'pair of red heels' 
WITH p0 
MATCH p0-[:event]->(ev:view)-[:event]->(p2:product) 
WHERE p2.name <> 'pair of red heels' 
RETURN p2.name as Product, count(p0) as Views
----

//table

=== Recommendation GraphGists ===

It's your turn! Fork this GraphGist on GitHub and modify the code to create your own recommendation GraphGists.

Also, follow me on Twitter for more Neo4j GraphGists -> http://www.twitter.com/kennybastani[@kennybastani]

