mvptree

MVPTREE (بنية بيانات شجرة النقطة المتعددة)

بنية البيانات القائمة على المسافة لفهرسة البيانات متعددة الأبعاد. يقوم MVPtree بفهرسة كائنات ناقلاتها وفقًا لمسافة من نقاط التحديد المختارة مباشرة من البيانات المفهرسة.

اختبارات الأداء

الاختبارات التالية تقيس أوقات البناء والاستعلام لأحجام الفهرس المختلفة. نقاط البيانات عبارة عن كائن متجه حقيقي ذو القيمة الحقيقية 16 (موحد موزعة بشكل مستقل). تعكس عمليات البناء عدد عمليات المسافة اللازمة لبناء الشجرة. وبالمثل ، فإن عمليات الاستعلام هي متوسط ​​عدد عمليات المسافة للاستعلام عن الفهرس لنصف قطر ثابت قدره 0.04. يتم تطبيع كل من عمليات الإنشاء والاستعلام إلى حجم الشجرة والتعبير عنها كنسبة مئوية. كل سطر في الرسم البياني هو متوسط ​​5 أشواط تجريبية ، حيث يتم بناء هيكل الشجرة ، والاستعلام عن 10 مجموعات من 10 نقاط ، ثم إنزال.

ن	ميم	بناء opers	بناء الوقت	الاستعلام أوبوس	وقت الاستعلام
100 كيلو	122 ميجابايت	2554 ٪	21.4	0.0087 ٪	42.4
200k	289 ميجابايت	2693 ٪	26.3	0.0048 ٪	63.4
400 كيلو	548 ميجابايت	2792 ٪	36.8μs	0.0022 ٪	70.2μs
800k	963 ميجابايت	2872 ٪	59.4	0.0012 ٪	86.0μs
1M	1.1 جيجابايت	2899 ٪	62.9μs	0.0010 ٪	107μs
2 م	2.7 جيجابايت	3021 ٪	79.6	0.0005 ٪	163μs
4M	5.5 جيجابايت	3139 ٪	101μs	0.0002 ٪	242μs

فيما يلي إحصائيات الاستعلام لمختلف أحجام نصف القطر وحجم فهرس ثابت يبلغ ن = 1،000،000:

دائرة نصف قطرها	الاستعلام أوبوس.	وقت الاستعلام
0.02	0.00094 ٪	30.9
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