[發(fā)明專利]應(yīng)用于電子地圖的空間關(guān)鍵字查詢的搜索方法

在審

• 申請?zhí)枺?/td>: 201910333874.1
• 申請日: 2019-04-24
• 公開（公告）號: CN110069592A
• 公開（公告）日: 2019-07-30
• 發(fā)明（設(shè)計）人: 姚斌;劉音沛;徐陽;過敏意;陳全;李超;沈耀;冷靜文;鄭文立;林昊
• 申請（專利權(quán)）人: 上海交通大學(xué)
• 主分類號: G06F16/29
• 分類號: G06F16/29;G06F16/9537
• 代理公司: 上海市匯業(yè)律師事務(wù)所 31325
• 代理人: 王函

本發(fā)明公開了一種應(yīng)用于電子地圖的空間關(guān)鍵字查詢的搜索方法，其包括如下步驟：S1:讀取待查詢關(guān)鍵字的數(shù)目，若所述待查詢關(guān)鍵字為多關(guān)鍵字則跳轉(zhuǎn)至S2，否則跳轉(zhuǎn)至步驟S7；S2:將待查詢關(guān)鍵字的頻率與頻率閾值進(jìn)行比對，若待查詢關(guān)鍵字的頻率為低頻則跳轉(zhuǎn)至步驟S7、否則跳轉(zhuǎn)至步驟S3；S3，構(gòu)建葉子節(jié)點u：將各關(guān)鍵字t映射到包含t的對象列表來構(gòu)建u的倒排列表，并收集u的詞匯表構(gòu)建父節(jié)點的布隆過濾器；S4，構(gòu)建非葉子節(jié)點p：將p的各個子項指向的子節(jié)點構(gòu)成節(jié)點p的詞匯表，并插入初始化布隆過濾器；S5，基于布隆過濾器的IR?tree的構(gòu)建；S6，構(gòu)建IR?tree的查詢索引；S7：對待查詢關(guān)鍵字構(gòu)建R?tree查詢結(jié)構(gòu)。本發(fā)明提升其對關(guān)鍵字的索引效率，節(jié)約系統(tǒng)資源。

技術(shù)領(lǐng)域

本發(fā)明屬于定位技術(shù)領(lǐng)域，具體來說涉及一種應(yīng)用于Spark平臺上的應(yīng)用于電子地圖的空間關(guān)鍵字查詢的搜索方法。

背景技術(shù)

近年來隨著通信技術(shù)的發(fā)展和移動終端的廣泛使用，基于位置的社會服務(wù)層出不窮。空間關(guān)鍵字查詢是以用戶的地理位置信息和多個查詢關(guān)鍵字作為參數(shù)，返回和這些參數(shù)有著空間和文本相關(guān)度的空間對象。在一個查詢中，構(gòu)建有效的索引結(jié)構(gòu)，可以極大地提高查詢效率。對于一個空間中的索引，是指將對象的位置信息，大小形狀等按照一定結(jié)構(gòu)排列的一種數(shù)據(jù)結(jié)構(gòu)。準(zhǔn)確空間關(guān)鍵字查詢的最先進(jìn)的解決方案都是基于空間優(yōu)先的索引結(jié)構(gòu)，這種方案存在的問題是，一般的空間文本對象都會有至少數(shù)十個關(guān)鍵字。而基于空間優(yōu)先的結(jié)構(gòu)在對平均具有數(shù)十個關(guān)鍵字的空間文本對象進(jìn)行索引優(yōu)化時非常低效。此外,空間優(yōu)化結(jié)構(gòu)利用字符串匹配來剪枝無關(guān)節(jié)點，這在處理出現(xiàn)頻率較高的關(guān)鍵字時可能是無意義的，而在這種情況下，我們?nèi)匀恍枰L問許多子節(jié)點。因此，如何開發(fā)出一種新型的空間關(guān)鍵字查詢的搜索方法，能夠在空間關(guān)鍵字查詢過程中提升其對關(guān)鍵字的索引效率，節(jié)約系統(tǒng)資源，是本領(lǐng)域技術(shù)人員需要研究的方向。以下為本申請中所涉及的字母縮寫的注釋：R-tree：B-tree向多維空間發(fā)展的另一種形式，它將空間對象按范圍劃分，每個結(jié)點都對應(yīng)一個區(qū)域和一個磁盤頁，非葉結(jié)點的磁盤頁中存儲其所有子結(jié)點的區(qū)域范圍，非葉結(jié)點的所有子結(jié)點的區(qū)域都落在它的區(qū)域范圍之內(nèi)。IR-tree:以倒排索引和R-tree索引為基礎(chǔ)，通過倒排索引解決文本相似度的計算模型。BFIR-tree：基于海量數(shù)據(jù)處理實現(xiàn)的IR-tree；CBFIR-tree：動態(tài)的BFIR-tree；S2I-V結(jié)構(gòu)：對不同頻率的關(guān)鍵字應(yīng)被區(qū)別處理的模型結(jié)構(gòu)；eBRQ：基于關(guān)鍵字包含的范圍查詢；aBRQ：基于近似關(guān)鍵字包含的k最近鄰查詢；falsepositive：誤檢率；。KNN算法：即臨近算法，是數(shù)據(jù)挖掘分類技術(shù)中最簡單的方法之一。I-Node：一個葉子R樹節(jié)點，它存儲了將每個關(guān)鍵字映射到空間關(guān)鍵字對象的倒排列表。

發(fā)明內(nèi)容

本發(fā)明要解決的技術(shù)問題是提供了一種應(yīng)用于電子地圖的空間關(guān)鍵字查詢的搜索方法，能夠提升其對關(guān)鍵字的索引效率，節(jié)約系統(tǒng)資源。

其采用的技術(shù)方案如下：

一種應(yīng)用于電子地圖的空間關(guān)鍵字查詢的搜索方法，其包括如下步驟：S1：讀取數(shù)據(jù)集的各條數(shù)據(jù)進(jìn)行索引構(gòu)建、針對單條數(shù)據(jù)的各個關(guān)鍵字分別跳轉(zhuǎn)至步驟S2；S2:將關(guān)鍵字的頻率與頻率閾值進(jìn)行比對，若關(guān)鍵字的頻率低于所述頻率閾值則跳轉(zhuǎn)至步驟S7、否則跳轉(zhuǎn)至步驟S3；S3，構(gòu)建葉子節(jié)點u：設(shè)u中包含的點的集合為up，將各關(guān)鍵字t映射到包含t的對象列表來構(gòu)建u的倒排列表，并收集u的詞匯表構(gòu)建父節(jié)點的布隆過濾器；S4，構(gòu)建非葉子節(jié)點p：設(shè)p的子項為{c1,…,cf}，所述f為一個節(jié)點最大能容納的子項數(shù)目，將p的各個子項指向的子節(jié)點構(gòu)成節(jié)點p的詞匯表，并對各關(guān)鍵字插入初始化的布隆過濾器；S5，構(gòu)建根節(jié)點、完成基于布隆過濾器的IR-tree的構(gòu)建；S6，構(gòu)建基于布隆過濾器的IR-Tree結(jié)構(gòu)的查詢索引；S7：對待查詢關(guān)鍵字構(gòu)建R-tree數(shù)據(jù)查詢結(jié)構(gòu)。