mvptree

MVPTree (структура данных многомерных точек зрения)

Структура данных на расстоянии для индексации многомерных данных. Векторные объекты MVPTree Индексы в соответствии с его расстоянием от избранных точек зрения, выбранных непосредственно из индексированных данных.

Производительные тесты

Следующие тесты измеряют время сборки и запроса для различных размеров индекса. Точки данных представляют собой 16-мерную реальную векторную объект (единый независимо распределенный). Операции сборки отражают количество дистанционных операций, необходимых для построения дерева. Аналогичным образом, операции запроса являются средним количеством операций на расстоянии, чтобы запросить индекс для постоянного радиуса 0,04. Операции как строительства, так и запроса нормализованы до размера дерева и выражаются в процентах. Каждая линия на графике представляет собой среднее значение 5 пробных прогонов, где строится структура дерева, запрашивается на 10 кластеров из 10 баллов, а затем сбита.

Не	Мем	Построить Opers	Построить время	Запрос Opers	Время запроса
100 тыс	122 МБ	2554%	21,4 мкс	0,0087%	42,4 мкс
200k	289 МБ	2693%	26,3 мкс	0,0048%	63,4 мкс
400K	548 МБ	2792%	36,8 мкс	0,0022%	70,2 мкс
800K	963 МБ	2872%	59,4 мкс	0,0012%	86,0 мкс
1 м	1,1 ГБ	2899%	62,9 мкс	0,0010%	107 мкс
2м	2,7 ГБ	3021%	79,6 мкс	0,0005%	163 мкс
4 м	5,5 ГБ	3139%	101 мкс	0,0002%	242 мкс

Вот статистика запроса для различных размеров радиуса и постоянный размер индекса n = 1 000 000:

радиус	Запрос Opers.	Время запроса
0,02	0,00094%	30,9 мкс
0,04	0,00092%	121 мкс
0,06	0,0012%	359 мкс
0,08	0,00041%	971 мкс
0,10	0,0241%	2,67 мкс

Чтобы попробовать это сами, запустите тестовую программу, runmvptree2 . Вы можете возиться с параметрами теста в файле, Tests/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);
	}
	
};

Пользовательский тип данных должен предоставить копию контрактора, оператор назначения и реализацию функции расстояния.

Далее используйте шаблон класса:

 #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