hftrie

Hftrie

Une structure de données dynamique pour indexer les codes binaires 64 bits pour la recherche efficace de voisin le plus proche. L'index offre la capacité d'ajouter, de supprimer et de rechercher tous les points dans un rayon donné d'un point cible.

Description

Le HFTrie est une structure de données où les éléments indexés - ou les points de données - sont traités comme une séquence de bits. Chaque couche du Trie trie les points de données en fonction d'une partie préfixe des bits. Par exemple, la couche One trie le point de données dans une sous-noeud correspondant à la valeur de son premier bit. La deuxième couche trie les points de données dans la sous-noeud pour la valeur de ses deux premiers bits. Et ainsi de suite.

 Organigramme TD
		  root [r] -> l [0xxx]
		  root [r] -> r [1xxx]
		  L -> ll [00xx]
		  L --- rr [01xx]
		  R -> ll_ [10xx]
		  R -> rr_ [11xx]

C'est l'idée de base, mais pour l'efficacité, les bits sont en train de secouer ensemble. Ainsi, au lieu de considérer un seul bit par niveau, plusieurs bits (par exemple 4) sont utilisés à partir de la séquence de bits à chaque niveau pour trier les nœuds enfants. Cela augmente naturellement le fanout de chaque nœud. Pour deux bits par couche, chaque nœud tarira en quatre nœuds enfants possibles. Pour 4 bits par couche, il y a 16 nœuds enfants possibles. Et ainsi de suite.

Performance

Voici les métriques de performance de la HFTrie pour diverses tailles d'index. Les temps d'insertion et de requête sont les temps moyens nécessaires pour insérer ou interroger l'index. Les opérations de requête concernent le nombre moyen de calculs de distance effectués pour une recherche de plage, normalisé à la taille de l'indice et exprimé en pourcentage. La dernière colonne concerne le pourcentage de rappel, ou la proportion moyenne du cluster qui doit être retournée à chaque requête. La recherche rapide se sacrifie un peu de précision pour une augmentation significative de l'efficacité de la vitesse.

Recherche de plage rapide

N	Mem	Insérer	Requête OPERS.	Temps de requête	Rappel
100k	4,0 Mo	135 ns	0,97%	37,1 μs	87,2%
200K	6,5 Mo	146 ns	0,96%	72,9 μs	89,4%
400k	12 Mo	172 ns	0,89%	124 μs	88,2%
800k	35 Mo	241 ns	0,43%	206 μs	86,2%
1m	45 Mo	263 ns	0,34%	250 μs	86,0%
2m	75 Mo	297 ns	0,30%	387 μs	86,2%
4m	127 Mo	330 ns	0,30%	618 μs	85,6%
8m	268 Mo	373 ns	0,25%	953 μs	85,0%
16m	727 Mo	461 ns	0,11%	1,75 ms	85,2%
32m	1,2 Go	538 ns	0,09%	3,27 ms	86,4%
64m	1,9 Go	613 ns	0,09%	5,21 ms	86,4%
128m	4,3 Go	674 ns	0,08%	7,39 ms	92,4%

Pour une taille d'indice constante, n = 4m, la performance de la requête varie pour différentes valeurs de rayon. Une meilleure précision est garantie pour les recherches de rayon inférieures avec des réductions de précision modestes pour les recherches plus importantes.

Rayon	Requête OPERS.	Temps de requête	Rappel
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%

Recherche de plage standard

Une recherche standard garantit la précision des requêtes avec des coûts supplémentaires à vitesse supplémentaires.

N	Mem	Insérer	Requête OPERS.	Temps de requête	Rappel
100k	4,0 Mo	134 ns	89,5%	3,40 ms	100%
200K	6,5 Mo	142 ns	89,5%	6,54 ms	100%
400k	12 Mo	169 ns	86,7%	11.7 MS	100%
800k	35 Mo	238 ns	65,7%	30,4 ms	100%
1m	45 Mo	257 ns	60,7%	39,7 ms	100%
2m	75 Mo	295 ns	58,8%	68,5 ms	100%
4m	127 Mo	327 ns	58,6%	111 ms	100%
8m	268 Mo	363 ns	51,2%	191 MS	100%
16m	727 Mo	457 ns	29,0%	454 ms	100%
32m	1,2 Go	533 ns	27,1%	783 ms	100%
64m	1,9 Go	604 ns	27,0%	1,29 s	100%
128m	4,3 Go	665 ns	22,8%	1,95 s	100%

Comparaison

Voici une comparaison de différentes méthodes pour indexer un ensemble de données distribué uniforme de 4 millions. Les opérations de requête notent le nombre de calculs de distance effectués par requête, normalisés à la taille de l'ensemble de données. Toutes les requêtes de recherche sont formées pour un rayon = 10. Notez que toutes les méthodes sous-performent une simple recherche séquentielle à un si grand rayon. Seule la recherche rapide de la plage rapide de HFTrie surpasse la recherche séquentielle avec l'inconvénient qu'il n'est en mesure d'obtenir que 85% de rappel de tous les objets de cluster pour un rayon étendu. Il est cependant garanti de retourner toutes les correspondances exactes pour les recherches de plus petites plages.

Pour la taille de l'ensemble de données, n = 4m et le rayon de requête = 10:

Méthode	Mem	Insérer	Requête OPERS.	Temps de requête	Rappel
SequentialSearch	64 Mo	n / A	100%	9.08 MS	100%
Mvptree	2,67 Go	43,9 μs	25,0%	276 MS	100%
Mtree	113 Mo	631ns	69,5%	68,2 ms	100%
Hwtree	312 Mo	1,69 μs	17,6%	222 ms	100%
Hftrie-std	124 Mo	327 ns	58,6%	111 ms	100%
Hftrie-rapide	124 Mo	330 ns	0,30%	618 μs	85,6%

Vous pouvez exécuter ces tests avec le programme compilé runhftrie . Affichez la source dans Tests / Run_hftrie.cpp.

Installer

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