mvptree

MVPTREE (다중 Vantage Point 트리 데이터 구조)

다차원 데이터의 인덱싱을위한 거리 기반 데이터 구조. MVPTREE는 인덱스 된 데이터에서 직접 선택한 선택된 vantage 지점으로부터의 거리에 따라 벡터 객체를 인덱싱합니다.

성능 테스트

다음 테스트는 다양한 인덱스 크기의 빌드 및 쿼리 시간을 측정합니다. 데이터 포인트는 16 차원 실제 값 벡터 객체입니다 (독립적으로 분산 된 균일). 빌드 작업은 트리를 구축하는 데 필요한 거리 작업의 수를 반영합니다. 마찬가지로, 쿼리 작업은 0.04의 일정한 반경에 대한 인덱스를 쿼리하기위한 평균 거리 작업 수입니다. 빌드 및 쿼리 작업은 트리 크기로 정규화되어 백분율로 표현됩니다. 차트의 각 라인은 평균 5 개의 시험 실행이며, 여기서 트리 구조가 구축되고 10 점의 10 클러스터가 쿼리 된 다음 무너졌습니다.

N	밈	열렬한 구축	시간을 만듭니다	쿼리가 열립니다	쿼리 시간
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);
	}
	
};

사용자 정의 데이터 유형은 사본 대조공, 할당 연산자 및 거리 기능 구현을 제공해야합니다.

다음으로 템플릿 클래스를 사용하십시오.

 #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