hftrie

hftrie

효율적인 가장 가까운 이웃 검색을위한 64 비트 바이너리 코드를 색인화하기위한 동적 데이터 구조. 이 인덱스는 대상 지점의 주어진 반경 내의 모든 지점을 추가, 삭제 및 범위 검색 할 수있는 기능을 제공합니다.

설명

HFTRIE는 인덱스 된 요소 또는 데이터 포인트가 일련의 비트로 취급되는 데이터 구조입니다. 트리의 각 층은 비트의 접두사 부분에 따라 데이터 포인트를 정렬합니다. 예를 들어, 레이어는 데이터 포인트를 첫 번째 비트의 값에 해당하는 서브 노드로 정렬합니다. 두 번째 층은 처음 두 비트의 값에 대한 데이터 포인트를 서브 노드로 정렬합니다. 등.

 흐름도 TD
		  루트 [r] -> l [0xxx]
		  루트 [r] -> r [1xxx]
		  l-> ll [00xx]
		  L --- RR [01XX]
		  r-> ll_ [10xx]
		  r-> rr_ [11xx]

그것이 기본적인 아이디어이지만 효율성을 위해 비트는 함께 뭉쳐집니다. 따라서 레벨 당 하나의 비트 만 고려하는 대신 각 레벨의 비트 시퀀스에서 여러 비트 (예 : 4)를 사용하여 하위 노드로 정렬합니다. 이것은 자연스럽게 각 노드의 팬 아웃을 증가시킵니다. 레이어 당 2 비트의 경우 각 노드는 4 개의 가능한 하위 노드로 정렬됩니다. 층당 4 비트의 경우 16 개의 가능한 하위 노드가 있습니다. 등.

성능

다음은 다양한 인덱스 크기에 대한 HFTRIE의 성능 메트릭입니다. 삽입 및 쿼리 시간은 인덱스를 삽입하거나 쿼리하는 데 걸리는 평균 시간입니다. 쿼리 작업은 범위 검색에 대해 수행되는 평균 거리 계산 수에 대한 것이며 인덱스 크기로 정규화되고 백분율로 표현됩니다. 마지막 열은 리콜 백분율 또는 각 쿼리와 함께 반환 해야하는 클러스터의 평균 비율입니다. 빠른 범위 검색은 속도 효율을 크게 향상시키기 위해 약간의 정확도를 희생합니다.

빠른 범위 검색

N	밈	시간을 삽입하십시오	쿼리가 열립니다.	쿼리 시간	상기하다
100k	4.0MB	135 ns	0.97%	37.1 μs	87.2%
200k	6.5MB	146 ns	0.96%	72.9 μs	89.4%
400K	12MB	172 ns	0.89%	124 μs	88.2%
800K	35MB	241 ns	0.43%	206 μs	86.2%
1m	45MB	263 ns	0.34%	250 μs	86.0%
2m	75MB	297 ns	0.30%	387 μs	86.2%
4m	127MB	330 ns	0.30%	618 μs	85.6%
8m	268MB	373 ns	0.25%	953 μs	85.0%
16m	727MB	461 ns	0.11%	1.75ms	85.2%
32m	1.2GB	538 ns	0.09%	3.27ms	86.4%
64m	1.9GB	613 ns	0.09%	5.21ms	86.4%
128m	4.3GB	674 ns	0.08%	7.39ms	92.4%

일정한 인덱스 크기의 경우 n = 4m의 경우 쿼리 성능은 반경 값마다 다릅니다. 더 넓은 범위 검색의 정확도가 약간 줄어든 반경 검색이 적을수록 정확도가 향상됩니다.

반지름	쿼리가 열립니다.	쿼리 시간	상기하다
0	0.0003%	1.46 μs	100%
2	0.02%	49.0 μs	99.8%
4	0.02%	434 μs	96.6%
6	0.30%	613 μs	93.4%
8	0.30%	617 μs	88.6%
10	0.30%	616 μs	83.2%
12	0.30%	619 μs	88.8%

표준 범위 검색

표준 범위 검색은 속도가 상당한 추가 비용으로 쿼리 정확도를 보장합니다.

N	밈	시간을 삽입하십시오	쿼리가 열립니다.	쿼리 시간	상기하다
100k	4.0MB	134 ns	89.5%	3.40ms	100%
200k	6.5MB	142 ns	89.5%	6.54ms	100%
400K	12MB	169 ns	86.7%	11.7ms	100%
800K	35MB	238 ns	65.7%	30.4ms	100%
1m	45MB	257 ns	60.7%	39.7ms	100%
2m	75MB	295 ns	58.8%	68.5ms	100%
4m	127MB	327 ns	58.6%	111ms	100%
8m	268MB	363 ns	51.2%	191ms	100%
16m	727MB	457 ns	29.0%	454ms	100%
32m	1.2GB	533 ns	27.1%	783ms	100%
64m	1.9GB	604 ns	27.0%	1.29 s	100%
128m	4.3GB	665 ns	22.8%	1.95 s	100%

비교

다음은 4 백만의 균일 한 분산 데이터 세트를 색인화하는 다양한 방법을 비교하는 것입니다. 쿼리 작업에 따르면 쿼리 당 수행되는 거리 계산의 수는 데이터 세트의 크기로 정규화됩니다. 모든 검색 쿼리는 RADIUS = 10에 대해 성형되어 있습니다. 모든 메소드는 이러한 큰 반경에서 간단한 순차적 검색을 저조합니다. HFTRIE의 빠른 범위 검색 만 확장 반경에 대해 모든 클러스터 객체의 85% 리콜 만 달성 할 수 있다는 단점으로 순차적 검색보다 우수합니다. 그러나 더 작은 범위 검색의 모든 정확한 일치를 반환해야합니다.

데이터 세트 크기의 경우 n = 4m 및 쿼리 반경 = 10 :

방법	밈	시간을 삽입하십시오	쿼리가 열립니다.	쿼리 시간	상기하다
순차적 인 검색	64MB	N/A	100%	9.08ms	100%
MVPTREE	2.67GB	43.9μs	25.0%	276ms	100%
Mtree	113MB	631ns	69.5%	68.2ms	100%
hwtree	312MB	1.69 μs	17.6%	222ms	100%
hftrie-std	124MB	327 ns	58.6%	111ms	100%
hftrie-fast	124MB	330 ns	0.30%	618 μs	85.6%

컴파일 된 프로그램 runhftrie 로이 테스트를 실행할 수 있습니다. Tests/run_hftrie.cpp에서 소스를 봅니다.

설치하다

 cmake .
make
make test
make install

간단한 API

 HFTrie trie;

long long id;
uint64_t code;

// insert an element
trie.Insert({ id, code });

// delete an element
trie.Delete({ id, code });


uint64_t target;
int radius = 10;
vector<hf_t> results trie.RangeSearch(target, radius);

size_t sz = trie.Size();

size_t nbytes = trie.MemoryUsage();

// for debugging
trie.Print(cout);