hftrie

hftrie

効率的な近隣検索のための64ビットバイナリコードをインデックス作成するための動的なデータ構造。インデックスは、ターゲットポイントの特定の半径内のすべてのポイントを追加、削除、および範囲の検索を提供する機能を提供します。

説明

HFTRIEは、イン​​デックス付き要素またはデータポイントがビットのシーケンスとして扱われるデータ構造です。 Trieの各層は、ビットのプレフィックス部分に従ってデータポイントをソートします。たとえば、レイヤー1つは、データポイントを最初のビットの値に対応するサブノードにソートします。 2番目のレイヤーは、最初の2ビットの値に対してデータポイントをサブノードに並べ替えます。等々。

フローチャートTD
		  root [r]  - > l [0xxx]
		  root [r]  - > r [1xxx]
		  l-> ll [00xx]
		  L --- RR [01xx]
		  r-> ll_ [10xx]
		  r-> rr_ [11xx]

それが基本的なアイデアですが、効率のために、ビットは一緒に噛まれます。したがって、レベルごとに1ビットのみを考慮する代わりに、各レベルのビットシーケンスから複数のビット（4）を使用して、子ノードに分類します。これにより、各ノードのファンアウトが自然に増加します。レイヤーごとに2ビットの場合、各ノードは4つの可能な子ノードに分類されます。レイヤーあたり4ビットの場合、16の可能性のある子ノードがあります。等々。

パフォーマンス

さまざまなインデックスサイズのHFTRIEのパフォーマンスメトリックを以下に示します。挿入時間とクエリの時間は、インデックスを挿入またはクエリするのにかかる平均時間です。クエリ操作は、範囲検索に対して実行される距離計算の平均数、インデックスのサイズに正規化され、パーセンテージとして表されます。最後の列は、リコール率、または各クエリで返す必要があるクラスターの平均割合です。高速範囲の検索は、速度効率を大幅に向上させるために少し正確に犠牲になります。

高速範囲検索

n	メム	時間を挿入します	クエリOpers。	クエリ時間	想起
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.75ミリ秒	85.2％
32m	1.2GB	538 ns	0.09％	3.27ミリ秒	86.4％
64m	1.9GB	613 ns	0.09％	5.21 ms	86.4％
128m	4.3GB	674 ns	0.08％	7.39ミリ秒	92.4％

一定のインデックスサイズ、n = 4mの場合、クエリのパフォーマンスは半径の値が異なります。より低い範囲検索の精度がわずかに減少すると、より低い半径検索の精度が保証されます。

半径	クエリOpers。	クエリ時間	想起
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	メム	時間を挿入します	クエリOpers。	クエリ時間	想起
100k	4.0MB	134 ns	89.5％	3.40ミリ秒	100％
200k	6.5MB	142 ns	89.5％	6.54ミリ秒	100％
400k	12MB	169 ns	86.7％	11.7ミリ秒	100％
800k	35MB	238 ns	65.7％	30.4ミリ秒	100％
1m	45MB	257 ns	60.7％	39.7ミリ秒	100％
2m	75MB	295 ns	58.8％	68.5ミリ秒	100％
4m	127MB	327 ns	58.6％	111ミリ秒	100％
8m	268MB	363 ns	51.2％	191ミリ秒	100％
16m	727MB	457 ns	29.0％	454ミリ秒	100％
32m	1.2GB	533 ns	27.1％	783ミリ秒	100％
64m	1.9GB	604 ns	27.0％	1.29 s	100％
128m	4.3GB	665 ns	22.8％	1.95秒	100％

比較

以下は、400万の均一な分散データセットをインデックス作成するさまざまな方法の比較です。クエリ操作には、データセットのサイズに正規化されたクエリごとに実行される距離計算数が記録されています。すべての検索クエリは、半径= 10に対してpeformedされます。すべてのメソッドは、このような大きな半径での単純なシーケンシャル検索を下回っていることに注意してください。 HFTRIEの高速範囲検索のみが、延長された半径のすべてのクラスターオブジェクトの85％のリコールしか達成できないという欠点でシーケンシャル検索を上回ります。ただし、より小さな範囲の検索ですべての正確な一致を返すことが保証されています。

データセットサイズの場合、n = 4mおよびクエリ半径= 10：

方法	メム	時間を挿入します	クエリOpers。	クエリ時間	想起
SequentialSearch	64MB	n/a	100％	9.08ミリ秒	100％
mvptree	2.67GB	43.9μs	25.0％	276ミリ秒	100％
Mtree	113MB	631ns	69.5％	68.2 ms	100％
hwtree	312MB	1.69μs	17.6％	222ミリ秒	100％
hftrie-std	124MB	327 ns	58.6％	111ミリ秒	100％
hftrie-fast	124MB	330 ns	0.30％	618μs	85.6％

コンパイルされたプログラムrunhftrieでこれらのテストを実行できます。テストでソースを表示/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);