[發(fā)明專(zhuān)利]用于提供位置信息的裝置、系統(tǒng)和方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201480014711.2
• 申請(qǐng)日: 2014-03-14
• 公開(kāi)（公告）號(hào): CN105556511A
• 公開(kāi)（公告）日: 2016-05-04
• 發(fā)明（設(shè)計(jì)）人: A·拉娜;B·西馬諾夫斯基
• 申請(qǐng)（專(zhuān)利權(quán)）人: 美國(guó)結(jié)構(gòu)數(shù)據(jù)有限公司
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 北京市中咨律師事務(wù)所 11247
• 代理人: 楊曉光;于靜

1.一種裝置，包括：

處理器，其被配置為運(yùn)行存儲(chǔ)在存儲(chǔ)器中的一個(gè)或多個(gè)模塊，其中所 述一個(gè)或多個(gè)模塊被配置為：

接收與感興趣區(qū)域關(guān)聯(lián)的一個(gè)或多個(gè)多邊形；

確定包含在所述一個(gè)或多個(gè)多邊形內(nèi)的多個(gè)子多邊形，其中每個(gè) 所述子多邊形與唯一代碼關(guān)聯(lián)；以及

至少基于所述多個(gè)子多邊形的子集生成第一索引系統(tǒng)，從而提供 用于判定特定位置是否在所述感興趣區(qū)域內(nèi)的有效機(jī)制。

2.根據(jù)權(quán)利要求1所述的裝置，其中所述唯一代碼包括基于分層編碼 方案的位置標(biāo)識(shí)符。

3.根據(jù)權(quán)利要求1所述的裝置，其中所述索引系統(tǒng)包括散列表或概率 數(shù)據(jù)結(jié)構(gòu)中的一個(gè)。

4.根據(jù)權(quán)利要求1所述的裝置，其中所述一個(gè)或多個(gè)模塊被進(jìn)一步配 置為：

確定所述索引系統(tǒng)與先前生成的索引系統(tǒng)之間的差異；以及

向計(jì)算設(shè)備提供所述差異以便更新所述計(jì)算設(shè)備中的所述先前生成的 索引系統(tǒng)。

5.根據(jù)權(quán)利要求1所述的裝置，其中所述一個(gè)或多個(gè)模塊被進(jìn)一步配 置為標(biāo)識(shí)基于所述唯一代碼的層次結(jié)構(gòu)對(duì)所述多個(gè)子多邊形的所述唯一代 碼建模的樹(shù)結(jié)構(gòu)，并且基于所述樹(shù)結(jié)構(gòu)生成所述第一索引系統(tǒng)。

6.根據(jù)權(quán)利要求5所述的裝置，其中所述樹(shù)結(jié)構(gòu)包括分支節(jié)點(diǎn)和葉節(jié) 點(diǎn)，并且所述分支節(jié)點(diǎn)與大于所述葉節(jié)點(diǎn)的地理區(qū)域的地理區(qū)域相關(guān)聯(lián)， 并且其中所述一個(gè)或多個(gè)模塊被配置為通過(guò)從所述分支節(jié)點(diǎn)到所述葉節(jié)點(diǎn) 遍歷所述樹(shù)結(jié)構(gòu)來(lái)生成所述索引系統(tǒng)的索引。

7.根據(jù)權(quán)利要求5所述的裝置，其中所述一個(gè)或多個(gè)模塊被進(jìn)一步配 置為：

確定包括特定子多邊形的一系列多邊形；以及

將所述一系列多邊形與所述樹(shù)結(jié)構(gòu)的對(duì)應(yīng)于所述特定子多邊形的葉節(jié) 點(diǎn)相關(guān)聯(lián)。

8.根據(jù)權(quán)利要求5所述的裝置，其中所述一個(gè)或多個(gè)模塊被進(jìn)一步配 置為將對(duì)應(yīng)于所述感興趣區(qū)域的所述樹(shù)結(jié)構(gòu)與對(duì)應(yīng)于第二感興趣區(qū)域的第 二樹(shù)結(jié)構(gòu)相合并，從而提供對(duì)所述樹(shù)結(jié)構(gòu)和所述第二樹(shù)結(jié)構(gòu)兩者建模的單 個(gè)索引系統(tǒng)。

9.根據(jù)權(quán)利要求1所述的裝置，其中所述一個(gè)或多個(gè)模塊被進(jìn)一步配 置為從所述索引系統(tǒng)中刪除對(duì)應(yīng)于特定多邊形的一個(gè)或多個(gè)子多邊形。

10.根據(jù)權(quán)利要求1所述的裝置，其中所述一個(gè)或多個(gè)模塊被進(jìn)一步 配置為從所述多個(gè)子多邊形中刪除一個(gè)或多個(gè)子多邊形以提供一組精簡(jiǎn)后 的子多邊形，并且從所述一組精簡(jiǎn)后的子多邊形生成所述索引系統(tǒng)，從而 減小所述索引系統(tǒng)的大小。

11.根據(jù)權(quán)利要求1所述的裝置，其中所述一個(gè)或多個(gè)模塊被進(jìn)一步 配置為從另一個(gè)計(jì)算設(shè)備接收第二索引系統(tǒng)，并且通過(guò)考慮與所述第一索 引系統(tǒng)和所述第二索引系統(tǒng)對(duì)應(yīng)的子多邊形的重疊來(lái)合并所述第一索引系 統(tǒng)和所述第二索引系統(tǒng)。

12.根據(jù)權(quán)利要求1所述的裝置，其中所述一個(gè)或多個(gè)模塊被進(jìn)一步 配置為向計(jì)算設(shè)備提供所述索引系統(tǒng)，使得所述計(jì)算設(shè)備能夠使用所述索 引系統(tǒng)來(lái)服務(wù)于位置查詢(xún)。

13.一種用于提供感興趣區(qū)域的索引系統(tǒng)的方法，所述方法包括：

在計(jì)算系統(tǒng)的索引生成模塊處，接收與所述感興趣區(qū)域關(guān)聯(lián)的一個(gè)或 多個(gè)多邊形；

在所述索引生成模塊處，確定包含在所述一個(gè)或多個(gè)多邊形內(nèi)的多個(gè) 子多邊形，其中每個(gè)所述子多邊形與唯一代碼關(guān)聯(lián)；

在所述索引生成模塊處，至少基于所述多個(gè)子多邊形的子集生成第一 索引系統(tǒng)，從而提供用于判定特定位置是否在所述感興趣區(qū)域內(nèi)的有效機(jī) 制。

14.根據(jù)權(quán)利要求13所述的方法，其中所述索引系統(tǒng)包括散列表或概 率數(shù)據(jù)結(jié)構(gòu)中的一個(gè)。