hnsrtreefileobj.cpp

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

    else
	HnAbort("unexpected block type.");

    return sum;
}

void
HnSRTreeFileObj::describeExclusion(long offset, const HnPoint &center)
{
    HnSRTreeBlock block = readBlock(offset);

    if ( block.isNode() ) {
	HnSRTreeNode node = new_HnSRTreeNode(info, block);
	int i;

	for ( i=0; i<node.getCount(); i++ ) {
	    HnSRTreeCluster cluster = node.getClusterAt(i);
	    double sphereMaxDistance, rectMaxDistance;

	    sphereMaxDistance =
		cluster.getSphere().getUpperBoundMaxDistance(center);
	    rectMaxDistance =
		cluster.getRect().getUpperBoundMaxDistance(center);
			
	    printf("    %2d: cluster = %s, "
		   "sphereMaxDistance = %g, rectMaxDistance = %g\n",
		   i, (char *)cluster.toString(),
		   sphereMaxDistance, rectMaxDistance);
	}
    }
    else if ( block.isLeaf() ) {
	HnSRTreeLeaf leaf = new_HnSRTreeLeaf(info, block);
	int i;

	for ( i=0; i<leaf.getCount(); i++ ) {
	    HnPoint point = leaf.getPointAt(i);
	    double distance = point.getDistance(center);

	    printf("    %2d: point = %s, distance = %g\n",
		   i, (char *)point.toString(), distance);
	}
    }
    else
	HnAbort("unexpected block type.");
}

/*
 * Print
 */

void
HnSRTreeFileObj::print(HnBool verbose)
{
    int blockSize = info.getBlockSize();
    long offset, size;
    double entryUtilization;
    double blockUtilization;
    int numNodes, numLeaves, numLeafEntries, numFreeBlocks;

    HnStatistics rootEntryUtilization;
    HnStatistics nodeEntryUtilization, leafEntryUtilization;
    HnStatistics totalBlockUtilization, rootBlockUtilization;
    HnStatistics nodeBlockUtilization, leafBlockUtilization;
    HnStatistics nodeSphereRadius, nodeSphereVolume;
    HnStatistics nodeRectDiagonal, nodeRectVolume;
    HnStatistics leafSphereRadius, leafSphereVolume;
    HnStatistics leafRectDiagonal, leafRectVolume;

    rootEntryUtilization = new_HnStatistics();
    nodeEntryUtilization = new_HnStatistics();
    leafEntryUtilization = new_HnStatistics();

    totalBlockUtilization = new_HnStatistics();
    rootBlockUtilization = new_HnStatistics();
    nodeBlockUtilization = new_HnStatistics();
    leafBlockUtilization = new_HnStatistics();

    nodeSphereRadius = new_HnStatistics();
    nodeSphereVolume = new_HnStatistics();

    nodeRectDiagonal = new_HnStatistics();
    nodeRectVolume = new_HnStatistics();

    leafSphereRadius = new_HnStatistics();
    leafSphereVolume = new_HnStatistics();

    leafRectDiagonal = new_HnStatistics();
    leafRectVolume = new_HnStatistics();

    readSuperBlock();

    size = blockFile.getFileSize();

    numNodes = 0;
    numLeaves = 0;
    numLeafEntries = 0;
    numFreeBlocks = 0;

    for ( offset = blockSize; offset < size; offset += blockSize ) {
	HnSRTreeBlock block = readBlock(offset);

	if ( block.isNode()) {
	    HnSRTreeNode node = new_HnSRTreeNode(info, block);

	    if ( verbose ) {
		printNode(node);
	    }

	    entryUtilization =
		(double)node.getCount() / HnSRTreeNode::getMaxCount(info);
	    blockUtilization =
		(double)node.getContentSize() / info.getBlockSize();

	    if ( offset == info.getRootOffset() ) {
		rootEntryUtilization.addSample(entryUtilization);
		rootBlockUtilization.addSample(blockUtilization);
		totalBlockUtilization.addSample(blockUtilization);
	    }
	    else {
		nodeEntryUtilization.addSample(entryUtilization);
		nodeBlockUtilization.addSample(blockUtilization);
		totalBlockUtilization.addSample(blockUtilization);
	    }

	    numNodes ++;
	}
	else if ( block.isLeaf() ) {
	    HnSRTreeLeaf leaf = new_HnSRTreeLeaf(info, block);

	    if ( verbose ) {
		printLeaf(leaf);
	    }

	    entryUtilization =
		(double)leaf.getCount() / HnSRTreeLeaf::getMaxCount(info);
	    blockUtilization =
		(double)leaf.getContentSize() / info.getBlockSize();

	    leafEntryUtilization.addSample(entryUtilization);
	    leafBlockUtilization.addSample(blockUtilization);
	    totalBlockUtilization.addSample(blockUtilization);

	    numLeaves ++;
	    numLeafEntries += leaf.getCount();
	}
	else if ( block.isFree() ) {
	    numFreeBlocks ++;
	}
	else {
	    HnAbort("unexpected block type.");
	}
    }

    measureClusters(info.getRootOffset(), 0,
		    nodeSphereRadius, nodeSphereVolume,
		    nodeRectDiagonal, nodeRectVolume,
		    leafSphereRadius, leafSphereVolume,
		    leafRectDiagonal, leafRectVolume);

    printf("SuperBlock\n");
    printf("    magic               : %c%c%c%c\n",
	   (HnSRTreeMagic >> 24) & 0xff, (HnSRTreeMagic >> 16) & 0xff,
	   (HnSRTreeMagic >>  8) & 0xff, (HnSRTreeMagic      ) & 0xff);
    printf("    dimension           : %d\n", info.getDimension());
    printf("    dataItemSize        : %d\n", info.getDataItemSize());
    printf("    fileSize            : %ld\n", info.getFileSize());
    printf("    freeOffset          : 0x%08X\n",
	   (unsigned int)info.getFreeOffset());
    printf("    rootOffset          : 0x%08X\n",
	   (unsigned int)info.getRootOffset());
    printf("    height              : %d\n", info.getHeight());
    printf("    blockSize           : %d\n", info.getBlockSize());
    printf("    splitFactor         : %d\n", info.getSplitFactor());
    printf("    reinsertFactor      : %d\n", info.getReinsertFactor());
    printf("    staticAlgorithm     : %s\n",
	   (char *)staticAlgorithmToString(info.getStaticAlgorithm()));
    printf("    nonLeafFloatType    : %s\n",
	   (char *)nonLeafFloatTypeToString(info.getNonLeafFloatType()));

    printf("Node maxCount           : %d\n", HnSRTreeNode::getMaxCount(info));
    printf("Leaf maxCount           : %d\n", HnSRTreeLeaf::getMaxCount(info));
    printf("File Size is 0x%08X\n", (unsigned int)size);

    printf("Root entry utilization  : "
	   "    %8.5f %%\n",
	   rootEntryUtilization.getAvg() * 100);

    printf("Node entry utilization  : "
	   "avg %8.5f %%, min %8.5f %%, max %8.5f %%\n",
	   nodeEntryUtilization.getAvg() * 100,
	   nodeEntryUtilization.getMin() * 100,
	   nodeEntryUtilization.getMax() * 100);

    printf("Leaf entry utilization  : "
	   "avg %8.5f %%, min %8.5f %%, max %8.5f %%\n",
	   leafEntryUtilization.getAvg() * 100,
	   leafEntryUtilization.getMin() * 100,
	   leafEntryUtilization.getMax() * 100);

    printf("Root block utilization  : "
	   "    %8.5f %%\n",
	   rootBlockUtilization.getAvg() * 100);
    printf("Node block utilization  : "
	   "avg %8.5f %%, min %8.5f %%, max %8.5f %%\n",
	   nodeBlockUtilization.getAvg() * 100,
	   nodeBlockUtilization.getMin() * 100,
	   nodeBlockUtilization.getMax() * 100);
    printf("Leaf block utilization  : "
	   "avg %8.5f %%, min %8.5f %%, max %8.5f %%\n",
	   leafBlockUtilization.getAvg() * 100,
	   leafBlockUtilization.getMin() * 100,
	   leafBlockUtilization.getMax() * 100);
    printf("Total block utilization : "
	   "avg %8.5f %%, min %8.5f %%, max %8.5f %%\n",
	   totalBlockUtilization.getAvg() * 100,
	   totalBlockUtilization.getMin() * 100,
	   totalBlockUtilization.getMax() * 100);

    printf("Number of nodes : %d\n", numNodes);
    printf("Number of leaves: %d\n", numLeaves);
    printf("Number of free blocks: %d\n", numFreeBlocks);
    printf("Number of leaf entries: %d\n", numLeafEntries);

    printf("Node sphere radius: avg %13.6g, min %13.6g, max %13.6g\n",
	   nodeSphereRadius.getAvg(),
	   nodeSphereRadius.getMin(),
	   nodeSphereRadius.getMax());
    printf("Node sphere volume: avg %13.6g, min %13.6g, max %13.6g\n",
	   nodeSphereVolume.getAvg(),
	   nodeSphereVolume.getMin(),
	   nodeSphereVolume.getMax());

    printf("Node rect diagonal: avg %13.6g, min %13.6g, max %13.6g\n",
	   nodeRectDiagonal.getAvg(),
	   nodeRectDiagonal.getMin(),
	   nodeRectDiagonal.getMax());
    printf("Node rect volume  : avg %13.6g, min %13.6g, max %13.6g\n",
	   nodeRectVolume.getAvg(),
	   nodeRectVolume.getMin(),
	   nodeRectVolume.getMax());

    printf("Leaf sphere radius: avg %13.6g, min %13.6g, max %13.6g\n",
	   leafSphereRadius.getAvg(),
	   leafSphereRadius.getMin(),
	   leafSphereRadius.getMax());
    printf("Leaf sphere volume: avg %13.6g, min %13.6g, max %13.6g\n",
	   leafSphereVolume.getAvg(),
	   leafSphereVolume.getMin(),
	   leafSphereVolume.getMax());

    printf("Leaf rect diagonal: avg %13.6g, min %13.6g, max %13.6g\n",
	   leafRectDiagonal.getAvg(),
	   leafRectDiagonal.getMin(),
	   leafRectDiagonal.getMax());
    printf("Leaf rect volume  : avg %13.6g, min %13.6g, max %13.6g\n",
	   leafRectVolume.getAvg(),
	   leafRectVolume.getMin(),
	   leafRectVolume.getMax());
}

void
HnSRTreeFileObj::printNode(const HnSRTreeNode &node)
{
    int i;

    printf("Block (0x%08X)\n", (unsigned int)node.getOffset());
    printf("    type              : NODE\n");
    printf("    entry utilization : %d (%g %%)\n",
	   node.getCount(),
	   (double)node.getCount() / HnSRTreeNode::getMaxCount(info) * 100);
    printf("    block utilization : %d (%g %%)\n",
	   node.getContentSize(),
	   (double)node.getContentSize() / info.getBlockSize() * 100);

    /* children */
    for ( i=0; i<node.getCount(); i++ ) {
	printf("    %5d: cluster = %s, offset = 0x%08X\n",
	       i,
	       (char *)node.getClusterAt(i).toString(),
	       (unsigned int)node.getOffsetAt(i));
    }
}

void
HnSRTreeFileObj::printLeaf(const HnSRTreeLeaf &leaf)
{
    int i;

    printf("Block (0x%08X)\n", (unsigned int)leaf.getOffset());
    printf("    type              : LEAF\n");
    printf("    entry utilization : %d (%g %%)\n",
	   leaf.getCount(),
	   (double)leaf.getCount() / HnSRTreeLeaf::getMaxCount(info) * 100);
    printf("    block utilization : %d (%g %%)\n",
	   leaf.getContentSize(),
	   (double)leaf.getContentSize() / info.getBlockSize() * 100);

    for ( i=0; i<leaf.getCount(); i++ ) {
	printf("    %5d: %s\n", i, (char *)leaf.getPointAt(i).toString());
    }
}

void
HnSRTreeFileObj::measureClusters(long offset, int level,
				 HnStatistics nodeSphereRadius,
				 HnStatistics nodeSphereVolume,
				 HnStatistics nodeRectDiagonal,
				 HnStatistics nodeRectVolume,
				 HnStatistics leafSphereRadius,
				 HnStatistics leafSphereVolume,
				 HnStatistics leafRectDiagonal,
				 HnStatistics leafRectVolume)
{
    HnSRTreeBlock block = readBlock(offset);

    if ( block.isNode() ) {
	HnSRTreeNode node;
	int i;

	if ( level >= info.getHeight() - 1 ) {
	    HnAbort("tree is not balanced.");
	}

	node = new_HnSRTreeNode(info, block);

	for ( i=0; i<node.getCount(); i++ ) {
	    HnSRTreeCluster cluster;
	    HnSphere sphere;
	    HnRect rect;

	    cluster = node.getClusterAt(i);
	    sphere = cluster.getSphere();
	    rect = cluster.getRect();

	    if ( level == info.getHeight() - 2 ) {
		leafSphereRadius.addSample(sphere.getRadius());
		leafSphereVolume.addSample(sphere.getVolume());
		leafRectDiagonal.addSample(rect.getDiagonal());
		leafRectVolume.addSample(rect.getVolume());
	    }
	    else {
		nodeSphereRadius.addSample(sphere.getRadius());
		nodeSphereVolume.addSample(sphere.getVolume());
		nodeRectDiagonal.addSample(rect.getDiagonal());
		nodeRectVolume.addSample(rect.getVolume());
	    }

	    measureClusters(node.getOffsetAt(i), level + 1,
			    nodeSphereRadius, nodeSphereVolume,
			    nodeRectDiagonal, nodeRectVolume,
			    leafSphereRadius, leafSphereVolume,
			    leafRectDiagonal, leafRectVolume);
	}
    }
    else if ( block.isLeaf() ) {
	if ( level != info.getHeight() - 1 ) {
	    HnAbort("tree is not balanced.");
	}
    }
    else {
	HnAbort("unexpected block type.");
    }
}

HnBool
HnSRTreeFileObj::dumpToFile(const char *fileName)
{
    return blockFile.dumpToFile(fileName);
}

HnBool
HnSRTreeFileObj::dumpToFileStream(FILE *fp)
{
    return blockFile.dumpToFileStream(fp);
}