mvptree下载mvptree源代码下载

mvptree

其他源码

1.0.0

下载

MVPTREE（多个有利位点树数据结构）

基于距离的数据结构，用于索引多维数据。 MVPTREE根据其距离从索引数据直接选择的选择优势点的距离索引矢量对象。

绩效测试

以下测试测量了各种索引大小的构建和查询时间。数据点是16维实价矢量对象（独立分布）。构建操作反映了建造树所需的距离操作数量。同样，查询操作是查询索引的平均距离操作数量的恒定半径为0.04。构建和查询操作均标准化为树的大小，并表示为百分比。图表中的每一行都是5个试验的平均值，其中树结构是建立的，查询10点10分，然后取下。

n	mem	建立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 。您可以在文件中使用测试参数，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);

有关更多详细信息，请参阅测试目录中的程序。