The PH-tree (Patricia Hypercube Tree) is a space efficient multi-dimensional index structure. It can be described as a k-dimensional quadtree with prefix sharing and hypercube navigation. The performance of the tree is very efficient up to 10-15 dimensions. Tree space usage is also efficient and typically below that of plain float[] for k>8. More details can be found here or here (original paper, SIGMOD '14).

Java source code is available here: ph-tree-2015-07-29b or on the GitHub repository.


  • Dr Tilmann Z√§schke