gist_rstartree.cc

Libgist is an implementation of the Generalized Search Tree, a template index structure that makes i

// gist_rstartree.cc						-*- c++ -*-
// Copyright (c) 1998, Regents of the University of California
// $Id: gist_rstartree.cc,v 1.19 2000/03/15 00:24:51 mashah Exp $

#ifdef __GNUG__
#pragma implementation "gist_rstartree.h"
#endif

#include <stdlib.h>

#include "gist_compat.h"	// for MAXDOUBLE
#include "gist_rtpred_point.h"
#include "gist_rstartree.h"
#include "gist_support.h" // for print<>, parse<>, etc.


// VCPORT_B
// # of entries involved in overlap computation during findMinPen
const int rstar_ext_t::MINPENENTRIES = 16;

// minimum page utilization after split (according to R*-tree paper)
const float rstar_ext_t::MINSPLITUTIL = 0.4;
// VCPORT_E

/////////////////////////////////////////////////////////////////////////
// rstar_ext_t::minPenAuxCmp - qsort comparison fct for MinPenAux
//
// Description:
//	- comparison of the penalty component in MinPenAux to sort
//	  in ascending order
//
// Return Values:
//      -1, 0, 1
/////////////////////////////////////////////////////////////////////////

int
rstar_ext_t::minPenAuxCmp(const void* a, const void* b)
{
    MinPenAux* e1 = (MinPenAux *) a;
    MinPenAux* e2 = (MinPenAux *) b;

    if (e1->p < e2->p) {
        return -1;
    } else if (e2->p < e1->p) {
        return 1;
    } else {
        return 0;
    }
}


/////////////////////////////////////////////////////////////////////////
// rstar_ext_t::findMinPen - min. penalty computation
//
// Description:
// 	- level > 2: entry with min. area enlargement (min. area for ties)
// 	- level = 2: entry with min overlap enlargement
// 	  (enlargement of overlap with other nodes on that page),
//	  min area enlargement for ties. Since the latter is O(n^2), we approximate
//	  it by only computing the overlap for the best 32 entries (best in terms of
//	  area enlargement)
//
/////////////////////////////////////////////////////////////////////////

void
rstar_ext_t::findMinPen(
    const gist_p& page,
    const vec_t& newKey,
    const vec_t& data,
    int& slot)
{
    int count = page.nrecs();

    // loop through all the entries and compute the area enlargements
    for (int i = 0; i < count; i++) {
	const keyrec_t &tup = page.rec(i);
	ext.penalty((void *) tup.key(), tup.klen(), page.level(), newKey.ptr(0),
	    newKey.len(0), temps.penalties[i].p);
	temps.penalties[i].slot = i;
    }

    // sort area enlargements
    qsort(temps.penalties, count, sizeof(MinPenAux), minPenAuxCmp);

    if (page.level() > 2) {
        // pick item with min. area enlargement, min. area
	gist_penalty_t minPenalty(gist_penalty_t::max_penalty);
	double minArea = 0.0;
	slot = -1;

	for (int i = 0; i < count; i++) {
	    const keyrec_t& tup = page.rec(temps.penalties[i].slot);
	    rt_rect br(rt_rect::size2dim(tup.klen()), (const double *) tup.key());

	    if (temps.penalties[i].p < minPenalty) {
		minPenalty = temps.penalties[i].p;
		minArea = br.span();
	        slot = temps.penalties[i].slot;
	    } else if (temps.penalties[i].p == minPenalty) {
		if (br.span() < minArea) {
		    minArea = br.span();
		    slot = temps.penalties[i].slot;
		}
	    } else {
	        // minPenalty < temps.penalties[i].p: we're done
		assert(slot != -1);
		break;
	    } 
	}

    } else {
        assert(page.level() == 2);
	// pick item with min overlap enlargement, min area enlargement among
	// the best 32 entries in terms of area enlargement

	double minOverlapEnlargement = MAXDOUBLE; // min overlap enlargement
	gist_penalty_t minAreaEnlargement(gist_penalty_t::max_penalty);
	double overlapEnlargement;
	
	for (int i = 0; i < count && i < MINPENENTRIES; i++) {
	    const keyrec_t& tup = page.rec(temps.penalties[i].slot);
	    rt_rect br(rt_rect::size2dim(tup.klen()), (const double *) tup.key());

	    computeOverlapEnlargement(temps.penalties[i].slot, newKey, page,
	        overlapEnlargement);
	    if (overlapEnlargement <= minOverlapEnlargement) {
		gist_penalty_t pen;
		// compute area enlargement
		ext.penalty((void *) tup.key(), tup.klen(), page.level(), newKey.ptr(0),
		    newKey.len(0), pen);
	        if (overlapEnlargement == minOverlapEnlargement &&
		    pen >= minAreaEnlargement) {

		    continue;
		}

		minOverlapEnlargement = overlapEnlargement;
		minAreaEnlargement = pen;
		slot = temps.penalties[i].slot;
	    }
	}

    }
    return;
}


/////////////////////////////////////////////////////////////////////////
// rstar_ext_t::computeOverlapEnlargement - betw. enlarged BR and remaining BRs
//
// Description:
// 	- iterates through all BRs on page, computing enlargement of overlap
//	  with expanded target BR
//
/////////////////////////////////////////////////////////////////////////

void
rstar_ext_t::computeOverlapEnlargement(
    int slot,
    const vec_t& newKey,
    const gist_p& page,
    double& overlapEnlargement)
{
    // compute enlarged rect
    const keyrec_t& tup = page.rec(slot);
    rt_rect preBr(rt_rect::size2dim(tup.klen()), (const double *) tup.key());
    rt_rect postBr(preBr); // make a copy, so we don't overwrite data on the page
    (*((rt_ext_t&) ext).expandFcts[0])(&postBr, newKey.ptr(0), newKey.len(0), true);

    int recCnt = page.nrecs();
    overlapEnlargement = 0.0;
    int i;
    for (i = 0; i < recCnt; i++) {
	if (i != slot) {
	    // extract rect
	    const keyrec_t& t = page.rec(i);
	    rt_rect rect(rt_rect::size2dim(t.klen()), (const double *) t.key());
	    overlapEnlargement += rect.overlap(postBr) - rect.overlap(preBr);
	}
    }
}


/////////////////////////////////////////////////////////////////////////
// rstar_ext_t::splitAuxCmp - qsort comparison fct for SplitAux
//
// Description:
//	- sorts in ascending order, first on lo, then hi
//
// Return Values:
//      -1, 0, 1
/////////////////////////////////////////////////////////////////////////

int
rstar_ext_t::splitAuxCmp(const void* a, const void* b)
{
    const SplitAux* e1 = (const SplitAux *) a;
    const SplitAux* e2 = (const SplitAux *) b;

    if (e1->lo < e2->lo) {
        return -1;
    } else if (e1->lo == e2->lo) {
        if (e1->hi < e2->hi) {
	    return -1;
	} else if (e1->hi == e2->hi) {
	    return 0;
	} else {
	    return 1;
	}
    } else {
        return 1;
    }
}


/////////////////////////////////////////////////////////////////////////
// rstar_ext_t::SplitAux::init - initialize SplitAux 
//
// Description:
//
/////////////////////////////////////////////////////////////////////////

void
rstar_ext_t::SplitAux::init(
    int slot,
    const double* val,
    int dims,
    int dim,
    bool isPoint)
{
    this->slot = slot;
    if (isPoint) {
	rt_point pt(dims, val);
	this->lo = pt.co(dim);
	this->hi = pt.co(dim);
    } else {
	rt_rect rect(dims, val);
	this->lo = rect.lo(dim);
	this->hi = rect.hi(dim);
    }
}


/////////////////////////////////////////////////////////////////////////
// rstar_ext_t::initalBr - initialize BR with single page entry
//
// Description:
//
/////////////////////////////////////////////////////////////////////////

void
rstar_ext_t::initialBr(
    rt_rect& r,
    bool isPoint,
    const double* coords)
{
    int dims = r.dim();
    for (int i = 0; i < dims; i++) {
	if (isPoint) {
	    r.lo(i) = r.hi(i) = coords[i];
	} else {