本章介紹用HBase存儲、高效查詢地理位置資訊。
Geohash空間索引
考慮LBS應用中常見的兩個問題：1）查找離某地近期的k個地點。2）查找某區域内地點。
假設要用HBase實作高效查找，首先要考慮的是空間局部性（Spatial Locality），即位置上相近的點得實體存儲在一起。
最簡單的地理位置資料由兩個次元組成：經度X和緯度Y。那麼相相應最簡單的Rowkey也能夠由X和Y組成。Rowkey的有序性決定了資料首先依照經度X排序。再依照緯度Y排序，這樣的方式最大的問題是經度值相等的A地點和B地點，可能緯度上相差十萬八千裡。
Geohash的解決思路是将經度和緯度以同樣的權重建構空間索引。詳細算法例如以下圖：在經度範圍[-180。180]，緯度範圍[-90,90]内不斷進行二分查找，假設值位于上半區則記辨別位為1，位于下半區則記辨別位為0。終于結果由經度緯度辨別位交叉組成。
（注：在HBase中能夠存儲辨別位的Base32編碼串，每一個字元是5個bit位的編碼結果）
觀察下面資料例子。可知geohash較好地反映了空間局部性：資料依照距離遠近有序排列，距離相近的點geohash值有着很多其它的同樣字首。
查找近期K個鄰居
通過掃描geohash字首能夠高效解決這個問題1：查找離某地近期的k個地點。
當然，須要選擇合适的位數來進行字首比對掃描。使用較少的位數能降低掃描次數，但可能會傳回多餘的資料，而使用較多的位數能可能每次掃描傳回的結果優先，導緻須要多次掃描。
然而，geohash值也存在一些問題，不能使用簡單的字首比對掃描來查找鄰居，例如以下圖：有限長度的geohash值在地圖上表示為一個矩形區域。位于中間的是dr5ruzb區域，它下方的鄰居區域和它有着5位長度的同樣字首，而上方的三個區域盡管位置相鄰，但僅僅有這2位長度的同樣字首。
是以，假設要查找dr5ruzb的近期k個鄰居，保險起見，能夠一起查找它周圍8個相鄰區域的近期k個鄰居。然後将全部查找到的點依照距離排序再得出終于結果。僞代碼例如以下：takeN查找某個區域的近期n個點
queryKNN則使用takeN查找四周8個相鄰區域的近期n個點。終于再排序取值。
區域内查找
來一個區域内查找的執行個體：在某某廣場内有多少個wifi熱點？解決思路分兩步：
第一步。将區域内查找轉化為對一系列geohash索引的掃描。
第二步。推斷掃描到的坐标點是否包括在待查找區域多邊形内。
工具方面。能夠使用JTS Topology Suite(http://tsusiatsoftware.net/jts/main.html),JTS實作了常見幾何對象、空間拓撲資料結構和操作算法。使用JTS查找待掃描的geohash坐标詳細過程例如以下：
- 依據待查找區域的各個頂點初始化多邊形對象Geometry。并得出多邊形對象的質心Centroid。
- 對質心Centorid坐标進行geohash編碼，精度取一定位數，假設geohash編碼所代表的閉包已經覆寫了待查找多邊形對象Geometry，那麼直接傳回質心作為待掃描的坐标。假設沒有覆寫，繼續步驟3。
-
與前一節類似做法找到質心Centroid的四周8個相鄰區域，閉包的範圍擴大至包括這8個相鄰區域頂點，再次推斷閉包是否覆寫待查找區域。
假設覆寫，那麼這9個點一起作為待掃描的坐标傳回；假設還是不能覆寫。傳回到步驟2。使用更短的geohash編碼長度來擴大位置範圍，直到覆寫待查找區域為止。
得到待掃描geohash坐标後，使用前一節近期K個鄰居查找算法在HBase表中掃描出一系列附近坐标點，最後過濾掉不在待查找區域範圍内的坐标點。當中，過濾步驟能夠通過Filter過濾器完畢。能利用上HBase的分布式并行處理能力，降低到client的傳輸資料量。