Tree-M/MT/MT.cpp

/*********************************************************************
*                                                                    *
* 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 <stdlib.h>
#include "list.h"
#include "MT.h"
#include "MTpredicate.h"
#include "MTcursor.h"

#ifdef _WIN32   // these functions are defined under UNIX
void srandom(int seed) { srand(seed); }
int random() { return rand(); }
#endif

TruePredicate truePredicate;

int
PickRandom(int from, int to)
{
        return (random()%(to-from))+from;
}

MTnode *
MT::ParentNode(MTnode *node)
{
        GiSTpath path=node->Path();
        MTnode *parentnode;

        path.MakeParent();
        parentnode=(MTnode *)ReadNode(path);
        return parentnode;      // parentnode should be destroyed by the caller
}

void
MT::CollectStats()
{
/*#if defined(_DEBUG)
        CMemoryState msOld, msNew, msDif;
        msOld.Checkpoint();
#endif */
        GiSTpath path;
        GiSTnode *node;

        path.MakeRoot();
        node=ReadNode(path);
        if(!node->IsLeaf()) {
                TruePredicate truePredicate;
                GiSTlist<GiSTentry*> list=node->Search(truePredicate);  // retrieve all the children
                double *areas, *radii, totarea=0;
                int *n, maxn=node->Level(), totn=1, i;

                areas=new double[maxn];
                radii=new double[maxn];
                n=new int[maxn];
                for(i=0; i<maxn; i++) {
                        n[i]=0;
                        areas[i]=0;
                        radii[i]=0;
                }
                delete node;
                while(!list.IsEmpty()) {
                        GiSTentry *e=list.RemoveFront();
                        GiSTlist<GiSTentry*> newlist;

                        path.MakeChild(e->Ptr());
                        node=ReadNode(path);
                        n[node->Level()]++;
                        areas[node->Level()]+=((MTkey *)e->Key())->area();
                        radii[node->Level()]+=((MTkey *)e->Key())->maxradius();
                        if(!node->IsLeaf()) newlist=node->Search(truePredicate);        // recurse to next level
                        while(!newlist.IsEmpty()) list.Append(newlist.RemoveFront());
                        path.MakeParent();
                        delete e;
                        delete node;
                }
                // output the results
                cout << "Level:\tPages:\tRadius:\tArea:\n";
                for(i=maxn-1; i>=0; i--) {
                        totn+=n[i];
                        totarea+=areas[i];
                        cout << i << ":\t" << n[i] << "\t" << radii[i]/n[i] << "\t" << areas[i]/n[i] << endl;
                }
                cout << "tot:\t" << totn << "\t" << totarea << endl;
                delete []areas;
                delete []radii;
                delete []n;
        }
        else delete node;
/* #if defined(_DEBUG)
        msNew.Checkpoint();
        msDif.Difference(msOld, msNew);
        msDif.DumpStatistics();
#endif */
}

BOOL
MT::CheckNode(GiSTpath path, MTentry *e)
{
        MTnode *node=(MTnode *)ReadNode(path);
        BOOL ret=TRUE;

        for(int i=0; (i<node->NumEntries())&&ret; i++) {
            MTentry *child=(MTentry *)(*node)[i].Ptr();

            if((e!=NULL)&&(((child->Key()->distance+child->maxradius())>e->maxradius())||(child->object().distance(e->object())!=child->Key()->distance))) {
                        cout << "Error with entry " << child << "in " << node;
                        ret=FALSE;
                }
                path.MakeChild(child->Ptr());
                if(!node->IsLeaf()) ret&=CheckNode(path, child);
                path.MakeParent();
        }
        delete node;
        return ret;
}

GiSTlist<MTentry *>
MT::RangeSearch(const MTquery& query)
{
        GiSTpath path;

        path.MakeRoot();
        MTnode *root=(MTnode *)ReadNode(path);
        GiSTlist<MTentry *> list=root->RangeSearch(query);

        delete root;
        return list;
}

MTentry **
MT::TopSearch(const TopQuery& query)
{
        GiSTpath path;  // path for retrieving root node
        MTnode *node;   // next node to be examined
        MTentry **results=new MTentry*[query.k];        // the results list (ordered for increasing distances)
        list<dst *> queue(comparedst);  // list for ordering the nodes
        SimpleQuery q(query.Pred(), maxDist(), TRUE);
        double *dists=new double[query.k];      // array containing the NN distances
        int i;

        for (i=0; i<query.k; i++) dists[i]=maxDist();   // initialization of the NN-distances array
        path.MakeRoot();
        node=(MTnode *)ReadNode(path);  // retrieve the root node
        while(node!=NULL) {     // examine current node
                double oldDist=q.Grade();

                // search the first children to be examined
//              cout << "Examining node " << node->Path() << endl;
                for(unsigned int i=0; i<node->NumEntries(); i++) {      // for each entry in the current node
                        MTentry *e=(MTentry *)((*node)[i].Ptr());

                        q.SetGrade(oldDist);
//                      cout << "range=" << q.Radius() << ", oldDist=" << q.Grade() << ": Checking " << e;
                        if(q.Consistent(*e)) {  // check if the entry is consistent with the query
//                              cout << "grade=" << q.Grade() << endl;
                                if(e->IsLeaf()) {       // object qualifies
                                        if(dists[query.k-1]<maxDist()) delete results[query.k-1];       // delete last element of the results list

                                        MTentry *key=(MTentry *)e->Copy();
                                        int j=0;

                                        key->setminradius(0);
                                        key->setmaxradius(q.Grade());   // we insert the actual distance from the query object as the key radius
                                        // insert dist in the results list (sorting for incr. distance)
                                        // could be improved using binary search
                                        while(dists[j]<q.Grade()) j++;
//                                      cout << "\tInserted (" << q.Grade() << "<" << dists[query.k-1] << ") into list in position " << j << endl;
                                        for(int l=query.k-1; l>j; l--) {        // shift up results array
                                                results[l]=results[l-1];
                                                dists[l]=dists[l-1];
                                        }
                                        results[j]=key;
                                        dists[j]=q.Grade();
                                        q.SetRadius(dists[query.k-1]);
                                }
                                else {  // we have to insert the child node in the priority queue
                                        GiSTpath path=node->Path();
                                        double dmin=q.Grade()-e->maxradius(), dmax=q.Grade()+e->maxradius();    // these are lower- and upper-bounds on the distances of the descendants of the entry from the query object

                                        if(dmin<0) dmin=0;
                                        // insert the node in the stack (sorting for decr. level and incr. LB on distance)
                                        // could be improved using binary search
                                        path.MakeChild(e->Ptr());
                                        dst *d=new dst(path, dmin, q.Grade());

                                        queue.Insert(d);
//                                      cout << "\tInserted (" << dmin << "<" << dists[query.k-1] << ") into list\n";
                                }
                        }
                        else {
//                              cout << "\tPruned (" << q.Grade() << ">" << dists[query.k-1] << ") from the list\n";
                                // if we're in a "true" leaf node (i.e. not in the root) and last entry was pruned, we can safely prune all other entries too
//                              if(e->IsLeaf()&&(!e->Node()->Path().IsRoot())&&(fabs(e->Key()->distance-oldDist)>q.Grade()))) break;
                        }
                }
                // the next entry to be chosen is that whose distance from the parent is most similar to the distance between the parent and the query object
                delete node;    // delete examined node
                if(!queue.IsEmpty()) {  // retrieve next node to be examined
                        dst *d=queue.RemoveFirst();

                        if(d->Bound()>=dists[query.k-1]) {      // terminate the search
                                while(!queue.IsEmpty())
                                        delete queue.RemoveFirst();
                                node=NULL;
                        }
                        else {
                                node=(MTnode *)ReadNode(d->Path());
                                q.SetGrade(d->Dist());
                        }
                        delete d;
                }
                else node=NULL; // terminate the search
        }
        delete []dists;
        return results;
}
Revision:	1.1
Committed:	Sun May 6 00:45:52 2001 UTC (23 years, 1 month ago) by root
Branch:	MAIN
CVS Tags:	HEAD
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	/*********************************************************************
2			* *
3			* Copyright (c) 1997,1998, 1999 *
4			* Multimedia DB Group and DEIS - CSITE-CNR, *
5			* University of Bologna, Bologna, ITALY. *
6			* *
7			* All Rights Reserved. *
8			* *
9			* Permission to use, copy, and distribute this software and its *
10			* documentation for NON-COMMERCIAL purposes and without fee is *
11			* hereby granted provided that this copyright notice appears in *
12			* all copies. *
13			* *
14			* THE AUTHORS MAKE NO REPRESENTATIONS OR WARRANTIES ABOUT THE *
15			* SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING *
16			* BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, *
17			* FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT. THE AUTHOR *
18			* SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A *
19			* RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS *
20			* DERIVATIVES. *
21			* *
22			*********************************************************************/
23
24			#include <stdlib.h>
25			#include "list.h"
26			#include "MT.h"
27			#include "MTpredicate.h"
28			#include "MTcursor.h"
29
30			#ifdef _WIN32 // these functions are defined under UNIX
31			void srandom(int seed) { srand(seed); }
32			int random() { return rand(); }
33			#endif
34
35			TruePredicate truePredicate;
36
37			int
38			PickRandom(int from, int to)
39			{
40			return (random()%(to-from))+from;
41			}
42
43			MTnode *
44			MT::ParentNode(MTnode *node)
45			{
46			GiSTpath path=node->Path();
47			MTnode *parentnode;
48
49			path.MakeParent();
50			parentnode=(MTnode *)ReadNode(path);
51			return parentnode; // parentnode should be destroyed by the caller
52			}
53
54			void
55			MT::CollectStats()
56			{
57			/*#if defined(_DEBUG)
58			CMemoryState msOld, msNew, msDif;
59			msOld.Checkpoint();
60			#endif */
61			GiSTpath path;
62			GiSTnode *node;
63
64			path.MakeRoot();
65			node=ReadNode(path);
66			if(!node->IsLeaf()) {
67			TruePredicate truePredicate;
68			GiSTlist<GiSTentry*> list=node->Search(truePredicate); // retrieve all the children
69			double areas, radii, totarea=0;
70			int *n, maxn=node->Level(), totn=1, i;
71
72			areas=new double[maxn];
73			radii=new double[maxn];
74			n=new int[maxn];
75			for(i=0; i<maxn; i++) {
76			n[i]=0;
77			areas[i]=0;
78			radii[i]=0;
79			}
80			delete node;
81			while(!list.IsEmpty()) {
82			GiSTentry *e=list.RemoveFront();
83			GiSTlist<GiSTentry*> newlist;
84
85			path.MakeChild(e->Ptr());
86			node=ReadNode(path);
87			n[node->Level()]++;
88			areas[node->Level()]+=((MTkey *)e->Key())->area();
89			radii[node->Level()]+=((MTkey *)e->Key())->maxradius();
90			if(!node->IsLeaf()) newlist=node->Search(truePredicate); // recurse to next level
91			while(!newlist.IsEmpty()) list.Append(newlist.RemoveFront());
92			path.MakeParent();
93			delete e;
94			delete node;
95			}
96			// output the results
97			cout << "Level:\tPages:\tRadius:\tArea:\n";
98			for(i=maxn-1; i>=0; i--) {
99			totn+=n[i];
100			totarea+=areas[i];
101			cout << i << ":\t" << n[i] << "\t" << radii[i]/n[i] << "\t" << areas[i]/n[i] << endl;
102			}
103			cout << "tot:\t" << totn << "\t" << totarea << endl;
104			delete []areas;
105			delete []radii;
106			delete []n;
107			}
108			else delete node;
109			/* #if defined(_DEBUG)
110			msNew.Checkpoint();
111			msDif.Difference(msOld, msNew);
112			msDif.DumpStatistics();
113			#endif */
114			}
115
116			BOOL
117			MT::CheckNode(GiSTpath path, MTentry *e)
118			{
119			MTnode node=(MTnode )ReadNode(path);
120			BOOL ret=TRUE;
121
122			for(int i=0; (i<node->NumEntries())&&ret; i++) {
123			MTentry child=(MTentry )(*node)[i].Ptr();
124
125			if((e!=NULL)&&(((child->Key()->distance+child->maxradius())>e->maxradius())\|\|(child->object().distance(e->object())!=child->Key()->distance))) {
126			cout << "Error with entry " << child << "in " << node;
127			ret=FALSE;
128			}
129			path.MakeChild(child->Ptr());
130			if(!node->IsLeaf()) ret&=CheckNode(path, child);
131			path.MakeParent();
132			}
133			delete node;
134			return ret;
135			}
136
137			GiSTlist<MTentry *>
138			MT::RangeSearch(const MTquery& query)
139			{
140			GiSTpath path;
141
142			path.MakeRoot();
143			MTnode root=(MTnode )ReadNode(path);
144			GiSTlist<MTentry *> list=root->RangeSearch(query);
145
146			delete root;
147			return list;
148			}
149
150			MTentry **
151			MT::TopSearch(const TopQuery& query)
152			{
153			GiSTpath path; // path for retrieving root node
154			MTnode *node; // next node to be examined
155			MTentry *results=new MTentry[query.k]; // the results list (ordered for increasing distances)
156			list<dst *> queue(comparedst); // list for ordering the nodes
157			SimpleQuery q(query.Pred(), maxDist(), TRUE);
158			double *dists=new double[query.k]; // array containing the NN distances
159			int i;
160
161			for (i=0; i<query.k; i++) dists[i]=maxDist(); // initialization of the NN-distances array
162			path.MakeRoot();
163			node=(MTnode *)ReadNode(path); // retrieve the root node
164			while(node!=NULL) { // examine current node
165			double oldDist=q.Grade();
166
167			// search the first children to be examined
168			// cout << "Examining node " << node->Path() << endl;
169			for(unsigned int i=0; i<node->NumEntries(); i++) { // for each entry in the current node
170			MTentry e=(MTentry )((*node)[i].Ptr());
171
172			q.SetGrade(oldDist);
173			// cout << "range=" << q.Radius() << ", oldDist=" << q.Grade() << ": Checking " << e;
174			if(q.Consistent(*e)) { // check if the entry is consistent with the query
175			// cout << "grade=" << q.Grade() << endl;
176			if(e->IsLeaf()) { // object qualifies
177			if(dists[query.k-1]<maxDist()) delete results[query.k-1]; // delete last element of the results list
178
179			MTentry key=(MTentry )e->Copy();
180			int j=0;
181
182			key->setminradius(0);
183			key->setmaxradius(q.Grade()); // we insert the actual distance from the query object as the key radius
184			// insert dist in the results list (sorting for incr. distance)
185			// could be improved using binary search
186			while(dists[j]<q.Grade()) j++;
187			// cout << "\tInserted (" << q.Grade() << "<" << dists[query.k-1] << ") into list in position " << j << endl;
188			for(int l=query.k-1; l>j; l--) { // shift up results array
189			results[l]=results[l-1];
190			dists[l]=dists[l-1];
191			}
192			results[j]=key;
193			dists[j]=q.Grade();
194			q.SetRadius(dists[query.k-1]);
195			}
196			else { // we have to insert the child node in the priority queue
197			GiSTpath path=node->Path();
198			double dmin=q.Grade()-e->maxradius(), dmax=q.Grade()+e->maxradius(); // these are lower- and upper-bounds on the distances of the descendants of the entry from the query object
199
200			if(dmin<0) dmin=0;
201			// insert the node in the stack (sorting for decr. level and incr. LB on distance)
202			// could be improved using binary search
203			path.MakeChild(e->Ptr());
204			dst *d=new dst(path, dmin, q.Grade());
205
206			queue.Insert(d);
207			// cout << "\tInserted (" << dmin << "<" << dists[query.k-1] << ") into list\n";
208			}
209			}
210			else {
211			// cout << "\tPruned (" << q.Grade() << ">" << dists[query.k-1] << ") from the list\n";
212			// if we're in a "true" leaf node (i.e. not in the root) and last entry was pruned, we can safely prune all other entries too
213			// if(e->IsLeaf()&&(!e->Node()->Path().IsRoot())&&(fabs(e->Key()->distance-oldDist)>q.Grade()))) break;
214			}
215			}
216			// the next entry to be chosen is that whose distance from the parent is most similar to the distance between the parent and the query object
217			delete node; // delete examined node
218			if(!queue.IsEmpty()) { // retrieve next node to be examined
219			dst *d=queue.RemoveFirst();
220
221			if(d->Bound()>=dists[query.k-1]) { // terminate the search
222			while(!queue.IsEmpty())
223			delete queue.RemoveFirst();
224			node=NULL;
225			}
226			else {
227			node=(MTnode *)ReadNode(d->Path());
228			q.SetGrade(d->Dist());
229			}
230			delete d;
231			}
232			else node=NULL; // terminate the search
233			}
234			delete []dists;
235			return results;
236			}