[發(fā)明專(zhuān)利]知識(shí)圖譜標(biāo)簽松散場(chǎng)景下地理信息索引系統(tǒng)及檢索方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202011048405.4
• 申請(qǐng)日: 2020-09-29
• 公開(kāi)（公告）號(hào): CN112214612B
• 公開(kāi)（公告）日: 2022-09-30
• 發(fā)明（設(shè)計(jì)）人: 龍萬(wàn)成;王麗蘋(píng)
• 申請(qǐng)（專(zhuān)利權(quán)）人: 華東師范大學(xué)
• 主分類(lèi)號(hào): G06F16/36
• 分類(lèi)號(hào): G06F16/36;G06F16/31;G06F16/29;G06F16/9537
• 代理公司: 上海藍(lán)迪專(zhuān)利商標(biāo)事務(wù)所(普通合伙) 31215
• 代理人: 徐筱梅;張翔

1.一種知識(shí)圖譜標(biāo)簽松散場(chǎng)景下地理信息索引系統(tǒng)，其特征在于，所述索引系統(tǒng)為L(zhǎng)R樹(shù)；所述LR樹(shù)以R樹(shù)為基礎(chǔ)，在存儲(chǔ)空間信息的同時(shí)，再存儲(chǔ)每個(gè)節(jié)點(diǎn)的可達(dá)標(biāo)簽集合，以增強(qiáng)檢索時(shí)剪枝效力；

其中可達(dá)標(biāo)簽集合具體為：

設(shè)S是知識(shí)圖譜G中所有地理節(jié)點(diǎn)的集合，NS是知識(shí)圖譜中所有NS-DFS遍歷樹(shù)的集合，L_U是知識(shí)圖譜G中的標(biāo)簽全集，L(t)表示NS-DFS遍歷樹(shù)t中所有節(jié)點(diǎn)標(biāo)簽的集合，即并有集合L＝{L(t)|t∈NS}，由NS-DFS遍歷樹(shù)的定義可知，每一個(gè)地理節(jié)點(diǎn)唯一對(duì)應(yīng)一棵NS-DFS遍歷樹(shù)，即

由于每一棵NS-DFS遍歷樹(shù)的節(jié)點(diǎn)數(shù)量是有限且確定的，每一個(gè)節(jié)點(diǎn)所關(guān)聯(lián)的標(biāo)簽也是有限且確定的，那么根據(jù)一棵NS-DFS遍歷樹(shù)計(jì)算出唯一的節(jié)點(diǎn)標(biāo)簽集合，即

那么對(duì)于有即存在滿射

即對(duì)于任意一個(gè)在知識(shí)圖譜G中的地理節(jié)點(diǎn)s，總能夠找到一個(gè)標(biāo)簽集合ψ(s)與其對(duì)應(yīng)，將標(biāo)簽集合ψ(s)稱(chēng)為地理節(jié)點(diǎn)s的可達(dá)標(biāo)簽集合；

基于所述的可達(dá)標(biāo)簽集合：

LR樹(shù)中的每一個(gè)葉節(jié)點(diǎn)存儲(chǔ)的信息：1)地理節(jié)點(diǎn)s的節(jié)點(diǎn)信息；2)該地理節(jié)點(diǎn)的可達(dá)標(biāo)簽集合ψ(s)；

LR樹(shù)中的每一個(gè)非葉節(jié)點(diǎn)存儲(chǔ)的信息：1)其子節(jié)點(diǎn)的最小外接矩形；2)其子節(jié)點(diǎn)的可達(dá)標(biāo)簽集合的并集；

即對(duì)于LR樹(shù)中的每一個(gè)節(jié)點(diǎn)R，都維護(hù)著該節(jié)點(diǎn)的可達(dá)標(biāo)簽集合L(R)，且有：

其中表示LR樹(shù)的節(jié)點(diǎn)R維護(hù)地理節(jié)點(diǎn)s的信息，表示LR樹(shù)的節(jié)點(diǎn)R維護(hù)子節(jié)點(diǎn)r的信息；

所述NS-DFS：若在知識(shí)圖譜G中以地理節(jié)點(diǎn)為起點(diǎn)進(jìn)行深度優(yōu)先搜索DFS的過(guò)程中，除了作為起點(diǎn)的地理節(jié)點(diǎn)外，只對(duì)非地理節(jié)點(diǎn)進(jìn)行遞歸搜索，則稱(chēng)該深度優(yōu)先搜索為NS-DFS；

所述NS-DFS遍歷樹(shù)：對(duì)地理節(jié)點(diǎn)s進(jìn)行一次NS-DFS遍歷所得到的遍歷樹(shù)稱(chēng)為地理節(jié)點(diǎn)s的NS-DFS遍歷樹(shù)。

2.一種利用權(quán)利要求1所述索引系統(tǒng)進(jìn)行檢索的方法，其特征在于，該方法包括以下具體步驟：

步驟1：根據(jù)查詢條件得到該查詢所限定的標(biāo)簽集合L(Q)；

步驟2：從根節(jié)點(diǎn)開(kāi)始，對(duì)索引系統(tǒng)即LR樹(shù)每一個(gè)節(jié)點(diǎn)進(jìn)行檢索；在對(duì)LR樹(shù)的節(jié)點(diǎn)R進(jìn)行檢索時(shí)，需滿足：1)節(jié)點(diǎn)R滿足空間謂詞；2)否則，直接對(duì)LR樹(shù)節(jié)點(diǎn)R的子樹(shù)進(jìn)行剪枝；在檢索到葉節(jié)點(diǎn)時(shí)，若該葉節(jié)點(diǎn)仍然滿足上述的兩個(gè)條件，則將該葉節(jié)點(diǎn)加入候選集S_Q；

步驟3：對(duì)于候選集S_Q中的每一個(gè)元素s，對(duì)其N(xiāo)S-DFS遍歷樹(shù)進(jìn)行常規(guī)的導(dǎo)航式查詢，將滿足條件的結(jié)果加入結(jié)果集；若候選集S_Q中的每一個(gè)元素都已搜索完畢，則返回結(jié)果集。