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

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

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

3、雜度為： 4 0 萬(wàn)* 矩形過(guò)濾函數(shù) + n * 距離函數(shù)（ n 4 0 萬(wàn)） ?；诘乩砦恢玫膽?yīng)用實(shí)現(xiàn)根據(jù)這個(gè)思路我們執(zhí)行SQl查詢（ 圖5 ）（ 注： 經(jīng) 度或緯度每隔0 . 001 度， 距離相差約100 米， 由此 推算出矩形左下角和右上角坐標(biāo)）， 發(fā)現(xiàn)過(guò)濾后 正好剩下兩個(gè)POI。此查詢花費(fèi)了0.36秒，相比于方法一查詢時(shí)間大大降低， 但是對(duì)于一次查詢來(lái)說(shuō)還是很長(zhǎng)。時(shí)間長(zhǎng)的原因在于遍 歷了40萬(wàn)次?；诘乩砦恢玫膽?yīng)用實(shí)現(xiàn)方法三：B樹(shù)對(duì)經(jīng)度或緯度建立索 引方法二耗時(shí)的原因在于執(zhí)行了遍歷操 作，為了不進(jìn)行遍歷，我們自然想到了索引。我們對(duì)緯度進(jìn)行了B樹(shù)索引。執(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è)例子:飯飽之后楠哥開(kāi)始想一個(gè)類(lèi)似的問(wèn)題， 地圖后臺(tái)如何根據(jù)自己所在位置查詢來(lái)查詢附近餐館的呢？ 苦 思冥想了半天， 先計(jì)算所在位置P與北京所有餐館的距離， 然后返回距離= 1000 米的餐館。( 暴力)小得意了一會(huì)兒， 楠哥發(fā)現(xiàn)北京的餐館何其多啊， 這樣計(jì)算不得了， 于是想了， 既然知道經(jīng)緯度了， 那它應(yīng)該知道自己在西城區(qū)， 那應(yīng)該計(jì)算所在位置P與西城區(qū)所有餐館的距離啊.( 畫(huà)個(gè)區(qū)域)楠哥運(yùn)用了遞歸的思想， 縮小這個(gè)區(qū)域, 西城區(qū)也很多餐館啊， 太大了, 把方框縮小, 應(yīng)該計(jì)算他的位 置P

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

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

7、情況下， 字符串前綴匹配越多的距離越近， 回到我們的案例， 根 據(jù)所在位置查詢來(lái)查詢附近餐館時(shí)， 只需要將所在位置經(jīng)緯度轉(zhuǎn)換成Geo Hash字 符串， 并與各個(gè)餐館的Geo Hash字符串進(jìn)行前綴匹配， 匹配越多的距離越近。Geo Hash核心原理解析Geo Hash算法的步驟地球緯度區(qū)間是-90,90， 北海公園的緯度是39.928167，可以通 過(guò)下面算法對(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；遞歸上述過(guò)程39.928167總是屬于某個(gè)區(qū)間a,b。隨著 每次迭代區(qū)間a,b總在縮小，并越來(lái)越逼近39.928167；如果給定的緯度x（39.928167）屬于左區(qū)間，則記錄0， 如果屬于右區(qū)間則記錄1，這樣隨著算法的進(jìn)行會(huì)產(chǎn)生 一個(gè)序列1011100，序列的長(zhǎng)度跟給定的區(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 編碼長(zhǎng)度為8 時(shí)， 精度在19 米左右， 而當(dāng)編碼長(zhǎng)度為9 時(shí)， 精度在2 米左右， 編碼長(zhǎng)度需要根 據(jù)數(shù)據(jù)情況進(jìn)行選擇。Geo Hash核心原理解析Geo Hash缺陷這種類(lèi)型的空間填充曲線的優(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)致以下問(wèn)題， 比如紅色的點(diǎn)是我們的位 置， 綠色的兩個(gè)點(diǎn)分別是附近的兩個(gè)餐館， 但是 在查詢的時(shí)候會(huì)發(fā)現(xiàn)距離較遠(yuǎn)餐館的Geo Hash編 碼與我們一樣（ 因?yàn)樵谕粋€(gè)Geo Hash區(qū)域塊上）， 而較近餐館的Geo Hash編碼與我們不一致。 這個(gè)問(wèn)題往往產(chǎn)生在邊界處。Geo Hash缺陷解決解決的思路很簡(jiǎn)單， 我們查詢時(shí)， 除了使 用定位點(diǎn)的Geo Hash編碼進(jìn)行匹配外， 還 使用周?chē)? 個(gè)區(qū)域的Geo Hash編碼， 這樣 可以避免這個(gè)問(wèn)題。Geo Hash缺陷解決如何獲取周?chē)藗€(gè)區(qū)域的G e o H a s h 值這個(gè)問(wèn)題我們可以做 如下轉(zhuǎn)化:我們已經(jīng)知道當(dāng)前點(diǎn)的經(jīng)緯度值， 我們也知道每一個(gè)區(qū)域內(nèi) 的經(jīng)度、緯度的寬度，如果