The PH-tree is a tree data structure used for spatial indexing of multi-dimensional data (keys) such as geographical coordinates, points, feature vectors, rectangles or bounding boxes. The PH-tree is space partitioning index with a structure similar to that of a quadtree or octree. However, unlike quadtrees, it uses a splitting policy based on tries and similar to Crit bit trees that is based on the bit-representation of the keys.The bit-based splitting policy, when combined with the use of different internal representations for nodes, provides scalability with high-dimensional data. The bit-representation splitting policy also imposes a maximum depth, thus avoiding degenerated trees and the need for rebalancing.
| Property |
Value |
| dbo:abstract |
The PH-tree is a tree data structure used for spatial indexing of multi-dimensional data (keys) such as geographical coordinates, points, feature vectors, rectangles or bounding boxes. The PH-tree is space partitioning index with a structure similar to that of a quadtree or octree. However, unlike quadtrees, it uses a splitting policy based on tries and similar to Crit bit trees that is based on the bit-representation of the keys.The bit-based splitting policy, when combined with the use of different internal representations for nodes, provides scalability with high-dimensional data. The bit-representation splitting policy also imposes a maximum depth, thus avoiding degenerated trees and the need for rebalancing. (en) |
| dbo:thumbnail |
wiki-commons:Special:FilePath/Hypercube_addressing_with_bit_strings.svg?width=300 |
| dbo:wikiPageExternalLink |
http://phtree.org https://github.com/improbable-eng/phtree-cpp https://github.com/mcxme/phtree https://github.com/tzaeschke/phtree https://github.com/tzaeschke/phtree-cpp |
| dbo:wikiPageID |
70019617 (xsd:integer) |
| dbo:wikiPageLength |
27603 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1114294543 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:M-ary_tree dbr:Binary_tree dbr:Curse_of_dimensionality dbr:Dynamic_array dbr:Crit_bit_tree dbr:Quadtree dbr:R-tree dbr:Tree_data_structure dbr:B-Tree dbr:B-tree dbc:Geometric_data_structures dbr:Trie dbr:Feature_vector dbr:Array_data_type dbc:Trees_(data_structures) dbr:K-nearest_neighbors_algorithm dbr:Binary_space_partitioning dbr:Binary_tiling dbr:UB-tree dbc:Database_index_techniques dbr:Spatial_index dbr:Cast_(computer_science) dbr:Map_(computer_science) dbr:Z-order_curve dbr:IEEE_754 dbr:Octree dbr:Multimap dbr:Spatial_database dbr:R-Tree dbr:Balanced_tree dbr:Bounding_box dbr:Kd-tree dbr:File:Hypercube_addressing_with_bit_strings.svg dbr:File:PH-tree_Example_2D.svg dbr:File:PH-tree_example_1D.svg |
| dbp:deleteAvg |
O (en) |
| dbp:deleteWorst |
O (en) |
| dbp:insertAvg |
O (en) |
| dbp:insertWorst |
O (en) |
| dbp:inventedYear |
2014 (xsd:integer) |
| dbp:name |
PH-tree (en) |
| dbp:searchAvg |
O (en) |
| dbp:searchWorst |
O (en) |
| dbp:spaceAvg |
O (en) |
| dbp:spaceWorst |
O (en) |
| dbp:type |
tree, map (en) |
| dbp:wikiPageUsesTemplate |
dbt:CS-Trees dbt:Cn dbt:Mvar dbt:Reflist dbt:Short_description dbt:Infobox_data_structure |
| dct:subject |
dbc:Geometric_data_structures dbc:Trees_(data_structures) dbc:Database_index_techniques |
| rdfs:comment |
The PH-tree is a tree data structure used for spatial indexing of multi-dimensional data (keys) such as geographical coordinates, points, feature vectors, rectangles or bounding boxes. The PH-tree is space partitioning index with a structure similar to that of a quadtree or octree. However, unlike quadtrees, it uses a splitting policy based on tries and similar to Crit bit trees that is based on the bit-representation of the keys.The bit-based splitting policy, when combined with the use of different internal representations for nodes, provides scalability with high-dimensional data. The bit-representation splitting policy also imposes a maximum depth, thus avoiding degenerated trees and the need for rebalancing. (en) |
| rdfs:label |
PH-tree (en) |
| owl:sameAs |
wikidata:PH-tree https://global.dbpedia.org/id/GVwKv |
| prov:wasDerivedFrom |
wikipedia-en:PH-tree?oldid=1114294543&ns=0 |
| foaf:depiction |
wiki-commons:Special:FilePath/Hypercube_addressing_with_bit_strings.svg wiki-commons:Special:FilePath/PH-tree_Example_2D.svg wiki-commons:Special:FilePath/PH-tree_example_1D.svg |
| foaf:isPrimaryTopicOf |
wikipedia-en:PH-tree |
| is dbo:wikiPageRedirects of |
dbr:Phtree |
| is dbo:wikiPageWikiLink of |
dbr:Z-order_curve dbr:Spatial_database dbr:Phtree |
| is foaf:primaryTopic of |
wikipedia-en:PH-tree |
