hftrie

hftrie

用於索引64位二進制代碼的動態數據結構，用於有效的最近鄰居搜索。該索引提供了在目標點的給定半徑內添加，刪除和範圍搜索所有點的功能。

描述

HFTRIE是一個數據結構，其中索引元素（或數據點）被視為位序列。三層的每一層根據位前的前綴部分對數據點進行分類。例如，將數據點分配給對應於其第一個位值的子節點。第二層將數據點對其前兩個位的值分類為子節點。等等。

流程圖TD
		  root [r]  - > l [0xxx]
		  root [r]  - > r [1xxx]
		  l-> ll [00xx]
		  l --- RR [01xx]
		  r-> ll_ [10xx]
		  r-> rr_ [11xx]

這是一個基本的想法，但是為了效率，碎屑是在一起的。因此，從每個級別的位序列中使用多個位（例如4），而不是僅考慮每個級別的位，而是將其分類為子節點。這自然會增加每個節點的粉絲。對於每個層兩個位，每個節點將分為四個可能的子節點。對於每層4位，有16個可能的兒童節點。等等。

表現

這是HFTRIE的各種索引大小的性能指標。插入時間和查詢時間是插入或查詢索引所需的平均時間。查詢操作是針對用於範圍搜索的距離計算的平均數量，該計算標準化為索引的大小，並表示為百分比。最後一列是用於召回百分比，或每個查詢應返回的群集的平均比例。快速範圍搜索的犧牲精度有明顯提高速度效率。

快速範圍搜索

n	mem	插入時間	查詢操作。	查詢時間	記起
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毫秒	86.4％
128m	4.3GB	674 ns	0.08％	7.39毫秒	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	mem	插入時間	查詢操作。	查詢時間	記起
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 ms	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 ms	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 s	100％

比較

這是對索引統一分佈式數據集的不同方法的比較。查詢操作指出，每個查詢執行的距離計算數量，標準化為數據集的大小。所有搜索查詢均均為半徑= 10。請注意，所有方法的表現都不足以在如此大的半徑上進行簡單的順序搜索。只有HFTRIE的快速範圍搜索的表現才能優於順序搜索，因為它只能為擴展半徑的所有群集對象實現85％的回憶。但是，可以保證為較小的範圍搜索返回所有精確匹配。

對於數據集大小，n = 4m，查詢半徑= 10：

方法	mem	插入時間	查詢操作。	查詢時間	記起
sequentialSearch	64MB	N/A。	100％	9.08毫秒	100％
mvptree	2.67GB	43.9μs	25.0％	276毫秒	100％
姆特里	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 ms	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);