mvptree

MVPTREE (Struktur Data Pohon Titik Vantage)

Struktur data berbasis jarak untuk pengindeksan data multi-dimensi. MVPTREE mengindeks objek vektor sesuai dengan jaraknya dari titik pandang terpilih yang dipilih langsung dari data yang diindeks.

Tes kinerja

Tes berikut mengukur waktu build dan kueri untuk berbagai ukuran indeks. Poin data adalah objek vektor bernilai nyata 16 dimensi (seragam terdistribusi secara independen). Bangun operasi mencerminkan jumlah operasi jarak yang diperlukan untuk membangun pohon. Demikian juga, operasi kueri adalah jumlah rata -rata operasi jarak untuk meminta indeks untuk jari -jari konstan 0,04. Operasi build dan kueri dinormalisasi dengan ukuran pohon dan dinyatakan sebagai persentase. Setiap baris dalam grafik adalah rata -rata 5 uji coba, di mana struktur pohon dibangun, ditanyakan untuk 10 kelompok 10 poin, dan kemudian diturunkan.

N	Mem	Bangun Opers	Membangun waktu	Opers kueri	Waktu permintaan
100K	122MB	2554%	21.4μs	0,0087%	42.4μs
200k	289MB	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.1GB	2899%	62.9μs	0,0010%	107μs
2m	2.7GB	3021%	79.6μs	0,0005%	163μs
4m	5.5GB	3139%	101μs	0,0002%	242μs

Berikut adalah statistik kueri untuk berbagai ukuran radius dan ukuran indeks konstan n = 1.000.000:

radius	Opers kueri.	Waktu permintaan
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

Untuk mencobanya sendiri, jalankan program pengujian, runmvptree2 . Anda dapat mengutak -atik parameter pengujian di file, tes/run_mvptree2.cpp.

Pemrograman

Gunakan file header template. Pertama, buat tipe data khusus. Contoh disediakan di bawah 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);
	}
	
};

Tipe data khusus harus memberikan kontraktor salin, operator penugasan, dan implementasi fungsi jarak.

Selanjutnya, gunakan kelas templated:

 #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);

Untuk detail lebih lanjut, lihat program di direktori tes.

Memasang

 cmake .
make
make test
make install