srtree_search.c

基于内容的多媒体数据检索算法SR-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 "srtree.h"

//#define DEBUG
//#define DEBUG_MM

#define _EPSILON  1e-10

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->datafile, FILENAME_MAX, fp);
  string_len = strlen(config->datafile);
  config->datafile[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.srtree", config->datafile);
}
/* initialize */


void tree_leaf_node_allocate(node_type **node)
{

  (*node) = (node_type *)malloc(sizeof(node_type));
  if (!*node) {
        printf("Out of memory\n");
        exit(EXIT_FAILURE);
  }

  (*node)->a = (double *)malloc(sizeof(double) * dim);
  (*node)->b = (double *)malloc(sizeof(double) * dim);

  if (!(*node)->a || !(*node)->b) {
        printf("Out of memory\n");
        exit(EXIT_FAILURE);
  }

} /* tree_leaf_node_allocate */


void tree_node_allocate(node_type **node)
{

  (*node) = (node_type *)malloc(sizeof(node_type));
  if (!*node) {
        printf("Out of memory\n");
        exit(EXIT_FAILURE);
  }

  (*node)->a = (double *)malloc(sizeof(double) * dim);
  (*node)->b = (double *)malloc(sizeof(double) * dim);
  (*node)->ptr = (node_type **)malloc(sizeof(node_type *) * M);

  if (!(*node)->a || !(*node)->b  || !(*node)->ptr) {
        printf("Out of memory\n");
        exit(EXIT_FAILURE);
  }

  (*node)->centroid = (double *)malloc(sizeof(double) * dim);

 if (!(*node)->centroid) {
        printf("Out of memory\n");
        exit(EXIT_FAILURE);
  }
}

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

  int i,j;

  //no_query=100;

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

  (*query) = (double **)malloc(no_query * sizeof(double *));
  for (i=0; i<no_query; i++)
  	(*query)[i] = (double *)malloc(dim * sizeof(double));

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

  return(no_query);

} /* read_query */


/* Distance Computation */
double MINDIST(double *P, double *a, double *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, double *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, double *query, double 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, double **query, double 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, "%lf\n", &((node->a)[i]));
  
  for (i = 0; i<dim; i++)
        fscanf(fp, "%lf\n", &((node->b)[i]));

  fscanf(fp, "%d\n", &(node->attribute));

  if (node->attribute != LEAF)
  	for (i = 0; i<dim; i++)
        	fscanf(fp, "%lf\n", &((node->centroid)[i]));
  else
	memcpy(node->centroid, node->a, sizeof(double) * dim);


  if (node->attribute == LEAF) {
	fscanf(fp, "%d\n", &(node->id));
  }
  fscanf(fp, "%d\n", &(node->vacancy));

  if (node->attribute != LEAF) {
	fscanf(fp, "%lf\n", &(node->radius));
	fscanf(fp, "%d\n", &(node->total_size));
  } else {
	node->radius = 0.0;	// Ling
	node->total_size = 1;
  }

  /****************************************
  printf("press 1\n");
  scanf("%d", &dummy);

  for (i = 0; i<dim; i++)
        printf("%f ", node->a[i]);
  printf("\n");
   
  for (i = 0; i<dim; i++)
        printf("%f ", node->b[i]);
  printf("\n");
  
  printf("attrib[%d]  ", node->attribute);
  if (node->attribute == LEAF) {
        printf("id[%d] ", node->id);
  }
  printf("vacancy[%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_srtree(node_type **root, char save_tree_file[])
{ 
  FILE *fp;
 
  tree_node_allocate(root);

  //fp = fopen(SAVE_SRTREE_FILE, "r");
  fp = fopen(save_tree_file, "r");
  //printf("save_tree: %s\n", save_tree_file);

  if (!fp) {
	printf("Can't open %s\n", save_tree_file);
	exit(EXIT_FAILURE);
  }

  read_inter_node(*root, fp);
  
  fclose(fp);
 
  return;
  
}

void free_tree(node_type *node)
{
  int i;

  if (!node) return;

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

  free(node->centroid);

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

  free(node);

  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);
}

/* Return the distance between the centroid */
double dist_centroid(double *centroid1, double *centroid2)
{
 int i=dim;
 double d,distance=0.0;

 while (i--) {
	d = (*centroid1++) - (*centroid2++);
	distance += d*d;
 }
/*
 for (i=0; i < dim; i++) {
        distance += (centroid1[i] - centroid2[i]) * (centroid1[i] - centroid2[i]);
 }
*/
 return sqrt(distance);
}


void gen_ABL(node_type *node, ABL branch[], double *query, int total)
{
  int i;
  double dist_rectangle;
  double dist_sphere;

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

	dist_rectangle = MINDIST(query, node->ptr[i]->a, node->ptr[i]->b);
	//dist_rectangle = sqrt(dist_rectangle);

	dist_sphere = dist_centroid(query, node->ptr[i]->centroid) - node->ptr[i]->radius;
	if (dist_sphere < 0.0)
	    	dist_sphere = 0.0;
	else
		dist_sphere *= dist_sphere;

       #ifdef DEBUG
        printf("ABL %d: dist_sphere=%f, dist_rectangle=%f, radius=%f\n", 
				i, dist_sphere, dist_rectangle, node->ptr[i]->radius);
       #endif

	if (dist_rectangle > dist_sphere)
	    branch[i].min = dist_rectangle;
	else
	    branch[i].min = dist_sphere;
  }
  qsort(branch,total,sizeof(struct BranchArray),compare);
  return;
}

void k_NN_NodeSearch(node_type *curr_node, double *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++)
	{
               #ifdef DEBUG
                printf("compare with %d\n", curr_node->ptr[i]->id);
               #endif

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

       #ifdef DEBUG_MM
        if (!branch) {
                printf("Out of memory\n");
                exit(EXIT_FAILURE);
        }
       #endif

 	gen_ABL(curr_node, branch, query, total);

       #ifdef DEBUG
        printf("[node=%p]\n", curr_node);
        i = total;
        while (i--)
                printf("branch[%d].min = %f, NN->dist = %f\n", i, branch[i].min,  NN->dist);
       #endif

	for (i=0;i<total;i++)
	{
		if (branch[i].min - _EPSILON >= NN->dist)
			break;
		else
	                k_NN_NodeSearch(branch[i].node,query,NN,k);
	}
	free(branch);
  }
  return;
}

void k_NN_search(node_type *root, double *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;
   
}

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

  // 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]);
	printf("Usage: %s <config> <k> <#query>\n", argv[0]);
	exit(EXIT_FAILURE);
  }

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

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

  printf("read_srtree\n");
  read_srtree(&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("%lf", &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);

	// for experiment

 	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);
                                
  }  // end kNN search 
	
  printf("free_tree\n");
  free_tree(root);

  return(0);
}