Original question: http://disq.us/p/2t9jcp5
All examples are pseudocode.
Imagine that you have a method called from_z_address
that will take a Z-address and
give you back the dimensions you used to create it in the first place.
z_address = to_z_address(x, y)
(x, y) = from_z_address(z_address)
The is_relevant
method would look something like this:
def is_relevant(query_min_z_address,
query_max_z_address,
z_address_to_test):
(min_x, min_y) = from_z_address(query_min_z_address)
(max_x, max_y) = from_z_address(query_max_z_address)
(test_x, test_y) = from_z_address(z_address_to_test)
# Make sure that each of the test address's dimensions are within the min/max's respective dimensions
return (test_x >= min_x
&& test_x <= max_x
&& test_y >= min_y
&& test_y <= max_y)
A fully optimized implementation would achieve the same effect by examining the bits of the z-addresses in-place, without the intermediate step of converting them back to the individual dimensions.
The implementation of next_jump_in
is much more complex. It goes by different names in academic papers
that discuss it (nextJumpIn
, BIGMIN
, GetNextZAddress
, etc), and none of the papers make it very easy
to digest. I believe I used the description found on page 267 (section 4.2) of
Integrating the UB-Tree into a Database System Kernel when I was
running my benchmarks for the blog post.