【摘要】：隨著移動終端,如手機,平板電腦等的普及,和位置傳感器、定位及導航系統(tǒng)的廣泛應用,產(chǎn)生了大量帶有地理位置信息的空間數(shù)據(jù),也催生了大量對基于位置的服務的需求。比如,百度地圖中的導航功能,大眾點評中離我最近的餐廳功能等都給用戶帶來了便捷。針對如何利用空間查詢技術(shù)對海量空間數(shù)據(jù)進行存儲和分析,并最終支持用戶日益?zhèn)�性化、多樣化的查詢需求,如何進行高效的空間關(guān)鍵詞查詢(Spatial Keyword Query)顯得至關(guān)重要。常見的空間關(guān)鍵詞查詢分為范圍查詢和最近鄰查詢,盡管這兩類查詢已經(jīng)帶來了大量便利,但這兩類查詢?nèi)匀淮嬖谝粋�問題:無法精確捕捉用戶意圖。比如,現(xiàn)有的空間關(guān)鍵詞查詢算法不能處理對于不同對象之間的關(guān)系有限制的需求,也不能處理多個查詢對象且任意兩個對象間距離區(qū)間都不同的需求。針對此問題,本文圍繞空間模式匹配(Spatial Pattern Matching)展開研究。本文的主要研究工作有:(1)改進了現(xiàn)有的空間查詢模型,使用基于圖的空間模式對查詢條件進行建模�？臻g模式是簡單圖,圖的每個頂點對應了一個對象,圖的每條邊對應了頂點間距離區(qū)間和相互關(guān)系。對于同一個模式,本文使用現(xiàn)有的空間查詢mCK算法和本文設(shè)計的適用于SPM的算法找出匹配,對比這兩個匹配,可以看出,空間模式能夠更加精準地捕捉和滿足用戶需求。(2)改進了適用于圖模式匹配問題的算法來進行空間模式匹配,同時,基于多路連接的思想設(shè)計了 MSJ算法,MSJ通過動態(tài)規(guī)劃簡化模式中的距離關(guān)系,并采用剪枝策略進一步優(yōu)化,實驗表明MSJ算法更高效。(3)針對當用戶給定的空間模式要求較寬松時,找到的匹配過多對用戶進行選擇造成了負擔的情況,設(shè)計了評估函數(shù)用于評價不同匹配的質(zhì)量,并提出了快速排序算法IncMatch能夠在不求出全部匹配的情況下增量搜索并返回最佳的匹配。(4)針對用戶給定的空間模式限制過多,導致模式無法在空間數(shù)據(jù)庫中找到匹配的情況,引入最大可行子模式的概念來衡量匹配程度,并分別基于Aporiori思想和MARGIN思想設(shè)計了兩種算法APM和MPM來找出最大可行子模式,進而找到對應于最大可行子模式的部分匹配。
【圖文】：

定義２－３邋（ｃｕｔ［２】）如果ｌａｔｔｉｃｅ中一對節(jié)點（０？，，尺）滿足Ｃ７？是／？的孩子，且／？頻逡逑繁而Ｃ／？不頻繁，則（以，７？）構(gòu)成一個Ｍ。逡逑以圖２－５（ｂ）為例，Ｌ是圖Ｇ的ｌａｔｔｉｃｅ：邋Ｌ包含７個節(jié)點，最底層的節(jié)點是逡逑空圖，最頂層的節(jié)點代表Ｇ，每對父子節(jié)點都用虛線相連。假設(shè)圖２－５（ｂ）中虛逡逑線圈出的圖是頻繁圖，而圖Ｇ不頻繁，則這對節(jié)點是一個ｃｕｔ邋（圖中用加粗實逡逑線標出）。逡逑ＭＡＲＧＩＮ的基本思路如下：首先不斷刪除Ｇ中的一條邊直到得到一逡逑個頻繁子圖義Ａ和的孩子Ｃ７？形成初始ｃｕｔ，然后對（Ｃ７？，／？）調(diào)用算法逡逑ＥｘｐａｎｄＣｕｔＲ從而發(fā)現(xiàn)該ｃｕｔ附近的其他ｃｕｔ，遞歸地對新發(fā)現(xiàn)的所有ｃｕｔ調(diào)逡逑用ＥｘｐａｎｄＣｕｔ１２１，直到?jīng)]有新的ｃｕｔ被發(fā)現(xiàn)。找到所有ｃｕｔ后，對這些ｃｕｔ中逡逑的頻繁節(jié)點進行比較，找到其中的最大子圖，該子圖（可能有多個最大頻繁子逡逑圖）即為Ｇ的最大頻繁子圖。逡逑％邐ｃ0＞逡逑／邐ｃ，邋＞邐＼邋ｃ邐＼逡逑ｐ邐ｐ邋Ｐ］邋ｐ２邐＼邐＞邋ｉ邋＾逡逑（ａ）邐（ｂ）邐Ｐ＊邐Ｓ丨？邋？邐＆逡逑（Ｃ＞邐（ｄ）逡逑——Ｉｎｆｒｅｑｕｅｎｔ邋ｓｕｂｇｒａｐｈ邐——Ｆｒｅｑｕｅｎｔ邋ｓｕｂｇｒａｐｈ逡逑圖２－６：邋ＥｘｐａｎｄＣｕｔ算法實例逡逑以圖２－６為例

圖３－３：邋ＰＪ中候選對圖解逡逑
【學位授予單位】：南京大學
【學位級別】：碩士
【學位授予年份】：2019
【分類號】：TP311.13

【相似文獻】

相關(guān)期刊論文 前10條

1 劉琪;毛繼光;;概念整合視角下《三體》英譯本七空間模式研究[J];長江叢刊;2017年02期

2 李p

本文編號：2595325