hftrie

Hftrie

Una estructura de datos dinámico para indexar códigos binarios de 64 bits para la búsqueda eficiente de vecinos más cercanos. El índice ofrece la capacidad de agregar, eliminar y alcanzar la búsqueda de todos los puntos dentro de un radio dado de un punto de destino.

Descripción

El HFTRIE es una estructura de datos donde los elementos indexados, o puntos de datos, se tratan como una secuencia de bits. Cada capa del TRIE clasifica los puntos de datos de acuerdo con una parte de prefijo de bits. Por ejemplo, la capa uno clasifica el punto de datos en un subnodo correspondiente al valor de su primer bit. La segunda capa clasifica los puntos de datos en el subnodo para el valor de sus primeros dos bits. Etcétera.

 TD de diagrama de flujo
		  raíz [r] -> l [0xxx]
		  raíz [r] -> r [1xxx]
		  L -> ll [00xx]
		  L --- RR [01xx]
		  R -> ll_ [10xx]
		  R -> rr_ [11xx]

Esa es la idea básica, pero para la eficiencia, los bits están juntos. Entonces, en lugar de considerar solo un bit por nivel, se usan múltiples bits (p. Ej. Esto naturalmente aumenta la previsión de cada nodo. Para dos bits por capa, cada nodo se ordenará en cuatro posibles nodos infantiles. Para 4 bits por capa, hay 16 posibles nodos infantiles. Etcétera.

Actuación

Estas son las métricas de rendimiento para el HFTRIE para varios tamaños de índice. Los tiempos de inserción y consulta son los tiempos promedio que se necesitan para insertar o consultar el índice. Las operaciones de consulta son para el número promedio de cálculos de distancia realizados para una búsqueda de rango, normalizado al tamaño del índice y expresado como porcentaje. La última columna es para el porcentaje de recuperación, o la proporción promedio del clúster que debe devolverse con cada consulta. El rango rápido se sacrifica un poco en precisión para un aumento significativo en la eficiencia de la velocidad.

Búsqueda de rango rápido

norte	Memorando	Tiempo de insertar	Consulta Opers.	Tiempo de consulta	Recordar
100k	4.0 MB	135 ns	0.97%	37.1 μs	87.2%
200K	6.5Mb	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	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 ms	85.2%
32m	1.2GB	538 ns	0.09%	3.27 ms	86.4%
64m	1.9GB	613 ns	0.09%	5.21 ms	86.4%
128m	4.3GB	674 ns	0.08%	7.39 ms	92.4%

Para un tamaño de índice constante, n = 4m, el rendimiento de la consulta varía para diferentes valores de radio. Se garantiza una mejor precisión para búsquedas de radio más bajos con reducciones modestas en precisión para búsquedas de rango más grande.

Radio	Consulta Opers.	Tiempo de consulta	Recordar
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%

Búsqueda de rango estándar

Una búsqueda de rango estándar garantiza la precisión de la consulta con costos adicionales significativos para acelerar.

norte	Memorando	Tiempo de insertar	Consulta Opers.	Tiempo de consulta	Recordar
100k	4.0 MB	134 ns	89.5%	3.40 ms	100%
200K	6.5Mb	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	127MB	327 ns	58.6%	111 ms	100%
8m	268MB	363 ns	51.2%	191 MS	100%
16m	727mb	457 ns	29.0%	454 ms	100%
32m	1.2GB	533 ns	27.1%	783 MS	100%
64m	1.9GB	604 ns	27.0%	1.29 s	100%
128m	4.3GB	665 ns	22.8%	1.95 s	100%

Comparación

Aquí hay una comparación de diferentes métodos para indexar un conjunto de datos distribuidos uniformes de 4 millones. Operaciones de consulta señala el número de cálculos de distancia realizados por consulta, normalizado al tamaño del conjunto de datos. Todas las consultas de búsqueda se realizan para un radio = 10. Tenga en cuenta que todos los métodos tienen un rendimiento inferior a una búsqueda secuencial simple en un radio tan grande. Solo la búsqueda de rango rápido de HFTRIE supera la búsqueda secuencial con el inconveniente de que solo puede lograr el 85% de recuperación de todos los objetos de clúster para un radio extendido. Sin embargo, se garantiza que devolverá todas las coincidencias exactas para búsquedas de rango más pequeñas.

Para el tamaño del conjunto de datos, n = 4m y el radio de consulta = 10:

Método	Memorando	Tiempo de insertar	Consulta Opers.	Tiempo de consulta	Recordar
SequentialSearch	64 MB	n / A	100%	9.08 ms	100%
Mvptree	2.67GB	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-rápido	124 MB	330 ns	0.30%	618 μs	85.6%

Puede ejecutar estas pruebas con el programa compilado runhftrie . Vea la fuente en Tests/Run_Hftrie.cpp.

Instalar

 cmake .
make
make test
make install

API simple

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