comparison lshlib.cpp @ 293:9fd5340faffd

Refactored LSH interface to separate hashfunctions and parameters from insertion/retrieval/serialization

     perror(sysFunc);
   }
   exit(1);
 }
 
-H::H(Uns32T kk, Uns32T mm, Uns32T dd, Uns32T NN, Uns32T CC):
+H::H(){
+  // Delay initialization of lsh functions until we know the parameters
+}
+
+H::H(Uns32T kk, Uns32T mm, Uns32T dd, Uns32T NN, Uns32T CC, float ww, float rr):
 #ifdef USE_U_FUNCTIONS
   use_u_functions(true),
 #else
   use_u_functions(false),
 #endif
+  maxp(0),
   bucketCount(0),
   pointCount(0),
   N(NN),
   C(CC),
   k(kk),
   m(mm),
-  L(mm*(mm-1)/2),
-  d(dd)
+  L((mm*(mm-1))/2),
+  d(dd),
+  w(ww),
+  radius(rr)
 {
-  Uns32T j;
+
+  if(m<2){
+    m=2;
+    L=1; // check value of L
+    cout << "warning: setting m=2, L=1" << endl;
+  }
+  if(use_u_functions && k%2){
+    k++; // make sure k is even
+    cout << "warning: setting k even" << endl;
+  }
+
   cout << "file size: ~" << (((unsigned long long)L*N*C*sizeof(SerialElementT))/1000000UL) << "MB" << endl;
   if(((unsigned long long)L*N*C*sizeof(SerialElementT))>4000000000UL)
     error("Maximum size of LSH file exceded: 12*L*N*C > 4000MB");
   else if(((unsigned long long)N*C*sizeof(SerialElementT))>1000000000UL)
     cout << "warning: hash tables exceed 1000MB." << endl;
-
-  if(m<2){
-    m=2;
-    L=1; // check value of L
-    cout << "warning: setting m=2, L=1" << endl;
-  }
-  if(use_u_functions && k%2){
-    k++; // make sure k is even
-    cout << "warning: setting k even" << endl;
-  }
-  __initialize_data_structures();
-  for(j=0; j<L; j++)
-    for(kk=0; kk<k; kk++) {
-      r1[j][kk]=__randr(); // random 1..2^29
-      r2[j][kk]=__randr(); // random 1..2^29
-    }
-}
-
-// Post constructor initialization
-void H::__initialize_data_structures(){  
+  
+  // We have the necessary parameters, so construct hashfunction datastructures
+  initialize_lsh_functions();
+}
+
+void H::initialize_lsh_functions(){
   H::P = UH_PRIME_DEFAULT;
   
   /* FIXME: don't use time(); instead use /dev/random or similar */
   /* FIXME: write out the seed somewhere, so that we can get
      repeatability */
 #ifdef MT19937
   init_genrand(time(NULL));
 #else
   srand(time(NULL)); // seed random number generator
 #endif
-  Uns32T i,j;
+  Uns32T i,j, kk;
+#ifdef USE_U_FUNCTIONS
+  H::A = new float**[ H::m ]; // m x k x d random projectors
+  H::b = new float*[ H::m ];  // m x k random biases
+#else
+  H::A = new float**[ H::L ]; // m x k x d random projectors
+  H::b = new float*[ H::L ];  // m x k random biases
+#endif
+  H::g = new Uns32T*[ H::L ];   //  L x k random projections 
+  assert( H::g && H::A && H::b ); // failure
+#ifdef USE_U_FUNCTIONS
+  // Use m \times u_i functions \in R^{(k/2) \times (d)}
+  // Combine to make L=m(m-1)/2 hash functions \in R^{k \times d}
+  for( j = 0; j < H::m ; j++ ){ // m functions u_i(v)
+    H::A[j] = new float*[ H::k/2 ];  // k/2 x d  2-stable distribution coefficients     
+    H::b[j] = new float[ H::k/2 ];   // bias
+    assert( H::A[j] && H::b[j] ); // failure
+    for( kk = 0; kk < H::k/2 ; kk++ ){
+      H::A[j][kk] = new float[ H::d ];
+      assert( H::A[j][kk] ); // failure
+      for(Uns32T i = 0 ; i < H::d ; i++ )
+	H::A[j][kk][i] = H::randn(); // Normal
+      H::b[j][kk] = H::ranf()*H::w;        // Uniform
+    }
+  }
+#else
+  // Use m \times u_i functions \in R^{k \times (d)}
+  // Combine to make L=m(m-1)/2 hash functions \in R^{k \times d}
+  for( j = 0; j < H::L ; j++ ){ // m functions u_i(v)
+    H::A[j] = new float*[ H::k ];  // k x d  2-stable distribution coefficients     
+    H::b[j] = new float[ H::k ];   // bias
+    assert( H::A[j] && H::b[j] ); // failure
+    for( kk = 0; kk < H::k ; kk++ ){
+      H::A[j][kk] = new float[ H::d ];
+      assert( H::A[j][kk] ); // failure
+      for(Uns32T i = 0 ; i < H::d ; i++ )
+	H::A[j][kk][i] = H::randn(); // Normal
+      H::b[j][kk] = H::ranf()*H::w;        // Uniform
+    }
+  }
+#endif
+
+  // Storage for LSH hash function output (Uns32T)
+  for( j = 0 ; j < H::L ; j++ ){    // L functions g_j(u_a, u_b) a,b \in nchoosek(m,2)
+    H::g[j] = new Uns32T[ H::k ];   // k x 32-bit hash values, gj(v)=[x0 x1 ... xk-1] xk \in Z
+    assert( H::g[j] );
+  }
+
+  // LSH Hash tables
   H::h = new bucket**[ H::L ];  
-  H::r1 = new Uns32T*[ H::L ];
-  H::r2 = new Uns32T*[ H::L ];
-  assert( H::h && H::r1 && H::r2 ); // failure
-  for( j = 0 ; j < H::L ; j++ ){
-    H::r1[ j ] = new Uns32T[ H::k ];
-    H::r2[ j ] = new Uns32T[ H::k ];
-    assert( H::r1[j] && H::r2[j] ); // failure
-  }
-
+  assert( H::h );
   for( j = 0 ; j < H::L ; j++ ){
     H::h[j] = new bucket*[ H::N ];
     assert( H::h[j] );
     for( i = 0 ; i < H::N ; i++)
       H::h[j][i] = 0;
   }
-}
-
-// Destruct hash tables
-H::~H(){
-  Uns32T i,j;
-  for( j=0 ; j < H::L ; j++ ){
-      delete[] H::r1[ j ];
-      delete[] H::r2[ j ];
-      for(i = 0; i< H::N ; i++)
-	delete H::h[ j ][ i ];
-      delete[] H::h[ j ];
-  }
-  delete[] H::r1;
-  delete[] H::r2;
-  delete[] H::h;
-}
-
-
-// make hash value \in Z
-void H::__generate_hash_keys(Uns32T*g,Uns32T* r1, Uns32T* r2){
-  H::t1 = __computeProductModDefaultPrime( g, r1, H::k ) % H::N;
-  H::t2 = __computeProductModDefaultPrime( g, r2, H::k );
-
-}
-
-#define CR_ASSERT(b){if(!(b)){fprintf(stderr, "ASSERT failed on line %d, file %s.\n", __LINE__, __FILE__); exit(1);}}
-
-// Computes (a.b) mod UH_PRIME_DEFAULT
-inline Uns32T H::__computeProductModDefaultPrime(Uns32T *a, Uns32T *b, IntT size){
-  LongUns64T h = 0;
-
-  for(IntT i = 0; i < size; i++){
-    h = h + (LongUns64T)a[i] * (LongUns64T)b[i];
-    h = (h & TWO_TO_32_MINUS_1) + 5 * (h >> 32);
-    if (h >= UH_PRIME_DEFAULT) {
-      h = h - UH_PRIME_DEFAULT;
-    }
-    CR_ASSERT(h < UH_PRIME_DEFAULT);
-  }
-  return h;
-}
-
-Uns32T H::bucket_insert_point(bucket **pp){
-  Uns32T collisionCount = 0;
-  if(!*pp){
-    *pp = new bucket();
-#ifdef LSH_BLOCK_FULL_ROWS
-    (*pp)->t2 = 0; // Use t2 as a collision counter for the row
-    (*pp)->next = new bucket();
-#endif
-  }
-#ifdef LSH_BLOCK_FULL_ROWS
-  collisionCount = (*pp)->t2;
-  if(collisionCount < H::C){ // Block if row is full
-    (*pp)->t2++; // Increment collision counter
-    pointCount++;
-    collisionCount++;
-    __bucket_insert_point((*pp)->next); // First bucket holds collision count
-  }
-#else
-    pointCount++;
-    __bucket_insert_point(*pp); // No collision count storage
-#endif
-  return collisionCount;
-}
-
-void H::__bucket_insert_point(bucket* p){
-  if(p->t2 == IFLAG){ // initialization flag, is it in the domain of t2?
-    p->t2 = H::t2;
-    bucketCount++; // Record start of new point-locale collision chain
-    p->snext = new sbucket();
-    __sbucket_insert_point(p->snext);
-    return;
-  }
-
-  if(p->t2 == H::t2){
-    __sbucket_insert_point(p->snext);
-    return;
-  }
-
-  if(p->next){
-    __bucket_insert_point(p->next);
-  }
-
-  else{
-    p->next = new bucket();
-    __bucket_insert_point(p->next);
-  }
-
-}
-
-void H::__sbucket_insert_point(sbucket* p){
-  if(p->pointID==IFLAG){
-    p->pointID = H::p;
-    return;
-  }
-
-  // Search for pointID
-  if(p->snext){
-    __sbucket_insert_point(p->snext);
-  }
-  else{
-  // Make new point collision bucket at end of list
-  p->snext = new sbucket();
-  __sbucket_insert_point(p->snext);
-  }
-}
-
-inline bucket** H::__get_bucket(int j){
-  return  *(h+j);
-}
-
-// hash functions G
-G::G(float ww, Uns32T kk,Uns32T mm, Uns32T dd, Uns32T NN, Uns32T CC, float r):
-  H(kk,mm,dd,NN,CC),
-  w(ww),
-  radius(r),
-  maxp(0),
-  calling_instance(0),
-  add_point_callback(0),
-  lshHeader(0)
-{
-  Uns32T j;
+
+  // Standard hash functions
+  H::r1 = new Uns32T*[ H::L ];
+  H::r2 = new Uns32T*[ H::L ];
+  assert( H::r1 && H::r2 ); // failure
+  for( j = 0 ; j < H::L ; j++ ){
+    H::r1[ j ] = new Uns32T[ H::k ];
+    H::r2[ j ] = new Uns32T[ H::k ];
+    assert( H::r1[j] && H::r2[j] ); // failure
+    for( i = 0; i<H::k; i++){
+      H::r1[j][i] = randr();
+      H::r2[j][i] = randr();
+    }
+  }
+
+  // Storage for whole or partial function evaluation depdenting on USE_U_FUNCTIONS
+  H::initialize_partial_functions();
+}
+
+void H::initialize_partial_functions(){
+
 #ifdef USE_U_FUNCTIONS
-  G::A = new float**[ H::m ]; // m x k x d random projectors
-  G::b = new float*[ H::m ];  // m x k random biases
-#else
-  G::A = new float**[ H::L ]; // m x k x d random projectors
-  G::b = new float*[ H::L ];  // m x k random biases
-#endif
-  G::g = new Uns32T*[ H::L ];   //  L x k random projections 
-  assert( G::g && G::A && G::b ); // failure
-#ifdef USE_U_FUNCTIONS
-  // Use m \times u_i functions \in R^{(k/2) \times (d)}
-  // Combine to make L=m(m-1)/2 hash functions \in R^{k \times d}
-  for( j = 0; j < H::m ; j++ ){ // m functions u_i(v)
-    G::A[j] = new float*[ H::k/2 ];  // k/2 x d  2-stable distribution coefficients     
-    G::b[j] = new float[ H::k/2 ];   // bias
-    assert( G::A[j] && G::b[j] ); // failure
-    for( kk = 0; kk < H::k/2 ; kk++ ){
-      G::A[j][kk] = new float[ H::d ];
-      assert( G::A[j][kk] ); // failure
-      for(Uns32T i = 0 ; i < H::d ; i++ )
-	G::A[j][kk][i] = randn(); // Normal
-      G::b[j][kk] = ranf()*G::w;        // Uniform
-    }
-  }
-#else
-  // Use m \times u_i functions \in R^{k \times (d)}
-  // Combine to make L=m(m-1)/2 hash functions \in R^{k \times d}
-  for( j = 0; j < H::L ; j++ ){ // m functions u_i(v)
-    G::A[j] = new float*[ H::k ];  // k x d  2-stable distribution coefficients     
-    G::b[j] = new float[ H::k ];   // bias
-    assert( G::A[j] && G::b[j] ); // failure
-    for( kk = 0; kk < H::k ; kk++ ){
-      G::A[j][kk] = new float[ H::d ];
-      assert( G::A[j][kk] ); // failure
-      for(Uns32T i = 0 ; i < H::d ; i++ )
-	G::A[j][kk][i] = randn(); // Normal
-      G::b[j][kk] = ranf()*G::w;        // Uniform
-    }
-  }
-#endif
-  
-  for( j = 0 ; j < H::L ; j++ ){ // L functions g_j(u_a, u_b) a,b \in nchoosek(m,2)
-    G::g[j] = new Uns32T[ H::k ];   // k x 32-bit hash values, gj(v)=[x0 x1 ... xk-1] xk \in Z
-    assert( G::g[j] );
-  }
-  
-  initialize_partial_functions(); // m partially evaluated hash functions
-}
-
-// Serialize from file LSH constructor
-// Read parameters from database file
-// Load the hash functions, close the database
-// Optionally load the LSH tables into head-allocated lists in core 
-G::G(char* filename, bool lshInCoreFlag):
-  calling_instance(0),
-  add_point_callback(0)
-{
-  int dbfid = unserialize_lsh_header(filename);
-  unserialize_lsh_functions(dbfid);
-  initialize_partial_functions();
-
-  // Format1 only needs unserializing if specifically requested
-  if(!(lshHeader->flags&O2_SERIAL_FILEFORMAT2) && lshInCoreFlag){
-    unserialize_lsh_hashtables_format1(dbfid);
-  }
-
-  // Format2 always needs unserializing
-  if(lshHeader->flags&O2_SERIAL_FILEFORMAT2 && lshInCoreFlag){
-    unserialize_lsh_hashtables_format2(dbfid);
-  }
-
-  close(dbfid);
-}
-
-void G::initialize_partial_functions(){
-
-#ifdef USE_U_FUNCTIONS
-  uu = vector<vector<Uns32T> >(H::m);
+  H::uu = vector<vector<Uns32T> >(H::m);
   for( Uns32T aa=0 ; aa < H::m ; aa++ )
-    uu[aa] = vector<Uns32T>( H::k/2 );
-#else
-  uu = vector<vector<Uns32T> >(H::L);
+    H::uu[aa] = vector<Uns32T>( H::k/2 );
+#else
+  H::uu = vector<vector<Uns32T> >(H::L);
   for( Uns32T aa=0 ; aa < H::L ; aa++ )
-    uu[aa] = vector<Uns32T>( H::k );
+    H::uu[aa] = vector<Uns32T>( H::k );
 #endif
 }
 
 
 // Generate z ~ N(0,1)
-float G::randn(){
+float H::randn(){
 // Box-Muller
   float x1, x2;
   do{
     x1 = ranf();
   } while (x1 == 0); // cannot take log of 0

   float z;
   z = sqrtf(-2.0 * logf(x1)) * cosf(2.0 * M_PI * x2);
   return z;
 }
 
-float G::ranf(){
+float H::ranf(){
 #ifdef MT19937
   return (float) genrand_real2();
 #else
   return (float)( (double)rand() / ((double)(RAND_MAX)+(double)(1)) );
 #endif
 }
 
 // range is 1..2^29
 /* FIXME: that looks like an ... odd range.  Still. */
-Uns32T H::__randr(){
+Uns32T H::randr(){
 #ifdef MT19937
   return (Uns32T)((genrand_int32() >> 3) + 1);
 #else
   return (Uns32T) ((rand() >> 2) + 1); 
 #endif
 }
 
-G::~G(){
-  Uns32T j,kk;
+// Destruct hash tables
+H::~H(){
+  Uns32T i,j,kk;
 #ifdef USE_U_FUNCTIONS
   for( j = 0 ; j < H::m ; j++ ){
     for( kk = 0 ; kk < H::k/2 ; kk++ )
       delete[] A[j][kk];
     delete[] A[j];

 #endif
 
   for( j = 0 ; j < H::L ; j++ )
     delete[] g[j];
   delete[] g;
-  delete lshHeader;
-}
+  for( j=0 ; j < H::L ; j++ ){
+      delete[] H::r1[ j ];
+      delete[] H::r2[ j ];
+      for(i = 0; i< H::N ; i++)
+	delete H::h[ j ][ i ];
+      delete[] H::h[ j ];
+  }
+  delete[] H::r1;
+  delete[] H::r2;
+  delete[] H::h;
+}
+
 
 // Compute all hash functions for vector v
 // #ifdef USE_U_FUNCTIONS use Combination of m \times h_i \in R^{(k/2) \times d}
 // to make L \times g_j functions \in Z^k
-void G::compute_hash_functions(vector<float>& v){ // v \in R^d
-  float iw = 1. / G::w; // hash bucket width
+void H::compute_hash_functions(vector<float>& v){ // v \in R^d
+  float iw = 1. / H::w; // hash bucket width
   Uns32T aa, kk;
   if( v.size() != H::d ) 
     error("v.size != H::d","","compute_hash_functions"); // check input vector dimensionality
   double tmp = 0;
   float *pA, *pb;

 
 #ifdef USE_U_FUNCTIONS
   Uns32T bb;
   // Store m dot products to expand
   for( aa=0; aa < H::m ; aa++ ){
-    ui = uu[aa].begin();
+    ui = H::uu[aa].begin();
     for( kk = 0 ; kk < H::k/2 ; kk++ ){
-      pb = *( G::b + aa ) + kk;
-      pA = * ( * ( G::A + aa ) + kk );
+      pb = *( H::b + aa ) + kk;
+      pA = * ( * ( H::A + aa ) + kk );
       dd = H::d;
       tmp = 0.;
       vi = v.begin();
       while( dd-- )
 	tmp += *pA++ * *vi++;  // project

   }
   // Binomial combinations of functions u_{a,b} \in Z^{(k/2) \times d}
   Uns32T j;
   for( aa=0, j=0 ; aa < H::m-1 ; aa++ )
     for( bb = aa + 1 ; bb < H::m ; bb++, j++ ){
-      pg= *( G::g + j ); // L \times functions g_j(v) \in Z^k      
+      pg= *( H::g + j ); // L \times functions g_j(v) \in Z^k      
       // u_1 \in Z^{(k/2) \times d}
-      ui = uu[aa].begin();
+      ui = H::uu[aa].begin();
       kk=H::k/2;
       while( kk-- )
 	*pg++ = *ui++;      // hash function g_j(v)=[x1 x2 ... x(k/2)]; xk \in Z
       // u_2 \in Z^{(k/2) \times d}
-      ui = uu[bb].begin();
+      ui = H::uu[bb].begin();
       kk=H::k/2;
       while( kk--)
 	*pg++ = *ui++;      // hash function g_j(v)=[x(k/2+1) x(k/2+2) ... xk]; xk \in Z
     }
 #else
   for( aa=0; aa < H::L ; aa++ ){
-    ui = uu[aa].begin();
+    ui = H::uu[aa].begin();
     for( kk = 0 ; kk < H::k ; kk++ ){
-      pb = *( G::b + aa ) + kk;
-      pA = * ( * ( G::A + aa ) + kk );
+      pb = *( H::b + aa ) + kk;
+      pA = * ( * ( H::A + aa ) + kk );
       dd = H::d;
       tmp = 0.;
       vi = v.begin();
       while( dd-- )
 	tmp += *pA++ * *vi++;  // project

       *ui++ = (Uns32T) (floor(tmp));   // floor
     }
   }
   // Compute hash functions
   for( aa=0 ; aa < H::L ; aa++ ){
-    pg= *( G::g + aa ); // L \times functions g_j(v) \in Z^k      
+    pg= *( H::g + aa ); // L \times functions g_j(v) \in Z^k      
     // u_1 \in Z^{k \times d}
-    ui = uu[aa].begin();
+    ui = H::uu[aa].begin();
     kk=H::k;    
     while( kk-- )
       *pg++ = *ui++;      // hash function g_j(v)=[x1 x2 ... xk]; xk \in Z
   }
 #endif
-
-}
-
+}
+
+// make hash value \in Z
+void H::generate_hash_keys(Uns32T*g, Uns32T* r1, Uns32T* r2){
+  H::t1 = computeProductModDefaultPrime( g, r1, H::k ) % H::N;
+  H::t2 = computeProductModDefaultPrime( g, r2, H::k );
+}
+
+#define CR_ASSERT(b){if(!(b)){fprintf(stderr, "ASSERT failed on line %d, file %s.\n", __LINE__, __FILE__); exit(1);}}
+
+// Computes (a.b) mod UH_PRIME_DEFAULT
+inline Uns32T H::computeProductModDefaultPrime(Uns32T *a, Uns32T *b, IntT size){
+  LongUns64T h = 0;
+
+  for(IntT i = 0; i < size; i++){
+    h = h + (LongUns64T)a[i] * (LongUns64T)b[i];
+    h = (h & TWO_TO_32_MINUS_1) + 5 * (h >> 32);
+    if (h >= UH_PRIME_DEFAULT) {
+      h = h - UH_PRIME_DEFAULT;
+    }
+    CR_ASSERT(h < UH_PRIME_DEFAULT);
+  }
+  return h;
+}
+
+Uns32T H::bucket_insert_point(bucket **pp){
+  Uns32T collisionCount = 0;
+  if(!*pp){
+    *pp = new bucket();
+#ifdef LSH_BLOCK_FULL_ROWS
+    (*pp)->t2 = 0; // Use t2 as a collision counter for the row
+    (*pp)->next = new bucket();
+#endif
+  }
+#ifdef LSH_BLOCK_FULL_ROWS
+  collisionCount = (*pp)->t2;
+  if(collisionCount < H::C){ // Block if row is full
+    (*pp)->t2++; // Increment collision counter
+    pointCount++;
+    collisionCount++;
+    __bucket_insert_point((*pp)->next); // First bucket holds collision count
+  }
+#else
+    pointCount++;
+    __bucket_insert_point(*pp); // No collision count storage
+#endif
+  return collisionCount;
+}
+
+void H::__bucket_insert_point(bucket* p){
+  if(p->t2 == IFLAG){ // initialization flag, is it in the domain of t2?
+    p->t2 = H::t2;
+    bucketCount++; // Record start of new point-locale collision chain
+    p->snext = new sbucket();
+    __sbucket_insert_point(p->snext);
+    return;
+  }
+
+  if(p->t2 == H::t2){
+    __sbucket_insert_point(p->snext);
+    return;
+  }
+
+  if(p->next){
+    __bucket_insert_point(p->next);
+  }
+
+  else{
+    p->next = new bucket();
+    __bucket_insert_point(p->next);
+  }
+
+}
+
+void H::__sbucket_insert_point(sbucket* p){
+  if(p->pointID==IFLAG){
+    p->pointID = H::p;
+    return;
+  }
+
+  // Search for pointID
+  if(p->snext){
+    __sbucket_insert_point(p->snext);
+  }
+  else{
+  // Make new point collision bucket at end of list
+  p->snext = new sbucket();
+  __sbucket_insert_point(p->snext);
+  }
+}
+
+inline bucket** H::get_bucket(int j){
+  return  *(h+j);
+}
+
+// Interface to Locality Sensitive Hashing G
+G::G(float ww, Uns32T kk,Uns32T mm, Uns32T dd, Uns32T NN, Uns32T CC, float rr):
+  H(kk,mm,dd,NN,CC,ww,rr), // constructor to initialize data structures
+  lshHeader(0),
+  calling_instance(0),
+  add_point_callback(0)
+{
+
+}
+
+// Serialize from file LSH constructor
+// Read parameters from database file
+// Load the hash functions, close the database
+// Optionally load the LSH tables into head-allocated lists in core 
+G::G(char* filename, bool lshInCoreFlag):
+  H(), // default base-class constructor call delays data-structure initialization 
+  lshHeader(0),
+  calling_instance(0),
+  add_point_callback(0)
+{
+  int dbfid = unserialize_lsh_header(filename);
+
+  H::initialize_lsh_functions(); // Base-class data-structure initialization
+  unserialize_lsh_functions(dbfid); // populate with on-disk hashfunction values
+
+  // Format1 only needs unserializing if specifically requested
+  if(!(lshHeader->flags&O2_SERIAL_FILEFORMAT2) && lshInCoreFlag){
+    unserialize_lsh_hashtables_format1(dbfid);
+  }
+
+  // Format2 always needs unserializing
+  if(lshHeader->flags&O2_SERIAL_FILEFORMAT2 && lshInCoreFlag){
+    unserialize_lsh_hashtables_format2(dbfid);
+  }
+
+  close(dbfid);}
+
+G::~G(){
+  delete lshHeader;
+}
 
 // single point insertion; inserted values are hash value and pointID
 Uns32T G::insert_point(vector<float>& v, Uns32T pp){
   Uns32T collisionCount = 0;
   H::p = pp;
-  if(pp>G::maxp)
-    G::maxp=pp; // Store highest pointID in database
-  compute_hash_functions( v );
+  if(pp>H::maxp)
+    H::maxp=pp; // Store highest pointID in database
+  H::compute_hash_functions( v );
   for(Uns32T j = 0 ; j < H::L ; j++ ){ // insertion
-    __generate_hash_keys( *( G::g + j ), *( H::r1 + j ), *( H::r2 + j ) ); 
+    H::generate_hash_keys( *( H::g + j ), *( H::r1 + j ), *( H::r2 + j ) ); 
     collisionCount += bucket_insert_point( *(h + j) + t1 );
   }
   return collisionCount;
 }
 

 
 // point retrieval routine
 void G::retrieve_point(vector<float>& v, Uns32T qpos, ReporterCallbackPtr add_point, void* caller){
   calling_instance = caller;
   add_point_callback = add_point;
-  compute_hash_functions( v );
+  H::compute_hash_functions( v );
   for(Uns32T j = 0 ; j < H::L ; j++ ){
-    __generate_hash_keys( *( G::g + j ), *( H::r1 + j ), *( H::r2 + j ) ); 
-    if( bucket* bPtr = *(__get_bucket(j) + get_t1()) )
+    H::generate_hash_keys( *( H::g + j ), *( H::r1 + j ), *( H::r2 + j ) ); 
+    if( bucket* bPtr = *(get_bucket(j) + get_t1()) )
 #ifdef LSH_BLOCK_FULL_ROWS
       bucket_chain_point( bPtr->next, qpos);
 #else
     bucket_chain_point( bPtr , qpos);
 #endif

 // r2[0][0] r2[0][1] ... r2[0][k-1]
 // r2[1][0] r2[1][1] ... r2[1][k-1]
 // ...
 // r2[L-1][0] r2[L-1][1] ... r2[L-1][k-1]
 //
+// ******* HASHTABLES FORMAT1 (optimized for LSH_ON_DISK retrieval) *******
 // ---hash table 0: N x C x 8 ---
 // [t2 pointID][t2 pointID]...[t2 pointID]
 // [t2 pointID][t2 pointID]...[t2 pointID]
 // ...
 // [t2 pointID][t2 pointID]...[t2 pointID]

 // [t2 pointID][t2 pointID]...[t2 pointID]
 // [t2 pointID][t2 pointID]...[t2 pointID]
 // ...
 // [t2 pointID][t2 pointID]...[t2 pointID]
 //
+// ******* HASHTABLES FORMAT2 (optimized for LSH_IN_CORE retrieval) *******
+//
+// State machine controlled by regular expression.
+// legend:
+//
+// O2_SERIAL_FLAGS_T1_BIT = 0x80000000U
+// O2_SERIAL_FLAGS_T2_BIT = 0x40000000U
+// O2_SERIAL_FLAGS_END_BIT = 0x20000000U
+//
+// T1(t1) - T1 hash token containing t1 hash key with O2_SERIAL_FLAGS_T1_BIT set (t1 range 0..2^29-1) 
+// T2 - T2 hash token with O2_SERIAL_FLAGS_T2_BIT set
+// t2 - t2 hash key (range 1..2^32-6)
+// p  - point identifier (range 0..2^32-1)
+// E  - end hash table token with O2_SERIAL_FLAGS_END_BIT set
+// {...} required arguments
+// [...] optional arguments
+// *  - match zero or more occurences
+// +  - match one or more occurences
+// {...}^L - repeat argument L times
+//
+// FORMAT2 Regular expression:
+// { [T1(t1) T2 t2 p+ [T2 t2 p+]* ]* E. }^L
+//
 
 // Serial header constructors
 SerialHeader::SerialHeader(){;}
 SerialHeader::SerialHeader(float W, Uns32T L, Uns32T N, Uns32T C, Uns32T k, Uns32T d, float r, Uns32T p, Uns32T FMT):
   lshMagic(O2_SERIAL_MAGIC),

     serialize_lsh_hashtables_format2(dbfid, !dbIsNew);
 
   if(!dbIsNew){
     db = serial_mmap(dbfid, O2_SERIAL_HEADER_SIZE, 1);// get database pointer
     //serial_get_header(db);           // read header
-    cout << "maxp = " << G::maxp << endl;
-    lshHeader->maxp=G::maxp;
+    cout << "maxp = " << H::maxp << endl;
+    lshHeader->maxp=H::maxp;
     // Default to FILEFORMAT1
     if(!(lshHeader->flags&O2_SERIAL_FILEFORMAT2))
       lshHeader->flags|=O2_SERIAL_FILEFORMAT2;
     memcpy((char*)db, (char*)lshHeader, sizeof(SerialHeaderT));
     serial_munmap(db, O2_SERIAL_HEADER_SIZE); // drop mmap

 int G::serialize_lsh_hashfunctions(int fid){
   float* pf;
   Uns32T *pu;
   Uns32T x,y,z;
   
-  db = serial_mmap(fid, get_serial_hashtable_offset(), 1);// get database pointer  
+  char* db = serial_mmap(fid, get_serial_hashtable_offset(), 1);// get database pointer  
   pf = get_serial_hashfunction_base(db);
 
   // HASH FUNCTIONS
   // Write the random projectors A[][][]
 #ifdef USE_U_FUNCTIONS

 #else
       for( x = 0 ; x < H::L ; x++ )
 	for( y = 0 ; y < H::k ; y++ )
 #endif
 	  for( z = 0 ; z < d ; z++ )
-	    *pf++ = A[x][y][z];
+	    *pf++ = H::A[x][y][z];
   
   // Write the random biases b[][]
 #ifdef USE_U_FUNCTIONS
   for( x = 0 ; x < H::m ; x++ )
     for( y = 0 ; y < H::k/2 ; y++ )
 #else
       for( x = 0 ; x < H::L ; x++ )
 	for( y = 0 ; y < H::k ; y++ )
 #endif
-	  *pf++=b[x][y];
+	  *pf++ = H::b[x][y];
   
   pu = (Uns32T*)pf;
   
   // Write the Z projectors r1[][]
   for( x = 0 ; x < H::L ; x++)
     for( y = 0 ; y < H::k ; y++)
-      *pu++ = r1[x][y];
+      *pu++ = H::r1[x][y];
   
   // Write the Z projectors r2[][]
   for( x = 0 ; x < H::L ; x++)
     for( y = 0; y < H::k ; y++)
-      *pu++ = r2[x][y];  
+      *pu++ = H::r2[x][y];  
   
   serial_munmap(db, get_serial_hashtable_offset());
   return 1;
 }
 

   
   // write a dummy byte at the last location
   if (write (dbfid, "", 1) != 1)
     error("write error", "", "write");
   
-  db = serial_mmap(dbfid, O2_SERIAL_HEADER_SIZE, 1);
+  char* db = serial_mmap(dbfid, O2_SERIAL_HEADER_SIZE, 1);
 
   memcpy (db, lshHeader, O2_SERIAL_HEADER_SIZE);
 
   serial_munmap(db, O2_SERIAL_HEADER_SIZE);
 

 
   return 1;  
 }
 
 char* G::serial_mmap(int dbfid, Uns32T memSize, Uns32T forWrite, off_t offset){
+  char* db;
   if(forWrite){
     if ((db = (char*) mmap(0, memSize, PROT_READ | PROT_WRITE,
 			   MAP_SHARED, dbfid, offset)) == (caddr_t) -1)
       error("mmap error in request for writable serialized database", "", "mmap");  
   }

   H::m = (Uns32T)( (1.0 + sqrt(1 + 8.0*(int)H::L)) / 2.0);
   H::N = lshHeader->numRows;
   H::C = lshHeader->numCols;
   H::k = lshHeader->numFuns;
   H::d = lshHeader->dataDim;
-  G::w = lshHeader->binWidth;
-  G::radius = lshHeader->radius;
-  G::maxp = lshHeader->maxp;
+  H::w = lshHeader->binWidth;
+  H::radius = lshHeader->radius;
+  H::maxp = lshHeader->maxp;
 
   return dbfid;
 }
 
 // unserialize the LSH parameters

   Uns32T* pu;
 
   // Load the hash functions into core
   char* db = serial_mmap(dbfid, get_serial_hashtable_offset(), 0);// get database pointer again  
   
-#ifdef USE_U_FUNCTIONS
-  G::A = new float**[ H::m ]; // m x k x d random projectors
-  G::b = new float*[ H::m ];  // m x k random biases
-#else
-  G::A = new float**[ H::L ]; // m x k x d random projectors
-  G::b = new float*[ H::L ];  // m x k random biases
-#endif
-  G::g = new Uns32T*[ H::L ];   //  L x k random projections 
-  assert(g&&A&&b); // failure
-  
   pf = get_serial_hashfunction_base(db);
   
 #ifdef USE_U_FUNCTIONS
   for( j = 0 ; j < H::m ; j++ ){ // L functions gj(v)
-    G::A[j] = new float*[ H::k/2 ];  // k x d  2-stable distribution coefficients     
-    G::b[j] = new float[ H::k/2 ];   // bias
-    assert( G::A[j] && G::b[j] ); // failure    
     for( kk = 0 ; kk < H::k/2 ; kk++ ){ // Normally distributed hash functions
 #else
       for( j = 0 ; j < H::L ; j++ ){ // L functions gj(v)
-	G::A[j] = new float*[ H::k ];  // k x d  2-stable distribution coefficients     
-	G::b[j] = new float[ H::k ];   // bias
-	assert( G::A[j] && G::b[j] ); // failure    
 	for( kk = 0 ; kk < H::k ; kk++ ){ // Normally distributed hash functions
 #endif
-	  G::A[j][kk] = new float[ H::d ];
-	  assert( G::A[j][kk] ); // failure
 	  for(Uns32T i = 0 ; i < H::d ; i++ )
-	    G::A[j][kk][i] = *pf++; // Normally distributed random vectors
+	    H::A[j][kk][i] = *pf++; // Normally distributed random vectors
 	}
       }
 #ifdef USE_U_FUNCTIONS
       for( j = 0 ; j < H::m ; j++ ) // biases b
 	for( kk = 0 ; kk < H::k/2 ; kk++ )
 #else
 	  for( j = 0 ; j < H::L ; j++ ) // biases b
 	    for( kk = 0 ; kk < H::k ; kk++ )
 #endif
-	      G::b[j][kk] = *pf++;
-      
-      for( j = 0 ; j < H::L ; j++){ // 32-bit hash values, gj(v)=[x0 x1 ... xk-1] xk \in Z
-	G::g[j] = new Uns32T[ H::k ];   
-	assert( G::g[j] );
-      }
-      
-      
-      H::__initialize_data_structures();
+	      H::b[j][kk] = *pf++;
       
       pu = (Uns32T*)pf;
       for( j = 0 ; j < H::L ; j++ ) // Z projectors r1
 	for( kk = 0 ; kk < H::k ; kk++ )
 	  H::r1[j][kk] = *pu++;
       
       for( j = 0 ; j < H::L ; j++ ) // Z projectors r2
 	for( kk = 0 ; kk < H::k ; kk++ )
 	  H::r2[j][kk] = *pu++;
 
-  serial_munmap(db, get_serial_hashtable_offset());
+      serial_munmap(db, get_serial_hashtable_offset());
 }
 
 void G::unserialize_lsh_hashtables_format1(int fid){
   SerialElementT *pe, *pt;
   Uns32T x,y;

 			   align_up(get_serial_hashtable_offset()+j*hashTableSize,get_page_logn()));
     if(madvise(db, hashTableSize, MADV_RANDOM)<0)
       error("could not advise local hashtable memory","","madvise");
     SerialElementT* pe = (SerialElementT*)db ;
     for(Uns32T qpos=0; qpos<vv.size(); qpos++){
-      compute_hash_functions(vv[qpos]);
-      __generate_hash_keys(*(g+j),*(r1+j),*(r2+j)); 
+      H::compute_hash_functions(vv[qpos]);
+      H::generate_hash_keys(*(g+j),*(r1+j),*(r2+j)); 
       serial_bucket_chain_point(pe+t1*lshHeader->numCols, qpos); // Point to correct row
     }
     serial_munmap(db, hashTableSize); // drop hashtable mmap
   }  
   serial_close(dbfid);    

 
   // size of each hash table
   Uns32T hashTableSize=sizeof(SerialElementT)*lshHeader->numRows*lshHeader->numCols;
   calling_instance = caller;
   add_point_callback = add_point;
-  compute_hash_functions(v);
+  H::compute_hash_functions(v);
   for(Uns32T j=0; j<L; j++){
     // memory map a single hash table for random access
     char* db = serial_mmap(dbfid, hashTableSize, 0, 
 			   align_up(get_serial_hashtable_offset()+j*hashTableSize,get_page_logn()));
     if(madvise(db, hashTableSize, MADV_RANDOM)<0)
       error("could not advise local hashtable memory","","madvise");
     SerialElementT* pe = (SerialElementT*)db ;
-    __generate_hash_keys(*(g+j),*(r1+j),*(r2+j)); 
+    H::generate_hash_keys(*(g+j),*(r1+j),*(r2+j)); 
     serial_bucket_chain_point(pe+t1*lshHeader->numCols, qpos); // Point to correct row
     serial_munmap(db, hashTableSize); // drop hashtable mmap
   }  
   serial_close(dbfid);    
 }