Skip to content

TREE_ANSWER.md

Latest commit

 

History

History
28 lines (21 loc) · 1.52 KB

TREE_ANSWER.md

File metadata and controls

28 lines (21 loc) · 1.52 KB
Raw

How to pick the tree?

¯_(ツ)_/¯ The answer is all about the operation you need: whether it is update-heavy or query-heavy.

tree answer

In short: orth_tree for update-heavy work, p_tree when updates dominate and the data is low-dimensional, kd_tree for query-heavy work and higher dimensions. See the manual for the exact C++ type each one needs.

In PSI:

  • Pkd-tree: the SOTA parallel kd-tree;
  • P-Orth tree: parallel orth-trees (known as the quad-tree in 2d and oct-tree in 3d);
  • SPaC-H: parallel self-balanced 1d-tree using Hilbert code to order points;
  • SPaC-Z: similar with SPaC-H but use Morton code instead;

Compared against, but not part of the library:

  • CPAM-H/Z: another 1d-tree based on the parallel augmented map;
  • Zd-tree: yet another 1d-tree based on the Morton code;
  • BHL-tree: a plain parallel kd-tree.
  • Log-tree: a parallel kd-tree using logarithmic layout.

Benchmark:

  • Uniform: points are uniformly distributed across the cube;
  • Sweepline: points are ordered by a certain dimension;
  • Varden: points have very skewed distribution.