PH -tree ^{[ 1 ]}เป็นโครงสร้างข้อมูลแบบต้นไม้ที่ใช้สำหรับการจัดทำดัชนีเชิงพื้นที่ของข้อมูลหลายมิติ (คีย์) เช่น พิกัดทางภูมิศาสตร์ จุดเวกเตอร์คุณลักษณะสี่เหลี่ยมผืน หรือกล่องขอบเขต PH-tree เป็นดัชนีการแบ่งพื้นที่^{[ 2 ]}ที่มีโครงสร้างคล้ายกับquadtreeหรือoctree ^{[ 3 ]} อย่างไรก็ตาม ต่างจาก quadtree ตรง ที่ PH-tree ใช้การแบ่งตามนโยบายโดยใช้triesและคล้ายกับCrit bit treesซึ่งอิงตามการแสดงบิตของคีย์ นโยบายการแบ่งตามบิต เมื่อรวมกับการใช้การแสดงภายในที่แตกต่างกันสำหรับโหนด จะให้ความสามารถในการปรับขนาดกับข้อมูลที่มีมิติสูง นโยบายการแบ่งตามการแสดงบิตยังกำหนดความลึกสูงสุด จึงหลีกเลี่ยงต้นไม้ที่เสื่อมสภาพและความจำเป็นในการปรับสมดุลใหม่^{[ 1 ]}

PH-tree พื้นฐานเป็นดัชนีเชิงพื้นที่ที่แมปคีย์ ซึ่งเป็น เวกเตอร์ dมิติที่มีจำนวนเต็ม ไปยังค่าที่ผู้ใช้กำหนด PH-tree เป็นการขยายแบบหลายมิติของCrit bit treeในแง่ที่ว่า Crit bit tree เทียบเท่ากับ PH-tree ที่มีคีย์ d มิติ เช่นเดียวกับ Crit bit tree และแตกต่างจากดัชนีเชิงพื้นที่อื่นๆ ส่วนใหญ่ PH-tree เป็นแผนที่มากกว่าแผนที่หลายมิติ^{[ 1 ] [ 4 ]}${\displaystyle 1}$

ต้นไม้ PH มิติ dคือต้นไม้ของโหนด โดยแต่ละโหนดจะแบ่งพื้นที่ออกเป็นควอดแรนต์ (ดูด้านล่างสำหรับวิธีที่โหนดขนาดใหญ่สามารถปรับขนาดตามข้อมูลมิติสูงได้) แต่ละควอดแรนต์จะมีรายการได้ไม่เกินหนึ่งรายการซึ่งอาจเป็นคู่คีย์-ค่า (ควอดแรนต์ใบ) หรือคู่คีย์-ซับโหนด สำหรับคู่คีย์-ซับโหนด คีย์จะแสดงถึงจุดศูนย์กลางของซับโหนด คีย์ยังเป็นคำนำหน้าทั่วไป (การแสดงบิต) ของคีย์ทั้งหมดในซับโหนดและซับโหนดลูกของมัน แต่ละโหนดมีรายการอย่างน้อยสองรายการ มิฉะนั้นจะถูกรวมเข้ากับโหนดแม่^{[ 1 ]}${\displaystyle 2^{d}}$

คุณสมบัติโครงสร้างอื่นๆ ของ PH-tree ได้แก่: ^{[ 1 ]}

• พวกมันคือต้นไม้ที่มีนามสกุล -ary${\displaystyle 2^{n}}$
• โดยเนื้อแท้แล้วมันไม่สมดุลแต่ความไม่สมดุลนั้นมีขอบเขตจำกัดเนื่องจากความลึกของมันถูกจำกัดด้วยความกว้างของบิตของคีย์ เช่น 32 สำหรับคีย์มิติที่มีจำนวนเต็ม 32 บิต${\displaystyle d}$
• การดำเนินการแทรกหรือลบจะส่งผลให้มีการแก้ไขโหนดเพียงหนึ่งโหนดเท่านั้น และอาจมีการเพิ่มหรือลบโหนดที่สองได้ ซึ่งอาจเป็นประโยชน์สำหรับการใช้งานแบบขนาน นอกจากนี้ยังหมายความว่าต้นทุนในการแก้ไขจะมีความผันแปรน้อย
• โครงสร้างของพวกมันไม่ขึ้นอยู่กับลำดับการใส่/ถอดออก

เช่นเดียวกับควอดทรี ส่วนใหญ่ PH-tree เป็นลำดับชั้นของโหนด โดยแต่ละโหนดจะแบ่งพื้นที่ในมิติd ทั้งหมด ^{[ 1 ]}ดังนั้น โหนดหนึ่งสามารถมีโหนดย่อยได้มากถึงโหนดย่อย โดยแต่ละโหนดย่อยจะอยู่ในควอดแรนต์เดียวกัน ${\displaystyle 2^{d}}$

PH-tree ใช้บิตของคีย์หลายมิติเพื่อกำหนดตำแหน่งในต้นไม้ คีย์ทั้งหมดที่มีบิตนำหน้าเหมือนกันจะถูกเก็บไว้ในสาขาเดียวกันของต้นไม้^{[ 1 ]}

ตัวอย่างเช่น ในโหนดระดับLเพื่อกำหนดว่าควรแทรก (หรือลบ หรือค้นหา) คีย์ในควอดแรนต์ใด โหนดจะดูที่ บิตของ Lในแต่ละมิติของคีย์ สำหรับโหนด 3 มิติที่มี 8 ควอดแรนต์ (ประกอบเป็นลูกบาศก์) บิตของ Lในมิติแรกของคีย์จะกำหนดว่าควอดแรนต์เป้าหมายอยู่ทางซ้ายหรือขวาของลูกบาศก์ บิตของ Lในมิติที่สองจะกำหนดว่าอยู่ด้านหน้าหรือด้านหลัง และ บิตของ Lในมิติที่สามจะกำหนดว่าอยู่ด้านล่างหรือด้านบน ดูภาพประกอบ

ตัวอย่างที่มีคีย์ 1 มิติสามตัวที่มีค่า 8 บิต ได้แก่, และการเพิ่มและลงในต้นไม้ว่างเปล่าจะทำให้เกิดโหนดเดียว คีย์ทั้งสองแตกต่างกันในบิตที่ 6 ก่อน ดังนั้นโหนดจึงมีระดับ(เริ่มต้นที่ 0) โหนดมีคำนำหน้า 5 บิตที่แสดงถึง 5 บิตที่เหมือนกันของคีย์ทั้งสอง โหนดมีสองควอดแรนต์ โดยแต่ละคีย์จะถูกเก็บไว้ในควอดแรนต์หนึ่ง การเพิ่มคีย์ที่สามจะทำให้เกิดโหนดเพิ่มเติมที่ โดยควอดแรนต์หนึ่งจะมีโหนดเดิมเป็นโหนดย่อย และอีกควอดแรนต์หนึ่ง จะ มีคีย์ใหม่${\displaystyle k_{0}=\{1\}_{base\ 10}=\{00000001\}_{base\ 2}}$${\displaystyle k_{1}=\{4\__{10}=\{00000100\__{2}}$${\displaystyle k_{2}=\{35\__{10}=\{00100011\__{2}}$${\displaystyle k_{0}}$${\displaystyle k_{1}}$${\displaystyle L=5}$${\displaystyle k_{3}}$${\displaystyle L=2}$${\displaystyle k_{2}}$

สำหรับคีย์แบบ 2 มิติ แต่ละโหนดจะมีควอดแรนต์ ตำแหน่งของควอดแรนต์ที่เก็บคีย์ไว้จะถูกดึงออกมาจากบิตที่เกี่ยวข้องของคีย์ โดยดึงบิตหนึ่งบิตจากแต่ละมิติ ควอดแรนต์ทั้งสี่ของโหนดจะประกอบกันเป็นไฮเปอร์คิวบ์ 2 มิติ (ควอดแรนต์อาจว่างเปล่าก็ได้) บิตที่ดึงออกมาจากคีย์จะประกอบกันเป็นแอดเดรสของไฮเปอร์คิวบ์สำหรับและ สำหรับโดยที่ คือตำแหน่งของควอดแรนต์ในไฮเปอร์คิวบ์ของโหนดนั้น ${\displaystyle 2^{d}=4}$${\displaystyle h}$${\displaystyle k_{0}\rightarrow h=\{00\}_{2}}$${\displaystyle k_{1}\rightarrow h=\{01\}_{2}}$${\displaystyle h}$

ลำดับของรายการในโหนดจะเรียงลำดับตามลำดับ Z เสมอ รายการในโหนดสามารถจัดเก็บได้ เช่น ในอาร์เรย์ขนาดคงที่ขนาดh ซึ่งก็คือดัชนีอาร์เรย์ของควอดแรนต์นั่นเอง วิธีนี้ช่วยให้สามารถค้นหา แทรก และลบได้และไม่จำเป็นต้องจัดเก็บhอย่างไรก็ตาม ความซับซ้อนของพื้นที่คือต่อโหนด ดังนั้นจึงไม่เหมาะสมสำหรับข้อมูลที่มีมิติสูง^{[ 1 ]}${\displaystyle 2^{d}}$${\displaystyle O(1)}$${\displaystyle O(2^{d})}$

วิธีแก้ปัญหาอีกวิธีหนึ่งคือการจัดเก็บรายการไว้ในคอลเลกชันที่เรียงลำดับ เช่นอาร์เรย์แบบไดนามิกและ/หรือB-treeวิธีนี้จะทำให้การค้นหาช้าลงแต่ลดการใช้หน่วยความจำลง^{[ 1 ]}${\displaystyle O(\log {n_{node\_entries}})}$${\displaystyle O(n_{node\_entries})}$

การใช้งานดั้งเดิมมีเป้าหมายเพื่อลดการใช้หน่วยความจำให้น้อยที่สุดโดยการสลับระหว่างการแสดงอาร์เรย์แบบคงที่และแบบไดนามิก ขึ้นอยู่กับว่าแบบใดใช้หน่วยความจำน้อยกว่า^{[ 1 ]}การใช้งานอื่นๆ[1] [2]ไม่ได้สลับแบบไดนามิก แต่ใช้อาร์เรย์แบบคงที่สำหรับอาร์เรย์แบบไดนามิกสำหรับและ B-tree สำหรับข้อมูลที่มีมิติสูง ${\displaystyle d\lesssim 4}$${\displaystyle d\lesssim 8}$

การค้นหาการแทรกและ การ ลบข้อมูล ทำงานคล้ายกันมาก คือ ค้นหาโหนดที่ถูกต้อง จากนั้นจึงดำเนินการกับโหนดนั้น การ ค้นหาแบบ Window queriesและ การค้นหาแบบ k -nearest-neighborนั้นซับซ้อนกว่า

การ ดำเนินการ Lookupจะตรวจสอบว่าคีย์นั้นมีอยู่ในต้นไม้หรือไม่ โดยจะเดินลงไปตามต้นไม้และตรวจสอบทุกโหนดว่ามีซับโหนดที่เป็นไปได้หรือค่าผู้ใช้ที่ตรงกับคีย์หรือไม่^{[ 1 ]}

ฟังก์ชัน lookup(key) คือ entry ← get_root_entry() // ถ้าโครงสร้างต้นไม้ไม่ว่างเปล่า รายการรากจะมีโหนดรากอยู่ ในขณะที่ entry ไม่เท่ากับ NIL และ entry เป็นโหนดย่อย ให้ทำดังนี้ node ← entry.get_node() รายการ ← node.get_entry(key) รายการ ส่งคืนซ้ำ // รายการสามารถเป็นค่าว่างได้ 

ฟังก์ชัน get_entry(key) คือ โหนด ← โหนดปัจจุบัน h ← extract_bits_at_depth(key, node.get_depth()} รายการ ← node.get_entry_at(h) รายการ ส่งคืน // รายการสามารถเป็นค่าว่างได้ 

การ ดำเนินการ แทรกจะแทรกคู่คีย์-ค่าใหม่ลงในต้นไม้ เว้นแต่ว่าคีย์นั้นมีอยู่แล้ว การดำเนินการจะสำรวจต้นไม้เหมือนกับ ฟังก์ชัน ค้นหาจากนั้นจึงแทรกคีย์ลงในโหนด มีหลายกรณีที่ต้องพิจารณา: ^{[ 1 ]}

1. ช่องดังกล่าวว่างเปล่า และเราสามารถแทรกรายการใหม่ลงในช่องนั้นแล้วกลับไปได้เลย
2. ควอดแรนต์นั้นมีรายการที่ผู้ใช้ป้อนเข้ามาซึ่งมีคีย์ที่เหมือนกับรายการใหม่ วิธีหนึ่งในการจัดการกับการชน กันดังกล่าว คือการส่งแฟล็กที่ระบุว่าการแทรกข้อมูลล้มเหลว หากโครงสร้างต้นไม้ถูกนำไปใช้ในรูปแบบมัลติแมปโดยมีคอลเลกชันเป็นรายการของโหนด ค่าใหม่จะถูกเพิ่มเข้าไปในคอลเลกชันนั้น
3. ช่องสี่เหลี่ยมนี้มีรายการ (รายการของผู้ใช้หรือรายการของโหนดรอง) ที่มีคีย์แตกต่างกัน ในกรณีนี้ จำเป็นต้องแทนที่รายการที่มีอยู่ด้วยโหนดรองใหม่ที่เก็บทั้งรายการเก่าและรายการใหม่ไว้

ฟังก์ชันแทรก (โหนด, คีย์, ค่า) ระดับ ← node.get_level() // ระดับคือ 0 สำหรับโหนดราก h ← extract_bits_at_level(key, level) รายการ ← node.get_entry(h) ถ้าค่าที่ป้อนเท่ากับ NIL แล้ว // กรณีที่ 1. entry_new ← create_entry(key, value) node.set_entry(h, entry_new) มิฉะนั้น หาก !entry.is_subnode() และ entry.get_key() == key แล้ว // กรณีที่ 2 การชนกัน เนื่องจากมีรายการอยู่แล้ว ส่งคืน ← การแทรกที่ล้มเหลว มิฉะนั้น // กรณีที่ 3. level_diff ← get_level_of_difference(key, entry.get_key()) entry_new ← create_entry(key, value) // โหนดย่อยใหม่ที่มีรายการเดิมและรายการใหม่ subnode_new ← create_node(level_diff, entry, entry_new) node.set_entry(h, subnode_new) จบถ้าส่งคืน

การลบทำงานในลักษณะตรงกันข้ามกับการแทรก โดยมีข้อจำกัดเพิ่มเติมว่าโหนดย่อยใด ๆ จะต้องถูกลบออกหากเหลือรายการน้อยกว่าสองรายการ รายการที่เหลือจะถูกย้ายไปยังโหนดแม่^{[ 1 ]}

การค้นหาแบบ Window queries คือการค้นหาที่ส่งคืนคีย์ทั้งหมดที่อยู่ภายในไฮเปอร์บ็อก ซ์สี่เหลี่ยมผืนผ้าที่จัดเรียงตามแกน สามารถกำหนดให้เป็นจุดสองมิติd จุด และแสดงถึงมุม "ล่างซ้าย" และ "บนขวา" ของกล่องค้นหา การใช้งานแบบง่ายๆ จะสำรวจรายการทั้งหมดในโหนด (เริ่มต้นจากโหนดราก) และหากรายการใดตรงกัน ก็จะเพิ่มรายการนั้นลงในรายการผลลัพธ์ (หากเป็นรายการที่ผู้ใช้ป้อน) หรือสำรวจรายการนั้นซ้ำ (หากเป็นโหนดย่อย) ^{[ 1 ]}${\displaystyle min}$${\displaystyle max}$

ฟังก์ชัน query(node, min, max, result_list) คือforeach entry ← node.get_entries() do if entry.is_subnode() then if entry.get_prefix() >= min and entry.get_prefix() <= max then query(entry.get_subnode(), min, max, result_list) จบ if else if entry.get_key() >= min และ entry.get_key() <= max แล้ว รายการผลลัพธ์.เพิ่ม(รายการ) จบถ้าจบถ้าทำซ้ำส่งคืน

เพื่อให้สามารถประเมินความซับซ้อนของเวลาในการสอบถามได้อย่างแม่นยำ การวิเคราะห์จำเป็นต้องรวมมิติเข้าไปด้วยการสำรวจและเปรียบเทียบรายการทั้งหมดในโหนดมีความซับซ้อนของเวลาเท่ากับเนื่องจากการเปรียบเทียบคีย์มิติกับ แต่ละครั้ง ใช้เวลา เนื่องจากโหนดสามารถมีรายการได้มากถึง^จึงไม่สามารถรองรับการเพิ่มมิติได้ดีมีหลายวิธีในการปรับปรุงแนวทางนี้โดยใช้ที่อยู่ไฮเปอร์คิวบ์h [ ^{4 ]}${\displaystyle d}$${\displaystyle n_{node\_entries}}$${\displaystyle O(d\cdot n_{node\_entries})}$${\displaystyle d}$${\displaystyle min/max}$${\displaystyle O(d)}$${\displaystyle 2^{d}}$${\displaystyle d}$

แนวคิดคือการหาค่าต่ำสุดและสูงสุดสำหรับที่อยู่ของควอดแรนต์เพื่อให้การค้นหาสามารถหลีกเลี่ยงควอดแรนต์บางส่วนที่ไม่ทับซ้อนกับกล่องคำถาม ให้เป็นจุดศูนย์กลางของโหนด (ซึ่งเท่ากับคำนำหน้าของโหนด) และและเป็นสตริงบิตสองสตริงที่มีบิตละ นอกจากนี้ ให้ดัชนีที่มี แสดงถึงบิต ของและและมิติที่ ของและตามลำดับ ${\displaystyle h}$${\displaystyle C}$${\displaystyle h_{min}}$${\displaystyle h_{max}}$${\displaystyle d}$${\displaystyle i}$${\displaystyle 0\leq i<d}$${\displaystyle i}$${\displaystyle h_{min}}$${\displaystyle h_{max}}$${\displaystyle i}$${\displaystyle min}$${\displaystyle max}$${\displaystyle C}$

ให้และ. จากนั้นจะมี ` ` สำหรับทุกมิติที่ครึ่ง "ล่าง" ของโหนดและควอดแรนต์ทั้งหมดในนั้นไม่ทับซ้อนกับกล่องคำถาม ในทำนองเดียวกันจะมี ` ` สำหรับทุกมิติที่ครึ่ง "บน" ไม่ทับซ้อนกับกล่องคำถาม ${\displaystyle h_{min,i}=(min_{i}\leq C_{i})}$${\displaystyle h_{max,i}=(max_{i}\geq C_{i})}$${\displaystyle h_{min}}$${\displaystyle 1}$${\displaystyle h_{min}}$${\displaystyle 0}$

${\displaystyle h_{min}}$จากนั้นจึงนำเสนอค่าต่ำสุดและสูงสุดในโหนดที่ต้องสำรวจ ควอดแรนต์ที่มีหรือไม่มีการตัดกับกล่องคำถาม มีหลักฐานอยู่ใน^{[ 4 ]}ด้วยเหตุนี้ ฟังก์ชันการสอบถามข้างต้นจึงสามารถปรับปรุงได้ดังนี้: ${\displaystyle h_{max}}$${\displaystyle h}$${\displaystyle h<h_{min}}$${\displaystyle h>h_{max}}$

ฟังก์ชัน query(node, min, max, result_list) คือ h_min ← คำนวณ h_min h_max ← คำนวณ h_max สำหรับแต่ละรายการ ← node.get_entries_range(h_min, h_max) ทำ [ ... ] ส่งคืนซ้ำ

การคำนวณและคือ. ขึ้นอยู่กับการกระจายของควอดแรนต์ที่ถูกครอบครองในโหนด วิธีนี้จะช่วยให้หลีกเลี่ยงการเปรียบเทียบคีย์ได้ตั้งแต่ไม่มีเลยไปจนถึงเกือบทั้งหมด ซึ่งจะช่วยลดเวลาการเดินทางโดยเฉลี่ย แต่ความซับซ้อนที่ได้ก็ยังคงอยู่ที่^{[ 4 ]}${\displaystyle h_{min}}$${\displaystyle h_{max}}$${\displaystyle O(2d)=O(d)}$${\displaystyle O(d+d\cdot n_{node\_entries})}$

ระหว่างและยังคงมีควอดแรนต์ที่ไม่ทับซ้อนกับกล่องคำถามได้ แนวคิด: และแต่ละอันมีบิตหนึ่งบิตสำหรับแต่ละมิติที่ระบุว่ากล่องคำถามทับซ้อนกับครึ่งล่าง/ครึ่งบนของโหนดในมิตินั้นหรือไม่ สามารถใช้วิธีนี้เพื่อตรวจสอบอย่างรวดเร็วว่าควอดแรนต์ทับซ้อนกับกล่องคำถามหรือไม่โดยไม่ต้องเปรียบเทียบคีย์หลายมิติ: ควอดแรนต์ทับซ้อนกับกล่องคำถามหากสำหรับทุกบิต ` ` ในจะมีบิต ` ` ที่สอดคล้องกันในและสำหรับทุกบิต ` ` ในจะมีบิต ` ` ที่สอดคล้องกันในบนซีพียูที่มีรีจิสเตอร์ 64 บิต จึงสามารถตรวจสอบการทับซ้อนของคีย์หลายมิติในได้^{[ 4 ]}${\displaystyle h_{min}}$${\displaystyle h_{max}}$${\displaystyle h_{min}}$${\displaystyle h_{max}}$${\displaystyle h}$${\displaystyle d}$${\displaystyle h}$${\displaystyle 0}$${\displaystyle h}$${\displaystyle 0}$${\displaystyle h_{min}}$${\displaystyle 1}$${\displaystyle h}$${\displaystyle 1}$${\displaystyle h_{max}}$${\displaystyle 64}$${\displaystyle O(1)}$

ฟังก์ชัน is_overlap(h, h_min, h_max) จะคืนค่า (h | h_min) & h_max == h // ประเมินค่าเป็น 'true' ถ้าควอดแรนต์และแบบสอบถามทับซ้อนกัน 

ฟังก์ชัน query(node, min, max, result_list) คือ h_min ← คำนวณ h_min h_max ← คำนวณ h_max สำหรับแต่ละรายการ ← node.get_entries_range(h_min, h_max) ทำ h ← entry.get_h(); ถ้า (h | h_min) & h_max == h แล้ว // จะประเมินค่าเป็น 'true' ถ้าควอดแรนต์และแบบสอบถามทับซ้อนกัน [ ... ] จบถ้าทำซ้ำส่งคืน

ความซับซ้อนของเวลาที่ได้จะถูกเปรียบเทียบกับการวนซ้ำทั้งหมด^{[ 4 ]}${\displaystyle O(d+n_{node\_entries})}$${\displaystyle O(d\cdot n_{node\_entries})}$

สำหรับมิติที่สูงขึ้นซึ่งมีโหนดขนาดใหญ่กว่า ก็สามารถหลีกเลี่ยงการวนซ้ำผ่านทั้งหมดและคำนวณค่าถัดไปที่สูงกว่าซึ่งทับซ้อนกับกล่องคำถามได้โดยตรง ขั้นตอนแรกจะใส่บิต ` ` ลงในค่าที่กำหนดสำหรับทุกควอดแรนต์ที่ไม่ทับซ้อนกับกล่องคำถาม ขั้นตอนที่สองจะเพิ่มค่าที่ปรับแล้วและบิต ` ` ที่เพิ่มเข้ามาจะทำให้เกิดการล้นเพื่อให้ข้ามควอดแรนต์ที่ไม่ทับซ้อนกัน ขั้นตอนสุดท้ายจะลบบิตที่ไม่ต้องการทั้งหมดที่ใช้ในการทำให้เกิดการล้น ตรรกะนี้อธิบายไว้โดยละเอียดใน^{[ 4 ]}การคำนวณทำงานดังนี้: ${\displaystyle h}$${\displaystyle h}$${\displaystyle 1}$${\displaystyle h_{input}}$${\displaystyle h}$${\displaystyle 1}$

ฟังก์ชัน increment_h(h_input, h_min, h_max) คือ h_out = h_input | (~ h_max ) // หน้ากากก่อน h_out += 1 // เพิ่มค่า h_out = ( h_out & h_max ) | h_min // post - mask ส่งคืน h_out 

อีกครั้ง เนื่องจากสิ่งนี้สามารถทำได้บน CPU ส่วนใหญ่ความซับซ้อนของเวลาที่ได้สำหรับการสำรวจโหนดคือ[ ^{4 ] วิธี}นี้ได้ผลดีที่สุดหากควอดแรนต์ส่วนใหญ่ที่ทับซ้อนกับกล่องคำถามถูกครอบครองด้วยรายการ ${\displaystyle d\leq 64}$${\displaystyle O(1)}$${\displaystyle O(d+n_{overlapping\_quadrants})}$

การค้นหาเพื่อนบ้านที่ใกล้ที่สุดk ตัว สามารถดำเนินการได้โดยใช้อัลกอริธึมมาตรฐาน ^{[ 5 ]}

PH-tree สามารถเก็บค่าจำนวนเต็มได้เท่านั้น ค่าจุดลอยตัวสามารถเก็บเป็นจำนวนเต็มได้โดยการแปลงเป็นจำนวนเต็ม อย่างไรก็ตาม ผู้เขียนยังเสนอแนวทางที่ไม่สูญเสียความแม่นยำอีกด้วย^{[ 1 ] [ 4 ]}

การแปลงค่าจุดลอยตัวเป็นค่าจำนวนเต็ม (และกลับกัน) โดยไม่สูญเสียความแม่นยำ สามารถทำได้โดยการตีความบิต 32 หรือ 64 บิตของค่าจุดลอยตัวเป็นจำนวนเต็ม (ด้วย 32 หรือ 64 บิต) เนื่องจากวิธีการ เข้ารหัสค่าจุดลอยตัว ของ IEEE 754ค่าจำนวนเต็มที่ได้จะมีลำดับเดียวกันกับค่าจุดลอยตัวดั้งเดิม อย่างน้อยก็สำหรับค่าบวก ลำดับสำหรับค่าลบสามารถทำได้โดยการกลับบิตที่ไม่ใช่เครื่องหมาย^{[ 1 ] [ 4 ]}

ตัวอย่างการใช้งานในภาษา Java :

เข้ารหัสแบบยาว( ค่าดับเบิล) { long r = Double.doubleToRawLongBits ( value ); return ( r > = 0 ) ? r : r ^ 0x7FFFFFFFFFFFFFFFL ; }

ตัวอย่างการใช้งานในภาษา C++ :

std :: int64_t encode ( double value ) { std :: int64_t r ; memcpy ( & r , & value , sizeof ( r )); return r >= 0 ? r : r ^ 0x7FFFFFFFFFFFFFFFL ; }

การเข้ารหัส (และการถอดรหัสแบบผกผัน) จะไม่สูญเสียข้อมูลสำหรับค่าจุดลอยตัวทั้งหมด ลำดับการทำงานใช้ได้ดีในทางปฏิบัติ รวมถึงและอย่างไรก็ตาม การแสดงผลจำนวนเต็มยังกลายเป็นค่าที่เปรียบเทียบได้ตามปกติ (น้อยกว่าอนันต์) อนันต์สามารถเปรียบเทียบกันได้ และ มี ค่ามากกว่า^{[ 6 ]}นั่นหมายความว่า ตัวอย่างเช่น ช่วงการค้นหาจะไม่ตรงกับค่าของเพื่อให้ตรงกับช่วงการค้นหา ค่าจะต้องเป็น ${\displaystyle \pm \infty }$${\displaystyle -0.0}$${\displaystyle NaN}$${\displaystyle 0.0}$${\displaystyle -0.0}$${\displaystyle [0.0,10.0]}$${\displaystyle -0.0}$${\displaystyle -0.0}$${\displaystyle [-0.0,10.0]}$

เพื่อจัดเก็บปริมาตร (ไฮเปอร์บ็อกซ์ที่จัดเรียงตามแกน) เป็นคีย์ โดยทั่วไปการใช้งานจะใช้การแสดงมุม^{[ 7 ]}ซึ่งแปลงมุมต่ำสุดและสูงสุดสองมิติของกล่องให้เป็นคีย์เดียวที่มีมิติ เช่น โดยการสลับกัน: . ${\displaystyle d}$${\displaystyle 2d}$${\displaystyle k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}}$

วิธีนี้ใช้ได้ผลดีสำหรับการค้นหา แทรก และลบข้อมูล การค้นหาแบบ Window query จำเป็นต้องแปลงจากเวกเตอร์มิติเป็นเวกเตอร์มิติ ตัวอย่างเช่น สำหรับ Window query ที่ตรงกับกล่องทั้งหมดที่อยู่ภายในกล่องค้นหาอย่างสมบูรณ์ คีย์การค้นหาจะเป็นดังนี้: ^{[ 7 ] [ 8 ]}${\displaystyle d}$${\displaystyle 2d}$

${\displaystyle k_{min}=\{min_{0},min_{0},min_{1},min_{1},...,min_{d-1},min_{d-1}\}}$

${\displaystyle k_{max}=\{max_{0},max_{0},max_{1},max_{1},...,max_{d-1},max_{d-1}\}}$

สำหรับการดำเนินการค้นหาหน้าต่างที่ตรงกับกล่องทั้งหมดที่ตัดกับกล่องค้นหา คีย์การค้นหาคือ: ^{[ 8 ]}

${\displaystyle k_{min}=\{-\infty ,min_{0},-\infty ,min_{1},...,-\infty ,min_{d-1}\}}$

${\displaystyle k_{max}=\{max_{0},+\infty ,max_{1},+\infty ,...,max_{d-1},+\infty \}}$

ในมิติสูงที่มีจำนวนรายการน้อยกว่าPH-tree อาจมีโหนดเพียงโหนดเดียว ซึ่งโดยพื้นฐานแล้วจะ “เสื่อมสภาพ” กลายเป็นB-Treeที่มีเส้นโค้งลำดับ Zการดำเนินการเพิ่ม/ลบ/ค้นหายังคงอยู่และการค้นหาแบบหน้าต่างสามารถใช้ตัวกรองควอดแรนต์ได้ อย่างไรก็ตาม สิ่งนี้ไม่สามารถหลีกเลี่ยงคำสาปของมิติได้สำหรับข้อมูลที่มีมิติสูงPH -tree จะดีกว่าการสแกนแบบเต็มเพียงเล็กน้อยเท่านั้น^{[ 9 ]}${\displaystyle 2^{d}}$${\displaystyle O(\log {n})}$${\displaystyle d=50}$${\displaystyle d=100}$

งานวิจัยได้รายงานการดำเนินการเพิ่ม/ลบ/จับคู่ที่แม่นยำอย่างรวดเร็วกับชุดข้อมูลขนาดใหญ่และเปลี่ยนแปลงอย่างรวดเร็ว^{[ 10 ]}การค้นหาแบบหน้าต่างได้รับการพิสูจน์แล้วว่าทำงานได้ดีโดยเฉพาะอย่างยิ่งสำหรับหน้าต่างขนาดเล็ก^{[ 11 ]}หรือชุดข้อมูลขนาดใหญ่^{[ 12 ]}

PH-tree เหมาะสำหรับการใช้งานในหน่วยความจำเป็นหลัก^{[ 10 ] [ 13 ] [ 14 ]} ขนาดของโหนด (จำนวนรายการ) จะคงที่ ในขณะที่การจัดเก็บข้อมูลถาวรมักจะได้รับประโยชน์จากดัชนีที่มีขนาดโหนดที่กำหนดค่าได้ เพื่อให้ขนาดโหนดสอดคล้องกับขนาดหน้าบนดิสก์ ซึ่งทำได้ง่ายกว่าด้วยดัชนีเชิงพื้นที่อื่นๆ เช่นR- Trees

• Java: ที่เก็บโค้ดบน GitHub โดยผู้คิดค้นดั้งเดิม
• C++: ที่เก็บโค้ดบน GitHub โดยผู้คิดค้นดั้งเดิม
• C++: ที่เก็บ GitHub
• C++: ที่เก็บ GitHub

• การแบ่งพื้นที่ไบนารี
• การปูพื้นแบบไบนารี
• ต้นไม้k -d
• อ็อกทรี
• ควอดทรี
• อาร์-ทรี
• ต้นไม้ UB
• ฐานข้อมูลเชิงพื้นที่

• เว็บไซต์ของ PH-tree มีคำอธิบายโดยละเอียด ตัวอย่าง และการเปรียบเทียบประสิทธิภาพ