hftrie

hftrie

โครงสร้างข้อมูลแบบไดนามิกสำหรับการจัดทำดัชนีรหัสไบนารี 64 บิตสำหรับการค้นหาเพื่อนบ้านที่ใกล้ที่สุด ดัชนีมีความสามารถในการเพิ่มลบและค้นหาช่วงสำหรับทุกจุดภายในรัศมีที่กำหนดของจุดเป้าหมาย

คำอธิบาย

HFTRIE เป็นโครงสร้างข้อมูลที่องค์ประกอบที่จัดทำดัชนี - หรือจุดข้อมูล - ถือเป็นลำดับของบิต แต่ละเลเยอร์ของ Trie เรียงลำดับจุดข้อมูลตามส่วนคำนำหน้าของบิต ตัวอย่างเช่นเลเยอร์หนึ่งเรียงลำดับจุดข้อมูลไปยังโซนย่อยที่สอดคล้องกับค่าของบิตแรก เลเยอร์ที่สองเรียงลำดับ datapoints ลงในโซนย่อยสำหรับค่าของสองบิตแรก และอื่น ๆ

 ผังงาน TD
		  รูท [r] -> l [0xxx]
		  รูท [r] -> r [1xxx]
		  l -> ll [00xx]
		  l --- rr [01xx]
		  r -> ll_ [10xx]
		  r -> rr_ [11xx]

นั่นเป็นความคิดพื้นฐาน แต่เพื่อประสิทธิภาพบิตจะถูกรวมเข้าด้วยกัน ดังนั้นแทนที่จะพิจารณาเพียงหนึ่งบิตต่อระดับจะใช้หลายบิต (เช่น 4) จากลำดับบิตในแต่ละระดับเพื่อจัดเรียงเป็นโหนดลูก สิ่งนี้จะเพิ่ม fanout ของแต่ละโหนด สำหรับสองบิตต่อเลเยอร์แต่ละโหนดจะจัดเรียงเป็นสี่โหนดลูกที่เป็นไปได้ สำหรับ 4 บิตต่อเลเยอร์มี 16 โหนดลูกที่เป็นไปได้ และอื่น ๆ

ผลงาน

นี่คือตัวชี้วัดประสิทธิภาพสำหรับ HFTRIE สำหรับขนาดดัชนีต่างๆ เวลาแทรกและแบบสอบถามเป็นเวลาเฉลี่ยที่ใช้ในการแทรกหรือสอบถามดัชนี การดำเนินการแบบสอบถามมีไว้สำหรับจำนวนการคำนวณระยะทางเฉลี่ยที่ดำเนินการสำหรับการค้นหาช่วงซึ่งปรับขนาดให้เป็นมาตรฐานของดัชนีและแสดงเป็นเปอร์เซ็นต์ คอลัมน์สุดท้ายใช้สำหรับเปอร์เซ็นต์การเรียกคืนหรือสัดส่วนเฉลี่ยของคลัสเตอร์ที่ควรส่งคืนพร้อมกับแต่ละแบบสอบถาม การค้นหาอย่างรวดเร็วในช่วงที่รวดเร็วนั้นมีความแม่นยำเล็กน้อยเพื่อเพิ่มประสิทธิภาพความเร็วอย่างมีนัยสำคัญ

การค้นหาช่วงที่รวดเร็ว

n	เมม	แทรกเวลา	คำถามแบบสอบถาม	เวลาสอบถาม	ระลึกถึง
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%

สำหรับขนาดดัชนีคงที่ n = 4m ประสิทธิภาพการสืบค้นจะแตกต่างกันไปตามค่ารัศมีที่แตกต่างกัน รับประกันความแม่นยำที่ดีกว่าสำหรับการค้นหารัศมีที่ต่ำกว่าด้วยการลดความแม่นยำเล็กน้อยสำหรับการค้นหาช่วงที่ใหญ่ขึ้น

รัศมี	คำถามแบบสอบถาม	เวลาสอบถาม	ระลึกถึง
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%

การค้นหาช่วงมาตรฐาน

การค้นหาช่วงมาตรฐานรับประกันความแม่นยำในการสืบค้นด้วยค่าใช้จ่ายที่เพิ่มขึ้นอย่างมากเพื่อเพิ่มความเร็ว

n	เมม	แทรกเวลา	คำถามแบบสอบถาม	เวลาสอบถาม	ระลึกถึง
100k	4.0MB	134 ns	89.5%	3.40 มิลลิวินาที	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 มิลลิวินาที	100%
4m	127MB	327 ns	58.6%	111 มิลลิวินาที	100%
8m	268MB	363 ns	51.2%	191 มิลลิวินาที	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%

การเปรียบเทียบ

นี่คือการเปรียบเทียบวิธีการต่าง ๆ ในการจัดทำดัชนีชุดข้อมูลแบบกระจายที่เหมือนกัน 4 ล้านชุด การดำเนินการแบบสอบถามบันทึกจำนวนการคำนวณระยะทางที่ดำเนินการต่อการสืบค้นซึ่งทำให้เป็นมาตรฐานตามขนาดของชุดข้อมูล คำค้นหาการค้นหาทั้งหมดจะถูก peformed สำหรับ radius = 10. โปรดทราบว่าวิธีการทั้งหมดมีประสิทธิภาพต่ำกว่าการค้นหาตามลำดับอย่างง่ายที่รัศมีขนาดใหญ่ เฉพาะการค้นหาช่วงที่รวดเร็วของ HFTRIE นั้นดีกว่าการค้นหาตามลำดับด้วยข้อเสียเปรียบว่าสามารถเรียกคืนวัตถุคลัสเตอร์ทั้งหมดได้ 85% สำหรับรัศมีขยาย อย่างไรก็ตามมันรับประกันได้ว่าจะส่งคืนการจับคู่ที่แน่นอนทั้งหมดสำหรับการค้นหาช่วงที่เล็กลง

สำหรับขนาดชุดข้อมูล, n = 4m และ radius แบบสอบถาม = 10:

วิธี	เมม	แทรกเวลา	คำถามแบบสอบถาม	เวลาสอบถาม	ระลึกถึง
SequentialSearch	64MB	N/A	100%	9.08 ms	100%
mvptree	2.67GB	43.9μs	25.0%	276 มิลลิวินาที	100%
mtree	113MB	631NS	69.5%	68.2 ms	100%
hwtree	312MB	1.69 μs	17.6%	222 มิลลิวินาที	100%
hftrie-std	124MB	327 ns	58.6%	111 มิลลิวินาที	100%
hftrie เร็ว	124MB	330 ns	0.30%	618 μs	85.6%

คุณสามารถเรียกใช้การทดสอบเหล่านี้ด้วยโปรแกรมที่รวบรวมได้ runhftrie ดูแหล่งที่มาในการทดสอบ/run_hftrie.cpp

ติดตั้ง

 cmake .
make
make test
make install

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