knnsearch.c

基于内容的多媒体数据库检索算法

/*
 * knnsearch.c
 *
 * VP-tree Program - K-Near-neighbor search
 *
 * By Philip Fu
 *
 * Mon Jan 15 03:02:36 EST 2001
 *
 */


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/resource.h>
#include <sys/times.h>

#include "vptree.h"
#include "standard.h"




void
readQuery(char *queryFile, double **queryPt, int dimension)
{
    FILE  *fp;
    int    k,i;
    double f;
    char   buf[255];


    /////////////////////////////////////////
    // 1) Open file

    fp = fopen(queryFile,"r");

    if (!fp)
	errexit2("Err : cannot read file [%s]\n\n",queryFile);


    /////////////////////////////////////////
    // 2) Read queryPt

    // read k
    //fgets(buf,255,fp);
    //sscanf(buf,"%d",&k);

    // allocate memory for queryPt
    *queryPt = (double *) malloc(sizeof(double)*dimension);
    if (!(*queryPt))
	errexit("Err : Not enough memory for allocation!\n\n");

    // read queryPt
    for (i=0; i<dimension; i++) {
	fscanf(fp,"%lf",&f);
	(*queryPt)[i] = f;
    }


    /////////////////////////////////////////
    // 3) Done

    fclose(fp);

    return;
}



int
main(int argc, char **argv)
{
    VPTree *vpTree;
    int     i,k,n;
    double *queryPt;

    double *resultPt;
    int    *resultID;

    FILE *resultFp;
    int dim,nodeCount;

    float  userTime, sysTime;
    struct rusage startTime, stopTime;


    /////////////////////////////////////////////////////////

    getrusage(RUSAGE_SELF,&startTime);

    /////////////////////////////////////////////////////////
    // (1) Sanity check

    printf("\n");

    if (argc != 6) {
	printf("Usage : %s <dim> <k> <vptree file> <query file> <result file>\n\n",argv[0]);
	return;
    }

    dim = atoi(argv[1]);
    k = atoi(argv[2]);

    /////////////////////////////////////////////////////////
    // (2) Read VP-tree

    printf("Reading the VP-Tree ........ ");
    fflush(stdout);

    vpTree = readVPTree(argv[3],&n);

    if (vpTree == NULL) {
	printf("Oh! No memory left for me...\n\n");
	return;
    }

    if (dim != vpTree->dimension) {
	printf("Dimension not match\n");
	exit(1);
    }

    printf("done [%d points, %d dimension]\n",n,vpTree->dimension);



    /////////////////////////////////////////////////////////
    // (3) Read Query File

    printf("Reading Query File ......... ");
    fflush(stdout);

    readQuery(argv[4],&queryPt,vpTree->dimension);

    printf("done [k = %d]\n",k);



    /////////////////////////////////////////////////////////
    // (4) Process the Query

    printf("Processing the Query ....... ");
    fflush(stdout);


    // 4a) allocate memory for resultPt and resultID
    resultPt = (double *) malloc(sizeof(double)*k*vpTree->dimension);
    resultID = (int *)    malloc(sizeof(int)*k);

    if (!resultID || !resultPt)
	errexit("Err : Not enough memory for allocation!\n\n");

    // 4b) call knnsearch in vptree.c
    nodeCount = knnsearch(vpTree,queryPt,k,resultPt,resultID);

    printf("done\n");


    /////////////////////////////////////////////////////////

    getrusage(RUSAGE_SELF,&stopTime);

    /////////////////////////////////////////////////////////
    // (5) Report result and Release resource


    // 5a) Report result

    /*
    printf("\n");
    printf("Query Pt  : ");
    printPt(stdout,queryPt,vpTree->dimension);
    printf("\n");
 
    printf("\n");
    printf("Result Pt : ");
    printPt(stdout,resultPt,vpTree->dimension);
    printf(" (%d)\n",resultID[0]);
    */

    if ((resultFp = fopen(argv[5], "w")) == NULL) {
	printf("Can't write to file, %s\n", argv[4]);
	exit(1);
    }
    fprintf(resultFp, "%d\n", resultID[0]);

    for (i=1; i<k; i++) {
	/*
	printf("            ");
	printPt(stdout,
	        resultPt+i*vpTree->dimension,
	        vpTree->dimension);
	printf(" (%d)\n",resultID[i]);
	*/
    	fprintf(resultFp, "%d\n", resultID[i]);
    }

    fclose(resultFp);

    // Report execution time
    userTime =
                ((float) (stopTime.ru_utime.tv_sec  - startTime.ru_utime.tv_sec)) +
                ((float) (stopTime.ru_utime.tv_usec - startTime.ru_utime.tv_usec)) * 1e-6;
    sysTime =
                ((float) (stopTime.ru_stime.tv_sec  - startTime.ru_stime.tv_sec)) +
                ((float) (stopTime.ru_stime.tv_usec - startTime.ru_stime.tv_usec)) * 1e-6;

    printf("\n");
    printf("number of nodes visited : %d\n",nodeCount);
    printf("User time   : %f seconds\n",userTime);
    printf("System time : %f seconds\n\n",sysTime);


    // 5e) Release resource

    freeVPTree(vpTree);

    free(resultPt);
    free(resultID);
    free(queryPt);


    printf("\n");
}