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);