Ruby
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
lib
test
.gitignore
LICENSE-2.0.txt
README
Rakefile
TODO
init.rb
install.rb
uninstall.rb

README

Grapher
=======

This plugin lets you store a graph representation of your data in
Redis. ("Graph" as in "Graph Theory", this is NOT charting sofrtware.)

A graph representation of your objects is a very powerful analytical
tool for discovering inter-object relationships that cannot be
discovered easily or nearly as efficiently using a relational
database.

For more info on Redis see http://redis.io/

Introduction
============

Imagine the following model:

User
  has_many :orders

Order
  belongs_to :user
  has_many :items, :through => order_items

OrderItem
  belongs_to :order
  belongs_to :item, :polymorphic => true
  has_one :user, :through => :order

Imagine that you would like to keep track of a user buying an
item. You can get a user's orders via user.orders, then for each of
those collect the items. So it's possible, but not in one step.

Imagine that you wanted to compare what a user has purchased with what
other users have purchased, so that you could make a recommendation
such as "users who purchased X also purchased Y". Given the above
database structure it would be a fairly complicated operation
requiring numerous SQL calls.

(Bear with us, we're getting to the point.)

Now imagine that you stored a user's purchases in a graph, like this
(numbers are users, letters are items):

+---> D <---+
|           |
1 --> A <-- 2 --> B
      ^
      |
      3 --> C <-- 4

In the above graph:

user 1 purchased [A, D]
user 2 purchased [A, B, D]
user 3 purchased [A, C]
user 4 purchased [C]

You can see that users 1 and 2 both purchased items A and D. Based on
this you could say that users 1 and 2 have a similar purchasing
pattern, and that item B may be of interest to user 1. You could also
say that items A and D may be related because more than one user
purchased them together.

You may have noticed that users 1 and 2 are two graph edges away from
each other. Also that there are multiple paths connecting users 1 and
2 (via A and via D).

This means that to find users with a similar purchasing pattern, all
we need to do is to enumerate all users exactly two "hops" away. And
if we were to count the number of time we come across the same user,
this count would become a rank of similarity - the higher the rank,
the more similar these users are.

Same principle applies to items. Items two edges apart can be deemed
similar, and the more common paths, the higher the degree of
similarity.

If we were to store the above graph as a two hashes of sets (one for
forward links from user to item, the second for reverse from item to
user), such as (in pseudo-ruby code):

forward = { 1 => {A, D},
            2 => {A, B, D},
            3 => {A, C},
            4 => {C} }

reverse = { A => {1, 2, 3},
            B => {2},
            C => {3, 4},
            D => {1, 2} }

we could quite easily accomplish the above operation. For example, all
users similar to 1 are:

forward[1].each { |item| reverse[item] }

Similarly items similar to A would be:

reverse[A].each { |user| forward[user] }

There is only one remaining problem - if your database is any decent
size by today's standards, building these hashes may take enough
CPU/memory to make it impractical. 

This is where Redis comes in. We can build this structure once and
maintain it with proper callbacks, having it stored in Redis. Redis
provides all the basic operations for the above calculations and is
fast enough for these calculations to be performed real-time.

Example
=======

class OrderItem < ActiveRecord::Base
  belongs_to :order
  belongs_to :item, :polymorphic => true
  has_one :user, :through => :order
  graph_edge_from :user, :to => :item, :on => :create, :verb => 'Purchased'
  ...

class User < ActiveRecord::Base
  has_many :orders
  graph_node :verbs => '>Purchased'

>> u = User.find(:first)
>> u.graph_neighbors
=> #<Set: {"Item:234", "Item:345", "Item:456"}>
>> u.graph_neighbors(:distance => 2)
=> #<Set: {"User:12", "User:23", "User:2345"}>
>> u.graph_neighbors_ranked(:distance => 2)
=> [[9, "User:23"], [5, "User:23"], [1, "User:2345"]]


Copyright (c) 2011 Tournesol Ventures, LLC

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.