mvptree

MVPTree (โครงสร้างข้อมูลต้นไม้จุดได้เปรียบหลายจุด)

โครงสร้างข้อมูลตามระยะทางสำหรับการจัดทำดัชนีของข้อมูลหลายมิติ MVPTree ดัชนีวัตถุเวกเตอร์ตามระยะทางจากจุดได้เปรียบเลือกที่เลือกโดยตรงจากข้อมูลที่จัดทำดัชนี

การทดสอบประสิทธิภาพ

การทดสอบต่อไปนี้วัดเวลาการสร้างและการสืบค้นสำหรับขนาดดัชนีต่างๆ จุดข้อมูลเป็นวัตถุเวกเตอร์ที่มีค่าจริง 16 มิติ (กระจายอย่างอิสระ) การดำเนินการสร้างสะท้อนจำนวนการดำเนินการระยะทางที่จำเป็นในการสร้างต้นไม้ ในทำนองเดียวกันการดำเนินการแบบสอบถามคือจำนวนเฉลี่ยของการดำเนินการระยะทางในการสืบค้นดัชนีสำหรับรัศมีคงที่ 0.04 ทั้งการสร้างและการสืบค้นจะถูกทำให้เป็นมาตรฐานตามขนาดของต้นไม้และแสดงเป็นเปอร์เซ็นต์ แต่ละบรรทัดในแผนภูมิคือค่าเฉลี่ยของการทดลอง 5 ครั้งซึ่งโครงสร้างต้นไม้ถูกสร้างขึ้นโดยสอบถาม 10 กลุ่ม 10 คะแนนจากนั้นนำลง

n	เมม	สร้าง opers	สร้างเวลา	คำถามแบบสอบถาม	เวลาสอบถาม
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

นี่คือสถิติการสืบค้นสำหรับขนาดรัศมีต่างๆและขนาดดัชนีคงที่ของ n = 1,000,000:

รัศมี	คำถามแบบสอบถาม	เวลาสอบถาม
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

หากต้องการลองด้วยตัวคุณเองให้เรียกใช้โปรแกรมทดสอบ, runmvptree2 คุณสามารถเล่นซอกับพารามิเตอร์ทดสอบในไฟล์การทดสอบ/run_mvptree2.cpp

การเขียนโปรแกรม

ใช้ไฟล์ส่วนหัวเทมเพลต ขั้นแรกให้สร้างประเภทข้อมูลที่กำหนดเอง ตัวอย่างมีให้ภายใต้ 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);
	}
	
};

ชนิดข้อมูลที่กำหนดเองจะต้องจัดเตรียมการคัดลอกตัวควบคุมผู้ดำเนินการที่ได้รับมอบหมายและการใช้งานฟังก์ชั่นระยะทาง

ถัดไปใช้คลาส 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);

สำหรับรายละเอียดเพิ่มเติมดูโปรแกรมในไดเรกทอรีการทดสอบ

ติดตั้ง

 cmake .
make
make test
make install