mvptree

mvptree（複数のvantage pointツリーデータ構造）

多次元データのインデックス作成の距離ベースのデータ構造。 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の一定のインデックスサイズは次のとおりです。

半径	クエリOpers。	クエリ時間
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);

詳細については、Tests Directoryのプログラムを参照してください。

インストール

 cmake .
make
make test
make install