rstree_build.c

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

	if (i == 0) {

                axis_chosen = i;
                min_margin_value = new_margin_value;
	}
	else {

		if (new_margin_value < min_margin_value) {

			axis_chosen = i;
			min_margin_value = new_margin_value;
		}

	}	
  }

  tree_node_deallocate(group1);
  tree_node_deallocate(group2);
  free(sorted_index);

  return(axis_chosen);

} /* ChooseSplitAxis */



void ChooseSplitIndex(node_type **overnode, int axis_chosen, node_type 
*group1_chosen, node_type *group2_chosen)
{
  int split_index, *sorted_index;
  node_type *group1, *group2;  
  double new_overlap_value, min_overlap_value;
  double vol_at_index, new_vol;

  int i, j, k, stop, cut;
  
                        
  sorted_index = (int *)malloc(sizeof(int) * M+1);

  tree_node_allocate(&group1);
  tree_node_allocate(&group2);

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


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

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


	cut = m + k; 
	for (j=0; j<M+1; j++) {
  
		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]]);
  
		}

	}

	new_overlap_value = cal_overlap(group1, group2);
 
        
	if (k == 0) {   

		split_index = k;
		min_overlap_value = new_overlap_value;
		vol_at_index = cal_vol(group1->a, group1->b) + cal_vol(group2->a, group2->b);

  	}
	else {   
                
		if (new_overlap_value < min_overlap_value) {

			split_index = k;
			min_overlap_value = new_overlap_value;
			vol_at_index = cal_vol(group1->a, group1->b) + cal_vol(group2->a, group2->b);

		}
		else {

			new_vol = cal_vol(group1->a, group1->b) + cal_vol(group2->a, group2->b);
			if (new_vol < vol_at_index) {
				split_index = k;
			}

		}
  	}

  }

	
  for (i=0; i<dim; i++) {
	group1_chosen->a[i] = overnode[sorted_index[0]]->a[i];
	group1_chosen->b[i] = overnode[sorted_index[0]]->b[i];
	group2_chosen->a[i] = overnode[sorted_index[M]]->a[i];
	group2_chosen->b[i] = overnode[sorted_index[M]]->b[i];
  }


  cut = m + split_index;

  for (j=0; j<M+1; j++) {


	if (j < cut) {
                
		group1_chosen->ptr[j] = overnode[sorted_index[j]];

		overnode[sorted_index[j]]->parent = group1_chosen;
		cal_MBR_node_node(group1_chosen->a, group1_chosen->b, group1_chosen, overnode[sorted_index[j]]);
	}


	else {

		group2_chosen->ptr[j-cut] = overnode[sorted_index[j]];
                overnode[sorted_index[j]]->parent = group2_chosen;
                cal_MBR_node_node(group2_chosen->a, group2_chosen->b, group2_chosen, overnode[sorted_index[j]]);
	}

  }       


  group1_chosen->vacancy = M - cut;
  group2_chosen->vacancy = cut - 1;	// M - (M+1 - cut);

  tree_node_deallocate(group1);
  tree_node_deallocate(group2);
  free(sorted_index);

                       
  return;
        
} /* ChooseSplitIndex() */




void split(node_type *splitting_node, node_type *extra_node, node_type *node1, node_type *node2) 
{
  node_type **overnode;
  int axis_chosen;

  int i;

  overnode = (node_type **)malloc((M+1) * sizeof(node_type *));
  for (i=0; i<M; i++) {
        overnode[i] = splitting_node->ptr[i];
  }

  overnode[M] = extra_node;

  for(i=0; i < M; i++) {
        node1->ptr[i]=NULL;
        node2->ptr[i]=NULL;
  }

  axis_chosen = ChooseSplitAxis(overnode);

  ChooseSplitIndex(overnode, axis_chosen, node1, node2);

  node1->attribute = NODE;
  node1->parent = splitting_node->parent;
  node1->id = NO_ID;

  node2->attribute = NODE;
  node2->parent = splitting_node->parent;
  node2->id = NO_ID;

  free(overnode);

  return;

} /* split() */



void adjust_tree(node_type *splitting_node, int over_level, int old_level, node_type 
*node1, node_type *node2, node_type *root) 
{
  int split_child_no = 0;
  node_type *split_parent;

  int i, j;

  if(splitting_node->attribute == ROOT) { 

	/* The splitting node is the root */

	node1->parent = root;
	node2->parent = root;
	root->ptr[0] = node1;
	root->ptr[1] = node2;
	for (j=2; j<M; j++) 
		root->ptr[j] = NULL;
	root->parent = NULL;
	root->vacancy=M-2;
	root->attribute=ROOT;

	cal_MBR_node_node(root->a, root->b, node1, node2);

	extra_level++;
  }
  else { 

	/* The splitted is an intermediate node */

	split_parent = splitting_node->parent;

        for(i=0; i < M; i++) {
		if(split_parent->ptr[i] == splitting_node) { 
			split_child_no = i;
	             	break;
		}
        }

	tree_node_deallocate(splitting_node);	

	/* insert first node */
	split_parent->ptr[split_child_no] = node1;
	node1->parent = split_parent;

	adjust_MBR_delete(node1);

	/* insert second node */
	
	if(split_parent->vacancy != 0) { 

		/* no need to split again */
           	split_parent->ptr[M - split_parent->vacancy] = node2;

		node2->parent = split_parent;
		split_parent->vacancy--;

//		cal_MBR_node_node(split_parent->a, split_parent->b, node1, split_parent);
		cal_MBR_node_node(split_parent->a, split_parent->b, node2, split_parent);

		adjust_MBR(split_parent);

	}
       	else { 

		/* need to split again */
		overflow(split_parent, over_level-1, old_level, node2, root);

	}

  }



  return;

} /* adjust_tree */



void choose_leaf_level(node_type **node_found, node_type *current_node, int 
current_level, node_type *inserted_node, int desired_level) 
{
 
  int child_chosen;

  if (current_level == desired_level) {
        *node_found = current_node;
//printf("7\n");

        return;
  }
  
//printf("current_level %d desired_level %d\n", current_level, desired_level);

//printf("current_node->ptr[0]->ptr[0] %d\n", current_node->ptr[0]->ptr[0]);
  if (current_node->ptr[0]->ptr[0]->attribute != LEAF) {
  
//printf("8\n");
        child_chosen = least_area_enlarge(current_node, inserted_node);
   
  }
  else {
        
//printf("9\n");
        child_chosen = least_overlap_enlarge(current_node, inserted_node);
  
  }

//printf("5\n");

  current_node = current_node->ptr[child_chosen];
//printf("current_level %d desired_level %d\n", current_level, desired_level);
  choose_leaf_level(node_found, current_node, current_level+1, inserted_node, desired_level);

  
  return;
                        
} /* choose_leaf_level */




void reinsert(node_type *over_node, int over_level, node_type *extra_node, 
node_type *root) 
{
  node_type *node_found;
  node_type **overnode;
  double *value; 
  int *sorted_index;

  int i, start, stop;

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

  overnode = (node_type **)malloc((M+1) * sizeof(node_type *));
  for (i=0; i<M; i++) {
        overnode[i] = over_node->ptr[i];
  }

  overnode[M] = extra_node;
  overnode[M]->parent = over_node;

  for (i=0; i<M+1; i++) {
	value[i] = Dist2(overnode[i], over_node);
	sorted_index[i] = i;
  }

  quicksort(sorted_index, value, 0, M);

  for (i=0; i<dim; i++) {
	over_node->a[i] = overnode[sorted_index[0]]->a[i];
	over_node->b[i] = overnode[sorted_index[0]]->b[i];
  }
  over_node->ptr[0] = overnode[sorted_index[0]];

//printf("1\n");

  stop = M+1-reinsert_p;

  for (i=1; i<stop; i++) {
	over_node->ptr[i] = overnode[sorted_index[i]];
	cal_MBR_node_node(over_node->a, over_node->b, over_node, overnode[sorted_index[i]]);
  }
  for (i=stop; i<M; i++)
	over_node->ptr[i] = NULL;

  over_node->vacancy = reinsert_p - 1;

  adjust_MBR_delete(over_node);

  start = M + 1 - reinsert_p;

  for (i=start; i<M+1; i++) {

	node_found = root;
	
	//choose_leaf_level(&node_found, root, 0, overnode[sorted_index[i]], over_level);
	choose_leaf_level(&node_found, root, 0, overnode[sorted_index[i]], over_level+extra_level);
//printf("2\n");
 
	/* Test whether the node has room or not */
	if(node_found->vacancy!=0) {
 
		/* have room to insert the entry */
//printf("3\n");

		overnode[sorted_index[i]]->parent = node_found;

	        node_found->ptr[M - node_found->vacancy] = overnode[sorted_index[i]];

        	node_found->vacancy--;

	        adjust_MBR(overnode[sorted_index[i]]);
//printf("4\n");
	}
	else {

		overflow(node_found, over_level, over_level, overnode[sorted_index[i]], root);

	}

  }        


  return;
  
} /* reinsert */




void overflow(node_type *over_node, int over_level, int old_level, node_type
*extra_node, node_type *root)
{
  node_type *node1, *node2;

  if (over_level < old_level && over_level != 0) {
	reinsert(over_node, over_level, extra_node, root);

  }
  else {

	tree_node_allocate(&node1);
	tree_node_allocate(&node2);

        split(over_node, extra_node, node1, node2);

        adjust_tree(over_node, over_level, old_level, node1, node2, root);

//printf("overflow, go out adjust, extra_node->id %d\n", extra_node->id);


  }
        
  
  return;
  
}



void insert_node(node_type *root, float *data, int seq_id)
{
  node_type *node_found, *new_node, *data_node;
  int level_found;


  int i;

  /******/
  /* I1 */
  /******/


  node_found = root;
  extra_level=0;

  tree_node_allocate(&data_node);
  for (i=0; i<dim; i++) {
	data_node->a[i] = data[i];
	data_node->b[i] = data[i];
  }
  level_found = choose_leaf(&node_found, root, 0, data_node);
  /* Now, node_found is the pointer to the leaf chosen */


  /******/
  /* I2 */
  /******/
  
  /********************************************************/
  /* Add record to leaaf node:                            */
  /* If L has room for another entry, install the entry   */
  /* Otherwise invoke split() to split the node */
  /********************************************************/  
  
  /* Make a leaf node */

  tree_node_allocate(&new_node);


  for(i=0; i < dim; i++) { 
       	new_node->a[i]=data[i];
       	new_node->b[i]=data[i];
  }
  new_node->id = seq_id;		//data[dim] is the seq_id   
  new_node->attribute=LEAF;
  new_node->vacancy=M;
  new_node->parent=node_found;
  for(i=0; i < M; i++)
     new_node->ptr[i]=NULL;

  /* Test whether the node has room or not */
  if(node_found->vacancy!=0) { 

//printf("insert new->id %d\n", seq_id);

	/* have room to insert the entry */

	node_found->ptr[M - node_found->vacancy] = new_node;

      	node_found->vacancy--;
     
	adjust_MBR(new_node);

  }
  else {

	overflow(node_found, level_found, level_found+1, new_node, root);

  }


  return;

} /* insert_node */
  




/********************/
/* build_tree():    */
/* build the R-tree */
/********************/
      
void build_tree(node_type **root, float **data, int no_data)
{ 
  int i, j;


  /* make tree root node first */

  tree_node_allocate(root);

  for(i=0; i < dim; i++) { 
	(*root)->b[i] = (float)(-1 * INT_MAX);
       	(*root)->a[i] = (float)(INT_MAX);
  }
  (*root)->id = -3;		//NO_ID
  (*root)->attribute=ROOT;
  (*root)->vacancy=M;   
  (*root)->parent=NULL; 
  for(j=0; j < M; j++)
     	(*root)->ptr[j]=NULL;


  /* add data to the tree */
  for(i=0; i<no_data; i++) { 

#ifdef DEBUG
if (i+1%1000==0)
	printf("insert data %d\n", i+1);
#endif

      	insert_node(*root, data[i], i);  // i is the seq id.


	free(data[i]);
  }

  free(data);

} /*build_tree */


int make_data(char *positionfile, float ***data)
{ 
  int no_data;
  int i,j;
  FILE *fp_position;

  fp_position=fopen(positionfile,"r");  

  no_data = no_histogram;

  (*data) = (float **)malloc(sizeof(float*) * no_data);
  for(i=0; i<no_data; i++)
        (*data)[i] = (float *)malloc(sizeof(float) * dim);

  for(i=0; i<no_data; i++)
	for (j=0; j<dim; j++)
		fscanf(fp_position,"%f",&((*data)[i][j]));

  fclose(fp_position);

  return(no_data);

} /* make_data */



void write_leaf_node(node_type *node, FILE *fp)
{
  int i;
                
  for (i = 0; i<dim; i++)
        fprintf(fp, "%f\n", (node->a)[i]);
 
  for (i = 0; i<dim; i++)
        fprintf(fp, "%f\n", (node->b)[i]);
 
  fprintf(fp, "%d\n", node->attribute);
  fprintf(fp, "%d\n", node->id);
  fprintf(fp, "%d\n", node->vacancy);

  return;

}


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

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

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

  fprintf(fp, "%d\n", node->attribute);
  fprintf(fp, "%d\n", node->vacancy);

  count = M - node->vacancy;
  for (i=0; i<count; i++) {
	if (node->ptr[i]->attribute != LEAF)
		write_inter_node(node->ptr[i], fp);
	else
		write_leaf_node(node->ptr[i], fp);
  }

  return;

}
  

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

  //fp = fopen(SAVE_RTREE_FILE, "w");
  fp = fopen(save_tree_file, "w");
  if (!fp) {
	printf("Can't write to %s\n", save_tree_file);
	exit(EXIT_FAILURE);
  }
  
  write_inter_node(root, fp);

  fclose(fp);
 
  return;

}



int main(int argc, char *argv[])
{ 

  int no_data;
  float **data;
  config_type config;
  node_type *root;
  float  userTime, sysTime;
  struct rusage myTime1, myTime2;


  //////////////
  if (argc != 2) {
        printf("Usage: %s <config>\n", argv[0]);
        exit(1);
  }
  //////////////

  printf("initialize\n");
  initialize(&config, argv[1]);   

  printf("make_data\n");
  no_data=make_data(config.positionfile, &data);

  getrusage(RUSAGE_SELF,&myTime1);

  printf("build_tree\n");
  build_tree(&root, data, no_data);

  getrusage(RUSAGE_SELF,&myTime2);

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

  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;
  fprintf(stdout, "User time : %f seconds\n",userTime);
  fprintf(stdout, "System time : %f seconds\n",sysTime);
  fprintf(stdout, "Total time : %f seconds\n",userTime+sysTime);

  return(0);  
} /* main */