[發明專利]一種以地理位置緯度和經度數位上的數字組合為索引的高效地理位置信息檢索方法

在審

• 申請號: 201610227661.7
• 申請日: 2016-04-13
• 公開（公告）號: CN107291782A
• 公開（公告）日: 2017-10-24
• 發明（設計）人: 周子明
• 申請（專利權）人: 南京兆暢通訊技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及地理位置信息搜索領域，特別是大數據量的地理位置信息的索引和搜索。

背景技術

現代信息系統中，地理位置通常由緯度和經度來表示，例如（31.495688度，120.311257度）代表了江蘇省無錫市金匱公園的地理位置。如果沒有建立索引，在需要搜索系統中某個地理位置x周圍一定距離范圍r內的其他地理位置信息時，需要計算系統中所有的其他地理位置(y1,y2………yn)和x之間的距離(d1,d2…dn)，然后根據計算出的距離是否小于搜索給定的距離范圍（d 是否小于 r）來決定是否將該信息包括在內，這需要通過大量的浮點運算來實現，效率低耗時多。

發明內容

本發明對系統中地理位置根據需要利用緯度和經度的數位上的數字組合建立索引，然后在搜索某個地理位置周圍給定范圍的地理位置信息時時可以利用這些索引將搜索范圍快速縮小到搜索源點周圍的小長方形中，以避免對系統中所有的地理位置做距離計算。

例為地理位置（31.495688度，120.311257度）建立013210439151、0132104391、和01321043三個索引，這些索引產生的方式如下：如果緯度、經度小數點前不足三位，則先在前面加0以補足三位，然后將緯度、經度從左開始輪流取一個數字然后合并起來直到產生所需長度的索引為止。理論上可以為地理位置建立2位、4位、6位...到任意位數的很多索引，但是考慮到地球上兩個經度相同緯度相差1度的點之間的距離大約為111公里，而兩個緯度（）相同經度相差1度的點之間的距離大約為111 * cos(?)公里，而距離的搜索范圍通常是幾百米到幾百公里，那么實際只需要建立12位、10位、8位、6位這幾個索引就足夠了。

為地理位置建立索引后，在需要搜索系統中某個地理位置x周圍一定距離范圍r內的其他地理位置信息時，根據不同大小的搜索范圍選擇相應的索引可以很快將搜索區域縮小至包含搜索范圍的一個長方形中。由于搜索結果在以x為原點， r為半徑的園內，搜索結果內的地理位置緯度一定在x的緯度±r/111范圍內，同時搜索結果內的地理位置經度一定在x的經度±r/（111 * cos(?)）內。如果搜索范圍r在幾百米量級，可以采用12位索引，并通過以下方法獲得包含所有搜索結果的索引集：x的緯度和經度分別舍到小數點后三位，r以米為單位，緯度范圍[x的緯度 - ceiling（r/111）* 0.001]～[x的緯度 + ceiling（r/111）* 0.001]、經度范圍[x的經度 - ceiling（r/（111* cos(?)））* 0.001]～[x的經度 + ceiling（r/（111* cos(?)））* 0.001]所組成的12位索引集包含了所有的搜索結果， 其中ceiling是指向上取整。例如，我們要搜索信息系統中地理位置（31.495688度，120.311257度）周圍100米內(r=100)的地理位置信息，ceiling（r/111）* 0.001 = 0.001，ceiling（r/（111* cos(?)））* 0.001 = 0.002, 緯度31.494度～31.496度，經度120.309度～120.313度的區域包含了要搜索的全部結果，由此可以算出包含搜索結果的索引集{013210439049, 013210439140, 013210439141, 013210439142, 013210439143, 013210439059, 013210439150, 013210439151, 013210439152, 013210439153, 013210439069, 013210439160, 013210439161, 013210439162, 013210439163}，通過對這個索引集內包含的地理位置信息進行和搜索源點的距離計算就得到搜索結果了，圖1是描述了索引集和搜索范圍的關系。

同樣原理，如果搜索幾公里或幾十公里的范圍，則可分別采用10位和8位的索引來實現。

由于現代的信息系統通常可以很快地從巨量的數據中找出索引，在采用本發明索引的地理信息系統中，當需要搜索給定位置周圍某個范圍內的地理信息時，可以很快地先找出包含搜索結果的索引集，然后僅對該索引集所包含的地理信息和搜索位置進行距離計算以找出搜索結果，這樣搜索性能會遠高于沒有索引的系統。在沒有索引的系統中，需要對所有的地理信息和搜索位置進行距離計算才能找出搜索結果。