rstree_build.c

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

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <sys/resource.h>
#include <sys/times.h>
#include <unistd.h>
#include "rtree.h"

#define DEBUG 1

void overflow(node_type *, int, int, node_type *, node_type *);


/****************************/
/* Start Utility procedures */
/****************************/

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

}


void tree_node_deallocate(node_type *free_node)
{

  free(free_node->a);
  free(free_node->b);
  free(free_node->ptr);

  free(free_node);

}



void cal_MBR_node_node(float *new_a, float *new_b, node_type *node1, node_type *node2)
{
  int i;

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

	if (node1->a[i] < node2->a[i])
		new_a[i] = node1->a[i];
	else
		new_a[i] = node2->a[i];
  }

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

        if (node1->b[i] > node2->b[i])
                new_b[i] = node1->b[i];
        else
                new_b[i] = node2->b[i];
  }

  return;

}


double cal_vol(float *a, float *b)
{
  int i;
  double volume = 1.0;

  for (i=0; i<dim; i++)
	volume = volume * (double)(b[i] - a[i]);


  return(volume);

}


double cal_overlap(node_type *node1, node_type *node2)
{
  double overlap;

  int i;

  overlap = 1.0;
  for (i=0; i<dim; i++) {

	/* 6 possible cases */

	if (node2->a[i] > node1->b[i] || node1->a[i] > node2->b[i]) {

		overlap = 0.0;
		break;

	}
	else if (node2->a[i] <= node1->a[i]) {

		if (node2->b[i] <= node1->b[i]) {

			// a2, a1, b2, b1

			overlap = overlap * (node2->b[i] - node1->a[i]);

		}
		else {

			// a2, a1, b1, b2

			overlap = overlap * (node1->b[i] - node1->a[i]);

		}
	}
	else if (node1->a[i] < node2->a[i]) {

		if (node2->b[i] <= node1->b[i]) {

			// a1, a2, b2, b1

			overlap = overlap * (node2->b[i] - node2->a[i]);

		}
		else {

			// a1, a2, b1, b2

			overlap = overlap * (node1->b[i] - node2->a[i]);

		}

	}

  }


  return(overlap);

}


double cal_overlap_sum(node_type *node, int index_skip,  node_type *parent_node)
{
  double overlap;

  int i, stop;


  overlap = 0.0;
  stop = M - parent_node->vacancy;
  for (i=0; i<stop; i++) {

	if (i == index_skip) continue;

	overlap = overlap + cal_overlap(parent_node->ptr[i], node);

  }


  return(overlap);

}


double Dist2(node_type *node1, node_type *node2)
{
  double distance;
  float *point1, *point2;

  int i;

  point1 = (float *)malloc(sizeof(float) * dim);
  point2 = (float *)malloc(sizeof(float) * dim);

  for (i=0; i<dim; i++) {
	point1[i] = (node1->b[i] - node1->a[i])/2.0;
	point2[i] = (node2->b[i] - node2->a[i])/2.0;
  }

  distance = 0.0;
  for (i=0; i<dim; i++) {
	distance = distance + pow((double)(point1[i] - point2[i]), 2.0);
  }

  return(pow(distance, 0.5));

}


/**************************/
/* End Utility procedures */
/**************************/


int least_overlap_enlarge(node_type *parent_node, node_type  *data_node)
{
  double new_overlap_diff, old_overlap, new_overlap; 
  double vol_at_index, new_vol, min_overlap_diff;
  int index;
  node_type *temp_node;

  int i, stop;
 

  tree_node_allocate(&temp_node);

  stop = M - parent_node->vacancy;
  for(i=0; i<stop; i++) {

        /* original overlap */
   
        old_overlap = cal_overlap_sum(parent_node->ptr[i], i, parent_node);
 
        /* overlap after enlargement */
 
        cal_MBR_node_node(temp_node->a, temp_node->b, parent_node->ptr[i], data_node);
  
        new_overlap = cal_overlap_sum(temp_node, i, parent_node);

        /* check if index is needed to updated */
        new_overlap_diff = new_overlap - old_overlap;

	if (i == 0) {

                index = i;
                min_overlap_diff = new_overlap_diff;   

	}
	else {
        	if (new_overlap_diff < min_overlap_diff) {
                	index = i;
	                min_overlap_diff = new_overlap_diff;
        	}
        	else if (new_overlap_diff == min_overlap_diff) {

			vol_at_index = cal_vol(parent_node->ptr[index]->a, parent_node->ptr[index]->b);
			new_vol = cal_vol(temp_node->a, temp_node->b);
	                if(new_vol < vol_at_index) {

        	                index=i;

	                }
		}
       	}
        
  }  /* end i */

  tree_node_deallocate(temp_node);
        
                
  return (index);
                
}



/********************************************************/
/* least_area_enlarge():                                */
/* Select the node which will cause least bounding      */
/* box enlargement when insert an entry to it           */
/********************************************************/

int least_area_enlarge(node_type *parent_node, node_type *data_node)
{ 
  double new_vol_diff, old_vol, new_vol;
  double vol_at_index, min_vol_diff;
  int index;
  float *temp_a, *temp_b;
  int i, stop;

  temp_a = (float *)malloc(sizeof(float) * dim);
  temp_b = (float *)malloc(sizeof(float) * dim);


  stop = M - parent_node->vacancy;
  for(i=0; i<stop; i++) { 

	/* original volume */

	old_vol = cal_vol(parent_node->ptr[i]->a, parent_node->ptr[i]->b);            	

	/* volume after enlargement */

	cal_MBR_node_node(temp_a, temp_b, parent_node->ptr[i], data_node);

	new_vol = cal_vol(temp_a, temp_b);

	/* check if index is needed to updated */
        new_vol_diff = new_vol - old_vol;

	if (i == 0) {

                index = i;
                min_vol_diff = new_vol_diff;
                vol_at_index = new_vol;

	}
	else {
		if (new_vol_diff < min_vol_diff) { 
			index = i;
           		min_vol_diff = new_vol_diff;
	           	vol_at_index = new_vol;
		}
		else if (new_vol_diff == min_vol_diff) { 
			if(new_vol < vol_at_index) {
              			index=i;
              			vol_at_index = new_vol;
			}
	        }
	}
      
  }  /* end i */

  free(temp_a);
  free(temp_b);
            
  return (index);

} 
/* least_enlarge */




/**********************************************************/
/* choose_leaf():                                         */
/* Select a leaf node in which to place a new index entry */
/* current_level is the level of the current_node	  */
/**********************************************************/

int choose_leaf(node_type **node_found, node_type *current_node, int 
current_level, node_type *data_node) 
{

  int child_chosen, level_found;

  /*******/
  /* CL1 */
  /*******/
  
  /**********************************************************/
  /* Initialise: 			     		    */  
  /* Set N to be the root node(already done in insert_node) */
  /**********************************************************/

  /*  It has been already done in insert()  */

  /*******/
  /* CL2 */
  /*******/

  /**************/
  /* Leaf check */
  /**************/
  
  if(current_node->attribute == ROOT && (current_node->ptr[0]==NULL || current_node->ptr[0]->attribute==LEAF)) { 

	/************************************************************
	*node_found is the root of the tree because the root is 
	the only internal node of the tree at that time.
	*************************************************************/

   	return(current_level);		// root is at level 0				

  }

  if (current_node->ptr[0]->attribute == LEAF) {
        *node_found = current_node;
        return(current_level);
  }

  /*******/
  /* CL3 */
  /*******/

  /******************/
  /* Choose subtree */
  /******************/

  if (current_node->ptr[0]->ptr[0]->attribute != LEAF) {

	child_chosen = least_area_enlarge(current_node, data_node);

  }
  else {

	child_chosen = least_overlap_enlarge(current_node, data_node);

  }

  /*******/
  /* CL4 */
  /*******/
    
  /***********************/
  /* Descend recursively */
  /***********************/

  current_node = current_node->ptr[child_chosen];
  level_found = choose_leaf(node_found, current_node, current_level+1, data_node);


  return(level_found);

} /* choose_leaf */



void adjust_MBR(node_type *node_inserted)
{
  node_type *node = node_inserted;
  int i, flag;

  while(node->attribute != ROOT) {
	      
  	flag = FALSE;
  	for(i=0; i < dim; i++) { 
		if(node->parent->a[i] > node->a[i]) {
			node->parent->a[i] = node->a[i];
			flag = TRUE;
		}
		if(node->parent->b[i] < node->b[i]) {
			node->parent->b[i] = node->b[i];
			flag = TRUE;
		}
  	}

	if (flag == FALSE) break;

	node = node->parent;

  }

  return;

} /* adjust_MBR */



void adjust_MBR_delete(node_type *node_inserted)
{
  node_type *node = node_inserted, *parent;
  int j, stop;

  while(node->attribute != ROOT) {
  
	parent = node->parent;
	stop = M - parent->vacancy;

	for (j=0; j<dim; j++) {
		parent->a[j] = parent->ptr[0]->a[j];
		parent->b[j] = parent->ptr[0]->b[j];
	}
//printf("stop %d\n", stop);
	for (j=1; j<stop; j++) {
		cal_MBR_node_node(parent->a, parent->b, parent, parent->ptr[j]);
	}
  
//printf("3\n");
     //   if (flag == FALSE) break;
 
        node = parent;
        
  }
         
  return;

} /* adjust_MBR_delete */     



void swap(int *sorted_index, double *value, int i, int j)
{ 
  int temp_index;
  double temp_value; 

  temp_value = value[i];  
  value[i] = value[j];
  value[j] = temp_value;
  
  temp_index = sorted_index[i];
  sorted_index[i] = sorted_index[j];
  sorted_index[j] = temp_index;
                
  return;
   
}



int partition(int *sorted_index, double *value, int start_index, int end_index)
{
  double pivot_value;  
  int i, j;
        
  pivot_value = value[start_index];
        
  i = start_index - 1;
  j = end_index + 1;
                
  while (1) {
   
        do {    
                j = j - 1;
  
        } while (value[j] > pivot_value);
 
        do {
                i = i + 1;

        } while (value[i] < pivot_value);

        if (i < j)
                swap(sorted_index, value, i, j);
        else
                return(j);
        
  }     
}



/* I think it is sorted in increasing order */

void quicksort(int *sorted_index, double *value, int start_index, int end_index)
{
  int pivot;

  if (start_index < end_index) {

        pivot = partition(sorted_index, value, start_index, end_index);

        quicksort(sorted_index, value, start_index, pivot);

        quicksort(sorted_index, value, pivot+1, end_index);

  }
 
  return;

}



void sort_entries(int *sorted_index, node_type **overnode, int axis_sort)
{
  int i, start, end;
  double *value;

  value = (double *)malloc(sizeof(double) * M+1);


  for (i=0; i<M+1; i++) {
	sorted_index[i] = i;
	value[i] = (double)overnode[i]->a[axis_sort];
  }


  quicksort(sorted_index, value, 0, M);

  i = 0;
  while (i<M) {

	if (value[i] == value[i+1]) {

		start = i;

		while (i < M && value[i] == value[i+1]) {

			value[i] = (double)overnode[sorted_index[i]]->b[axis_sort];
			i ++;

		}

		value[i] = (double)overnode[sorted_index[i]]->b[axis_sort];
		end = i;	



		if ((end - start) > 1) {
			quicksort(sorted_index, value, start, end);
		}
		else {
			if (value[end] < value[start]) {
				swap(sorted_index, value, start, end);
			}
		}
	}


	i++;

  }

  free(value);


  return;

}


int ChooseSplitAxis(node_type **overnode)
{
  int axis_chosen, *sorted_index;
  node_type *group1, *group2;
  double new_margin_value, min_margin_value;


  int i, j, k, l, stop, cut;


  sorted_index = (int *)malloc(sizeof(int) * M+1);
  tree_node_allocate(&group1);
  tree_node_allocate(&group2);


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

	sort_entries(sorted_index, overnode, i);   // sort the entries by axis i


	new_margin_value = 0.0;
	stop = M - 2*m + 1;
	for (k=0; k<stop; k++) {

        	for (l=0; l<dim; l++) {
                	group1->a[l] = overnode[sorted_index[0]]->a[l];
	                group1->b[l] = overnode[sorted_index[0]]->b[l];
        	        group2->a[l] = overnode[sorted_index[M]]->a[l];
                	group2->b[l] = overnode[sorted_index[M]]->b[l];
        	}        


		j = 0;
		cut = m + k;
		while (j < M+1) {

			if (j < cut) {

				cal_MBR_node_node(group1->a, group1->b, group1, overnode[sorted_index[j]]);

			}
			else {

				cal_MBR_node_node(group2->a, group2->b, group2, overnode[sorted_index[j]]);

			}

			j++;

		}

		for (l=0; l<dim; l++) {

			new_margin_value = new_margin_value + group1->b[l] - group1->a[l];
			new_margin_value = new_margin_value + group2->b[l] - group2->a[l];

		}
	}