Class: Likes::Engines::FastJaccardSimilarity

Inherits:
Object
  • Object
show all
Defined in:
lib/likes/engines/fast_jaccard_similarity.rb

Overview

Job: Understands which items could be recommended

Calculates Minhash Signatures and uses them to give approximate relative intersection size. Returns recommendations from best approximate relative intersection sizes

Relative intersection size = intersection size / union size

Worst approximation of execution time:

Given P = how much distinct items we have

Given N = how much distinct people we have

Given D = depth of this implementation - maximum count of hash functions (~100)

Complexity: O(ND + PD) * O(hash operations ~ log N + log P) ~ O(N * log N)

Constant Summary collapse

MAX_HASH_FUNCTIONS_COUNT = 
200
ALLOW_FLUCTUATION = 
1.075
INFINITY = 
1.0 / 0

Instance Method Summary collapse

Constructor Details

#initialize(person, likes_of, liked) ⇒ FastJaccardSimilarity

Creates new instance of FastJaccardSimilarity engine

Parameters:

  • person (Person#==) —

    The person to provide recommendations for

  • likes_of (Hash<Person, Array<Item>>) —

    Input data in form of map person => [item]

  • liked (Hash<Item, Array<Person>>) —

    Input data in form of map item => [person]



35
36
37
38
39
40
41
 
# File 'lib/likes/engines/fast_jaccard_similarity.rb', line 35

def initialize(person, likes_of, liked)
  @person = person
  @likes_of = likes_of
  @liked = liked
  @items = liked.keys
  @people = likes_of.keys
end

Instance Method Details

#solve ⇒ Array<Item>

Solves the problem and returns recommendation list

Returns:

  • (Array<Item>) —

    Returns list of recommended items



46
47
48
49
50
51
 
# File 'lib/likes/engines/fast_jaccard_similarity.rb', line 46

def solve
  init_signature
  compute_hashes
  compute_signature
  recommendations
end