comparison multiprobe.h @ 518:ca1ee92c359c multiprobeLSH

Completed initial implementation of LSH MultiProbe class. Now needs to be joined to lshlib.cpp retrieve() method to perform multi-probe queries.

 /*
  * MultiProbe C++ class
  *
- * Given a LSH structure, perform lookup by probing nearby hash-function locations
+ * Given a vector of LSH boundary distances for a query, 
+ * perform lookup by probing nearby hash-function locations
  *
  * Implementation using C++ STL
  *
  * Reference:
  * Qin Lv, William Josephson, Zhe Wang, Moses Charikar and Kai Li,

  * Copyright (C) 2009 Michael Casey, Dartmouth College, All Rights Reserved
  * License: GNU Public License 2.0
  *
  */
 
+#ifndef __LSH_MULTIPROBE_
+#define __LSH_MULTIPROBE_
+
 #include <functional>
 #include <queue>
 #include <vector>
 #include <set>
 #include <algorithm>
 #include <iostream>
 
-using namespace std ;
+using namespace std;
 
 typedef set<int > perturbation_set ;
-typedef vector<perturbation_set > vector_of_perturbation_set ;
-typedef pair<perturbation_set, float > min_heap_element ;
-typedef vector<min_heap_element > vector_of_min_heap_element ;
-typedef priority_queue<
-  min_heap_element, 
-  vector_of_min_heap_element, 
-  greater<min_heap_element> 
-  > min_heap_of_perturbation_set ;
+
+typedef class MinHeapElement{
+public:
+  perturbation_set perturbs;
+  double score;
+  MinHeapElement(perturbation_set a, double s);
+  virtual ~MinHeapElement();
+} min_heap_element;
+
+typedef priority_queue<min_heap_element, 
+		       vector<min_heap_element>, 
+		       greater<min_heap_element> 
+		       > min_heap_of_perturbation_set ;
+
 typedef pair<double, pair<int, int> > sorted_distance_functions ;
-typedef vector<sorted_distance_functions> vector_of_sorted_distance_functions;
 
-bool operator>(const min_heap_element& a, const min_heap_element& b){
-  return a.second > b.second;
+bool operator> (const min_heap_element& a, const min_heap_element& b){
+  return a.score > b.score;
 }
 
-bool operator<(const min_heap_element& a, const min_heap_element& b){
-  return a.second < b.second;
+bool operator< (const min_heap_element& a, const min_heap_element& b){
+  return a.score < b.score;
 }
 
 bool operator>(const sorted_distance_functions& a, const sorted_distance_functions& b){
   return a.first > b.first;
 }

 }
 
 class MultiProbe{
 protected:
   min_heap_of_perturbation_set* minHeap;
-  vector_of_perturbation_set* outSets;
-  vector_of_sorted_distance_functions* distFuns;
+  min_heap_of_perturbation_set* outSets;
+  vector<sorted_distance_functions>* distFuns;
   unsigned numHashBoundaries;
-public: 
-  MultiProbe();
-  ~MultiProbe();
 
+  // data structure initialization and cleanup
+  void initialize();
+  void cleanup();
+  
   // perturbation set operations
   perturbation_set& shift(perturbation_set&);
   perturbation_set& expand(perturbation_set&);
   double score(perturbation_set&);
   bool valid(perturbation_set&);
+  void makeSortedDistFuns(vector<double> &);
+
+public: 
+  MultiProbe();
+  ~MultiProbe();
 
   // generation of perturbation sets
-  void generatePerturbationSets(int, vector<double>&);
-  void makeSortedDistFuns(vector<double> &);
-  void dump(perturbation_set& );
+  void generatePerturbationSets(vector<double>& vectorOfBounaryDistances, int numSetsToGenerate);  
+  perturbation_set getNextPerturbationSet();
+  void dump(perturbation_set);
+  size_t size(); // Number of perturbation sets are in the output queue
+  bool empty(); // predicate for empty MultiProbe set
 };
+
 
 /* NOTES:
 
 Reference:
 Qin Lv, William Josephson, Zhe Wang, Moses Charikar and Kai Li,

      until valid(Ai)
      output Ai
   end for
 
  */
+
+#endif // __LSH_MULTIPROBE_