hftrie

Hftrie

Eine dynamische Datenstruktur zur Indizierung von 64-Bit-Binärcodes für eine effiziente Suche nach der nächsten Nachbarn. Der Index bietet die Fähigkeit, die Suche nach allen Punkten innerhalb eines bestimmten Radius eines Zielpunkts hinzuzufügen, zu löschen und zu retten.

Beschreibung

Die Hftrie ist eine Datenstruktur, in der die indizierten Elemente - oder Datenpunkte - als Folge von Bits behandelt werden. Jede Schicht des Tries sortiert die Datenpunkte nach einem Präfixabschnitt der Bits. Layer One sortiert beispielsweise den Datenpunkt in einen Subnode, der dem Wert seines ersten Bits entspricht. Die zweite Ebene sortiert die DataPoints in den Subnode für den Wert ihrer ersten beiden Bits. Und so weiter.

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

Das ist die Grundidee, aber für die Effizienz werden die Bits zusammengeknackt. Anstatt nur ein Bit pro Level zu berücksichtigen, werden mehrere Bits (z. B. 4) aus der Bitsequenz auf jeder Ebene verwendet, um in untergeordnete Knoten zu sortieren. Dies erhöht natürlich den Fanout jedes Knotens. Bei zwei Bits pro Schicht sortiert jeder Knoten in vier mögliche Kinderknoten. Für 4 Bit pro Schicht gibt es 16 mögliche Kinderknoten. Und so weiter.

Leistung

Hier sind die Leistungsmetriken für die HFTRIE für verschiedene Indexgrößen. Die Einfügungs- und Abfragezeiten sind die durchschnittlichen Zeiten, die zum Einfügen oder Abfragen des Index benötigt werden. Abfragevorgänge sind für die durchschnittliche Anzahl von Entfernungsberechnungen für eine Reichweite, die auf die Größe des Index normalisiert und als Prozentsatz ausgedrückt wird. Die letzte Spalte ist für den Rückrufanteil oder für den durchschnittlichen Anteil des Clusters, der mit jeder Abfrage zurückgegeben werden sollte. Die Fast -Range -Suche ist ein wenig Genauigkeit für einen erheblichen Schub der Geschwindigkeitseffizienz.

Schnelle Reichweite

N	Mem	Zeit einfügen	Abfragen Opers.	Abfragestunde	Abrufen
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	12mb	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%
32 m	1,2 GB	538 ns	0,09%	3,27 ms	86,4%
64 m	1,9 GB	613 ns	0,09%	5.21 ms	86,4%
128 m	4,3 GB	674 ns	0,08%	7,39 ms	92,4%

Für eine konstante Indexgröße n = 4m variiert die Abfrageleistung für verschiedene Radiuswerte. Eine bessere Genauigkeit ist für niedrigere Radius -Suchvorgänge mit bescheidener Genauigkeit bei größeren Reichweite garantiert.

Radius	Abfragen Opers.	Abfragestunde	Abrufen
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%

Standard -Reichweite

Eine Standard -Reichweite garantiert die Abfragegenauigkeit mit erheblichen zusätzlichen Kosten für die Geschwindigkeit.

N	Mem	Zeit einfügen	Abfragen Opers.	Abfragestunde	Abrufen
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	12mb	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%
32 m	1,2 GB	533 ns	27,1%	783 ms	100%
64 m	1,9 GB	604 ns	27,0%	1,29 s	100%
128 m	4,3 GB	665 ns	22,8%	1,95 s	100%

Vergleich

Hier finden Sie einen Vergleich verschiedener Methoden zur Indexierung eines einheitlichen verteilten Datensatzes von 4 Millionen. Abfragebetriebe stellt fest, dass die Anzahl der pro Abfrage durchgeführten Entfernungsberechnungen auf die Größe des Datensatzes normalisiert wird. Alle Suchabfragen werden für einen Radius = 10 geformt. Beachten Sie, dass alle Methoden eine einfache sequenzielle Suche bei einem so großen Radius unterdurchschnittlich beeinflussen. Nur die Fast -Range -Suche des Hftrie übertrifft die sequentielle Suche mit dem Nachteil, dass sie nur 85% aller Clusterobjekte für einen erweiterten Radius abrufen kann. Es ist jedoch garantiert, dass alle exakten Übereinstimmungen für kleinere Reichweite gesucht werden.

Für die Datensatzgröße, n = 4m und Abfrageradius = 10:

Verfahren	Mem	Zeit einfügen	Abfragen Opers.	Abfragestunde	Abrufen
Sequentielle Suche	64 MB	n / A	100%	9.08 ms	100%
Mvptree	2,67 GB	43,9 μs	25,0%	276 ms	100%
Mtree	113MB	631ns	69,5%	68,2 ms	100%
Hwtree	312mb	1,69 μs	17,6%	222 ms	100%
Hftrie-std	124MB	327 ns	58,6%	111 ms	100%
Hftrie-Fast	124MB	330 ns	0,30%	618 μs	85,6%

Sie können diese Tests mit dem kompilierten Programm runhftrie ausführen. Zeigen Sie die Quelle in Tests an/run_hftrie.cpp.

Installieren

 cmake .
make
make test
make install

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