The specialization of quad-tree is to always use powers-of-two: cut your parents into four identical children; ensure the children are at a scale exactly half that of the parents. This yields nice behavior in the row/column, you can traverse to the parent row/column of a cell just be dividing the current row/column by two.
The packing of the information into a cell id is not completely clearly explained, because there is some talk of compacting and stop bits, to fit 31 levels, but even without compacting a 64-bit space can hold 29 levels quite easily (5 bits of level information, 29 bits of row address, 29 bits of column address).
I am a bit incredulous at the implied assertion that no one thought of chopping up the map of the world in descending powers-of-two before. The specific claims about the packing method might indeed be "original" but in such a trivial way as to be unimportant.
The whole process of software patenting reminds me of the historical acts of enclosure in England.
They hang the man, and flog the woman,
That steals the goose from off the common;
But let the greater villain loose,
That steals the common from the goose.
&mdash Oliver Goldsmith
2 comments:
Even the encoding and tree traversal looks a lot like results in a thesis on "Efficient Neighbor Finding Algorithms in Quadtree and Octree" (2001) by Bhattacharya. If you hurry, perhaps you can patent the Octree version and index not only the Earth's surface, but also the atmosphere and subsurface.
It's worth pointing out why Google is trying to index their map grids using a single global key... because Google has decided that all problems can be modeled as a hash table. And to that extent that they are right, they can use their powerful global hash database implementation, "bigtable".
Post a Comment