Class: Vptree::VPTree

Inherits:
Object
  • Object
show all
Includes:
CalcDistance
Defined in:
lib/vptree.rb

Overview

Implementation of VP-tree

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from CalcDistance

#calc_dist

Constructor Details

#initialize(data, options = {}, &block) ⇒ VPTree

Returns a new instance of VPTree.



101
102
103
104
105
106
 
# File 'lib/vptree.rb', line 101

def initialize(data, options = {}, &block)
  @data = data
  @is_block = block_given?
  @distance_measure = block || options[:distance_measure] || :euclidean_distance
  @root = VPNode.new(data, options, &block)
end

Instance Attribute Details

#root ⇒ Object

Returns the value of attribute root.



99
100
101
 
# File 'lib/vptree.rb', line 99

def root
  @root
end

Instance Method Details

#build_tree ⇒ Object 



110
111
112
 
# File 'lib/vptree.rb', line 110

def build_tree
  @root.separate
end

#find_k_nearest(obj, k) ⇒ Object 



114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
 
# File 'lib/vptree.rb', line 114

def find_k_nearest(obj, k)
  tau = Float::INFINITY
  nodes_to_visit = Containers::Queue.new
  nodes_to_visit.push(@root)

  # fixed size array for nearest neightbors
  # sorted from closest to farthest neighbor
  neighbors = FixedLengthQueue.new(k)

  while nodes_to_visit.size > 0
    node = nodes_to_visit.pop
    d = calc_dist(obj, node.vp_point)
    if d < tau
      # store node.vp_point as a neighbor if it's closer than any other point
      # seen so far
      neighbors.push([d, node.vp_point], d)
      # shrink tau
      tau = neighbors.max_priority
    end
    # check for intersection between q-tau and vp-mu regions
    # and see which branches we absolutely must search

    if d < node.mu
      # the object is in mu range of Vintage Point
      nodes_to_visit.push(node.right_node) if node.right_node # d < node.mu + tau # permanent true
      nodes_to_visit.push(node.left_node) if node.left_node && d >= node.mu - tau # partial overlap
    else
      nodes_to_visit.push(node.left_node) if node.left_node # d >= node.mu - tau
      nodes_to_visit.push(node.right_node) if node.right_node && d < node.mu + tau # partial overlap
    end
  end

  return neighbors.dump.reverse
end