srtree_build.c

srtree算法实现

	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;

}


/* Sort an array in increasing order according to a set of centroid along the axis */
void sort_entries_centroid(int *sorted_index, node_type **overnode, int axis_sort)
{
  double *value;
  int i;

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

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

  } else {

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


  quicksort(sorted_index, value, 0, M);

  free(value);

  return;

} /* sort_entries_centroid */


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;

} /* sort_entries */


/* Choose the split axis by maximizing the variance */
int ChooseSplitAxisByVariance(node_type **overnode)
{
  int axis_chosen;
  double max_variance = -1.0;
  double mean;
  double variance;
  int i, j;

  if (overnode[0]->attribute == LEAF) {
  	for (i=0; i<dim; i++) {

		mean = 0.0;
		for (j=0; j <= M; j++) 
			mean += overnode[j]->a[i];
		mean /= M;

		variance = 0.0;
		for (j=0; j <= M; j++) 
			variance += pow(overnode[j]->a[i] - mean, 2.0);

		if (max_variance < variance)
			axis_chosen = i;
  	}

  } else {

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

		mean = 0.0;
		for (j=0; j <= M; j++) 
			mean += overnode[j]->centroid[i];
		mean /= M;

		variance = 0.0;
		for (j=0; j <= M; j++) 
			variance += pow(overnode[j]->centroid[i] - mean, 2.0);

		if (max_variance < variance)
			axis_chosen = i;
	}
  }

  return(axis_chosen);

} /* ChooseSplitAxisByVariance */


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

		}
	}

	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 */


/* Find the splitting index by minimizing the sum of variances on each side of the split */
void ChooseSplitIndexByVariance(node_type **overnode, int axis_chosen, node_type 
*group1_chosen, node_type *group2_chosen)
{
  int split_index, *sorted_index;
  int i, j, k, stop, cut;
  double mean1;
  double mean2;
  double sum_variance;
  double min_variance = FLT_MAX;
                        

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

  // sort the entries by the centroid along the chosen axis
  sort_entries_centroid(sorted_index, overnode, axis_chosen);   

  stop = M - 2*m + 1;

  if (overnode[0]->attribute == LEAF) {
  	for (k=0; k <= stop; k++) {

		cut = m + k;
		mean1 = 0.0;
		mean2 = 0.0;
		sum_variance = 0.0;

		for (j=0; j < cut; j++)
			mean1 += overnode[sorted_index[j]]->a[axis_chosen];
		for (; j <= M; j++)
			mean2 += overnode[sorted_index[j]]->a[axis_chosen];

		mean1 /= cut;
		mean2 /= M + 1 - cut;

		for (j=0; j < cut; j++) 
			sum_variance += pow(overnode[sorted_index[j]]->a[axis_chosen] - mean1, 2.0);
		for (; j <= M; j++)
			sum_variance += pow(overnode[sorted_index[j]]->a[axis_chosen] - mean2, 2.0);

		if (min_variance > sum_variance) {
			min_variance = sum_variance;
			split_index = cut;	
		}
	}

  } else {

  	for (k=0; k <= stop; k++) {

		cut = m + k;
		mean1 = 0.0;
		mean2 = 0.0;
		sum_variance = 0.0;

		for (j=0; j < cut; j++)
			mean1 += overnode[sorted_index[j]]->centroid[axis_chosen];
		for (; j <= M; j++)
			mean2 += overnode[sorted_index[j]]->centroid[axis_chosen];
	
		mean1 /= cut;
		mean2 /= M + 1 - cut;

		for (j=0; j < cut; j++) 
			sum_variance += pow(overnode[sorted_index[j]]->centroid[axis_chosen] - mean1, 2.0);
		for (; j <= M; j++)
			sum_variance += pow(overnode[sorted_index[j]]->centroid[axis_chosen] - mean2, 2.0);

		if (min_variance > sum_variance) {
			min_variance = sum_variance;
			split_index = cut;	
		}
	}
  }


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

  update_centroid_node(group1_chosen);
  update_radius_node(group1_chosen);
  update_centroid_node(group2_chosen);
  update_radius_node(group2_chosen);

  free(sorted_index);

  return;
        
} /* ChooseSplitIndexByVariance */


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);
  axis_chosen = ChooseSplitAxisByVariance(overnode);

  //ChooseSplitIndex(overnode, axis_chosen, node1, node2);
  ChooseSplitIndexByVariance(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);

	update_centroid_node(root);
	update_radius_node(root);

	extra_level++;
	//printf("grow!!!!!!!!!!!!\n");
  }
  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);

		update_centroid(node2);

	}
       	else { 

		update_centroid(node1);		// Ling

		/* 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;

        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) {
  if (inserted_node->attribute != LEAF) {
  
  	child_chosen = nearest_centroid(current_node, inserted_node->centroid);
        //child_chosen = least_area_enlarge(current_node, inserted_node);
  }
  else {

  	child_chosen = nearest_centroid(current_node, inserted_node->a);
        //child_chosen = least_overlap_enlarge(current_node, inserted_node);
  }


  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 */