HBase空间索引设计

jieforest

Not all linearization techniques are created equal

The geohash is approximating the data space. That is, it's a function that computes a value on a single output dimension based on input from multiple dimensions. In this case, the dimensionality of the input is only 2, but you can imagine how this could work for more.

This is a form of linearization, and it's not the only one. Other techniques such as the Z-order curve[6] and the Hilbert curve[7] are also common. These are both classes of space-filling curves:[8] curves defined by a single, uninterrupted line that touches all partitions of a space.

None of these techniques can perfectly model a two-dimensional plane on a one-dimensional line and maintain the relative characteristics of objects in those spaces. We choose the geohash because, for our purposes, its error cases are less bad than the others.

jieforest

Summary

This article was as much about GIS as about HBase. Remember, HBase is just a tool. To use it effectively, you need to know both the tool and the domain in which you want to apply it. The geohash trick proves that point. A little domain knowledge can go a long way.

1. Some of those datasets are pretty cool, in particular the Street Tree Census data. Look for yourself at https://nycopendata.socrata.com/.

2. The raw dataset used in this chapter is available at https://nycopendata.socrata.com/d/ehc4-fktp.

3. Base32 is an encoding used to represent a binary value as a sequence of ASCII characters. Note that although geohash uses an alphabet of characters similar to that of Base32, the geohash spec doesn't follow the Base32 RFC. Learn more about Base32 at http://en.wikipedia.org/wiki/Base32.

4. When including a direction, degrees of latitude are measured from 0.0 to 90.0 with the northern hemisphere corresponding to positive values and the southern hemisphere to negative values on the absolute latitude range. Likewise, degrees of longitude are measured from 0.0 to 180.0 with the eastern hemisphere indicating positive values and western hemisphere indicating negative values.

5. We're using Silvio Heuberger's Java implementation at https://github.com/kungfoo/geohash-java. We've made it available in Maven for easy distribution.

6. The Z-order curve is extremely similar to the geohash, involving the interleaving of bits. Read more at http: //en.wikipedia.org/wiki/Z-order_curve.

jieforest

over.