comparison lshlib.h @ 754:9bd13c7819ae mkc_lsh_update

Adding mkc_lsh_update branch, trunk candidate with improved LSH: merged trunk 1095 and branch multiprobe_lsh

 */
 
 #ifndef __LSHLIB_H
 #define __LSHLIB_H
 
-using namespace std;
+#include <vector>
+#include <queue>
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/mman.h>
+#include <fcntl.h>
+#include <string.h>
+#include <iostream>
+#include <fstream>
+#include <math.h>
+#include <sys/time.h>
+#include <assert.h>
+#include <float.h>
+#include <signal.h>
+#include <time.h>
+#include <limits.h>
+#include <errno.h>
+#ifdef MT19937
+#include "mt19937/mt19937ar.h"
+#endif
+#include "multiprobe.h"
 
 #define IntT int
 #define LongUns64T long long unsigned
 #define Uns32T unsigned
 #define Int32T int
 #define BooleanT int
+#define TRUE 1
+#define FALSE 0
 
 // A big number (>> max #  of points)
 #define INDEX_START_EMPTY 1000000000U
 
 // 4294967291 = 2^32-5

 #define O2_SERIAL_TOKEN_T2 (0xFFFFFFFDU)
 #define O2_SERIAL_TOKEN_ENDTABLE (0xFFFFFFFEU)
 
 #define O2_INDEX_MAXSTR (256)
 
-#define align_up(x,w) (((x) + ((1<<w)-1)) & ~((1<<w)-1))
+unsigned align_up(unsigned x, unsigned w);
 
 #define O2_SERIAL_FUNCTIONS_SIZE (align_up(sizeof(float) * O2_SERIAL_MAX_TABLES * O2_SERIAL_MAX_FUNS * O2_SERIAL_MAX_DIM \
 + sizeof(float) * O2_SERIAL_MAX_TABLES * O2_SERIAL_MAX_FUNS + \
 + sizeof(Uns32T) * O2_SERIAL_MAX_TABLES * O2_SERIAL_MAX_FUNS * 2 \
 + O2_SERIAL_HEADER_SIZE,get_page_logn()))

 
 #define WRITE_UNS32(VAL, TOKENSTR) if( fwrite(VAL, sizeof(Uns32T), 1, dbFile) != 1 ){\
   fclose(dbFile);error("write error in serial_write_format2",TOKENSTR);}	
 
 //#define LSH_DUMP_CORE_TABLES  // set to dump hashtables on load
+//#define _LSH_DEBUG_             // turn on debugging information
 //#define USE_U_FUNCTIONS       // set to use partial hashfunction re-use
 
 // Backward-compatible CORE ARRAY lsh index
 #define LSH_CORE_ARRAY  // Set to use arrays for hashtables rather than linked-lists
 #define LSH_LIST_HEAD_COUNTERS // Enable counters in hashtable list heads

 #define LSH_LIST_HEAD_COUNTERS
 #endif
 
 #define LSH_CORE_ARRAY_BIT (0x80000000) //  LSH_CORE_ARRAY test bit for list head
 
+#ifndef LSH_MULTI_PROBE_COUNT
+#define LSH_MULTI_PROBE_COUNT 1 // How many adjacent hash-buckets to probe in LSH retrieval
+#endif
+
 Uns32T get_page_logn();
+
+using namespace std;
 
 // Disk table entry
 typedef class SerialElement SerialElementT;
 class SerialElement {
 public:

 #endif
   Uns32T maxp; // highest pointID stored in database
   Uns32T bucketCount;  // count of number of point buckets allocated
   Uns32T pointCount;    // count of number of points inserted
   Uns32T collisionCount; // number of points collided in a hash-table row
+  Uns32T tablesPointCount; // count of points per hash table on load
 
   Uns32T t1;       // first hash table key
   Uns32T t2;       // second hash table key
   Uns32T P;        // hash table prime number
+
 
   Uns32T N; // num rows per table
   Uns32T C; // num collision per row
   Uns32T k; // num projections per hash function
   Uns32T m; // ~sqrt num hash tables
   Uns32T L; // L = m*(m-1)/2, conversely, m = (1 + sqrt(1 + 8.0*L)) / 2.0
   Uns32T d; // dimensions
   Uns32T p; // current point
   float w;     // width of hash slots (relative to normalized feature space)
   float radius;// scaling coefficient for data (1./radius)
+
+  MultiProbe* multiProbePtr; // Utility class for handling multi-probe queries
+  float ** boundaryDistances; // Array of query bucket-boundary-distances per hashtable
 
   void initialize_data_structures();
   void initialize_lsh_functions();
   void initialize_partial_functions();
   void __bucket_insert_point(bucket*);

   Uns32T bucket_insert_point(bucket**);
 
   // Interface to hash functions
   void compute_hash_functions(vector<float>& v);
   void generate_hash_keys(Uns32T* g, Uns32T* r1, Uns32T* r2);
+  void generate_multiprobe_keys(Uns32T*g, Uns32T* r1, Uns32T* r2);
   Uns32T get_t1(){return t1;} // hash-key t1
   Uns32T get_t2(){return t2;} // hash-key t2
 };
 
 // Typedef for point-reporting callback function. Used to collect points during LSH retrieval

   // LSH serial data structure file handling
   void get_lock(int fd, bool exclusive);
   void release_lock(int fd);
   int serial_create(char* filename, Uns32T FMT);
   int serial_create(char* filename, float binWidth, Uns32T nTables, Uns32T nRows, Uns32T nCols, Uns32T k, Uns32T d, Uns32T FMT);
+  char* serial_mmap(int dbfid, Uns32T sz, Uns32T w, off_t offset = 0);
+  void serial_munmap(char* db, Uns32T N);
   int serial_open(char* filename,int writeFlag);
   void serial_close(int dbfid);
 
   // Function to write hashfunctions to disk
   int serialize_lsh_hashfunctions(int fid);

   // Helper functions
   void serial_print_header(Uns32T requestedFormat);
   float* get_serial_hashfunction_base(char* db);
   SerialElementT* get_serial_hashtable_base(char* db);  
   Uns32T get_serial_hashtable_offset();                   // Size of SerialHeader + HashFunctions
-  SerialHeaderT* serial_get_header(int fd);
-  void serial_write_header(int fd, SerialHeaderT *header);
-  void serial_get_table(int, int, void *, size_t);
-  void serial_write_table(int, int, void *, size_t);
+  SerialHeaderT* serial_get_header(char* db);
   SerialHeaderT* lshHeader;
 
   // Core Retrieval/Inspections Functions
   void bucket_chain_point(bucket* p, Uns32T qpos);
   void sbucket_chain_point(sbucket* p, Uns32T qpos);  

   SerialHeaderT* get_lshHeader(){return lshHeader;}
   void serial_dump_tables(char* filename);
   float get_mean_collision_rate(){ return (float) pointCount / bucketCount ; }
   char* get_indexName(){return indexName;}
   void dump_hashtables();
-
+  void dump_core_row(Uns32T n);
+  void dump_disk_row(char*, Uns32T n);
 };
 
 typedef class G LSH;