PH-tree

PH-tree
Type	tree, map
Invented	2014
Time complexity in big O notation

The PH-tree^[1] is a 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^[2] with a structure similar to that of a quadtree or octree^[3]. However, unlike quadtrees, it uses a splitting policy similar to Crit bit trees that is based on the bit-representation of the keys. The reliance on bit-representation also enables the use different internal representations for nodes that provide scalability with high-dimensional data. The bit-representation splitting policy also imposes a maximum depth, thus avoiding degenerated trees and the need for rebalancing.

PH-tree stands for Prefix Hypercube tree. PH-tree originally stood for PATRICIA Hypercube tree, however the reference to PATRICIA is misleading because PATRICIA tries store character data rather than numbers.

Overview

The basic PH-tree is a spatial index that maps keys, which are $d$ -dimensional vectors with integers, to user defined values. The PH-tree is a multi-dimensional generalization of a Crit bit tree in the sense that a Crit bit tree is equivalent to a PH-tree with $1$ -dimensional keys. In the basic version the keys are integer coordinates but this can be extended to floating point vectors and $d$ -dimensional boxes.

A $d$ -dimensional PH-tree is a tree of nodes where each node partitions space by subdividing it into $2^{d}$ quadrants (see below for how potentially large nodes scales with high dimensional data). Each quadrant contains at most one entry, either a key-value pair (leaf quadrant) or a key-subnode pair. For a key-subnode pair, the key represents the center of the subnode. The key is also the the common prefix (bit-representation) of all keys in the subnode and its child subnodes. Each node has at least two entries, otherwise it is merged with the parent node.^[1]

Some other structural properties of PH-trees are^[1]:

They are $2^{n}$ -ary trees.
They are inherently unbalanced but imbalance is limited due to their depth being limited to the bit width of the keys, e.g. to 32 for a $d$ -dimensional key with 32bit integers.
Insertion or removal operations cause exactly one node to be modified and potentially a second node to be added or removed. This can be useful for concurrent implementations. This also means little variation in modification cost.
Their structure is independent from insertion/removal order.

Splitting Strategy

Similar to most quadtrees, the PH-tree is a hierarchy of nodes where every node splits the space in all $d$ dimensions. Thus, a node can have up to $2^{d}$ subnodes, one for each quadrant.

Quadrant Numbering

The PH-tree uses the bits of the multi-dimensional keys to determine their position in the tree. All keys that have the same leading bits are stored in the same branch of the tree.

For example, in a node at level $L$ , to determine the quadrant where a key should be inserted (or removed or looked up), it looks at the $L$ 's bit of each dimension of the key. For a 3D node with 8 quadrants (forming a cube) the $L$ 's bit of the first dimension of the key determines whether the target quadrant is on the left or the right of the cube, the $L$ 's bit of the second dimension determines whether it is at the front or the back, and the $L$ 's bit of the third dimension determines bottom vs top, see picture.

1D example

Example with three 1D keys with 8bit values: $k_{0} = {1}_{b a s e 10} = {00000001}_{b a s e 2}$ , $k_{1} = {1}_{10} = {00000100}_{2}$ and $k_{2} = {35}_{10} = {00100011}_{2}$ . Adding $k_{0}$ and $k_{1}$ to an empty tree results in a single node. The two keys first differ in their 6th bit so the node has a level $L = 5$ (starting with 0). The node has a 5bit prefix representing the common 5 bits of both keys. The node has two quadrants, each key is stored in one quadrant. Adding a third key $k_{3}$ results in one additional node at $L = 2$ with one quadrant containing the original node as subnode and the other quadrant containing the new key $k_{2}$ .

2D example

With 2D keys every node has $2^{d} = 4$ quadrants. The position of the quadrant where a key is stored is extracted from the respective bits if the keys, one bit from each dimension. The four quadrants of the node form a 2D hypercube (quadrants may be empty). The bits that are extracted from the keys form the hypercube address $h$ , for $k_{0} \to h = {00}_{2}$ and for $k_{1} \to h = {01}_{2}$ . $h$ is effectively the position of the quadrant in the node's hypercube.

Node structure

The ordering of the entries in a node always follows Z-ordering.^[1] The way that entries are stored can vary, typical implementations use fixed arrays, dynamic arrays and/or B-trees.

Fixed arrays have a size of size $2^{d}$ . $h$ is effectively the array index of a quadrant. This allows lookup, insert and remove with $O (1)$ and there is no need to store $h$ . Space complexity is however $O (2^{d})$ per node, so it is less suitable for high dimensional data.

Dynamic arrays use an ordered collection of entries ${h, {k e y, v a l u e}}$ . Lookup with binary search is $O (\log n_{n o d e_e n t r i e s})$ and insert/remove are $O (n_{n o d e_e n t r i e s})$ . While lookup is fast, mutations do not scale well with higher dimensions.

B-trees use $h$ as key that maps to a multidimensional key-value pair: ${h, {k e y, v a l u e}}$ . All operations are $O (\log n_{n o d e_e n t r i e s})$ and space complexity is $O (n_{n o d e_e n t r i e s})$ .

The original implementation aimed for minimal memory consumption by switching between fixed and dynamic array representation depending on which uses less memory.^[1] Other implementations[1][2] do not switch dynamically but use fixed arrays for $d ≲ 4$ , dynamic arrays for $d ≲ 8$ and B-trees for high dimensional data.

Operations

Lookup, insertion and removal operations all work very similar: find the correct node, then perform the operation on the node. Window queries and $k$ -nearest-neighbor searches are more complex.

Lookup

The Lookup operation determines whether a key exists in the tree. It walks down the tree and checks every node whether it contains a candidate subnode or a user value that matches the key.^[1]

function lookup(key) is
    entry ← get_root_entry()    // if the tree is not empty the root entry contains a root node
    while entry != NIL && entry.is_subnode() do 
        node ← entry.get_node()
        entry ← node.get_entry(key)  
    repeat
return entry                    // entry can be NIL

function get_entry(key) is
    node ← current node
    h ← extract_bits_at_depth(key, node.get_depth()}
    entry ← n.get_entry_at(h)  
return entry                    // entry can be NIL

Insert

The Insert operation inserts a new key-value pair into the tree unless they key already exists. The operation traverses the tree like the Lookup function and then inserts the key into the node. There are several cases to consider^[1]:

The quadrant is empty and we can simply insert a new entry into the quadrant and return.
The quadrant contains a user entry with a key that is identical to the new entry. One way to deal with such a collision is to return a flag that indicates failed insertion. If the tree is implemented as multi-map with a collection as the node's entry, the new value is added to that collection.
The quadrant contains an entry (user entry or subnode entry) with a different key. This case requires replacing the existing entry with a new subnode that holds the old and the new entry.

function insert(node, key, value)
    level ← node.get_level()            // Level is 0 for root
    h ← extract_bits_at_level(key, level)
    entry ← node.get_entry(h)
    if entry == NIL then
        // Case 1.
        entry_new ← create_entry(key, value)
        n.set_entry(h, entry_new)       
    else if !entry.is_subnode() && entry.get_key() == key then
       // Case 2. Collision, there is already an entry
       return ← failed_insertion        
    else
        // Case 3.
        level_diff ← get_level_of_difference(key, entry.get_key()) 
        entry_new ← create_entry(key, value)
        // new subnode with existing entry and new entry
        subnode_new ← create_node(level_diff, entry, entry_new) 
        n.set_entry(h, subnode_new)     
    end if
return

Remove

Removal works inversely to insertion, with the additional constraint that any subnode has to be removed if less than two entries remain. The remaining entry is moved to the parent node.

Window queries

Windows queries are queries that return all keys that lie inside a rectangular axis-aligned hyperbox. They can be defined be two $d$ -dimensional points $m i n$ and $m a x$ that represent the "lower left" and "upper right" corners of the query box. A trivial implementation traverses all entries in a node (starting with the root node) and if an entry matches it either adds it to the result list (if it is a user entry) or recursively traverses it (if it is a subnode).

function query(node, min, max, result_list) is
    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)
            end if
        else
            if entry.get_key() >= min and entry.get_key() <= max then
                result_list.add(entry)
            end if
        end if
    repeat
return

In order to accurately estimate query time complexity the analysis needs to include the dimensionality $d$ . Traversing and comparing all $n_{n o d e_e n t r i e s}$ entries in a node has a time complexity of $O (d * n_{n o d e_e n t r i e s})$ because each comparison of $d$ -dimensional key with $m i n / m a x$ takes $O (d)$ time. Since nodes can have up to $2^{d}$ entries, this does not scale well with increasing dimensionality $d$ . There are various ways how this approach can be improved by making using of the hypecube address $h$ .

Min $h$ & max $h$

The idea is to find minimum and maximum values for the quadrant's addresses $h$ such that the search can avoid some quadrants that do not overlap with the query box. Let $C$ be the center of a node (this is equal to the node's prefix) and $h_{m i n}$ and $h_{m a x}$ be two bit strings with $d$ bits each. Also, let subscript $i$ with $0 \leq i < d$ indicate the $i$ 's bit of $h_{m i n}$ and $h_{m a x}$ and the $i$ 'th dimension of $m i n$ , $m a x$ and $C$ .

Let $h_{m i n, i} = (m i n_{i} \leq C_{i})$ and $h_{m a x, i} = (m a x_{i} \geq C_{i})$ . $h_{m i n}$ then has a ` $1$ ` for every dimension where the "lower" half of the node and all quadrants in it do not overlap with the query box. Similarly, $h_{m i n}$ has a ` $0$ ` for every dimension where the "upper" half does not overlap with the query box.

$h_{m i n}$ and $h_{m a x}$ then present the lowest and highest $h$ in a node that need to be traversed. Quadrants with $h < h_{m i n}$ or $h > h_{m a x}$ do not intersect with the query box. A proof is available in^[4]. With this, the above query function can be improved to:

function query(node, min, max, result_list) is
    h_min ← calculate h_min
    h_max ← calculate h_max
    for each entry ← node.get_entries_range(h_min, h_max) do
        [ ... ]
    repeat
return

Calculating $h_{m i n}$ and $h_{m a x}$ is $O (2 * d) = O (d)$ . Depending on the distribution of the occupied quadrants in a node this approach will allow avoiding anywhere from no to almost all key comparisons. This reduces the average traversal time but the resulting complexity is still $O (d + d * n_{n o d e_e n t r i e s})$ .

Check quadrants for overlap with query box

Between $h_{m i n}$ and $h_{m a x}$ there can still be quadrants that do not overlap with the query box. Idea: $h_{m i n}$ and $h_{m a x}$ each have one bit for every dimensions that indicates whether the query box overlaps with the lower/upper half of a node in that dimension. This can be used to quickly check whether a quadrant $h$ overlaps with the query box without having to compare $d$ -dimensional keys: a quadrant $h$ overlaps with the query box if for every ` $0$ ` bit in $h$ there is a corresponding ` $0$ ` bit in $h_{m i n}$ and for every ` $1$ ` bit in $h$ there is a corresponding ` $1$ ` bit in $h_{m a x}$ . On a CPU with 64bit registers it is thus possible to check for overlap of up to $64$ -dimensional keys in $O (1)$ .^[4]

function is_overlap(h, h_min, h_max) is
return (h | h_min) & h_max == h            // evaluates to 'true' if quadrant and query overlap.

function query(node, min, max, result_list) is
    h_min ← calculate h_min
    h_max ← calculate h_max
    for each entry ← node.get_entries_range(h_min, h_max) do
        h ← entry.get_h();
        if (h | h_min) & h_max == h then   // evaluates to 'true' if quadrant and query overlap.
           [ ... ]
        end if
    repeat
return

The resulting time complexity is $O (d + n_{n o d e_e n t r i e s})$ compared to the $O (d * n_{n o d e_e n t r i e s})$ of the full iteration.

Traverse quadrants that overlap with query box

For higher dimensions with larger nodes it is also possible to avoid iterating through all $h$ and instead directly calculate the next higher $h$ that overlaps with the query box. The first step puts ` $1$ `-bits into a given $h_{i n p u t}$ for all quadrants that have no overlap with the query box. The second step increments the adapted $h$ and the added ` $1$ `-bits trigger an overflow so that the non-overlapping quadrants are skipped. The last step removes all the undesirable bits used for triggering the overflow. The logic is described in detail in^[4]. The calculation works as follows:

function increment_h(h_input, h_min, h_max) is
    h_out = h_input | (~ h_max )        // pre - mask
    h_out += 1                          // increment
    h_out = ( h_out & h_max ) | h_min   // post - mask
return h_out

Again, for $d \leq 64$ this can be done on most CPUs in $O (1)$ . The resulting time complexity for traversing a node is $O (d + n_{o v e r l a p p i n g_q u a d r a n t s})$ .^[4] This works best if most of the quadrants that overlap with the query box are occupied with an entry.

$k$ -nearest neighbors

$k$ nearest neighbor searches can be efficiently implemented using standard algorithms.^[5]

Floating point keys

The approaches to store floating point keys in a PH-tree fall into two main groups: lossless conversion and lossy conversion. All conversions must provide an ordering guarantee in order for window queries to work properly: for $y_{i n t e g e r} = e n c o d e (x_{f l o a t})$ , $x_{f l o a t}$ and $y_{i n t e g e r}$ must have the same natural ordering.

Lossless conversion

The simplest form converting a floating point value into an integer value without loss if precision is to simply interpret the 32 or 64 bits of the floating point value as an integer (with 32 or 64 bits). Due to the way that IEEE 754 encodes floating point values, the resulting integer values have the same ordering as the original floating point values, at least for positive values. Ordering for negative values can be achieved by inverting the non-sign bits.^[1]^[4]

Example implementations in Java:

long encode(double value) {
    long r = Double.doubleToRawLongBits(value);
    return (r >= 0) ? r : r ^ 0x7FFFFFFFFFFFFFFFL;
}

Example implementations in C++:

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

Encoding (and the inverse decoding) is lossless for all floating point values. The ordering works well in practice, including $\pm \infty$ and $- 0.0$ . However, the integer representation also turns $N a N$ into a normal comparable value, infinities become comparable to each other and $0.0$ becomes larger than $- 0.0$ . That means that, for example, a query range $[0.0, 10.0]$ will not match a value of $- 0.0$ . In order to match $- 0.0$ the query range needs to be $[- 0.0, 10.0]$ .

Lossy conversion

One approach for lossy conversion is to multiply the floating point value by a constant and then converting it to an integer:

function encode (float f) is
return (int)(f * 1000)

The main downside is the loss of precision.

Hyperboxes as keys

It can be desirable to use axis-aligned (hyper-)boxes instead of (hyper-)points as keys. This can be achieved by converting the two $d$ -dimensional minimum and maximum corners of a box into a single key with $2 * d$ dimensions, for example by interleaving them: $k = {m i n_{0}, m a x_{0}, m i n_{1}, m a x_{1}, . . ., m i n_{d - 1}, m a x_{d - 1}}$ .

This works trivially for lookup, insert and remove operations. Window queries needs some additional conversion. For example, for a window query that matches all boxes that are completely inside the query box, the query keys are:

$k_{m i n} = {m i n_{0}, m i n_{0}, m i n_{1}, m i n_{1}, . . ., m i n_{d - 1}, m i n_{d - 1}}$

$k_{m a x} = {m a x_{0}, m a x_{0}, m a x_{1}, m a x_{1}, . . ., m a x_{d - 1}, m a x_{d - 1}}$

For a window query operation that matches all boxes that overlap with a query box, the query keys are:

$k_{m i n} = {- \infty, m i n_{0}, - \infty, m i n_{1}, . . ., - \infty, m i n_{d - 1}}$

$k_{m a x} = {m a x_{0}, + \infty, m a x_{1}, + \infty, . . ., m a x_{d - 1}, + \infty}$

Scalability

In high dimensions with less than $2^{d}$ entries, a PH-tree may have only a single node, i.e. it “degenerates” into a B-Tree with Z-order curve. All operations remain $O (\log n)$ with the added benefit that the overlap filter operations for window queries can still be used on the B-Tree. However, this cannot avoid the curse of dimensionalty, for high dimensional data with $d = 50$ or $d = 100$ a PH-tree is is only marginally better than a full scan.^[6]

Disadvantages

PH-tree is not a multimap

Unlike most other spatial indexes the PH-tree is a Map, not a Multimap. That means it can only store one value for each key. This can be easily overcome by storing a collection (such as a list or map) as value.

PH-tree is not well suited for disk storage

For fast updates to a stored index it is desirable to have updates align with cluster or block sizes so that only one cluster or block needs to be written to persistent storage. Some spatial indexes, such as R-tree, have configurable node sizes so that the size of a serialized node is the same as a cluster or block on disk. This is not possible with the PH-tree because node sizes are determined only by the number of dimensions of the keys.

Uses

The fast add/remove operations make it a good candidate for fast changing datasets, especially large ones.^[7]

The PH-tree is mainly suited for in-memory use.^[7]^[8]^[9] The size of the nodes (number of entries) is fixed while persistent storage tends to benefit from indexes with configurable node size to align node size with page size on disk. This is easier with other spatial indexes, such as R-Trees.

The PH-tree is often used as a baseline for performance analysis. ^[8]^[10]^[11]^[12]^[13]^[6]^[14]^[9]

Implementations

References

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 ^1.7 Zäschke, Tilmann; Zimmerli, Christoph; Norrie, Moira C. (June 2014). "The PH-tree: a space-efficient storage structure and multi-dimensional index". Proc. 2014 ACM SIGMOD International Conference on Management of Data: Pages 397–408. doi:10.1145/2588555.2588564. Retrieved 10 February 2022.
↑ Kouahla, Z.; Benrazek, A.-E.; Ferrag, M. A.; Farou, B.; Seridi, H.; Kurulay, M.; Anjum, A.; Asheralieva, A. (2022). "Survey on Big IoT Data Indexing: Potential Solutions, Recent Advancements, and Open Issues". Future Internet. 14 (1): 19. doi:10.3390/fi14010019.
↑ Mahmood, A. R.; Punni, S.; Aref, W. G. (2018). "Spatio-temporal access methods: a survey (2010 – 2017)". Geoinformatica. 23 (1): 1–36. doi:10.1007/s10707-018-0329-2.
↑ ^4.0 ^4.1 ^4.2 ^4.3 ^4.4 Zäschke, Tilmann; Norrie, Moira (2017). "Efficient Z-Ordered Traversal of Hypercube Indexes". Lecture Notes in Informatics (LNI). P-265 (Datenbanksysteme für Business, Technologie und Web (BTW 2017)): 465–484. doi:10.3929/ethz-a-010802003.
↑ Hjaltason, Gísli R.; Samet, Hanan (June 1999). "Distance browsing in spatial databases". ACM Transactions on Database Systems. 24 (2): 265–318. doi:10.1145/320248.320255. Retrieved 12 February 2022.
↑ ^6.0 ^6.1 Li, Yan; Ge, Tingjian; Chen, Cindy (2020). "Online Indices for Predictive Top-k Entity and Aggregate Queries on Knowledge Graphs". 2020 IEEE 36th International Conference on Data Engineering (ICDE): 1057–1068. doi:10.1109/ICDE48307.2020.00096.
↑ ^7.0 ^7.1 Sprenger, Stefan (2019). "Efficient Processing of Range Queries in Main Memory". doi:10.18452/19786.
↑ ^8.0 ^8.1 Wang, S.; Maier, D.; Ooi, B. (2016). "Fast and Adaptive Indexing of Multi-Dimensional Observational Data". VLDB Endowment. 9 (14): 1683. doi:10.14778/3007328.3007334.
↑ ^9.0 ^9.1 Herrera, Stiw; da Silva, Larissa Miguez; Reis, Paulo Ricardo; Silva, Anderson; Porto, Fabio (2021). "Managing Sparse Spatio-Temporal Data in SAVIME: an Evaluation of the PH-tree Index". Anais do XXXVI Simpósio Brasileiro de Bancos de Dados: 337--342. doi:10.5753/sbbd.2021.17895.
↑ Khatibi, A.; Porto, F.; Rittmeyer, J. G.; Ogasawara, E.; Valduriez, P.; Shasha, D. (August 2017). "Pre-processing and indexing techniques for constellation queries in big data". International Conference on Big Data Analytics and Knowledge Discovery: 164–172. doi:10.1007/978-3-319-64283-3_12.
↑ Sprenger, Stefan; Schäfer, Patrick; Leser, Ulf (2019). "BB-Tree: A Main-Memory Index Structure for Multidimensional Range Queries". 2019 IEEE 35th International Conference on Data Engineering (ICDE): 1566–1569. doi:10.1109/ICDE.2019.00143.
↑ Sprenger, Stefan; Schäfer, Patrick; Leser, Ulf (2020). "Sprenger, Stefan; Schäfer, Patrick; Leser, Ulf. BB-Tree: A practical and efficient main-memory index structure for multidimensional workloads". 2020 IEEE 36th International Conference on Data Engineering (ICDE): 1057–1068. doi:10.1109/ICDE48307.2020.00096.
↑ Winter, C.; Kipf, A.; Anneser, C.; Zacharatou, E. T.; Neumann, T.; Kemper, A. (2020). "GeoBlocks: A Query-Cache Accelerated Data Structure for Spatial Aggregation over Polygons". EDBT. 23: 169–180. doi:10.5441/002/edbt.2021.16.
↑ Chatterjee, B.; Walulya, I.; Tsigas, P. (13 September 2021). "Concurrent linearizable nearest neighbour search in lockfree-kd-tree". Theoretical Computer Science. 889: 27–48. doi:10.1145/3154273.3154307.

Category:Trees (data structures) Category:Database index techniques Category:Geometric data structures

This article "PH-tree" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:PH-tree. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

This page exists already on Wikipedia.

[PH-tree-2014-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 ^1.7 Zäschke, Tilmann; Zimmerli, Christoph; Norrie, Moira C. (June 2014). "The PH-tree: a space-efficient storage structure and multi-dimensional index". Proc. 2014 ACM SIGMOD International Conference on Management of Data: Pages 397–408. doi:10.1145/2588555.2588564. Retrieved 10 February 2022.

[Kouahla-2022-2] Kouahla, Z.; Benrazek, A.-E.; Ferrag, M. A.; Farou, B.; Seridi, H.; Kurulay, M.; Anjum, A.; Asheralieva, A. (2022). "Survey on Big IoT Data Indexing: Potential Solutions, Recent Advancements, and Open Issues". Future Internet. 14 (1): 19. doi:10.3390/fi14010019.

[Mahmood-2018-3] Mahmood, A. R.; Punni, S.; Aref, W. G. (2018). "Spatio-temporal access methods: a survey (2010 – 2017)". Geoinformatica. 23 (1): 1–36. doi:10.1007/s10707-018-0329-2.

[z-ordered-traversal-2017-4] 4.0 ^4.1 ^4.2 ^4.3 ^4.4 Zäschke, Tilmann; Norrie, Moira (2017). "Efficient Z-Ordered Traversal of Hypercube Indexes". Lecture Notes in Informatics (LNI). P-265 (Datenbanksysteme für Business, Technologie und Web (BTW 2017)): 465–484. doi:10.3929/ethz-a-010802003.

[kNN-5] Hjaltason, Gísli R.; Samet, Hanan (June 1999). "Distance browsing in spatial databases". ACM Transactions on Database Systems. 24 (2): 265–318. doi:10.1145/320248.320255. Retrieved 12 February 2022.

[Li-2020-6] 6.0 ^6.1 Li, Yan; Ge, Tingjian; Chen, Cindy (2020). "Online Indices for Predictive Top-k Entity and Aggregate Queries on Knowledge Graphs". 2020 IEEE 36th International Conference on Data Engineering (ICDE): 1057–1068. doi:10.1109/ICDE48307.2020.00096.

[Spengler-thesis-7] 7.0 ^7.1 Sprenger, Stefan (2019). "Efficient Processing of Range Queries in Main Memory". doi:10.18452/19786.

[Wang-2016-8] 8.0 ^8.1 Wang, S.; Maier, D.; Ooi, B. (2016). "Fast and Adaptive Indexing of Multi-Dimensional Observational Data". VLDB Endowment. 9 (14): 1683. doi:10.14778/3007328.3007334.

[Herrera-2021-9] 9.0 ^9.1 Herrera, Stiw; da Silva, Larissa Miguez; Reis, Paulo Ricardo; Silva, Anderson; Porto, Fabio (2021). "Managing Sparse Spatio-Temporal Data in SAVIME: an Evaluation of the PH-tree Index". Anais do XXXVI Simpósio Brasileiro de Bancos de Dados: 337--342. doi:10.5753/sbbd.2021.17895.

[Khatibi-2017-10] Khatibi, A.; Porto, F.; Rittmeyer, J. G.; Ogasawara, E.; Valduriez, P.; Shasha, D. (August 2017). "Pre-processing and indexing techniques for constellation queries in big data". International Conference on Big Data Analytics and Knowledge Discovery: 164–172. doi:10.1007/978-3-319-64283-3_12.

[Sprenger-2019-11] Sprenger, Stefan; Schäfer, Patrick; Leser, Ulf (2019). "BB-Tree: A Main-Memory Index Structure for Multidimensional Range Queries". 2019 IEEE 35th International Conference on Data Engineering (ICDE): 1566–1569. doi:10.1109/ICDE.2019.00143.

[Sprenger-2020-12] Sprenger, Stefan; Schäfer, Patrick; Leser, Ulf (2020). "Sprenger, Stefan; Schäfer, Patrick; Leser, Ulf. BB-Tree: A practical and efficient main-memory index structure for multidimensional workloads". 2020 IEEE 36th International Conference on Data Engineering (ICDE): 1057–1068. doi:10.1109/ICDE48307.2020.00096.

[Kipf-2020-13] Winter, C.; Kipf, A.; Anneser, C.; Zacharatou, E. T.; Neumann, T.; Kemper, A. (2020). "GeoBlocks: A Query-Cache Accelerated Data Structure for Spatial Aggregation over Polygons". EDBT. 23: 169–180. doi:10.5441/002/edbt.2021.16.

[Chatterjee-2021-14] Chatterjee, B.; Walulya, I.; Tsigas, P. (13 September 2021). "Concurrent linearizable nearest neighbour search in lockfree-kd-tree". Theoretical Computer Science. 889: 27–48. doi:10.1145/3154273.3154307.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

v t e Tree data structures
Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal Fibonacci Leftist Pairing Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

PH-tree

Contents

Overview

Splitting Strategy

Quadrant Numbering

1D example

2D example

Node structure

Operations

Lookup

Insert

Remove

Window queries

Min $h$ & max $h$

Check quadrants for overlap with query box

Traverse quadrants that overlap with query box

$k$ -nearest neighbors

Floating point keys

Lossless conversion

Lossy conversion

Hyperboxes as keys

Scalability

Disadvantages

PH-tree is not a multimap

PH-tree is not well suited for disk storage

Uses

Implementations

See also

References

PH-tree

Overview

Splitting Strategy

Quadrant Numbering

1D example

2D example

Node structure

Operations

Lookup

Insert

Remove

Window queries

Min h & max h

Check quadrants for overlap with query box

Traverse quadrants that overlap with query box

k-nearest neighbors

Floating point keys

Lossless conversion

Lossy conversion

Hyperboxes as keys

Scalability

Disadvantages

PH-tree is not a multimap

PH-tree is not well suited for disk storage

Uses

Implementations

See also

References

Min $h$ & max $h$

$k$ -nearest neighbors