本文關(guān)鍵詞：歐式空間與道路網(wǎng)上的Top-K查詢處理研究，由筆耕文化傳播整理發(fā)布。

【摘要】：最近十年以來,移動(dòng)互聯(lián)網(wǎng)的巨大變革,激發(fā)了移動(dòng)設(shè)備,如智能手機(jī)的革新以及手機(jī)上各類應(yīng)用的快速發(fā)展。在各類應(yīng)用中,基于地理位置信息的應(yīng)用(Location-Based Services)就是其中很重要的一大類。Top-K查詢就是最經(jīng)典的一種查詢模式。典型的應(yīng)用場景就是用戶使用手機(jī),在某個(gè)地理坐標(biāo)上,表達(dá)出查詢意圖(比如,關(guān)鍵詞),系統(tǒng)返回距離用戶最近,或跟意圖最相關(guān)的Top-K結(jié)果。在這個(gè)問題上,已有不少的研究工作。但是,現(xiàn)有方法存在兩方面的缺陷和不足。一方面是查詢處理效率上的不足,導(dǎo)致的用戶體驗(yàn)較差;另一方面是存儲(chǔ)和運(yùn)算的代價(jià)太高,很難支持大規(guī)模數(shù)據(jù)集。本文的研究核心,就是圍繞不同的查詢方式(是否支持即敲即得),不同空間距離度量(歐式距離,道路網(wǎng)距離),以及不同的文本相似性(是否支持關(guān)鍵詞),這三個(gè)層面,解決現(xiàn)有方法的以上問題,論文的主要貢獻(xiàn)如下:1.歐式空間上即敲即得的關(guān)鍵詞Top-K查詢:為了實(shí)現(xiàn)用戶體驗(yàn)更好的即敲即得查詢方式,并解決傳統(tǒng)查詢算法存儲(chǔ)代價(jià)高,剪枝效果差的問題,論文提出了一種新穎的索引結(jié)構(gòu),叫做PR-Tree。跟傳統(tǒng)方法只基于單個(gè)維度構(gòu)造索引,再增加過濾器的方法的不同之處在于,PR-Tree在構(gòu)造時(shí)候同時(shí)考慮了文本和空間這兩個(gè)維度的信息,從而克服了傳統(tǒng)方法在剪枝效果上的缺陷。基于PR-Tree,論文討論了基于單前綴的查詢算法,和基于多關(guān)鍵詞的查詢方法。與現(xiàn)有方法比較,PR-Tree能普遍快1到2個(gè)數(shù)量級(jí)。2.道路網(wǎng)上的可擴(kuò)展索引與Top-K查詢:基于道路距離的Top-K查詢比基于歐式距離的查詢更有現(xiàn)實(shí)意義,因?yàn)闊o論是行走還是駕車,人們都在道路網(wǎng)絡(luò)上進(jìn)行而非直線移動(dòng)。相比歐式空間,道路網(wǎng)上的Top-K查詢處理有兩大挑戰(zhàn)。第一是如何快速計(jì)算點(diǎn)到點(diǎn)最短路,第二是如何做到高效的剪枝。為了解決這兩大難題,論文構(gòu)造了一種平衡樹索引,名為G-Tree。G-Tree是通過遞歸切割道路網(wǎng)構(gòu)造而成的。為了計(jì)算道路距離,在每個(gè)G-Tree節(jié)點(diǎn)上,會(huì)預(yù)處理一系列最短路,并開創(chuàng)性的使用“距離拼接算法”,來求解任意兩點(diǎn)的最短路�；谶@個(gè)距離,可以利用最佳優(yōu)先遍歷算法,進(jìn)行高效的Top-K查詢剪枝。G-Tree比當(dāng)今前沿算法能快2到3個(gè)數(shù)量級(jí)左右,并能輕松支持全美國道路網(wǎng)規(guī)模的數(shù)據(jù)集。3.道路網(wǎng)上基于關(guān)鍵詞的Top-K查詢:現(xiàn)實(shí)中,用戶不僅只關(guān)心到目標(biāo)對(duì)象的道路距離,還可能通過關(guān)鍵詞表達(dá)查詢意圖。論文將查詢關(guān)鍵詞與目標(biāo)對(duì)象的文本相似度,與道路最短路兩者結(jié)合起來,加權(quán)得到一個(gè)新的排名度量進(jìn)行Top-K查詢處理。借助之前G-Tree的框架,論文改造出一種新的索引結(jié)構(gòu),稱為IG-Tree。IG-Tree的每個(gè)節(jié)點(diǎn)會(huì)存儲(chǔ)一個(gè)關(guān)鍵詞的倒排索引,以表示該關(guān)鍵詞在這棵子樹下可能取得的文本相似性的上界。通過對(duì)最佳優(yōu)先遍歷算法的優(yōu)化,IG-Tree表現(xiàn)出其優(yōu)秀的剪枝能力和擴(kuò)展性。
【關(guān)鍵詞】：Top-K查詢 空間數(shù)據(jù)庫 即敲即得 歐式空間 道路網(wǎng) 關(guān)鍵詞查詢
【學(xué)位授予單位】：清華大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP311.13
【目錄】：

• 摘要3-5
• abstract5-10
• 第1章 緒論10-21
• 1.1 選題背景和研究動(dòng)機(jī)10-18
• 1.1.1 歐式空間上即敲即得的關(guān)鍵詞Top-K查詢12-14
• 1.1.2 道路網(wǎng)上的可擴(kuò)展索引與Top-K查詢14-16
• 1.1.3 道路網(wǎng)上基于關(guān)鍵詞的Top-K查詢16-18
• 1.2 主要研究內(nèi)容及論文的貢獻(xiàn)18-20
• 1.3 章節(jié)安排20-21
• 第2章 歐式空間上即敲即得的關(guān)鍵詞Top-K查詢21-44
• 2.1 研究背景21-22
• 2.2 問題定義22-23
• 2.3 前綴-區(qū)域樹23-28
• 2.3.1 解決辦法概要23-24
• 2.3.2 前綴-區(qū)域樹24-26
• 2.3.3 PR-Tree的構(gòu)造26-28
• 2.4 PR-Tree的性質(zhì)討論28-29
• 2.4.1 平衡性28-29
• 2.4.2 空間復(fù)雜度29
• 2.4.3 存儲(chǔ)方式29
• 2.5 查詢算法29-34
• 2.5.1 單前綴查詢算法29-30
• 2.5.2 多關(guān)鍵詞查詢算法30-34
• 2.6 排名函數(shù)的擴(kuò)展34-35
• 2.7 實(shí)驗(yàn)結(jié)果35-41
• 2.7.1 實(shí)驗(yàn)設(shè)定35-36
• 2.7.2 單前綴查詢的對(duì)比實(shí)驗(yàn)36-38
• 2.7.3 多關(guān)鍵詞查詢的對(duì)比實(shí)驗(yàn)38-40
• 2.7.4 不同空間劃分策略的影響40
• 2.7.5 可擴(kuò)展性40-41
• 2.7.6 對(duì)排序函數(shù)的實(shí)驗(yàn)41
• 2.8 相關(guān)工作41-42
• 2.8.1 即敲即得的關(guān)鍵詞查詢41-42
• 2.8.2 空間關(guān)鍵詞查詢42
• 2.9 總結(jié)42-44
• 第3章 道路網(wǎng)上的可擴(kuò)展索引與Top-K查詢44-72
• 3.1 研究背景44-45
• 3.2 問題定義45
• 3.3 G-Tree索引45-49
• 3.3.1 解決辦法概要45-46
• 3.3.2 G-Tree的定義46-48
• 3.3.3 G-Tree的構(gòu)造48
• 3.3.4 G-Tree的空間復(fù)雜度48-49
• 3.4 查詢算法49-57
• 3.4.1 查詢算法概要49-51
• 3.4.2 SPDist函數(shù)的實(shí)現(xiàn)51-57
• 3.5 時(shí)間復(fù)雜度分析57
• 3.6 路徑恢復(fù)57-60
• 3.6.1 概覽57-58
• 3.6.2 路徑恢復(fù)算法58-60
• 3.6.3 路徑恢復(fù)時(shí)間空間復(fù)雜度分析60
• 3.7 補(bǔ)充討論60-62
• 3.7.1 高效計(jì)算距離矩陣60-61
• 3.7.2 拓展到有向圖61-62
• 3.7.3 平面圖的討論62
• 3.8 實(shí)驗(yàn)結(jié)果62-68
• 3.8.1 對(duì)參數(shù)f和τ的驗(yàn)證63-64
• 3.8.2 與現(xiàn)有最前沿方法的比較64-67
• 3.8.3 對(duì)路徑恢復(fù)效率的評(píng)估67
• 3.8.4 可擴(kuò)展性的評(píng)估67-68
• 3.8.5 對(duì)有向圖的評(píng)估68
• 3.9 相關(guān)工作68-70
• 3.9.1 基于道路網(wǎng)的Top-K查詢68-70
• 3.9.2 道路網(wǎng)上移動(dòng)目標(biāo)的Top-K查詢70
• 3.9.3 道路網(wǎng)上點(diǎn)到點(diǎn)最短路問題70
• 3.10 總結(jié)70-72
• 第4章 道路網(wǎng)上基于關(guān)鍵詞的Top-K查詢72-86
• 4.1 研究背景72-73
• 4.2 問題定義73-74
• 4.3 IG-Tree索引74-77
• 4.3.1 解決辦法概要74-75
• 4.3.2 IG-Tree的構(gòu)造75-76
• 4.3.3 IG-Tree的空間復(fù)雜度76-77
• 4.4 查詢算法77-80
• 4.4.1 G-Tree查詢算法的改進(jìn)77-79
• 4.4.2 基于IG-Tree的查詢算法79-80
• 4.5 實(shí)驗(yàn)結(jié)果80-83
• 4.5.1 實(shí)驗(yàn)設(shè)定80-81
• 4.5.2 改進(jìn)的G-Tree查詢處理效率評(píng)估81-83
• 4.5.3 基于IG-Tree的關(guān)鍵詞Top-K查詢效率評(píng)估83
• 4.6 相關(guān)工作83-84
• 4.6.1 道路網(wǎng)上基于關(guān)鍵詞的Top-K查詢83-84
• 4.7 總結(jié)84-86
• 第5章 總結(jié)與展望86-88
• 5.1 論文主要研究工作總結(jié)86-87
• 5.2 進(jìn)一步研究工作及展望87-88
• 參考文獻(xiàn)88-93
• 致謝93-95
• 個(gè)人簡歷、在學(xué)期間發(fā)表的學(xué)術(shù)論文與研究成果95

【相似文獻(xiàn)】

中國博士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 鐘睿鋮;歐式空間與道路網(wǎng)上的Top-K查詢處理研究[D];清華大學(xué);2015年

  本文關(guān)鍵詞：歐式空間與道路網(wǎng)上的Top-K查詢處理研究，由筆耕文化傳播整理發(fā)布。

，

本文編號(hào)：257596