hnsrtreefileobj3.cpp

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

    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(queryPoints, node.getClusterAt(i));
	entries[i].maxDistance =
	    getMaxDistance(queryPoints, node.getClusterAt(i));
    }

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

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

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

	    if ( minDistance <= farthestDistance ) {
		chooseColoredNeighbors(offset, queryPoints, maxCount,
				       distanceVector, colorVector,
				       compColorsFunc);
	    }
	}
    }

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

void
HnSRTreeFileObj::
chooseColoredNeighborsInLeaf(const HnSRTreeBlock &block,
			     const HnPointVector &queryPoints, int maxCount,
			     HnSRTreeNeighborVector &distanceVector,
			     HnSRTreeNeighborVector &colorVector,
			     HnSRTreeCompColorsFunc *compColorsFunc)
{
    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 colorIndex, distanceIndex;

	distance = getDistance(queryPoints, point);

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

	newNeighbor = new_HnSRTreeNeighbor(point, dataItem, distance);

	searchColorVector(colorVector, newNeighbor, compColorsFunc,
			  &found, &colorIndex);

	if ( found ) {
	    /* a point with the same color already exists. */
	    HnSRTreeNeighbor oldNeighbor = colorVector[colorIndex];

	    /* skip unless the new point is closer than the existing one. */
	    if ( distance > oldNeighbor.getDistance() ||
		 (distance == oldNeighbor.getDistance() &&
		  newNeighbor.compareTo(oldNeighbor) >= 0) ) {
		continue;
	    }

	    searchDistanceVector(distanceVector, oldNeighbor, compColorsFunc,
				 &found, &distanceIndex);
	    if ( !found ) {
		HnAbort("inconsistency between `distanceVector' and "
			"`colorVector'");
	    }
	    distanceVector.removeElementAt(distanceIndex);

	    searchDistanceVector(distanceVector, newNeighbor, compColorsFunc,
				 &found, &distanceIndex);
	    distanceVector.insertElementAt(newNeighbor, distanceIndex);

	    colorVector.setElementAt(newNeighbor, colorIndex);
	}
	else {
	    /* no point has the same color. */
	    searchDistanceVector(distanceVector, newNeighbor, compColorsFunc,
				 &found, &distanceIndex);
	    distanceVector.insertElementAt(newNeighbor, distanceIndex);

	    searchColorVector(colorVector, newNeighbor, compColorsFunc,
			      &found, &colorIndex);
	    colorVector.insertElementAt(newNeighbor, colorIndex);
	}
    }

    /* select closer neighbors up to the max count */
    for ( count = 0; count < distanceVector.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 = distanceVector[count - 1].getDistance();
	    double nextDistance = distanceVector[count	  ].getDistance();

	    if ( lastDistance != nextDistance ) {
		break;
	    }
	}
    }
    /* points must be removed from both `distanceVector' and `colorVector'. */
    for ( i=count; i<distanceVector.size(); i++ ) {
	HnBool found;
	int index;

	searchColorVector(colorVector, distanceVector[i], compColorsFunc,
			  &found, &index);
	if ( !found ) {
	    HnAbort("inconsistency between `distanceVector' and "
		    "`colorVector'");
	}
	colorVector.removeElementAt(index);
    }
    /* set the size of ``distanceVector'' */
    distanceVector.setSize(count);

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

/*
 * Colored Neighbor Search (BreadthFirst)
 */

void
HnSRTreeFileObj::
getColoredNeighborsByBreadthFirst(const HnPointVector &queryPoints,
				  int maxCount,
				  HnPointVector *points_return,
				  HnDataItemVector *dataItems_return,
				  HnSRTreeCompColorsFunc *compColorsFunc)
{
    HnSRTreeNeighborVector distanceVector, colorVector;
    int numPointsInVector;
    HnSRTreeBlock block;
    HnPointVector points;
    HnDataItemVector dataItems;
    int i;

    if ( compColorsFunc == NULL ) {
	compColorsFunc = defaultCompColorsFunc;
    }

    if ( queryPoints.size() == 0 ) {
	HnAbort("no query point is given.");
    }

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

    distanceVector = new_HnSRTreeNeighborVector();
    colorVector = new_HnSRTreeNeighborVector();
    numPointsInVector = 0;

    insertColoredNeighbors(distanceVector, colorVector, numPointsInVector,
			   queryPoints, maxCount,
			   info.getRootOffset(), compColorsFunc);

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

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

	offset = distanceVector.elementAt(index).getOffset();
	distanceVector.removeElementAt(index);
	insertColoredNeighbors(distanceVector, colorVector, numPointsInVector,
			       queryPoints, maxCount, offset, compColorsFunc);

	/*
	 * Discard useless neighbors.
	 * It is unnecessary to keep points more than the max count.
	 */
	numPointsInVector = 0;
	for ( index=0; index<distanceVector.size(); index++ ) {
	    if ( numPointsInVector >= maxCount ) {
		/*
		 * NOTE:
		 *	Even if the number of points is greater than
		 *	the max, neighbors that have the same distance
		 *	need to be appended together.
		 */
		double lastDistance = distanceVector[index-1].getDistance();
		double nextDistance = distanceVector[index  ].getDistance();

		if ( lastDistance != nextDistance ) {
		    break;
		}
	    }
	    if ( distanceVector.elementAt(index).isPoint() ) {
		numPointsInVector ++;
	    }
	}
	/*
	 * points must be removed from both `distanceVector' and
	 * `colorVector'.
	 */
	for ( i=index; i<distanceVector.size(); i++ ) {
	    if ( distanceVector[i].isPoint() ) {
		HnBool found;
		int colorIndex;

		searchColorVector(colorVector, distanceVector[i],
				  compColorsFunc,
				  &found, &colorIndex);
		if ( !found ) {
		    HnAbort("inconsistency between `distanceVector' and "
			    "`colorVector'");
		}
		colorVector.removeElementAt(colorIndex);
	    }
	}
	/* set the size of ``distanceVector'' */
	distanceVector.setSize(index);
    }

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

    for ( i=0; i<maxCount && i<distanceVector.size(); i++ ) {
	points.addElement(distanceVector.elementAt(i).getPoint());
	dataItems.addElement(distanceVector.elementAt(i).getDataItem());
    }

    while ( i<distanceVector.size() &&
	    distanceVector.elementAt(i).isPoint() &&
	    distanceVector.elementAt(i).getDistance() ==
	    distanceVector.elementAt(i-1).getDistance() ) {
	points.addElement(distanceVector.elementAt(i).getPoint());
	dataItems.addElement(distanceVector.elementAt(i).getDataItem());
	i ++;
    }

    *points_return = points;
    *dataItems_return = dataItems;
}

void
HnSRTreeFileObj::insertColoredNeighbors(HnSRTreeNeighborVector &distanceVector,
					HnSRTreeNeighborVector &colorVector,
					int &numPointsInVector,
					const HnPointVector &queryPoints,
					int maxCount,
					long offset,
					HnSRTreeCompColorsFunc *compColorsFunc)
{
    HnSRTreeBlock block = readBlock(offset);
    int i;

    if ( block.isLeaf() ) {
	HnSRTreeLeaf leaf = new_HnSRTreeLeaf(info, block);
	int numEntries = leaf.getCount();

	for ( i=0; i<numEntries; i++ ) {
	    HnPoint &point = leaf.getPointAt(i);
	    HnDataItem &dataItem = leaf.getDataItemAt(i);
	    double distance;
	    HnSRTreeNeighbor newNeighbor;

	    distance = getDistance(queryPoints, point);

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

	    newNeighbor = new_HnSRTreeNeighbor(point, dataItem, distance);

	    insertColoredNeighbor(distanceVector, colorVector,
				  numPointsInVector,
				  newNeighbor, compColorsFunc);
	}

	profile->numVisitedLeaves ++;
	profile->numComparedLeafEntries += numEntries;
    }
    else {
	HnSRTreeNode node = new_HnSRTreeNode(info, block);
	int numEntries = node.getCount();

	for ( i=0; i<numEntries; i++ ) {
	    double distance;
	    HnSRTreeNeighbor newNeighbor;

	    distance = getMinDistance(queryPoints, node.getClusterAt(i));

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

	    newNeighbor = new_HnSRTreeNeighbor(node.getOffsetAt(i), distance);

	    insertColoredNeighbor(distanceVector, colorVector,
				  numPointsInVector,
				  newNeighbor, compColorsFunc);
	}

	profile->numVisitedNodes ++;
	profile->numComparedNodeEntries += numEntries;
    }
}

void
HnSRTreeFileObj::insertColoredNeighbor(HnSRTreeNeighborVector &distanceVector,
				       HnSRTreeNeighborVector &colorVector,
				       int &numPointsInVector,
				       const HnSRTreeNeighbor &newNeighbor,
				       HnSRTreeCompColorsFunc *compColorsFunc)
{
    if ( newNeighbor.isPoint() ) {
	/* new neighbor is a point */
	HnBool found;
	int colorIndex, distanceIndex;

	searchColorVector(colorVector, newNeighbor, compColorsFunc,
			  &found, &colorIndex);

	if ( found ) {
	    /* a point with the same color already exists. */
	    HnSRTreeNeighbor oldNeighbor = colorVector[colorIndex];

	    /* skip unless the new point is closer than the existing one. */
	    if ( newNeighbor.getDistance() > oldNeighbor.getDistance() ||
		 (newNeighbor.getDistance() == oldNeighbor.getDistance() &&
		  newNeighbor.compareTo(oldNeighbor) >= 0) ) {
		return;
	    }

	    searchDistanceVector(distanceVector, oldNeighbor, compColorsFunc,
				 &found, &distanceIndex);
	    if ( !found ) {
		HnAbort("inconsistency between `distanceVector' and "
			"`colorVector'");
	    }
	    distanceVector.removeElementAt(distanceIndex);

	    searchDistanceVector(distanceVector, newNeighbor, compColorsFunc,
				 &found, &distanceIndex);
	    distanceVector.insertElementAt(newNeighbor, distanceIndex);

	    colorVector.setElementAt(newNeighbor, colorIndex);
	}
	else {
	    /* no point has the same color. */
	    searchDistanceVector(distanceVector, newNeighbor, compColorsFunc,
				 &found, &distanceIndex);
	    distanceVector.insertElementAt(newNeighbor, distanceIndex);

	    searchColorVector(colorVector, newNeighbor, compColorsFunc,
			      &found, &colorIndex);
	    colorVector.insertElementAt(newNeighbor, colorIndex);

	    numPointsInVector ++;
	}
    }
    else {
	/* new neighbor is not a point */
	HnBool found;
	int index;

	searchDistanceVector(distanceVector, newNeighbor, compColorsFunc,
			     &found, &index);

	distanceVector.insertElementAt(newNeighbor, index);
    }
}