hftrie

Hftrie

Uma estrutura de dados dinâmicos para indexar códigos binários de 64 bits para uma pesquisa vizinha mais próxima eficiente. O índice oferece a capacidade de adicionar, excluir e ranger pesquisar todos os pontos dentro de um determinado raio de um ponto de destino.

Descrição

O HFTRIE é uma estrutura de dados em que os elementos indexados - ou pontos de dados - são tratados como uma sequência de bits. Cada camada do trie classifica os pontos de dados de acordo com uma parte do prefixo dos bits. Por exemplo, a camada um classifica o ponto de dados em um subnodo correspondente ao valor de seu primeiro bit. A segunda camada classifica os pontos de dados no subnodo para o valor de seus dois primeiros bits. E assim por diante.

 Fluxograma TD
		  raiz [r] -> l [0xxx]
		  raiz [r] -> r [1xxx]
		  L -> ll [00xx]
		  L --- RR [01XX]
		  R -> ll_ [10xx]
		  R -> rr_ [11xx]

Essa é a idéia básica, mas para a eficiência, os bits são fundidos. Portanto, em vez de considerar apenas um bit por nível, vários bits (por exemplo, 4) são usados ​​da sequência de bits em cada nível para classificar em nós filhos. Isso naturalmente aumenta a fanout de cada nó. Para dois bits por camada, cada nó classificará em quatro possíveis nós filhos. Para 4 bits por camada, existem 16 possíveis nós filhos. E assim por diante.

Desempenho

Aqui estão as métricas de desempenho para o HFTRIE para vários tamanhos de índice. Os tempos de inserção e consulta são os tempos médios necessários para inserir ou consultar o índice. As operações de consulta são para o número médio de cálculos de distância realizados para uma pesquisa de intervalo, normalizados para o tamanho do índice e expressos como uma porcentagem. A última coluna é para a porcentagem de recall ou a proporção média do cluster que deve ser retornado a cada consulta. A pesquisa rápida pesquisa um pouco de precisão para um impulso significativo na eficiência da velocidade.

Pesquisa de faixa rápida

N	Mem	Inserir tempo	Opers de consulta.	Tempo de consulta	Lembrar
100k	4,0 MB	135 ns	0,97%	37,1 μs	87,2%
200k	6,5 MB	146 ns	0,96%	72,9 μs	89,4%
400K	12 MB	172 ns	0,89%	124 μs	88,2%
800K	35 MB	241 ns	0,43%	206 μs	86,2%
1m	45 MB	263 ns	0,34%	250 μs	86,0%
2m	75 MB	297 ns	0,30%	387 μs	86,2%
4m	127 MB	330 ns	0,30%	618 μs	85,6%
8m	268 MB	373 ns	0,25%	953 μs	85,0%
16m	727 MB	461 ns	0,11%	1,75 ms	85,2%
32m	1,2 GB	538 ns	0,09%	3,27 ms	86,4%
64m	1,9 GB	613 ns	0,09%	5.21 ms	86,4%
128m	4.3 GB	674 ns	0,08%	7.39 ms	92,4%

Para um tamanho de índice constante, n = 4m, o desempenho da consulta varia para diferentes valores de raio. É garantida uma melhor precisão para pesquisas mais baixas de raio com reduções modestas na precisão para pesquisas de alcance maiores.

Raio	Opers de consulta.	Tempo de consulta	Lembrar
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%

Pesquisa de intervalo padrão

Um intervalo padrão garante precisão de consultas com custos adicionais significativos para acelerar.

N	Mem	Inserir tempo	Opers de consulta.	Tempo de consulta	Lembrar
100k	4,0 MB	134 ns	89,5%	3,40 ms	100%
200k	6,5 MB	142 ns	89,5%	6,54 ms	100%
400K	12 MB	169 ns	86,7%	11,7 ms	100%
800K	35 MB	238 ns	65,7%	30,4 ms	100%
1m	45 MB	257 ns	60,7%	39,7 ms	100%
2m	75 MB	295 ns	58,8%	68,5 ms	100%
4m	127 MB	327 ns	58,6%	111 ms	100%
8m	268 MB	363 ns	51,2%	191 MS	100%
16m	727 MB	457 ns	29,0%	454 ms	100%
32m	1,2 GB	533 ns	27,1%	783 ms	100%
64m	1,9 GB	604 ns	27,0%	1,29 s	100%
128m	4.3 GB	665 ns	22,8%	1,95 s	100%

Comparação

Aqui está uma comparação de diferentes métodos de indexação de um conjunto uniforme de dados distribuídos de 4 milhões. Operações de consulta observa o número de cálculos de distância realizados por consulta, normalizados para o tamanho do conjunto de dados. Todas as consultas de pesquisa são realizadas para um raio = 10. Observe que todos os métodos têm um desempenho inferior a uma pesquisa seqüencial simples em um raio tão grande. Somente a pesquisa rápida do HFTRIE supera a pesquisa seqüencial com a desvantagem de que ele só pode obter 85% de recall de todos os objetos de cluster para um raio estendido. No entanto, é garantido que retorne todas as correspondências exatas para pesquisas de alcance menores.

Para o tamanho do conjunto de dados, n = 4m e raio de consulta = 10:

Método	Mem	Inserir tempo	Opers de consulta.	Tempo de consulta	Lembrar
SequencialSearch	64 MB	n / D	100%	9.08 MS	100%
Mvptree	2,67 GB	43,9μs	25,0%	276 ms	100%
Mtree	113 MB	631ns	69,5%	68,2 ms	100%
Hwtree	312 MB	1,69 μs	17,6%	222 ms	100%
HFTRIE-STD	124 MB	327 ns	58,6%	111 ms	100%
Hftrie-Fast	124 MB	330 ns	0,30%	618 μs	85,6%

Você pode executar esses testes com o programa compilado runhftrie . Veja a fonte nos testes/run_hftrie.cpp.

Instalar

 cmake .
make
make test
make install

API simples

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