rstree_search.c

基于内容的多媒体数据库检索算法： 用于最近邻搜索的R*-tree算法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <sys/resource.h>
#include <sys/times.h>
#include <unistd.h>
#include "rtree.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;

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

  //fp = fopen(CONFIG_FILE, "r");
  fp = fopen(configFile, "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';

  sprintf(config->save_tree_file, "%s.rstree", config->positionfile);
}
/* 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 *) * M);
}

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

  int i,j;

  //no_query=100;

  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;
  
  /* Search leaf node */
  if(curr_node->attribute == LEAF) { 

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

        return(FOUND);
  
  }

  stop = M - 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));

/****************************************
  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) {
  	count = M - node->vacancy;
  	for (i=0; i<count; i++) {
		tree_node_allocate(&(node->ptr[i]));
                read_inter_node(node->ptr[i], fp);
	}
  }        
  
  return;
 
} 



void read_rtree(node_type **root, char save_tree_file[])
{ 
  FILE *fp;
 

  tree_node_allocate(root);

  //fp = fopen(SAVE_RTREE_FILE, "r");
  fp = fopen(save_tree_file, "r");
  if (!fp) {
	printf("Can't open file %s\n", save_tree_file);
	exit(EXIT_FAILURE);
  }

  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++;

  /* Please refer NN Queries paper */
  if (curr_node->ptr[0]->attribute == LEAF) 
  {
	total = M - 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 */
	total=M-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;

  printf("\n");

  while (NN != NULL) {
  
        printf("ID: %d    Dist: %f\n", NN->oid, NN->dist);
 
        NN = NN->next;

  }
  printf("\n");

  return;
   
}

void free_tree(node_type *node)
{
  int i;

  if (!node) return;

  free(node->a);
  free(node->b);

  for (i=0; i < M-node->vacancy; i++)
        free_tree(node->ptr[i]);

  free(node);

  return;
}


int main(int argc, char *argv[])
{
  node_type *root;
  config_type config;
  int no_query;
  float **query;
  float error;
  
  int i, nn;
  //char E_result_filename[FILENAME_MAX], dummy[80];

  // for experiment
  float  userTime, sysTime;
  struct rusage myTime1, myTime2;
  FILE *E_result_fp;            
  double E_represent_accuracy_sum, E_prune_accuracy_sum;
  int E_page_access_count_sum;

  //////////////
  if (argc != 4) {
	printf("Usage: %s <config> <k> <#query> <result file>\n", argv[0]);
	exit(EXIT_FAILURE);
  }

  //strcpy(E_result_filename, argv[4]);

  //////////////
  initialize(&config, argv[1]);

  printf("read_rtree\n");
  read_rtree(&root, config.save_tree_file);

  printf("read_query\n");
  no_query = read_query(config.queryfile, &query, atoi(argv[3]));

  printf("start searching\n");

  if (CHOICE==RANGE_SEARCH) {

	while (TRUE) {

		printf("Please input the error bound:");
		scanf("%f", &error);
		rectangle_search_tree(root, no_query, query, error);
	
	}
 }

  else if (CHOICE == kNN_SEARCH) {

	nn = atoi(argv[2]);

	E_page_access_count_sum = 0;
	E_represent_accuracy_sum = 0.0; 
	E_prune_accuracy_sum = 0.0;
	E_dist_comp_count = 0;
                         
	getrusage(RUSAGE_SELF,&myTime1);

	for (i=0; i<no_query; i++) {
                        
		printf("Query %d\n", i+1);
		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;
		E_represent_accuracy_sum += ((double)E_represent_accuracy)/((double)E_page_access_count);
		E_prune_accuracy_sum += ((double)E_overlap_yes)/((double)E_prune_ans_no);
                                
 		printf("---------------------------\n");
	}
                                
	getrusage(RUSAGE_SELF,&myTime2);

        userTime =
                ((float) (myTime2.ru_utime.tv_sec  - myTime1.ru_utime.tv_sec)) +
                ((float) (myTime2.ru_utime.tv_usec - myTime1.ru_utime.tv_usec)) * 1e-6;
        sysTime =
                ((float) (myTime2.ru_stime.tv_sec  - myTime1.ru_stime.tv_sec)) +
                ((float) (myTime2.ru_stime.tv_usec - myTime1.ru_stime.tv_usec)) * 1e-6;

                                
        //E_result_fp = fopen(E_result_filename, "w");
        E_result_fp = stdout;

	fprintf(E_result_fp, "Number of query is %d\n", 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, "User time : %f seconds\n",userTime);
        fprintf(E_result_fp, "System time : %f seconds\n",sysTime);
        fprintf(E_result_fp, "Total time : %f seconds\n",userTime+sysTime);
	fprintf(E_result_fp, "\n");
	fclose(E_result_fp);
                                
  }

  printf("free_tree\n");
  free_tree(root);

  return(0);
}