hnsrtreefileobj2.cpp

SR-tree is an index structure for high-dimensional nearest neighbor queries

};

void
HnSRTreeFileObj::searchPoint(const HnPointVector &points,
			     int offset, int count,
			     double keyCoord, int axis, int order,
			     HnBool *found_return, int *index_return)
{
    HnSRTreeSearchPoint::search(points, offset, count, keyCoord, axis, order,
				found_return, index_return);
}

/*
 * searchCluster()
 */

class HnSRTreeSearchCluster: public HnBinarySearch {
private:
    HnSRTreeClusterVector clusters;
    int offset;
    int count;
    double keyCoord;
    int axis;
    int order;

private:
    int getNumElements(void) {
	return count;
    }
    int compareToElementAt(int i) {
	double coord =
	    clusters[offset + i].getRect().getRangeAt(axis).getCenter();

	if ( order > 0 ) {
	    if ( keyCoord == coord) {
		return 0;
	    }
	    else if ( keyCoord < coord ) {
		return -1;
	    }
	    else {
		return 1;
	    }
	}
	else {
	    if ( keyCoord == coord ) {
		return 0;
	    }
	    else if ( keyCoord < coord ) {
		return 1;
	    }
	    else {
		return -1;
	    }
	}
    }   

    HnSRTreeSearchCluster(const HnSRTreeClusterVector &clusters,
			  int offset, int count,
			  double keyCoord, int axis, int order) {
	this->clusters = clusters;
	this->offset = offset;
	this->count = count;
	this->keyCoord = keyCoord;
	this->axis = axis;
	this->order = order;
    }

public:
    static void search(const HnSRTreeClusterVector &clusters,
		       int offset, int count,
		       double keyCoord, int axis, int order,
		       HnBool *found_return, int *index_return) {
	HnSRTreeSearchCluster searcher(clusters, offset, count,
				       keyCoord, axis, order);
	searcher.searchElements(found_return, index_return);
    }
};

void
HnSRTreeFileObj::searchCluster(const HnSRTreeClusterVector &clusters,
			       int offset, int count,
			       double keyCoord, int axis, int order,
			       HnBool *found_return, int *index_return)
{
    HnSRTreeSearchCluster::search(clusters, offset, count,
				  keyCoord, axis, order,
				  found_return, index_return);
}

/*
 * selectPoint()
 */

class HnSRTreeSelectPoint: public HnQuickSelect {
private:
    HnPointVector points;
    HnDataItemVector dataItems;
    int offset;
    int count;
    int axis;

private:
    HnSRTreeSelectPoint(HnPointVector &points, HnDataItemVector &dataItems,
			int offset, int count, int axis) {
	this->points = points;
	this->dataItems = dataItems;
	this->offset = offset;
	this->count = count;
	this->axis = axis;
    }
    int getNumElements(void) {
	return count;
    }
    int compareElementsAt(int i, int j) {
	double coord1 = points[offset + i].getCoordAt(axis);
	double coord2 = points[offset + j].getCoordAt(axis);

	if ( coord1 > coord2 ) {
	    return 1;
	}
	else if ( coord1 < coord2 ) {
	    return -1;
	}
	else {
	    return 0;
	}
    }
    void swapElementsAt(int i, int j) {
	points.swapElementsAt(offset + i, offset + j);
	dataItems.swapElementsAt(offset + i, offset + j);
    }

public:
    static void select(HnPointVector &points, HnDataItemVector &dataItems,
		       int offset, int count, int axis, int index) {
	HnSRTreeSelectPoint selecter(points, dataItems,
				     offset, count, axis);
	selecter.selectElement(index);
    }
};

void
HnSRTreeFileObj::selectPoint(HnPointVector &points,
			     HnDataItemVector &dataItems,
			     int offset, int count,
			     int axis, int index)
{
    HnSRTreeSelectPoint::select(points, dataItems, offset, count, axis, index);
}

/*
 * selectCluster()
 */

class HnSRTreeSelectCluster: public HnQuickSelect {
private:
    HnSRTreeClusterVector clusters;
    HnFTlongVector offsets;
    int offset;
    int count;
    int axis;

private:
    HnSRTreeSelectCluster(HnSRTreeClusterVector &clusters,
			  HnFTlongVector &offsets,
			  int offset, int count, int axis) {
	this->clusters = clusters;
	this->offsets = offsets;
	this->offset = offset;
	this->count = count;
	this->axis = axis;
    }
    int getNumElements(void) {
	return count;
    }
    int compareElementsAt(int i, int j) {
	double coord1 =
	    clusters[offset + i].getRect().getRangeAt(axis).getCenter();
	double coord2 =
	    clusters[offset + j].getRect().getRangeAt(axis).getCenter();

	if ( coord1 > coord2 ) {
	    return 1;
	}
	else if ( coord1 < coord2 ) {
	    return -1;
	}
	else {
	    return 0;
	}
    }
    void swapElementsAt(int i, int j) {
	clusters.swapElementsAt(offset + i, offset + j);
	offsets.swapElementsAt(offset + i, offset + j);
    }

public:
    static void select(HnSRTreeClusterVector &clusters,
		       HnFTlongVector &offsets,
		       int offset, int count, int axis, int index) {
	HnSRTreeSelectCluster selecter(clusters, offsets, offset, count, axis);
	selecter.selectElement(index);
    }
};

void
HnSRTreeFileObj::selectCluster(HnSRTreeClusterVector &clusters,
			       HnFTlongVector &offsets,
			       int offset, int count, int axis, int index)
{
    HnSRTreeSelectCluster::select(clusters, offsets,
				  offset, count, axis, index);
}

/*
 * sortPoints()
 */

class HnSRTreeSortPoints: public HnQuickSort {
private:
    HnPointVector points;
    HnDataItemVector dataItems;
    int offset;
    int count;
    int sortDimension;

private:
    HnSRTreeSortPoints(HnPointVector &points, HnDataItemVector &dataItems,
		       int offset, int count, int sortDimension) {
	this->points = points;
	this->dataItems = dataItems;
	this->offset = offset;
	this->count = count;
	this->sortDimension = sortDimension;
    }
    int getNumElements(void) {
	return count;
    }
    int compareElementsAt(int i, int j) {
	double coord1 = points[offset + i].getCoordAt(sortDimension);
	double coord2 = points[offset + j].getCoordAt(sortDimension);

	if ( coord1 > coord2 ) {
	    return 1;
	}
	else if ( coord1 < coord2 ) {
	    return -1;
	}
	else {
	    return 0;
	}
    }
    void swapElementsAt(int i, int j) {
	points.swapElementsAt(offset + i, offset + j);
	dataItems.swapElementsAt(offset + i, offset + j);
    }

public:
    static void sort(HnPointVector &points, HnDataItemVector &dataItems,
		     int offset, int count, int sortDimension) {
	HnSRTreeSortPoints sorter(points, dataItems,
				  offset, count, sortDimension);
	sorter.sortElements();
    }
};

void
HnSRTreeFileObj::sortPoints(HnPointVector &points, HnDataItemVector &dataItems,
			    int offset, int count, int sortDimension)
{
    HnSRTreeSortPoints::sort(points, dataItems,
			     offset, count, sortDimension);
}

/*
 * sortClusters()
 */

class HnSRTreeSortClusters: public HnQuickSort {
private:
    HnSRTreeClusterVector clusters;
    HnFTlongVector offsets;
    int offset;
    int count;
    int sortDimension;

private:
    HnSRTreeSortClusters(HnSRTreeClusterVector &clusters,
			 HnFTlongVector &offsets,
			 int offset, int count, int sortDimension) {
	this->clusters = clusters;
	this->offsets = offsets;
	this->offset = offset;
	this->count = count;
	this->sortDimension = sortDimension;
    }
    int getNumElements(void) {
	return count;
    }
    int compareElementsAt(int i, int j) {
	double coord1 = clusters[offset + i]
	    .getRect().getRangeAt(sortDimension).getCenter();
	double coord2 = clusters[offset + j]
	    .getRect().getRangeAt(sortDimension).getCenter();

	if ( coord1 > coord2 ) {
	    return 1;
	}
	else if ( coord1 < coord2 ) {
	    return -1;
	}
	else {
	    return 0;
	}
    }
    void swapElementsAt(int i, int j) {
	clusters.swapElementsAt(offset + i, offset + j);
	offsets.swapElementsAt(offset + i, offset + j);
    }

public:
    static void sort(HnSRTreeClusterVector &clusters, HnFTlongVector &offsets,
		     int offset, int count, int sortDimension) {
	HnSRTreeSortClusters sorter(clusters, offsets,
				    offset, count, sortDimension);
	sorter.sortElements();
    }
};

void
HnSRTreeFileObj::sortClusters(HnSRTreeClusterVector &clusters,
			      HnFTlongVector &offsets,
			      int offset, int count, int sortDimension)
{
    HnSRTreeSortClusters::sort(clusters, offsets,
			       offset, count, sortDimension);
}

/*
 * getMaxVarianceAxis()
 */

int
HnSRTreeFileObj::getMaxVarianceAxis(HnPointVector &points,
				    int offset, int count)
{
    int dimension = info.getDimension();
    int axis;
    double *sum = new double[dimension];
    double *sum2 = new double[dimension];
    int i;
    struct {
	int axis;
	double var;
    } max;

    for ( axis=0; axis<dimension; axis++ ) {
	sum[axis] = 0;
	sum2[axis] = 0;
    }

    for ( i=offset; i<offset + count; i++ ) {
	for ( axis=0; axis<dimension; axis++ ) {
	    double x = points[i].getCoordAt(axis);

	    sum[axis] += x;
	    sum2[axis] += x * x;
	}
    }

    max.axis = -1;
    max.var = 0;

    for ( axis=0; axis<dimension; axis++ ) {
	double mean = sum[axis] / count;
	double var = sum2[axis] / count - mean * mean;

	if ( axis == 0 ) {
	    max.axis = 0;
	    max.var = var;
	}
	else {
	    if ( var > max.var ) {
		max.axis = axis;
		max.var = var;
	    }
	}
    }

    delete[] sum;
    delete[] sum2;

    return max.axis;
}

int
HnSRTreeFileObj::getMaxVarianceAxis(HnSRTreeClusterVector &clusters,
				    int offset, int count)
{
    int dimension = info.getDimension();
    int axis;
    double *sum = new double[dimension];
    double *sum2 = new double[dimension];
    int totalWeight;
    int i;
    struct {
	int axis;
	double var;
    } max;

    for ( axis=0; axis<dimension; axis++ ) {
	sum[axis] = 0;
	sum2[axis] = 0;
    }
    totalWeight = 0;

    for ( i=offset; i<offset + count; i++ ) {
#if 0
	int weight = clusters[i].getWeight();

	for ( axis=0; axis<dimension; axis++ ) {
	    double coord = clusters[i].getCentroid().getCoordAt(axis);

	    /*
	     * NOTE:
	     *      In the calculation of the variance,
	     *	    it is assumed that all points are located
	     *      at the centroid of the cluster.
	     */

	    sum[axis] += coord * weight;
	    sum2[axis] += coord * coord * weight;
	}

	totalWeight += weight;
#else
	for ( axis=0; axis<dimension; axis++ ) {
	    double coord = clusters[i].getRect().getRangeAt(axis).getCenter();

	    sum[axis] += coord;
	    sum2[axis] += coord * coord;
	}

	totalWeight ++;
#endif
    }

    max.axis = -1;
    max.var = 0;

    for ( axis=0; axis<dimension; axis++ ) {
	double mean = sum[axis] / totalWeight;
	double var = sum2[axis] / totalWeight - mean * mean;

	if ( axis == 0 ) {
	    max.axis = 0;
	    max.var = var;
	}
	else {
	    if ( var > max.var ) {
		max.axis = axis;
		max.var = var;
	    }
	}
    }

    delete[] sum;
    delete[] sum2;

    return max.axis;
}