E2LSH源代码

/* * Copyright (c) 2004-2005 Massachusetts Institute of Technology. * All Rights Reserved. * * MIT grants permission to use, copy, modify, and distribute this software and * its documentation for NON-COMMERCIAL purposes and without fee, provided that * this copyright notice appears in all copies. * * MIT provides this software "as is," without representations or warranties of * any kind, either expressed or implied, including but not limited to the * implied warranties of merchantability, fitness for a particular purpose, and * noninfringement. MIT shall not be liable for any damages arising from any * use of this software. * * Author: Alexandr Andoni ([email protected]), Piotr Indyk ([email protected]) */ /* The main functionality of the LSH scheme is in this file (all except the hashing of the buckets). This file includes all the functions for processing a PRNearNeighborStructT data structure, which is the main R-NN data structure based on LSH scheme. The particular functions are: initializing a DS, adding new points to the DS, and responding to queries on the DS. */ #include "headers.h" void printRNNParameters(FILE *output, RNNParametersT parameters){ ASSERT(output != NULL); fprintf(output, "R\n"); fprintf(output, "%0.9lf\n", parameters.parameterR); fprintf(output, "Success probability\n"); fprintf(output, "%0.9lf\n", parameters.successProbability); fprintf(output, "Dimension\n"); fprintf(output, "%d\n", parameters.dimension); fprintf(output, "R^2\n"); fprintf(output, "%0.9lf\n", parameters.parameterR2); fprintf(output, "Use <u> functions\n"); fprintf(output, "%d\n", parameters.useUfunctions); fprintf(output, "k\n"); fprintf(output, "%d\n", parameters.parameterK); fprintf(output, "m [# independent tuples of LSH functions]\n"); fprintf(output, "%d\n", parameters.parameterM); fprintf(output, "L\n"); fprintf(output, "%d\n", parameters.parameterL); fprintf(output, "W\n"); fprintf(output, "%0.9lf\n", parameters.parameterW); fprintf(output, "T\n"); fprintf(output, "%d\n", parameters.parameterT); fprintf(output, "typeHT\n"); fprintf(output, "%d\n", parameters.typeHT); } RNNParametersT readRNNParameters(FILE *input){ ASSERT(input != NULL); RNNParametersT parameters; char s[1000];// TODO: possible buffer overflow fscanf(input, "\n");fscanf(input, "%[^\n]\n", s); FSCANF_REAL(input, &parameters.parameterR); fscanf(input, "\n");fscanf(input, "%[^\n]\n", s); FSCANF_REAL(input, &parameters.successProbability); fscanf(input, "\n");fscanf(input, "%[^\n]\n", s); fscanf(input, "%d", &parameters.dimension); fscanf(input, "\n");fscanf(input, "%[^\n]\n", s); FSCANF_REAL(input, &parameters.parameterR2); fscanf(input, "\n");fscanf(input, "%[^\n]\n", s); fscanf(input, "%d", &parameters.useUfunctions); fscanf(input, "\n");fscanf(input, "%[^\n]\n", s); fscanf(input, "%d", &parameters.parameterK); fscanf(input, "\n");fscanf(input, "%[^\n]\n", s); fscanf(input, "%d", &parameters.parameterM); fscanf(input, "\n");fscanf(input, "%[^\n]\n", s); fscanf(input, "%d", &parameters.parameterL); fscanf(input, "\n");fscanf(input, "%[^\n]\n", s); FSCANF_REAL(input, &parameters.parameterW); fscanf(input, "\n");fscanf(input, "%[^\n]\n", s); fscanf(input, "%d", &parameters.parameterT); fscanf(input, "\n");fscanf(input, "%[^\n]\n", s); fscanf(input, "%d", &parameters.typeHT); return parameters; } // Creates the LSH hash functions for the R-near neighbor structure // <nnStruct>. The functions fills in the corresponding field of // <nnStruct>. void initHashFunctions(PRNearNeighborStructT nnStruct){ ASSERT(nnStruct != NULL); LSHFunctionT **lshFunctions; // allocate memory for the functions FAILIF(NULL == (lshFunctions = (LSHFunctionT**)MALLOC(nnStruct->nHFTuples * sizeof(LSHFunctionT*)))); for(IntT i = 0; i < nnStruct->nHFTuples; i++){ FAILIF(NULL == (lshFunctions[i] = (LSHFunctionT*)MALLOC(nnStruct->hfTuplesLength * sizeof(LSHFunctionT)))); for(IntT j = 0; j < nnStruct->hfTuplesLength; j++){ FAILIF(NULL == (lshFunctions[i][j].a = (RealT*)MALLOC(nnStruct->dimension * sizeof(RealT)))); } } // initialize the LSH functions for(IntT i = 0; i < nnStruct->nHFTuples; i++){ for(IntT j = 0; j < nnStruct->hfTuplesLength; j++){ // vector a for(IntT d = 0; d < nnStruct->dimension; d++){ #ifdef USE_L1_DISTANCE lshFunctions[i][j].a[d] = genCauchyRandom(); #else lshFunctions[i][j].a[d] = genGaussianRandom(); #endif } // b lshFunctions[i][j].b = genUniformRandom(0, nnStruct->parameterW); } } nnStruct->lshFunctions = lshFunctions; } // Initializes the fields of a R-near neighbors data structure except // the hash tables for storing the buckets. PRNearNeighborStructT initializePRNearNeighborFields(RNNParametersT algParameters, Int32T nPointsEstimate){ PRNearNeighborStructT nnStruct; FAILIF(NULL == (nnStruct = (PRNearNeighborStructT)MALLOC(sizeof(RNearNeighborStructT)))); nnStruct->parameterR = algParameters.parameterR; nnStruct->parameterR2 = algParameters.parameterR2; nnStruct->useUfunctions = algParameters.useUfunctions; nnStruct->parameterK = algParameters.parameterK; if (!algParameters.useUfunctions) { // Use normal <g> functions. nnStruct->parameterL = algParameters.parameterL; nnStruct->nHFTuples = algParameters.parameterL; nnStruct->hfTuplesLength = algParameters.parameterK; }else{ // Use <u> hash functions; a <g> function is a pair of 2 <u> functions. nnStruct->parameterL = algParameters.parameterL; nnStruct->nHFTuples = algParameters.parameterM; nnStruct->hfTuplesLength = algParameters.parameterK / 2; } nnStruct->parameterT = algParameters.parameterT; nnStruct->dimension = algParameters.dimension; nnStruct->parameterW = algParameters.parameterW; nnStruct->nPoints = 0; nnStruct->pointsArraySize = nPointsEstimate; FAILIF(NULL == (nnStruct->points = (PPointT*)MALLOC(nnStruct->pointsArraySize * sizeof(PPointT)))); // create the hash functions initHashFunctions(nnStruct); // init fields that are used only in operations ("temporary" variables for operations). // init the vector <pointULSHVectors> and the vector // <precomputedHashesOfULSHs> FAILIF(NULL == (nnStruct->pointULSHVectors = (Uns32T**)MALLOC(nnStruct->nHFTuples * sizeof(Uns32T*)))); for(IntT i = 0; i < nnStruct->nHFTuples; i++){ FAILIF(NULL == (nnStruct->pointULSHVectors[i] = (Uns32T*)MALLOC(nnStruct->hfTuplesLength * sizeof(Uns32T)))); } FAILIF(NULL == (nnStruct->precomputedHashesOfULSHs = (Uns32T**)MALLOC(nnStruct->nHFTuples * sizeof(Uns32T*)))); for(IntT i = 0; i < nnStruct->nHFTuples; i++){ FAILIF(NULL == (nnStruct->precomputedHashesOfULSHs[i] = (Uns32T*)MALLOC(N_PRECOMPUTED_HASHES_NEEDED * sizeof(Uns32T)))); } // init the vector <reducedPoint> FAILIF(NULL == (nnStruct->reducedPoint = (RealT*)MALLOC(nnStruct->dimension * sizeof(RealT)))); // init the vector <nearPoints> nnStruct->sizeMarkedPoints = nPointsEstimate; FAILIF(NULL == (nnStruct->markedPoints = (BooleanT*)MALLOC(nnStruct->sizeMarkedPoints * sizeof(BooleanT)))); for(IntT i = 0; i < nnStruct->sizeMarkedPoints; i++){ nnStruct->markedPoints[i] = FALSE; } // init the vector <nearPointsIndeces> FAILIF(NULL == (nnStruct->markedPointsIndeces = (Int32T*)MALLOC(nnStruct->sizeMarkedPoints * sizeof(Int32T)))); nnStruct->reportingResult = TRUE; return nnStruct; } // Constructs a new empty R-near-neighbor data structure. PRNearNeighborStructT initLSH(RNNParametersT algParameters, Int32T nPointsEstimate){ ASSERT(algParameters.typeHT == HT_LINKED_LIST || algParameters.typeHT == HT_STATISTICS); PRNearNeighborStructT nnStruct = initializePRNearNeighborFields(algParameters, nPointsEstimate); // initialize second level hashing (bucket hashing) FAILIF(NULL == (nnStruct->hashedBuckets = (PUHashStructureT*)MALLOC(nnStruct->parameterL * sizeof(PUHashStructureT)