hftrie

Hftrie

Struktur data dinamis untuk mengindeks kode biner 64-bit untuk pencarian tetangga terdekat yang efisien. Indeks ini menawarkan kemampuan untuk menambah, menghapus, dan jangkauan pencarian semua titik dalam radius titik target yang diberikan.

Keterangan

HFTRIE adalah struktur data di mana elemen yang diindeks - atau titik data - diperlakukan sebagai urutan bit. Setiap lapisan trie mengurutkan titik data sesuai dengan bagian awalan bit. Misalnya, Layer One mengurutkan titik data menjadi subnode yang sesuai dengan nilai bit pertama. Lapisan kedua mengurutkan titik data ke subnode untuk nilai dua bit pertama. Dan sebagainya.

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

Itulah ide dasarnya, tetapi untuk efisiensi, bit dipotong bersama. Jadi, alih -alih mempertimbangkan hanya satu bit per level, beberapa bit (misalnya 4) digunakan dari urutan bit di setiap level untuk memilah menjadi node anak. Ini secara alami meningkatkan fanout dari setiap node. Untuk dua bit per lapisan, setiap node akan mengurutkan menjadi empat node anak yang mungkin. Untuk 4 bit per lapisan, ada 16 node anak yang mungkin. Dan sebagainya.

Pertunjukan

Berikut adalah metrik kinerja untuk hftrie untuk berbagai ukuran indeks. Waktu sisipan dan kueri adalah waktu rata -rata yang diperlukan untuk memasukkan atau meminta indeks. Operasi kueri adalah untuk jumlah rata -rata perhitungan jarak yang dilakukan untuk pencarian rentang, dinormalisasi dengan ukuran indeks dan dinyatakan sebagai persentase. Kolom terakhir adalah untuk persentase penarikan, atau proporsi rata -rata cluster yang harus dikembalikan dengan setiap kueri. Pencarian rentang cepat sedikit akurasi untuk meningkatkan efisiensi kecepatan yang signifikan.

Pencarian Rentang Cepat

N	Mem	Masukkan waktu	Opers kueri.	Waktu permintaan	Mengingat
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 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%

Untuk ukuran indeks konstan, n = 4m, kinerja kueri bervariasi untuk nilai radius yang berbeda. Akurasi yang lebih baik dijamin untuk pencarian radius yang lebih rendah dengan pengurangan sederhana dalam akurasi untuk pencarian rentang yang lebih besar.

Radius	Opers kueri.	Waktu permintaan	Mengingat
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%

Pencarian rentang standar

Pencarian rentang standar menjamin akurasi kueri dengan biaya tambahan yang signifikan.

N	Mem	Masukkan waktu	Opers kueri.	Waktu permintaan	Mengingat
100K	4.0MB	134 ns	89,5%	3,40 ms	100%
200k	6.5MB	142 ns	89,5%	6,54 ms	100%
400K	12MB	169 ns	86,7%	11,7 ms	100%
800K	35MB	238 ns	65,7%	30,4 ms	100%
1m	45MB	257 ns	60,7%	39,7 ms	100%
2m	75MB	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%

Perbandingan

Berikut adalah perbandingan berbagai metode pengindeksan set data terdistribusi seragam sebesar 4 juta. Operasi kueri mencatat jumlah perhitungan jarak yang dilakukan per kueri, dinormalisasi dengan ukuran dataset. Semua kueri pencarian diputuskan untuk radius = 10. Perhatikan bahwa semua metode berkinerja buruk dalam pencarian berurutan sederhana pada radius yang begitu besar. Hanya pencarian rentang cepat HFTRIE mengungguli pencarian berurutan dengan kelemahan bahwa ia hanya mampu mencapai penarikan 85% dari semua objek cluster untuk radius yang diperluas. Namun, dijamin akan mengembalikan semua kecocokan yang tepat untuk pencarian rentang yang lebih kecil.

Untuk ukuran kumpulan data, n = 4m dan jari -jari kueri = 10:

Metode	Mem	Masukkan waktu	Opers kueri.	Waktu permintaan	Mengingat
SequentialSearch	64MB	n/a	100%	9.08 ms	100%
Mvptree	2.67GB	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-cepat	124MB	330 ns	0,30%	618 μs	85,6%

Anda dapat menjalankan tes ini dengan program yang dikompilasi runhftrie . Lihat sumber dalam tes/run_hftrie.cpp.

Memasang

 cmake .
make
make test
make install

API Sederhana

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