hnsrtreefileobj1.cpp

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

/*
 * HnSRTreeFileObj1.cc (dynamic construction methods)
 * Copyright (C) 1997 Norio Katayama
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA
 *
 * 03/20/96 [e-mail]
 * $Id: HnSRTreeFileObj1.cc,v 1.5 2002/09/13 03:50:54 katayama Exp $
 */

#include <math.h>
#include <stdio.h>
#ifndef _MSC_VER
#include <unistd.h>
#include <sys/types.h>
#endif
#include "HnSRTree/HnSRTreeFile.hh"
#include "HnSRTree/HnSRTreeFileObj.hh"
#include "HnSRTree/HnStatistics.hh"

/*
 * Store
 */

void
HnSRTreeFileObj::store(const HnPoint &point, const HnDataItem &dataItem)
{
    if ( point.getDimension() != getDimension() ) {
	HnAbort("mismatch in the dimensions (point: %d, file: %d)",
		point.getDimension(), getDimension());
    }
    if ( dataItem.length() > info.getDataItemSize() ) {
	HnAbort("The size of data item (%d) exceeds the limit (%d).",
		dataItem.length(), info.getDataItemSize());
    }

    reinsertList = new_HnSRTreeReinsertVector();
    reinsertedBlocks = new_HnFTlongVector();

    reinsertList.addElement(new_HnSRTreeReinsert(point, dataItem));

    while ( reinsertList.size() != 0 ) {
	if ( reinsertList[0].getType() == HnSRTreeReinsert::POINT ) {
	    HnPoint point = reinsertList[0].getPoint();
	    HnDataItem dataItem = reinsertList[0].getDataItem();

	    reinsertList.removeElementAt(0);
	    insertPoint(point, dataItem);
	}
	else {
	    long offset = reinsertList[0].getOffset();
	    int level = reinsertList[0].getLevel();

	    reinsertList.removeElementAt(0);
	    insertBlock(offset, level);
	}
    }

    if ( debug ) {
	check();
    }
}

void
HnSRTreeFileObj::insertPoint(const HnPoint &point, const HnDataItem &dataItem)
{
    HnSRTreeStack stack;
    HnSRTreeLeaf leaf;

    stack = chooseLeaf(point);

    leaf = stack.getTopLeaf();

    if ( !leaf.isFull() ) {
	leaf.addElement(point, dataItem);
	writeLeaf(leaf);
	updateCluster(stack);
    }
    else {
	int reinsertCount =
	    (leaf.getCount() + 1) * info.getReinsertFactor() / 100;

	if ( stack.getDepth() == 1 ) {
	    /* leaf is the root node */
	    splitLeaf(stack, point, dataItem);
	}
	else if ( reinsertCount <= 0 ) {
	    /* no entry needs to be reinserted */
	    splitLeaf(stack, point, dataItem);
	}
	else {
	    /* reinsert some of entries */
	    int index = -1;

	    if ( (index = reinsertedBlocks.indexOf(leaf.getOffset())) < 0 ) {
		reinsertedBlocks.addElement(leaf.getOffset());
		reinsertLeaf(stack, point, dataItem);
	    }
	    else {
		reinsertedBlocks.removeElementAt(index);
		splitLeaf(stack, point, dataItem);
	    }
	}
    }
}

void
HnSRTreeFileObj::insertBlock(long offset, int level)
{
    HnSRTreeBlock block = readBlock(offset);
    HnSRTreeCluster cluster;
    HnSRTreeStack stack;
    HnSRTreeNode parent;

    if ( block.isNode() ) {
	HnSRTreeNode node = new_HnSRTreeNode(info, block);
	cluster = node.getCluster();
    }
    else if ( block.isLeaf() ) {
	HnSRTreeLeaf leaf = new_HnSRTreeLeaf(info, block);
	cluster = leaf.getCluster();
    }
    else {
	HnAbort("unexpected block type.");
    }

    stack = chooseNode(cluster.getCentroid(), level);

    parent = stack.getTopNode();

    if ( !parent.isFull() ) {
	parent.addElement(cluster, offset);
	writeNode(parent);
	updateCluster(stack);
    }
    else {
	int reinsertCount =
	    (parent.getCount() + 1) * info.getReinsertFactor() / 100;

	if ( stack.getDepth() == 1 ) {
	    /* parent is the root node */
	    splitNode(stack, cluster, offset);
	}
	else if ( reinsertCount <= 0 ) {
	    /* no entry needs to be reinserted */
	    splitNode(stack, cluster, offset);
	}	    
	else {
	    /* reinsert some of entries */
	    int index = -1;

	    if ( (index = reinsertedBlocks.indexOf(parent.getOffset())) < 0 ) {
		reinsertedBlocks.addElement(parent.getOffset());
		reinsertNode(stack, cluster, offset);
	    }
	    else {
		reinsertedBlocks.removeElementAt(index);
		splitNode(stack, cluster, offset);
	    }
	}
    }
}

HnSRTreeStack
HnSRTreeFileObj::chooseLeaf(const HnPoint &point)
{
    HnSRTreeStack stack = new_HnSRTreeStack();
    HnSRTreeBlock block;
    HnSRTreeNode node;
    HnSRTreeLeaf leaf;
    int index;

    /*
     * NOTE:
     *	    The stack is used for keeping the trace of the access path.
     *	    Cursors indicates which entry is used at each node.
     */

    block = readBlock(info.getRootOffset());

    while ( block.isNode() ) {
	node = new_HnSRTreeNode(info, block);
	index = chooseSubtree(node, point);

	stack.push(node, index);
	block = readBlock(node.getOffsetAt(index));
    }

    leaf = new_HnSRTreeLeaf(info, block);
    stack.push(leaf, -1);

    return stack;
}

int
HnSRTreeFileObj::chooseSubtree(const HnSRTreeNode &node, const HnPoint &point)
{
    struct {
	int index;
	double distance;
    } min, cur;

    min.index = -1;
    min.distance = -1;

    for ( cur.index=0; cur.index<node.getCount(); cur.index++ ) {
	HnSRTreeCluster cluster = node.getClusterAt(cur.index);

	cur.distance = point.getDistance(cluster.getCentroid());

	if ( min.index == -1 ) {
	    min = cur;
	}
	else {
	    if ( cur.distance < min.distance ) {
		min = cur;
	    }
	}
    }

    return min.index;
}

HnSRTreeStack
HnSRTreeFileObj::chooseNode(const HnPoint &centroid, int level)
{
    HnSRTreeStack stack = new_HnSRTreeStack();
    HnSRTreeBlock block;
    HnSRTreeNode node;
    int index;

    /*
     * NOTE:
     *	    The stack is used for keeping the trace of the access path.
     *	    Cursors indicates which entry is used at each node.
     */

    block = readBlock(info.getRootOffset());

    while ( stack.getDepth() != info.getHeight() - level ) {
	node = new_HnSRTreeNode(info, block);
	index = chooseSubtree(node, centroid);

	stack.push(node, index);
	block = readBlock(node.getOffsetAt(index));
    }

    return stack;
}

void
HnSRTreeFileObj::updateCluster(HnSRTreeStack stack)
{
    HnSRTreeCluster cluster;
    HnSRTreeNode parent;
    int cursor;

    if ( stack.getDepth() == 0 ) {
	HnAbort("stack is empty.");
    }

    if ( stack.isTopNode() ) {
	HnSRTreeNode node = stack.getTopNode();
	cluster = node.getCluster();
    }
    else {
	HnSRTreeLeaf leaf = stack.getTopLeaf();
	cluster = leaf.getCluster();
    }
    stack.pop();

    while ( stack.getDepth() > 0 ) {
	parent = stack.getTopNode();
	cursor = stack.getCursor();

	parent.setClusterAt(cluster, cursor);

	cluster = parent.getCluster();

	writeNode(parent);
	stack.pop();
    }
}

/*
 * Reinsert
 */

struct HnSRTreeReinsertionEntry {
    int index;
    double distance;
};

static int
HnSRTreeCompareReinsertionEntries(const void *ptr1, const void *ptr2)
{
    HnSRTreeReinsertionEntry *entry1 = (HnSRTreeReinsertionEntry *)ptr1;
    HnSRTreeReinsertionEntry *entry2 = (HnSRTreeReinsertionEntry *)ptr2;

    if ( entry1->distance == entry2->distance ) {
	return 0;
    }
    else {
	/* entries are compared for descending order */
	if ( entry1->distance < entry2->distance ) {
	    return 1;
	}
	else {
	    return -1;
	}
    }
}

/*
 * Reinsert (leaf)
 */

void
HnSRTreeFileObj::reinsertLeaf(HnSRTreeStack &stack,
			      const HnPoint &newPoint,
			      const HnDataItem &newDataItem)
{
    HnSRTreeLeaf leaf, newLeaf;
    HnPointArray points;
    int i;
    ReinsertFlag *flags;

    leaf = stack.getTopLeaf();

    /* put points into an array */
    points = new_HnPointArray(leaf.getCount() + 1);
    for ( i=0; i<leaf.getCount(); i++ ) {
	points[i] = leaf.getPointAt(i);
    }
    points[i] = newPoint;

    selectPoints(points, &flags);

    newLeaf = new_HnSRTreeLeaf(info, leaf.getOffset());

    for ( i=0; i<leaf.getCount(); i++ ) {
	HnPoint point = leaf.getPointAt(i);
	HnDataItem dataItem = leaf.getDataItemAt(i);

	switch ( flags[i] ) {
	case STAY:
	    newLeaf.addElement(point, dataItem);
	    break;
	case REINSERT:
	    reinsertList.addElement(new_HnSRTreeReinsert(point, dataItem));
	    break;
	default:
	    HnAbort("reinsert flag is incorrectly assigned.");
	}
    }
    switch ( flags[i] ) {
    case STAY:
	newLeaf.addElement(newPoint, newDataItem);
	break;
    case REINSERT:
	reinsertList.addElement(new_HnSRTreeReinsert(newPoint, newDataItem));
	break;
    default:
	HnAbort("reinsert flag is incorrectly assigned.");
    }

    writeLeaf(newLeaf);

    /* replace leaf with newLeaf in the stack */
    stack.pop();
    stack.push(newLeaf);

    updateCluster(stack);
}

void
HnSRTreeFileObj::selectPoints(const HnPointArray &points,
			      ReinsertFlag **flags_return)
{
    static ReinsertFlag *flags = NULL;
    int numPoints = points.length;
    int dimension = info.getDimension();
    int reinsertCount = numPoints * info.getReinsertFactor() / 100;
    HnPoint centroid;
    int i, axis;
    HnSRTreeReinsertionEntry *entries;

    /* initialize flags */
    if ( flags != NULL ) {
	delete[] flags;
    }
    flags = new ReinsertFlag[numPoints];

    for ( i=0; i<numPoints; i++ ) {
	flags[i] = REINSERT_NONE;
    }

    /* calculate centroid */
    centroid = new_HnPoint(dimension);

    for ( axis=0; axis<dimension; axis++ ) {
	double sum = 0;

	for ( i=0; i<numPoints; i++ ) {
	    sum += points[i].getCoordAt(axis);
	}

	centroid.setCoordAt(sum / numPoints, axis);
    }

    /* initialize entries */
    entries = (HnSRTreeReinsertionEntry *)
	HnMalloc(sizeof(HnSRTreeReinsertionEntry) * numPoints);

    for ( i=0; i<numPoints; i++ ) {
	entries[i].index = i;
	entries[i].distance = points[i].getDistance(centroid);
    }

    /* sort points by distance in descent order */
    qsort(entries, numPoints, sizeof(HnSRTreeReinsertionEntry),
	  HnSRTreeCompareReinsertionEntries);

    /* make reinsert flags */
    i=0;
    while ( i<reinsertCount ) {
	flags[entries[i].index] = REINSERT;
	i++;
    }
    while ( i<numPoints ) {
	flags[entries[i].index] = STAY;
	i++;
    }

    if ( debug ) {
	fprintf(stderr, "HnSRTreeFileObj::selectPoints:\n");
	fprintf(stderr, "    REINSERT\n");
	for ( i=0; i<numPoints; i++ ) {
	    if ( flags[i] == REINSERT )
		fprintf(stderr,
			"    points[%d].getDistance(centroid) = %g\n",
			i, points[i].getDistance(centroid));
	}
	fprintf(stderr, "    STAY\n");
	for ( i=0; i<numPoints; i++ ) {
	    if ( flags[i] == STAY )
		fprintf(stderr,
			"    points[%d].getDistance(centroid) = %g\n",
			i, points[i].getDistance(centroid));
	}
    }

    *flags_return = flags;

    HnFree(entries, sizeof(HnSRTreeReinsertionEntry) * numPoints);
}

/*
 * Reinsert (node)
 */

void
HnSRTreeFileObj::reinsertNode(HnSRTreeStack &stack,
			      const HnSRTreeCluster &newCluster,
			      long newOffset)
{
    HnSRTreeNode node, newNode;
    HnSRTreeClusterArray clusters;
    int i, level;
    ReinsertFlag *flags;

    node = stack.getTopNode();
    level = info.getHeight() - stack.getDepth();

    /* put clusters into an array */
    clusters = new_HnSRTreeClusterArray(node.getCount() + 1);
    for ( i=0; i<node.getCount(); i++ ) {
	clusters[i] = node.getClusterAt(i);
    }
    clusters[i] = newCluster;

    /* select clusters */
    selectClusters(clusters, &flags);

    newNode = new_HnSRTreeNode(info, node.getOffset());

    for ( i=0; i<node.getCount(); i++ ) {
	HnSRTreeCluster cluster = node.getClusterAt(i);
	long offset = node.getOffsetAt(i);

	switch ( flags[i] ) {
	case STAY:
	    newNode.addElement(cluster, offset);
	    break;
	case REINSERT:
	    reinsertList.addElement(new_HnSRTreeReinsert(offset, level));
	    break;
	default:
	    HnAbort("reinsert flag is incorrectly assigned.");
	}
    }
    switch ( flags[i] ) {
    case STAY:
	newNode.addElement(newCluster, newOffset);
	break;
    case REINSERT:
	reinsertList.addElement(new_HnSRTreeReinsert(newOffset, level));
	break;
    default:
	HnAbort("reinsert flag is incorrectly assigned.");
    }

    writeNode(newNode);

    /* replace node with newNode in the stack */
    stack.pop();
    stack.push(newNode);

    updateCluster(stack);
}

void
HnSRTreeFileObj::selectClusters(const HnSRTreeClusterArray &clusters,
				ReinsertFlag **flags_return)
{
    static ReinsertFlag *flags = NULL;
    int numClusters = clusters.length;
    int dimension = info.getDimension();