mvptree

Mvptree (Mehrfachaussichtspunktbaumdatenstruktur)

Eine nicht basierte Datenstruktur zur Indizierung mehrdimensionaler Daten. Die MVPTree indizieren Vektorobjekte gemäß dem Abstand von ausgewählten Vantage -Punkten, die direkt aus den indizierten Daten ausgewählt wurden.

Leistungstests

Die folgenden Tests messen die Build- und Abfragezeiten für verschiedene Indexgrößen. Datenpunkte sind ein 16-dimensionales realwertes Vektorobjekt (unabhängig verteilt). Die Build -Operationen spiegeln die Anzahl der Entfernungsvorgänge wider, die für den Bau des Baumes erforderlich sind. Ebenso sind Abfrageoperationen die durchschnittliche Anzahl von Entfernungsvorgängen, um den Index für einen konstanten Radius von 0,04 abzufragen. Sowohl Build- als auch Abfrageoperationen werden auf die Größe des Baumes normalisiert und als Prozentsatz ausgedrückt. Jede Zeile im Diagramm ist der Durchschnitt von 5 Versuchsläufen, bei denen die Baumstruktur aufgebaut, 10 Cluster mit 10 Punkten abgefragt und dann abgenommen wurde.

N	Mem	Opers bauen	Zeit aufbauen	Abfragen Opers	Abfragestunde
100k	122MB	2554%	21,4 μs	0,0087%	42,4 μs
200k	289 MB	2693%	26,3 μs	0,0048%	63,4 μs
400k	548MB	2792%	36,8 μs	0,0022%	70,2 μs
800K	963MB	2872%	59,4 μs	0,0012%	86,0 μs
1m	1,1 GB	2899%	62,9 μs	0,0010%	107 μs
2m	2,7 GB	3021%	79,6 μs	0,0005%	163 μs
4m	5,5 GB	3139%	101 μs	0,0002%	242 μs

Hier sind die Abfragestatistiken für verschiedene Radiusgrößen und eine konstante Indexgröße von n = 1.000.000:

Radius	Abfragen Opers.	Abfragestunde
0,02	0,00094%	30,9 μs
0,04	0,00092%	121 μs
0,06	0,0012%	359 μs
0,08	0,00041%	971 μs
0,10	0,0241%	2,67 μs

Um es selbst auszuprobieren, führen Sie das Testprogramm runmvptree2 aus. Sie können mit den Testparametern in der Datei, Tests/run_mvptree2.cpp gespielt.

Programmierung

Verwenden Sie die Vorlagen -Header -Dateien. Erstellen Sie zunächst einen benutzerdefinierten Datentyp. Beispiele finden Sie unter key.hpp:

 struct VectorKeyObject {
	double key[16];
	VectorKeyObject(){};
	VectorKeyObject(const double otherkey[]){
		for (int i=0;i < 16;i++) key[i] = otherkey[i];
	}
	VectorKeyObject(const VectorKeyObject &other){
		for (int i=0;i < 16;i++) key[i] = other.key[i];
	}
	const VectorKeyObject& operator=(const VectorKeyObject &other){
		for (int i=0;i < 16;i++) key[i] = other.key[i];
		return *this;
	}
	const double distance(const VectorKeyObject &other)const {
		double sum = 0;
		for (int i=0;i < 16;i++){
			sum += pow(key[i] - other.key[i], 2.0);
		}
		return sqrt(sum/16.0);
	}
	
};

Der benutzerdefinierte Datentyp muss dem Implementierung von Kopierkopien, Zuordnungsbetreiber und Distanzfunktion bereitstellen.

Verwenden Sie als nächstes die Vorlagenklasse:

 #include "mvptree/mvptree.hpp"


MVPTree<VectorKeyObject> mvptree;

vector<VectorKeyObject> points;

mvptree.Add(points);
mvptree.Sync();

int sz = mvptree.Size();
assert(sz == points.size());


VectorKeyObject target;
double radius = ...  //  value for data set 
vector<item_t<VectorKeyObject>> results = mvptree.Query(target, radius);


mvptree.Clear();
sz = mvptree.Size();
assert(sz == 0);

Weitere Informationen finden Sie in den Programmen im Testverzeichnis.

Installieren

 cmake .
make
make test
make install