view release on metacpan or  search on metacpan

README  view on Meta::CPAN

      quad tree is a more efficient. The MQT will make bad choices as the
      median of a contiguous subset of the ordered data will not reflect the
      overall distribution and the property of having fairly evenly filled
      buckets vanishes.

    * It is likely that polling a spatial index using an MQT is faster than
      an ordinary quad tree if the distribution of data is very different
      from uniformity. If in doubt, benchmark.

    * If the data is uniform but inserted in random order, the MQT will at
      best be equal in performance to a quad tree.

    * Filling a dynamically growing MQT has slightly more overhead than
      filling a dynamically growing quad tree due to the median calculation,
      but it is neither algorithmically slower nor necessarily slower in
      practice. Algorithmically, splitting a quad tree node will be O(n) in
      the bucket size. Splitting an MQT node will be O(n*log(n)) if a naive
      median calculation is used or also O(n) with a linear-time median
      calculation (like this implementation).

      If the MQT is filled in random order and the data is not uniformly

lib/Algorithm/SpatialIndex/Strategy/MedianQuadTree.pm  view on Meta::CPAN

evenly filled buckets vanishes.

=item *

It is likely that polling a spatial index using an MQT is faster than an ordinary quad
tree if the distribution of data is very different from uniformity. If in doubt,
benchmark.

=item *

If the data is uniform but inserted in random order, the MQT will at best be
equal in performance to a quad tree.

=item *

Filling a dynamically growing MQT has slightly more overhead than filling a dynamically
growing quad tree due to the median calculation, but it is neither algorithmically
slower nor necessarily slower in practice. Algorithmically, splitting a
quad tree node will be O(n) in the bucket size. Splitting an MQT node will be
O(n*log(n)) if a naive median calculation is used or also O(n) with a linear-time
median calculation (like this implementation).