main.cc

X-tree的C++源码

#include <math.h>
#include <stdlib.h>
#include <signal.h>
#include <time.h>

//////////////////////////////////////////////////////////////////////////////
// defines
//////////////////////////////////////////////////////////////////////////////
#ifndef TRUE
#define TRUE 1
#define FALSE 0
#endif


#define BLK_SIZE   4096
#define MAXLONGINT 32768 
#define NUM_TRIES 10
#define ZAEHLER

#include "blk_file.h"
#include "linlist.h"
#include "x_tree.h"


//////////////////////////////////////////////////////////////////////////////
// DATA
//////////////////////////////////////////////////////////////////////////////

class DATA
{
    int dimension;
public:
    float *data;                       // Vector
    float distanz;                     // anything
    float *get_mbr();                  // returns MBR of the object
    float get_area()                   // returns the area of the MBR
    { return 0.0; }                    // for vectors always 0.0
    void read_from_buffer(char *buffer);   
                                       // reads data from buffer
    void write_to_buffer(char *buffer);   
                                       // writes data to buffer
    int get_size();                    // returns amount of needed space
    void print();

    virtual DATA & operator = (DATA &_d);
    virtual bool operator < (DATA &_d);
    virtual bool operator > (DATA &_d);

    DATA(int *dimension = &XTDataNode__dimension);
    virtual ~DATA();
};

DATA::DATA(int *_dimension)
{
    dimension = *((int *)_dimension);
    data = new float[dimension];
}

DATA::~DATA()
{
    delete [] data;
}

DATA & DATA::operator = (DATA &_d)
{
    dimension = _d.dimension;
    distanz = _d.distanz;
    memcpy(data, _d.data, sizeof(float) * dimension);

    return *this;
}

bool DATA::operator < (DATA &_d)
{
    return (distanz < _d.distanz);
}

bool DATA::operator > (DATA &_d)
{
    return (distanz > _d.distanz);
}

void DATA::read_from_buffer(char *buffer)
{
    int i;

    i = dimension*sizeof(float);
    memcpy(data, buffer, i);
    memcpy(&distanz, &buffer[i], sizeof(int));
}

void DATA::write_to_buffer(char *buffer)
{
    int i;

    i = dimension*sizeof(float);
    memcpy(buffer, data, i);
    memcpy(&buffer[i], &distanz, sizeof(int));
}

int DATA::get_size()
{
    return dimension * sizeof(float) + sizeof(int);
}

void DATA::print()
{
 int i;

 printf("( ");

 for(i = 0; i < dimension; i++)
   printf("%7.5f ",data[i]);

 printf(")\n");

}

float *DATA::get_mbr()
// fuer Punktdaten trivial: untere_grenze == obere_grenze
{
    int i;
    float *f;

    f = new float[2*dimension];
    for (i = 0; i < dimension; i++)
	f[2*i] = f[2*i+1] = data[i];

    return f;
}


////////////////////////////////////////////////////////////////
// main()
///////////////////////////////////////////////////////////////

bool abort_flag;

void abort(int signal)
{
    abort_flag = TRUE;
}


void error(char *t, bool ex)
{
    fprintf(stderr, t);
    if (ex)
	exit(0);
}

void pm(float *mbr)
{
    int i;

    for (i = 0; i < 8; i++)
	printf("%f..%f ", mbr[2*i], mbr[2*i+1]);
    printf("\n");
}

float page_access;

class Timer
{
    float dist_time_cpu; 
    float dist_time; 

    clock_t clock_start, clock_end;
    time_t time_start, time_end;
public:
    void start();
    void end();
};

void Timer::start()
{
    clock_start = clock();
    time (&time_start);
}


void Timer::end()
{
    time (&time_end);
    clock_end = clock ();
    dist_time_cpu = (float) (clock_end - clock_start) / 
	(float) CLOCKS_PER_SEC;
    dist_time = difftime(time_end, time_start);
    
    printf("%f sec cpu,   %f sec real\n", 
	   dist_time_cpu, dist_time);
}

void usage()
{
    printf("X-tree usage:\n");
    printf("x-tree [command] [parameter]\n");
    printf("Available commands are:\n");
    printf("c  [dim]                             create X-tree of dimension dim\n");
    printf("re [dim] [filename] [dim_data] [num] insert num vectors from file filename of dimension dim\n");
    printf("fu [dim] [num]                       insert num uniformlly distributed vectors of dimension dim\n");
    printf("w  [dim]                             \n");
}


XTree<DATA> * create_tree(char *filename, int dimension)
// neuen Baum erzeugen
{
    return new XTree<DATA>(filename, BLK_SIZE, 4, dimension);
}

XTree<DATA> * open_tree(char *filename)
// Baum 鰂fnen
{
    return new XTree<DATA>("test.xt", 4);
}

void read_data(XTree<DATA> *xt, char *filename, int dim_data, int anz, int dim)
  // liest Daten aus einer Datei in den Baum ein
{
    Timer t;
    FILE *fp;
    int j, wie_oft;
    DATA *d;
	
    // Baum fuellen
	
    wie_oft = dim_data / dim;
    if (wie_oft == 0)
	error("cannot read vectors larger than dim_data from filename",
	      TRUE);
    
    fp = fopen(filename, "rb");
    
    printf("reading %d vectors into index of dimension %d\n",
	   anz, dim);
    
    if (fp == NULL)
	error("error opening founew.dump", TRUE);
    t.start();
    for (j = 0; j < anz && !abort_flag; j++ )
    {
	d = new DATA(&dim);
	fread(d->data, sizeof(float), dim, fp);
	
	xt->insert(d);
	
	if (j % 500 == 0)
	    printf("did %d\n",j);
	delete d;
    }
    t.end();
    fclose(fp);
} 


void fill_uniform(XTree<DATA> *xt, int dim, int anz)
// fuellt den Baum mit gleichverteilten Vektoren auf
{
    int j, l;
    Timer t;
    DATA *d;

    // Baum fuellen	
    t.start();
    for (j = 0; j < anz && !abort_flag; j++ )
    {
	d = new DATA(&dim);
	for(l = 0; l < dim; l++)
	    d->data[l] = drand48();
	
	xt->insert(d);
	delete d;
	
	if (j % 50 == 0)
	    printf("did %d\n",j);
    }
    t.end();
}

void overlap(XTree<DATA> *xt, int dim)
// berechnet Ueberlappung im Directory des Baums
{
    int i, j, l, all, num;
    int nodes_b[20];   // Anzahl der Knoten pro Tiefe
    int nodes_t[20];   
    int nodes_s[20];   
    int nodes_a[20];   
    float *mbr;
    float mi[30], ma[30], ex[30];
    DATA *d;
    
    for (i = 0; i < 20; i++)
	nodes_t[i] = nodes_s[i] = nodes_b[i] = nodes_a[i] = 0;
    
    // bestimme Anzahl der Knoten pro level
    xt->nodes(nodes_a);
    
    // bestimme 1 % Anfragepunkte
    all = xt->get_num();
    num = all / 100;
    
    printf("querying %d of %d data\n", num, all);
    xt->load_root();
    mbr = xt->root_ptr->get_mbr();
    
    for (i = 0; i < dim; i++)
    {
	ma[i] = -MAXREAL;
	mi[i] = MAXREAL;
    }
    
    for (i = 0; i < dim; i++)
    {
	ma[i] = max(mbr[2*i+1], ma[i]);
	mi[i] = min(mbr[2*i], mi[i]);
    }
    
    for (i = 0; i < dim; i++)
	ex[i] = ma[i] - mi[i];
    
    for (i = 0; i < num; i++)
    {
	d = xt->get(rand()/10);
	// d = new DATA(&dim);
	// for(l = 0; l < dim; l++)
	   //  d->data[l] = ma[l] - ex[l] * drand48();
	
	for (j = 0; j < 20; j++)
	    nodes_b[j] = 0;      
	
	xt->overlapping(d->data, nodes_b);
	
	for (j = 0; j < 20; j++)
	{
	    nodes_s[j] += nodes_b[j];
	    if (nodes_b[j] > 1)
		nodes_t[j]++;
	}
	delete d;
    }
    
    for (i = 0; i < 5; i++)
    {
	printf("nodes accessed on level %d: %f,  %f of %d\n", i, 
	       (float)nodes_t[i]/(float)num, 
	       (float)nodes_s[i]/(float)num, nodes_a[i]);
    }
}


void nearest_neighbour(XTree<DATA> *xt, int dim)
// stellt gleichverteilte Nearest Neighbour queries
{
    int z, l;
    DATA *d, *p;
    
    // alten Baum laden
    srand(12345);
    
    printf("tree is filled now --> nearest neighbour search von (0.05)^5 \n");
    for(z = 0; z < 1; z++)
    {
	page_access = 0.0;
	d = new DATA(&dim);
	for(l = 0; l < dim; l++)
	    d->data[l] = drand48();
	
	printf("Query-Point :");
	d->print();
	
	p = new DATA(&dim);
	for(l = 0; l < dim; l++)  
	    p->data[ l ] = 2.0;
	
	xt->nearest_neighbour_search( d, p);
	
	printf("\nNearest:");
	p->print(); 
	delete p;
	delete d;
	
	printf("\nQuery-Nummer: %d Plattenzugriffe: %f \n\n",
	       z, page_access);	
    }
}


void point_query(XTree<DATA> *xt, int dim)
// stellt gleichverteilte point queries
{
    float all_page;
    int nn, k, l;
    Timer t;
    DATA *d;
    
    // alten Baum laden
    srand(2314);
    
    t.start();
    all_page = 0.0;
    for (nn = 0; nn < NUM_TRIES; nn++)
    {
	page_access = 0.0;
	
	l = rand()/10;
	printf("/%d/\n", l);
	d = xt->get(l);
	
	xt->point_query(d->data);
	
	delete d;
	
	all_page += page_access;
	printf(".");
	fflush(stdout);
    }
    printf("average (%d) page_accesses: %f \n\n", 
	   NUM_TRIES, all_page / NUM_TRIES);
    t.end();
}

void k_nearest_neighbour(XTree<DATA> *xt, int dim, int k)
// stellt gleichverteilte Nearest-Neighbour queries
{
    SortedLinList<DATA> *res;
    float all_page;
    int nn, l, cache_size;
    Timer t;
    DATA *d;
    
    // alten Baum laden 
    srand(907932);
    
    // berechne Gewichte fuer Cache
    cache_size = (int) ((12 * dim * 
			 (xt->num_of_dnodes+xt->num_of_inodes)) / BLK_SIZE);
    xt->set_node_weight(cache_size);
    
    t.start();
    all_page = 0.0;
    for(nn = 0; nn < 10; nn++)
    {
	page_access = 0.0;
	
	d = new DATA(&dim);
	for(l = 0; l < dim; l++)
	    d->data[l] = drand48();
	d->distanz = MAXREAL;
	
//	    printf("Query-Point :");
//	    d->print();
	
	res = new SortedLinList<DATA>;
	xt->k_nearest_neighbour_search(d, k, res);
	
// 	    printf("\n%d Nearest:\n",k);
// 	    for(n = 0; n < k; n++)
// 	    {
//         	printf("%1d.Nearest: Distanz: %f Point: ",n,
// 		       res->get(n)->distanz);
// 		res->get(n)->print();
// 	    } 
	
	delete d;
	delete res;
	
	all_page += page_access;
	printf(".");
	fflush(stdout);
    }
    printf("average (10) page_accesses (%d NN): %f \n\n", 
	   k, all_page / 10.0);
    t.end();
}

main(int argc, char *argv[])
{
    XTree<DATA> *xt;
    char filename[255]; 

    int dim;

    abort_flag = FALSE;

    signal(SIGTERM, abort);
    
    if (argc < 2)
    {
	usage();
	exit(1);
    }

    dim = atoi(argv[2]);
    if (dim < 1)
    {
	usage();
	exit(1);
    }

    strcpy(filename, "test.xt");

    if (!strcmp(argv[1], "c"))
	xt = create_tree(filename, dim);
    else if (!strcmp(argv[1], "re"))
    {
	// alten Baum laden
	xt = open_tree(filename);
	
	// Daten einlesen
	read_data(xt, argv[4], atoi(argv[5]), atoi(argv[5]), atoi(argv[5]));

    }
    else if (!strcmp(argv[1], "fu"))
    {
	// alten Baum laden
	xt = open_tree(filename);
	
	fill_uniform(xt, dim, atoi(argv[3])); 
    }
    else if (!strcmp(argv[1], "overlap"))
    {
	xt = open_tree(filename);

	// Ueberlappung ausgeben
	overlap(xt, dim);
    }
    else if (!strcmp(argv[1], "w"))
    {
	FILE *f;

	xt = open_tree(filename);
	f = fopen("mbr","w");
	xt->write_info(f);
	fclose(f);
    }
    else if (!strcmp(argv[1], "pq"))
    {
	xt = open_tree(filename);

	point_query(xt, dim);
    }
    else if (!strcmp(argv[1], "nn"))
    {
	xt = open_tree(filename);

	nearest_neighbour(xt, dim);
    }
    else if (!strcmp(argv[1], "knn"))
    {
	xt = open_tree(filename);

	k_nearest_neighbour(xt, dim, atoi(argv[3]));
    }
    else 
    {
	usage();
	exit(1);
    }

    delete xt;

    return 0;
}