基于地理位置的大數(shù)據(jù)分析

1、技術(shù)創(chuàng)新，變革未來基于地理位置的大數(shù)據(jù)分析基于地理位置的應(yīng)用實(shí)現(xiàn)楠哥是個(gè)好動(dòng)又好學(xué)的孩子， 平日里就喜歡拿著手機(jī)地圖點(diǎn)點(diǎn)按按來查詢 一些好玩的東西( XJJ)。某一天楠哥到北海公園游玩， 肚肚餓了， 于是乎打 開手機(jī)地圖， 搜索北海公園附近的餐館， 并選了其中一家用餐。引申出一個(gè)問題: 如何根據(jù)自己所在位置查詢來查詢附近50 米的POI（ point of interest， 比如商家、景點(diǎn)等） 呢（ 圖1 a）？ 每個(gè)POI都有經(jīng)緯度信息， 我用圖 1 b的SQL語句在數(shù)據(jù)庫中建立了POI_ spatial的表， 其中l(wèi)at和lng兩個(gè)字段來代 表緯度和經(jīng)度。為后續(xù)分析方便起見， 我人造了4

2、0 萬個(gè)POI數(shù)據(jù)?；诘乩砦恢玫膽?yīng)用實(shí)現(xiàn) 20該方法的復(fù)雜度為：40萬*距離函數(shù)。 我們將球體距離函數(shù)寫為mysql存儲(chǔ) 過程distance，之后我們執(zhí)行查詢操 作（圖3），發(fā)現(xiàn)花費(fèi)了4.66秒。該方法耗時(shí)的原因顯而易見，執(zhí)行了40萬次復(fù)雜的距離計(jì)算函數(shù)。1基于地理位置的應(yīng)用實(shí)現(xiàn)方法二： 矩形過濾方法該方法分為兩部：先用矩形框過濾（圖4a），判斷一個(gè)點(diǎn)在矩形框內(nèi)很簡單，只要進(jìn)行兩次判斷（LtMinlatLtMax; LnMinlngLnMax），落在矩形框內(nèi)的POI個(gè)數(shù)為n（n40萬）；用球面距離公式計(jì)算位置與矩形框內(nèi)n個(gè)POI的距離（圖4b），并保留距離小于50米的POI矩形過濾方法的復(fù)

3、雜度為： 4 0 萬* 矩形過濾函數(shù) + n * 距離函數(shù)（ n 4 0 萬） 。基于地理位置的應(yīng)用實(shí)現(xiàn)根據(jù)這個(gè)思路我們執(zhí)行SQl查詢（ 圖5 ）（ 注： 經(jīng) 度或緯度每隔0 . 001 度， 距離相差約100 米， 由此 推算出矩形左下角和右上角坐標(biāo)）， 發(fā)現(xiàn)過濾后 正好剩下兩個(gè)POI。此查詢花費(fèi)了0.36秒，相比于方法一查詢時(shí)間大大降低， 但是對(duì)于一次查詢來說還是很長。時(shí)間長的原因在于遍 歷了40萬次?；诘乩砦恢玫膽?yīng)用實(shí)現(xiàn)方法三：B樹對(duì)經(jīng)度或緯度建立索 引方法二耗時(shí)的原因在于執(zhí)行了遍歷操 作，為了不進(jìn)行遍歷，我們自然想到了索引。我們對(duì)緯度進(jìn)行了B樹索引。執(zhí)行SQL查詢（圖7），發(fā)現(xiàn)時(shí)間已

4、 經(jīng)大大降低，從方法2的0.36秒下降 到0.01秒?；诘乩砦恢玫膽?yīng)用實(shí)現(xiàn)基于地理位置的應(yīng)用實(shí)現(xiàn)回到這個(gè)例子:飯飽之后楠哥開始想一個(gè)類似的問題， 地圖后臺(tái)如何根據(jù)自己所在位置查詢來查詢附近餐館的呢？ 苦 思冥想了半天， 先計(jì)算所在位置P與北京所有餐館的距離， 然后返回距離= 1000 米的餐館。( 暴力)小得意了一會(huì)兒， 楠哥發(fā)現(xiàn)北京的餐館何其多啊， 這樣計(jì)算不得了， 于是想了， 既然知道經(jīng)緯度了， 那它應(yīng)該知道自己在西城區(qū)， 那應(yīng)該計(jì)算所在位置P與西城區(qū)所有餐館的距離啊.( 畫個(gè)區(qū)域)楠哥運(yùn)用了遞歸的思想， 縮小這個(gè)區(qū)域, 西城區(qū)也很多餐館啊， 太大了, 把方框縮小, 應(yīng)該計(jì)算他的位 置P

5、與西城區(qū)下面他在的這個(gè)街道的所有餐館的距離， 這樣計(jì)算量又小了， 效率也提升了。楠哥的計(jì)算思想就是通過過濾的方法來減小參與計(jì)算的餐館數(shù)目， 從某種角度上講， 這是一種索引技 術(shù)基于地理位置的應(yīng)用實(shí)現(xiàn)一提到索引， 大家腦子里馬上浮現(xiàn)出B樹索引， 因?yàn)榇罅康臄?shù)據(jù)庫（ 如My SQL、oracle、 Postgre SQL等） 都在使用B樹。B樹索引本質(zhì)上是對(duì)索引字段進(jìn)行排序， 然后通過類似二 分查找的方法進(jìn)行快速查找， 即它要求索引的字段是可排序的， 一般而言， 可排序的是一 維字段， 比如時(shí)間、年齡、薪水等等。但是對(duì)于空間上的一個(gè)點(diǎn)（ 二維， 包括經(jīng)度和緯度）， 如何排序呢？ 又如何索引呢？思想

6、：如果能通過某種方法將二維的點(diǎn)數(shù)據(jù)轉(zhuǎn)換成一維的數(shù)據(jù)，那樣不就可以繼續(xù)使用B樹索引了嘛。 那這種方法真的存在嘛，答案是肯定的。目前很火的GeoHash算法就是運(yùn)用了上述思想，下面我們就 開始GeoHash之旅吧。基于地理位置的應(yīng)用實(shí)現(xiàn)Geo Hash核心原理解析Geo Hash核心原理解析字符串越長， 表示的范圍越精確。如圖所示， 5 位的編 碼能表示10 平方千米范圍的矩形區(qū)域， 而6 位編碼能表 示更精細(xì)的區(qū)域（ 約0 . 34 平方千米）。Geo Hash核心原理解析Geo Hash核心原理解析通過上面的介紹我們知道了Geo Hash就是一種將經(jīng)緯度轉(zhuǎn)換成字符串的方法， 并 且使得在大部分

7、情況下， 字符串前綴匹配越多的距離越近， 回到我們的案例， 根 據(jù)所在位置查詢來查詢附近餐館時(shí)， 只需要將所在位置經(jīng)緯度轉(zhuǎn)換成Geo Hash字 符串， 并與各個(gè)餐館的Geo Hash字符串進(jìn)行前綴匹配， 匹配越多的距離越近。Geo Hash核心原理解析Geo Hash算法的步驟地球緯度區(qū)間是-90,90， 北海公園的緯度是39.928167，可以通 過下面算法對(duì)緯度39.928167進(jìn)行逼近編碼:1.區(qū)間-90,90進(jìn)行二分為-90,0),0,90，稱為左右區(qū)間， 可以確定39.928167屬于右區(qū)間0,90，給標(biāo)記為1；2.接著將區(qū)間0,90進(jìn)行二分為 0,45),45,90，可以確定39

8、.928167屬于左區(qū)間 0,45)，給標(biāo)記為0；遞歸上述過程39.928167總是屬于某個(gè)區(qū)間a,b。隨著 每次迭代區(qū)間a,b總在縮小，并越來越逼近39.928167；如果給定的緯度x（39.928167）屬于左區(qū)間，則記錄0， 如果屬于右區(qū)間則記錄1，這樣隨著算法的進(jìn)行會(huì)產(chǎn)生 一個(gè)序列1011100，序列的長度跟給定的區(qū)間劃分次數(shù) 有關(guān)。Geo Hash算法的步驟Geo Hash算法的步驟奇數(shù)位放緯度10111 00011 , 偶數(shù)位放經(jīng)度11010 01011 ， 把2 串編碼組合生成 新串： 11100 11101 00100 01111 。Geo Hash核心原理解析生成 碼1110

9、0111010010001111緯度1101001011經(jīng)度10111000112829415wx4gGeo Hash核心原理解析Geo Hash算法的步驟當(dāng)geohash base 32 編碼長度為8 時(shí)， 精度在19 米左右， 而當(dāng)編碼長度為9 時(shí)， 精度在2 米左右， 編碼長度需要根 據(jù)數(shù)據(jù)情況進(jìn)行選擇。Geo Hash核心原理解析Geo Hash缺陷這種類型的空間填充曲線的優(yōu)點(diǎn)是將二維空間轉(zhuǎn)換成一維曲線（事實(shí)上是分 形維），對(duì)大部分而言，編碼相似的距離也相近， 但Peano空間填充曲線最 大的缺點(diǎn)就是突變性，有些編碼相鄰但距離卻相差很遠(yuǎn)，比如0111與1000， 編碼是相鄰的，但距離相

10、差很大。Geo Hash缺陷由于Geo Hash是將區(qū)域劃分為一個(gè)個(gè)規(guī)則矩形， 并對(duì)每個(gè)矩形進(jìn)行編碼， 這樣在查詢附近POI信 息時(shí)會(huì)導(dǎo)致以下問題， 比如紅色的點(diǎn)是我們的位 置， 綠色的兩個(gè)點(diǎn)分別是附近的兩個(gè)餐館， 但是 在查詢的時(shí)候會(huì)發(fā)現(xiàn)距離較遠(yuǎn)餐館的Geo Hash編 碼與我們一樣（ 因?yàn)樵谕粋€(gè)Geo Hash區(qū)域塊上）， 而較近餐館的Geo Hash編碼與我們不一致。 這個(gè)問題往往產(chǎn)生在邊界處。Geo Hash缺陷解決解決的思路很簡單， 我們查詢時(shí)， 除了使 用定位點(diǎn)的Geo Hash編碼進(jìn)行匹配外， 還 使用周圍8 個(gè)區(qū)域的Geo Hash編碼， 這樣 可以避免這個(gè)問題。Geo Hash缺陷解決如何獲取周圍八個(gè)區(qū)域的G e o H a s h 值這個(gè)問題我們可以做 如下轉(zhuǎn)化:我們已經(jīng)知道當(dāng)前點(diǎn)的經(jīng)緯度值， 我們也知道每一個(gè)區(qū)域內(nèi) 的經(jīng)度、緯度的寬度，如果