main.cpp

M树源代码

/*********************************************************************
*                                                                    *
* Copyright (c) 1997,1998, 1999                                      *
* Multimedia DB Group and DEIS - CSITE-CNR,                          *
* University of Bologna, Bologna, ITALY.                             *
*                                                                    *
* All Rights Reserved.                                               *
*                                                                    *
* Permission to use, copy, and distribute this software and its      *
* documentation for NON-COMMERCIAL purposes and without fee is       *
* hereby granted provided  that this copyright notice appears in     *
* all copies.                                                        *
*                                                                    *
* THE AUTHORS MAKE NO REPRESENTATIONS OR WARRANTIES ABOUT THE        *
* SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING  *
* BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY,      *
* FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT. THE AUTHOR  *
* SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A      *
* RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS    *
* DERIVATIVES.                                                       *
*                                                                    *
*********************************************************************/

#include <stdio.h>
#include <fstream.h>
#include <time.h>
#include <malloc.h>
#ifdef UNIX
#include <unistd.h>
#include <ctype.h>
#endif

#include "MT.h"
#include "MTpredicate.h"

#define IndObjs 11648

int compdists;
int IOread, IOwrite;
int objs;
int dimension=2;
double eps;

language query_language=FUZZY_STANDARD;
dist2sim hfunction=LINEAR;

extern double MIN_UTIL;
extern pp_function PROMOTE_PART_FUNCTION;
extern pv_function PROMOTE_VOTE_FUNCTION;
extern pp_function SECONDARY_PART_FUNCTION;
extern r_function RADIUS_FUNCTION;
extern int NUM_CANDIDATES;
extern s_function SPLIT_FUNCTION;

MT *gist=NULL;

int debug=0;

// close the tree and delete it
void
CommandClose()
{
	if(gist) {
		delete gist;
		gist=NULL;
	}
}

// create a new tree and open it
void
CommandCreate(const char *method, const char *table)
{
	CommandClose();
	if(!strcmp(method, "mtree")) gist=new MT;
	else {
		cerr << "The only supported method is mtree.\n";
		return;
	}
	gist->Create(table);
	if(!gist->IsOpen()) {
		cout << "Error opening index.\n";
		delete gist;
		return;
	}
	cout << "Table " << table << " created as type " << method << ".\n";
}

// delete the tree from disk
void
CommandDrop(const char *table)
{
	if (unlink(table)) cout << "There is no table by that name.\n";
	else cout << "Table " << table << " dropped.\n";
}

// open the specified tree
void
CommandOpen(const char *method, const char *table)
{
	CommandClose();
	if(!strcmp(method, "mtree")) gist=new MT;
	else {
		cerr << "The only supported method is mtree.\n";
		return;
	}
	gist->Open(table);
	if(!gist->IsOpen()) {
		delete gist;
		cout << "Error opening table.\n";
		return;
	}
//	cout << "Table " << table << " opened.\n";
}

// execute a nearest neighbor query
void
CommandNearest(const TopQuery &query)
{
//	cout << "Searching " << query.Pred() << "...\n";
	MTentry **results=gist->TopSearch(query);

	for(unsigned int i=0; i<query.k; i++) {
		MTentry *e=results[i];
		cout << e;
//		cout << e->Ptr() << " ";
		delete e;
		objs++;
	}
//	cout << endl;
	delete []results;
}

// execute a range query
void
CommandSelect(MTquery& query)
{
	GiSTlist<MTentry *> list=gist->RangeSearch(query);

	while(!list.IsEmpty()) {
		MTentry *e=list.RemoveFront();
//		cout << e;
		delete e;
		objs++;
	}
/*#if defined(_DEBUG)
	CMemoryState msOld, msNew, msDif;
	msOld.Checkpoint();
#endif
#if defined(_DEBUG)
	msNew.Checkpoint();
	msDif.Difference(msOld, msNew);
	msDif.DumpStatistics();
#endif */
}

// delete the objects satisfying the predicate
void
CommandDelete(const GiSTpredicate& pred)
{
	gist->Delete(pred);
}

// insert an object in the tree
void
CommandInsert(const MTkey& key, int ptr)
{
	gist->Insert(MTentry(key, (GiSTpage)ptr));
//	cout << key << "->" << ptr << " inserted into " << table << ".\n";
}

// use the BulkLoading alogrithm to create the tree
void
CommandLoad(const char *table, MTentry **data, int n)
{
	CommandDrop(table);
	CommandCreate("mtree", table);
//	if(gist==NULL) printf("M3 NULL!!\n");
	printf("MinUtil=%f\n", MIN_UTIL);
	gist->BulkLoad(data, n, 1, "tmp");
}

// close the tree and exit
void
CommandQuit()
{
	CommandClose();
	cout << "Goodbye.\n";
//	exit(0);
}

// print the prompt
void
CommandPrompt()
{
	cout << "MTree> ";
	cout.flush();
}

// activate the debug mode (currently unavailable)
void
CommandDebug()
{
	debug=!debug;
	cout << "Debugging Output ";
	cout << (debug ? "ON\n" : "OFF\n");
}

// print the help file (currently unavailable)
void
CommandHelp()
{
	ifstream is("MTree.help");
	char c;

	while(is.get(c)) cout << c;
}

// perform a check of the nodes of the tree
void
CommandCheck()
{
	GiSTpath path;
	path.MakeRoot();
	gist->CheckNode(path, NULL);
}

// print a dump of each node of the tree
void
CommandDump()
{
	GiSTpath path;
	path.MakeRoot();
#ifdef PRINTING_OBJECTS
	gist->DumpNode(cout, path);
#endif
}

// collect and print statistics on the tree
void
CommandStats()
{
	gist->CollectStats();
}

int main(int argc, char **argv)
{
//	cerr << "Now starting...\n";
//	malloc_stats();
	int i=1;
	char cmdLine[15];
	BOOL end=FALSE;

	compdists=IOread=IOwrite=objs=0;
	cout << "**  MTree: An M-Tree based on Generalized Search Trees\n";
	while(strcmp(cmdLine, "quit")) {
		scanf("%s", cmdLine);
		if(!strcmp(cmdLine, "drop")) {
			CommandDrop("graphs.M3");
			if(argc<5) {
				cout << "Usage is: MTree [min_util] [split_f] [promote_f] [sec_promote_f] ([vote_f] ([n_cand]|[radius_f]))\n";
				exit(-1);
			}
			MIN_UTIL=atof(argv[1]);
			SPLIT_FUNCTION=(s_function)atoi(argv[2]);
			PROMOTE_PART_FUNCTION=(pp_function)atoi(argv[3]);
			SECONDARY_PART_FUNCTION=(pp_function)atoi(argv[4]);
			if(SECONDARY_PART_FUNCTION==CONFIRMED) {
				cout << "The secondary promotion function must be an unconfirmed one\n";
				exit(-1);
			}
			if(PROMOTE_PART_FUNCTION==SAMPLING) {
				if(argc<6) {
					cout << "Usage is: MTree [min_util] [split_f] [promote_f] ([vote_f] ([n_cand]|[radius_f]))\n";
					exit(-1);
				}
				NUM_CANDIDATES=atoi(argv[5]);
			}
			if(PROMOTE_PART_FUNCTION==CONFIRMED) {
				if(argc<6) {
					cout << "Usage is: MTree [min_util] [split_f] [promote_f] [sec_promote_f] ([vote_f] ([n_cand]|[radius_f]))\n";
					exit(-1);
				}
				PROMOTE_VOTE_FUNCTION=(pv_function)atoi(argv[5]);
				if(PROMOTE_VOTE_FUNCTION==SAMPLINGV) {
					if(argc<7) {
						cout << "Usage is: MTree [min_util] [split_f] [promote_f] ([vote_f] ([n_cand]|[radius_f]))\n";
						exit(-1);
					}
					NUM_CANDIDATES=atoi(argv[6]);
				}
				else if(PROMOTE_VOTE_FUNCTION==mM_RAD) {
					if(argc<7) {
						cout << "Usage is: MTree [min_util] [split_f] [promote_f] ([vote_f] ([n_cand]|[radius_f]))\n";
						exit(-1);
					}
					RADIUS_FUNCTION=(r_function)atoi(argv[6]);
				}
			}
			switch(SPLIT_FUNCTION) {
				case G_HYPERPL:
					cout << "G_HYPL, ";
					break;
				case BAL_G_HYPERPL:
					cout << "BAL_G_HYPL, ";
					break;
				case BALANCED:
					cout << "BAL, ";
					break;
			}
			switch(PROMOTE_PART_FUNCTION) {
				case RANDOM:
					cout << "RAN_2 ";
					break;
				case MAX_UB_DIST:
					cout << "M_UB_d ";
					break;
				case SAMPLING:
					cout << "SAMP" << NUM_CANDIDATES << "_2 ";
					break;
				case MIN_RAD:
					cout << "m_R_2 ";
					break;
				case MIN_OVERLAPS:
					cout << "m_O_2 ";
					break;
				case CONFIRMED:
				switch(PROMOTE_VOTE_FUNCTION) {
					case RANDOMV:
						cout << "RAN_1 ";
						break;
					case SAMPLINGV:
						cout << "SAMP" << NUM_CANDIDATES << "_1 ";
						break;
					case MAX_LB_DIST:
						cout << "M_LB_d ";
						break;
					case mM_RAD:
						cout << "mM_";
						switch(RADIUS_FUNCTION) {
							case LB:
								cout << "m";
								break;
							case AVG:
								cout << "A";
								break;
							case UB:
								cout << "M";
								break;
						}
						cout << "_r ";
						break;
				}
				break;
			}
			switch(SECONDARY_PART_FUNCTION) {
				case RANDOM:
					cout << "(RAN_2)\n";