xsearch.c

xtree程序实现

/*******************************************************
  CSC 5120 Project
  Group 2
  Members : Cheung Ka Leong (99586612) (klcheung@cse)
            Wong Chi Wing   (99681242) (cwwong@cse)
*******************************************************/


/****************************************
Remark : If want to change the number of
		 query point , check the variable
		 no_query in read_query function
*****************************************/


#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>

#include <string.h>

#ifndef WIN32
#include <sys/times.h>
#include <unistd.h>
#endif

#include "xtree.h"

int E_dist_comp_count = 0;
int E_page_access_count = 0;
int E_represent_accuracy = 0;
int E_prune_ans_no = 0;
int E_overlap_yes = 0;
int E_no_answer = 0;
int Num_of_super_node_access = 0;

void initialize(config_type *config)
{
  FILE *fp;
  int string_len;

  fp = fopen(CONFIG_FILE, "r");


  fscanf(fp, "m=%d\n", &m);
  fscanf(fp, "M=%d\n", &M);
  fscanf(fp, "dim=%d\n", &dim);
  fscanf(fp, "reinsert_p=%d\n", &reinsert_p);
  fscanf(fp, "no_histogram=%d\n",&no_histogram);

  fgets(config->nodefile, FILENAME_MAX, fp);
  string_len = strlen(config->nodefile);
  config->nodefile[string_len-1] = '\0';

  fgets(config->rootfile, FILENAME_MAX, fp);
  string_len = strlen(config->rootfile);
  config->rootfile[string_len-1] = '\0';

  fgets(config->positionfile, FILENAME_MAX, fp);
  string_len = strlen(config->positionfile);
  config->positionfile[string_len-1] = '\0';

  fgets(config->queryfile, FILENAME_MAX, fp);
  string_len = strlen(config->queryfile);
  config->queryfile[string_len-1] = '\0';

}
/* initialize */


void tree_node_allocate(node_type **node)
{

  (*node) = (node_type *)malloc(sizeof(node_type));
  (*node)->a = (float *)malloc(sizeof(float) * dim);
  (*node)->b = (float *)malloc(sizeof(float) * dim);
  //(*node)->ptr = (node_type **)malloc(sizeof(node_type *) * MAX_X_SNODE * M);
  (*node)->ptr = (node_type **)malloc(sizeof(node_type *) * M);
}

int read_query(char *queryfile, float ***query)
{
  FILE *fp_pos;
  int no_query;

  int i,j;

  no_query=5;

  fp_pos = fopen(queryfile, "r");
  (*query) = (float **)malloc(no_query * sizeof(float*));
  for (i=0; i<no_query; i++)
  	(*query)[i] = (float *)malloc(dim * sizeof(float));

  for (i=0; i<no_query; i++)
	for (j=0; j<dim; j++)
                fscanf(fp_pos, "%f", &((*query)[i][j]));
  fclose(fp_pos);

  return(no_query);

} /* read_query */

/* Distance Computation */
double MINDIST(float *P, float *a, float *b)
{
        int i;
        double sum = 0.0;


        for(i=0 ;i<dim ;i++)
        {
                if (P[i] > b[i])
                        sum += pow(P[i] - b[i], 2.0);
                else if (P[i] < a[i])
                        sum += pow(a[i] - P[i], 2.0);
        }

        return sum;
}

double cal_Euclidean(node_type *node, float *query)
{
        int i;
        double distance;
        distance = 0.0;

        for(i=0; i< dim ;i++)
                distance += pow((node->a[i] - query[i]),(double)2.0);

        return (sqrt(distance));
}


/***********************************/
/* rectangle_search():             */
/* search query points on the tree */
/*************************** *******/

int rectangle_search(node_type *curr_node, float *query, float error)
{
  int find_flag;
  int i, j, stop, flag;
  int query_dim;

  query_dim = dim;
E_page_access_count ++;
if(curr_node->snodeSize > 1){

	Num_of_super_node_access++;
}

  /* Search leaf node */
  if(curr_node->attribute == LEAF) {

 if(cal_Euclidean(curr_node , query) <= error){

     for(j=0; j<query_dim; j++)
              printf("%f ", curr_node->a[j]);

      printf("  at %d\n", curr_node->id);
}
        return(FOUND);

  }

  //**** RAY CHANGED
  //stop = M - curr_node->vacancy;
  stop = M*curr_node->snodeSize - curr_node->vacancy;
  for(i=0; i < stop; i++) {

        flag = TRUE;

        /* search subtree */
        for(j=0; j < query_dim; j++) {

                if(curr_node->ptr[i]->a[j] > (query[j] + error) ||
                   curr_node->ptr[i]->b[j] < (query[j] - error))
                {
                        flag = FALSE;
                        break;
                }
        }

        /* search the node which contains the query */
        if(flag==TRUE) {
                find_flag = rectangle_search(curr_node->ptr[i], query, error);
        }
  }

  return(find_flag);

}
/* rectangle_search */



/**********************************/
/* rectangle_search_tree():       */
/* prepare to search query points */
/**********************************/

void rectangle_search_tree(node_type *root, int no_query, float **query, float error)
{
  int query_index;
  int j, find_flag = NOT_FOUND;
  int query_dim;

  query_dim = dim;

  /* start search data points by invoking rectangle_search() */
  for(query_index=0; query_index < no_query; query_index++) {


        printf("Query ");
        for(j=0; j < query_dim; j++)
               printf("%f ", query[query_index][j]);
        printf("is found satisfied with\n");


        find_flag = NOT_FOUND;
        find_flag = rectangle_search(root, query[query_index], error);

  }


} /* rectangle_search_tree */




void read_inter_node(node_type *node, FILE *fp)
{
  int i, count;

  for (i = 0; i<dim; i++)
        fscanf(fp, "%f\n", &((node->a)[i]));

  for (i = 0; i<dim; i++)
        fscanf(fp, "%f\n", &((node->b)[i]));

  fscanf(fp, "%d\n", &(node->attribute));
  if (node->attribute == LEAF) {
	fscanf(fp, "%d\n", &(node->id));
  }
  fscanf(fp, "%d\n", &(node->vacancy));
  // *** Ray added
  if (node->attribute != LEAF)
  {
	  fscanf(fp, "%d\n", &(node->snodeSize));

	  // *** RAY added
	  free(node->ptr);
	  node->ptr = (node_type **) malloc(sizeof(node_type *)*M*node->snodeSize);

	  //printf(" **** snodeSize: %d\n", node->snodeSize);
	  if (node->snodeSize > 1)
	  {
		  printf("hello\n");
		  printf("  vacancy: %d\n", node->vacancy);
		  printf("  snodeSize: %d\n", node->snodeSize);
	  }
  }

/****************************************
  for (i = 0; i<dim; i++)
        printf("%f\n", node->a[i]);

  for (i = 0; i<dim; i++)
        printf("%f\n", node->b[i]);

  printf("%d\n", node->attribute);
  if (node->attribute == LEAF) {
        printf("%d\n", node->id);
  }
  printf("%d\n", node->vacancy);
****************************************/

  if (node->attribute != LEAF) {
	// *** Ray modified
  	//count = M - node->vacancy;
	count = M*node->snodeSize - node->vacancy;
  	for (i=0; i<count; i++) {
		tree_node_allocate(&(node->ptr[i]));
                read_inter_node(node->ptr[i], fp);
	}
  }

  return;

}



void read_xtree(node_type **root)
{
  FILE *fp;


  tree_node_allocate(root);

  fp = fopen(SAVE_XTREE_FILE, "r");

  read_inter_node(*root, fp);

  fclose(fp);

  return;

}

void NN_update(NN_type *NN, double dist, node_type *node, int k)
{
  int i=0;
  while (i<k-1 && NN->next->dist >= dist)
  {
	NN->dist=NN->next->dist;
	NN->oid=NN->next->oid;
	NN->pointer=NN->next->pointer;
	NN=NN->next;
	i++;
  }
  NN->dist=dist;
  NN->oid=node->id;
  NN->pointer=node;
  return;
}


static int compare(ABL *i, ABL *j)
{
        if (i->min > j->min)
                  return (1);
        if (i->min < j->min)
                  return (-1);
        return (0);
}

void gen_ABL(node_type *node, ABL branch[], float *query, int total)
{
  int i;
  for (i=0;i<total;i++)
  {
	branch[i].node=node->ptr[i];
	branch[i].min=MINDIST(query, node->ptr[i]->a, node->ptr[i]->b);
  }
  qsort(branch,total,sizeof(struct BranchArray),compare);
  return;
}
void k_NN_NodeSearch(node_type *curr_node, float *query, NN_type *NN, int k)
{

  int i, total;
  double dist;
  ABL       *branch;

  E_page_access_count++;
if(curr_node->snodeSize > 1){

	Num_of_super_node_access++;
}

  /* Please refer NN Queries paper */
  if (curr_node->ptr[0]->attribute == LEAF)
  {
	 //*** Ray changed
	//total = M - curr_node->vacancy;
	  total = M*curr_node->snodeSize - curr_node->vacancy;
	for (i=0;i<total;i++)
	{
		dist = cal_Euclidean(curr_node->ptr[i], query);
		if (dist < NN->dist)
			NN_update(NN, dist, curr_node->ptr[i], k);
	}
  }
  else
  {
	/* Please refer SIGMOD record Sep. 1998 Vol. 27 No. 3 P.18 */
	//**** Ray changed
	//total=M-curr_node->vacancy;
	total = M*curr_node->snodeSize - curr_node->vacancy;
 	branch=(struct BranchArray *)malloc(total*sizeof(struct BranchArray));
 	gen_ABL(curr_node, branch, query, total);
	for (i=0;i<total;i++)
	{
		if (branch[i].min >= NN->dist)
			break;
		else
	                k_NN_NodeSearch(branch[i].node,query,NN,k);
	}
	free(branch);
  }
  return;
}

void k_NN_search(node_type *root, float *query, int k)
{
  int i;

  NN_type *NN, *head;

  if ((NN = (NN_type *)malloc(sizeof(NN_type))) == NULL)
        fprintf(stderr, "malloc error at k-NN_search 1\n");
  NN->oid = UNDEFINED;
  NN->dist = INFINITY;
  NN->pointer = NULL;
  head=NN;

  for (i=0; i<k-1; i++) {

        if ((NN->next = (NN_type *)malloc(sizeof(NN_type))) == NULL)
                fprintf(stderr, "malloc error at k-NN_search 1\n");

        NN->next->oid = UNDEFINED;
        NN->next->dist = INFINITY;

        NN = NN->next;
  }
  NN->next = NULL;

  k_NN_NodeSearch(root, query, head, k);

  NN=head;

  while (NN != NULL) {

        printf("%d %f\n", NN->oid, NN->dist);

        NN = NN->next;

  }

  return;

}
/*
int main()
{
	node_type *root;
	config_type config;

	initialize(&config);

	read_xtree(&root);

	return 0;
}
*/
//#ifdef RAYMOND
int main()
{
  node_type *root;
  config_type config;
  int no_query;
  float **query;
  float error;

  int i, choice, nn;
  char E_result_filename[FILENAME_MAX], dummy[80];

  // for experiment
  static long clktck=0;
  struct tms tmsstart1, tmsend1;
  double user_cputime;
  FILE *E_result_fp;
  double E_represent_accuracy_sum, E_prune_accuracy_sum;
  int E_page_access_count_sum;

  initialize(&config);

  read_xtree(&root);

  no_query = read_query(config.queryfile, &query);

/* added to do the NN search */
  while (1) {

        printf("1. Range Search.  2. NN Search: ");
        scanf("%d", &choice);

        gets(dummy);
        printf("\nPlease input the name of the file to record the result:");
        gets(E_result_filename);

	if (choice==1) {
/* modification ends */

//		  while (1) {

		  	printf("Please input the error bound:");
 		 	scanf("%f", &error);

 		 	     if((clktck=sysconf(_SC_CLK_TCK)) < 0) {
                        fprintf(stderr, "sysconf errors.\n");
                        exit(1);
                }

                if(times(&tmsstart1) == -1) {
                        fprintf(stderr, "times errors.\n");
                        exit(1);
                }
				Num_of_super_node_access = 0;
                E_page_access_count = 0;
                E_page_access_count_sum = 0;
                E_represent_accuracy_sum = 0.0;
                E_prune_accuracy_sum = 0.0;
                E_dist_comp_count = 0;

		  	rectangle_search_tree(root, no_query, query, error);

		  	 if(times(&tmsend1) == -1) {
                        fprintf(stderr, "times errors.\n");
                        exit(1);
                }

                E_result_fp = fopen(E_result_filename, "a");
                fprintf(E_result_fp, "the no. of query point in range query is %d\n", no_query);
                user_cputime=(tmsend1.tms_utime - tmsstart1.tms_utime)/(double)clktck;
                fprintf(E_result_fp, "average cpu time used = %f\n", user_cputime/(double)no_query);
                fprintf(E_result_fp, "average no. of page accesses = %f\n", (double)E_page_access_count/(double)no_query);
                fprintf(E_result_fp, "average no. of super node accesses = %f\n", (double)Num_of_super_node_access /(double)no_query);
                fprintf(E_result_fp, "\n");

                fclose(E_result_fp);


//		  }

	}
/* added to do the NN search */

        else if (choice == 2) {

                printf("Please input the no. of nearest neighbor:");
                scanf("%d", &nn);
                if((clktck=sysconf(_SC_CLK_TCK)) < 0) {
                        fprintf(stderr, "sysconf errors.\n");
                        exit(1);
                }

                if(times(&tmsstart1) == -1) {
                        fprintf(stderr, "times errors.\n");
                        exit(1);
                }

                E_page_access_count_sum = 0;
                E_represent_accuracy_sum = 0.0;
                E_prune_accuracy_sum = 0.0;
                E_dist_comp_count = 0;

                for (i=0; i<no_query; i++) {

                        printf("Query %d\n", i+1);

                        Num_of_super_node_access = 0;
                        E_page_access_count = 0;
                        E_represent_accuracy = 0;
                        E_prune_ans_no = 0;
                        E_overlap_yes = 0;

                        k_NN_search(root, query[i], nn);

                        E_page_access_count_sum = E_page_access_count_sum + E_page_access_count;
                        E_represent_accuracy_sum = E_represent_accuracy_sum + ((double)E_represent_accuracy)/((double)E_page_access_count);
                        E_prune_accuracy_sum = E_prune_accuracy_sum + ((double)E_overlap_yes)/((double)E_prune_ans_no);


                        printf("---------------------------\n");

                }


                // for experiment
                if(times(&tmsend1) == -1) {
                        fprintf(stderr, "times errors.\n");
                        exit(1);
                }

                E_result_fp = fopen(E_result_filename, "a");
                fprintf(E_result_fp, "the no. of nearest neighbor is %d\n", no_query);
                user_cputime=(tmsend1.tms_utime - tmsstart1.tms_utime)/(double)clktck;
                fprintf(E_result_fp, "average cpu time used = %f\n", user_cputime/(double)no_query);
                fprintf(E_result_fp, "average no. of page accesses = %f\n", (double)E_page_access_count_sum/(double)no_query);
                fprintf(E_result_fp, "average no. of super node accesses = %f\n", (double)Num_of_super_node_access /(double)no_query);
                fprintf(E_result_fp, "\n");

                fclose(E_result_fp);

                }  // end k
	} // end while (1)

	return(0);
}
//#endif