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.