hnsrtreefileobj3.cpp

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

	getNext(&point, &dataItem);
    }

    /* sort results */
    HnSRTreeRecordSort::sort(points, dataItems);

    *points_return = points;
    *dataItems_return = dataItems;
}

/*
 * Neighbor Search
 */

void
HnSRTreeFileObj::getNeighbors(const HnPoint &queryPoint, int maxCount,
			      HnPointVector *points_return,
			      HnDataItemVector *dataItems_return)
{
    switch ( info.getNeighborAlgorithm() ) {
    case HnSRTreeInfo::DEPTH_FIRST:
	getNeighborsByDepthFirst(queryPoint, maxCount,
				 points_return, dataItems_return);
	break;
    case HnSRTreeInfo::BREADTH_FIRST:
	getNeighborsByBreadthFirst(queryPoint, maxCount,
				   points_return, dataItems_return);
	break;
    default:
	HnAbort("unexpected value for ``NeighborAlgorithm'': %d.",
		info.getNeighborAlgorithm());
    }
}

double
HnSRTreeFileObj::getMinDistance(const HnPoint &point,
				const HnSRTreeCluster &cluster)
{
    double sphereMinDistance, rectMinDistance, minDistance;

    /*
     * NOTE:
     *
     *    Dec.13,2000 Norio KATAYAMA
     *
     *    Here ``getLowerBoundMinDistance()'' is used for spheres in
     *    order to prevent false drops caused by round-off errors.
     *	  As for rectangles, it is not necessary to use
     *	  ``getLowerBoundMinDistance()'' because the distance obtained
     *	  by ``getMinDistance()'' is guaranteed to be equal to or
     *    less than the distance to the nearest point.
     *
     * Additional Note:
     *
     *    The above comment is satisfied only when the distance to
     *    a point is always measured by ``getDistance()'' and when
     *    bounding rectangles have the same precision with points.
     *    It is better to use ``getLowerBoundMinDistance()'' instead
     *    of ``getMinDistance()''.
     */

    /* sphere distance */
    sphereMinDistance = cluster.getSphere().getLowerBoundMinDistance(point);

    /* rect distance */
    rectMinDistance = cluster.getRect().getLowerBoundMinDistance(point);

    /* compare distances */
    if ( sphereMinDistance == rectMinDistance ) {
	minDistance = sphereMinDistance;
	profile->numEqualDistances ++;
    }
    else if ( sphereMinDistance > rectMinDistance ) {
	minDistance = sphereMinDistance;
	profile->numFartherSpheres ++;
    }
    else {
	minDistance = rectMinDistance;
	profile->numFartherRects ++;
    }

    return minDistance;
}

double
HnSRTreeFileObj::getMaxDistance(const HnPoint &point,
				const HnSRTreeCluster &cluster)
{
    double sphereMaxDistance, rectMaxDistance, maxDistance;

    /*
     * NOTE:
     *
     *    Dec.13,2000 Norio KATAYAMA
     *
     *    Here ``getUpperBoundMaxDistance()'' is used for spheres in
     *    order to prevent false drops caused by round-off errors.
     *	  As for rectangles, it is not necessary to use
     *	  ``getUpperBoundMaxDistance()'' because the distance obtained
     *	  by ``getMaxDistance()'' is guaranteed to be equal to or
     *    greater than the distance to the farthest point.
     *
     * Additional Note:
     *
     *    The above comment is satisfied only when the distance to
     *    a point is always measured by ``getDistance()'' and when
     *    bounding rectangles have the same precision with points.
     *    It is better to use ``getUpperBoundMaxDistance()'' instead
     *    of ``getMaxDistance()''.
     */

    /* sphere distance */
    sphereMaxDistance = cluster.getSphere().getUpperBoundMaxDistance(point);

    /* rect distance */
    rectMaxDistance = cluster.getRect().getUpperBoundMaxDistance(point);

    /* compare distances */
    if ( sphereMaxDistance < rectMaxDistance ) {
	maxDistance = sphereMaxDistance;
    }
    else {
	maxDistance = rectMaxDistance;
    }

    return maxDistance;
}

class HnSRTreeNeighborSearch: HnBinarySearch {
private:
    HnSRTreeNeighborVector vector;
    HnSRTreeNeighbor key;

private:
    int getNumElements(void) {
	return vector.size();
    }
    int compareToElementAt(int i) {
	return key.compareTo(vector.elementAt(i));
    }

    HnSRTreeNeighborSearch(const HnSRTreeNeighborVector &vector,
			   const HnSRTreeNeighbor &key) {
	this->vector = vector;
	this->key = key;
    }

public:
    static void search(const HnSRTreeNeighborVector &vector,
		       const HnSRTreeNeighbor &key,
		       HnBool *found_return, int *index_return) {
	HnSRTreeNeighborSearch searcher(vector, key);
	searcher.searchElements(found_return, index_return);
    }
};

struct HnSRTreeNodeNeighborEntry {
    int index;
    double minDistance;
    double maxDistance;
};

static int
HnSRTreeCompareNodeNeighborEntries(const void *ptr1, const void *ptr2)
{
    HnSRTreeNodeNeighborEntry *entry1 = (HnSRTreeNodeNeighborEntry *)ptr1;
    HnSRTreeNodeNeighborEntry *entry2 = (HnSRTreeNodeNeighborEntry *)ptr2;

    /* minDistance */
    if ( entry1->minDistance != entry2->minDistance ) {
	if ( entry1->minDistance < entry2->minDistance ) {
	    return -1;
	}
	else {
	    return 1;
	}
    }
    
    /* maxDistance */
    if ( entry1->maxDistance != entry2->maxDistance ) {
	if ( entry1->maxDistance < entry2->maxDistance ) {
	    return -1;
	}
	else {
	    return 1;
	}
    }

    /* index */
    if ( entry1->index != entry2->index ) {
	if ( entry1->index < entry2->index ) {
	    return -1;
	}
	else {
	    return 1;
	}
    }

    return 0;
}

/*
 * Neighbor Search (DepthFirst)
 */

void
HnSRTreeFileObj::getNeighborsByDepthFirst(const HnPoint &queryPoint,
					  int maxCount,
					  HnPointVector *points_return,
					  HnDataItemVector *dataItems_return)
{
    HnSRTreeNeighborVector neighbors;
    HnPointVector points;
    HnDataItemVector dataItems;
    int i;

    if ( queryPoint.getDimension() != getDimension() ) {
	HnAbort("mismatch in the dimensions (queryPoint: %d, file: %d)",
		queryPoint.getDimension(), getDimension());
    }

    if ( maxCount <= 0 ) {
	HnAbort("invalid max count %d.", maxCount);
    }

    neighbors = new_HnSRTreeNeighborVector();

    chooseNeighbors(info.getRootOffset(), queryPoint, maxCount, neighbors);

    /* make output */
    points = new_HnPointVector();
    dataItems = new_HnDataItemVector();

    for ( i=0; i<neighbors.size(); i++ ) {
	points.addElement(neighbors[i].getPoint());
	dataItems.addElement(neighbors[i].getDataItem());
    }

    *points_return = points;
    *dataItems_return = dataItems;
}

void
HnSRTreeFileObj::chooseNeighbors(long offset,
				 const HnPoint &queryPoint, int maxCount,
				 HnSRTreeNeighborVector &neighbors)
{
    HnSRTreeBlock block = readBlock(offset);

    if ( block.isNode() ) {
	chooseNeighborsInNode(block, queryPoint, maxCount, neighbors);
    }
    else if ( block.isLeaf() ) {
	chooseNeighborsInLeaf(block, queryPoint, maxCount, neighbors);
    }
    else {
	HnAbort("unexpected block type.");
    }
}

void
HnSRTreeFileObj::chooseNeighborsInNode(const HnSRTreeBlock &block,
				       const HnPoint &queryPoint, int maxCount,
				       HnSRTreeNeighborVector &neighbors)
{
    HnSRTreeNode node = new_HnSRTreeNode(info, block);
    int numEntries = node.getCount();
    int i;
    HnSRTreeNodeNeighborEntry *entries;
		
    profile->numVisitedNodes ++;
    profile->numComparedNodeEntries += numEntries;

    /* initialize entries */
    entries = (HnSRTreeNodeNeighborEntry *)
	HnMalloc(sizeof(HnSRTreeNodeNeighborEntry) * numEntries);

    for ( i=0; i<numEntries; i++ ) {
	entries[i].index = i;
	entries[i].minDistance =
	    getMinDistance(queryPoint, node.getClusterAt(i));
	entries[i].maxDistance =
	    getMaxDistance(queryPoint, node.getClusterAt(i));
    }

    /* sort entries */
    qsort(entries, numEntries, sizeof(HnSRTreeNodeNeighborEntry),
	  HnSRTreeCompareNodeNeighborEntries);

    if ( debug ) {
	fprintf(stderr, "HnSRTreeFileObj::chooseNeighborsInNode: "
		"sorted rectangles\n");
	for ( i=0; i<numEntries; i++ ) {
	    HnRect rect = node.getClusterAt(entries[i].index).getRect();
	    fprintf(stderr,
		    "	 %2d: cnt = %7.6f, "
		    "min = %7.6f, max = %7.6f, inc = %s\n",
		    i, queryPoint.getDistance(rect.getCenterPoint()),
		    entries[i].minDistance, entries[i].maxDistance,
		    (rect.includes(queryPoint) ? "yes" : "no"));
	}
    }

    for ( i=0; i<numEntries; i++ ) {
	long offset = node.getOffsetAt(entries[i].index);
	double minDistance = entries[i].minDistance;

	if ( neighbors.size() < maxCount ) {
	    /*
	     * If the number of neighbors does not reach the max,
	     * try every children to collect neighbors.
	     */
	    chooseNeighbors(offset, queryPoint, maxCount, neighbors);
	}
	else {
	    HnSRTreeNeighbor &farthest = neighbors.lastElement();
	    double farthestDistance = farthest.getDistance();

	    if ( minDistance <= farthestDistance ) {
		chooseNeighbors(offset, queryPoint, maxCount, neighbors);
	    }
	}
    }

    HnFree(entries, sizeof(HnSRTreeNodeNeighborEntry) * numEntries);
}

void
HnSRTreeFileObj::chooseNeighborsInLeaf(const HnSRTreeBlock &block,
				       const HnPoint &queryPoint, int maxCount,
				       HnSRTreeNeighborVector &neighbors)
{
    HnSRTreeLeaf leaf = new_HnSRTreeLeaf(info, block);
    int numEntries = leaf.getCount();
    int i, count;

    profile->numVisitedLeaves ++;
    profile->numComparedLeafEntries += numEntries;

    /* add points in the leaf */
    for ( i=0; i<numEntries; i++ ) {
	HnPoint &point = leaf.getPointAt(i);
	HnDataItem &dataItem = leaf.getDataItemAt(i);
	double distance;
	HnSRTreeNeighbor newNeighbor;
	HnBool found;
	int index;

	distance = queryPoint.getDistance(point);

	/* skip such a point that is farther than the farthest candidate */
	if ( neighbors.size() >= maxCount &&
	     distance > neighbors.lastElement().getDistance() ) {
	    continue;
	}

	newNeighbor = new_HnSRTreeNeighbor(point, dataItem, distance);

	HnSRTreeNeighborSearch::search(neighbors, newNeighbor,
				       &found, &index);

	neighbors.insertElementAt(newNeighbor, index);
    }

    /* select closer neighbors up to the max count */
    for ( count = 0; count < neighbors.size(); count ++ ) {
	if ( count >= maxCount ) {
	    /*
	     * NOTE:
	     *	    Even if the count is greater than the max,
	     *	    points that have the same distance
	     *	    need to be appended together.
	     */

	    double lastDistance = neighbors[count - 1].getDistance();
	    double nextDistance = neighbors[count    ].getDistance();

	    if ( lastDistance != nextDistance ) {
		break;
	    }
	}
    }
    neighbors.setSize(count);

    if ( debug ) {
	fprintf(stderr, "HnSRTreeFileObj::getNeighborsInLeaf: \n");
	for ( i=0; i<neighbors.size(); i++ ) {
	    fprintf(stderr, "	 neighbors[%d] = %s\n",
		    i, (char *)neighbors[i].toString());
	}
    }
}

/*
 * Neighbor Search (BreadthFirst)
 */

void
HnSRTreeFileObj::getNeighborsByBreadthFirst(const HnPoint &queryPoint,
					    int maxCount,
					    HnPointVector *points_return,
					    HnDataItemVector *dataItems_return)
{
    HnSRTreeNeighborVector neighbors = new_HnSRTreeNeighborVector();
    int numPointsInVector = 0;
    HnSRTreeBlock block;
    HnPointVector points;
    HnDataItemVector dataItems;
    int i;

    if ( queryPoint.getDimension() != info.getDimension() ) {
	HnAbort("mismatch in the dimensions (queryPoint: %d, file: %d)",
		queryPoint.getDimension(), info.getDimension());
    }

    if ( maxCount <= 0 ) {
	HnAbort("invalid max count %d.", maxCount);
    }

    insertNeighbors(neighbors, numPointsInVector, queryPoint, maxCount,
		    info.getRootOffset());

    for ( ;; ) {
	HnBool everyNeighborIsPoint = HnTRUE;
	long offset;
	int index;

	for ( index=0; index<maxCount && index<neighbors.size(); index++ ) {
	    if ( !neighbors.elementAt(index).isPoint() ) {
		everyNeighborIsPoint = HnFALSE;
		break;
	    }