本文關鍵詞：道路網skyline查詢處理技術研究

  更多相關文章： 道路網 skyline查詢 位置范圍 道路支配路段 K近鄰 安全范圍 連續(xù)查詢 移動對象

【摘要】：信息技術的發(fā)展使得人們獲取信息的能力逐步提升,信息量急劇增大,形式也逐漸多樣化,對數(shù)據(jù)庫的存儲能力和處理技術的要求也不斷提高。Skyline查詢作為一種能夠在多屬性數(shù)據(jù)中進行多準則優(yōu)化的數(shù)據(jù)庫操作得到大家的廣泛關注。它能夠幫助用戶從海量數(shù)據(jù)信息中獲取感興趣的內容,從而做出正確的決策,在基于位置服務(Location-based Services,LBS)以及股票推薦,環(huán)境監(jiān)測等領域具有重要的應用價值�，F(xiàn)有的用于LBS的skyline查詢技術大多針對非受限的歐式空間環(huán)境,而實際LBS應用中,我們所關注的大部分對象都處在受限空間,尤其是道路網環(huán)境中。對于道路網特殊的拓撲結構,已有的算法未能準確考慮其網絡結構對查詢對象距離屬性的影響,以及對象點的非空間屬性支配關系與道路網支配關系之間的聯(lián)系,造成實際應用中算法的效率和精度都比較低。本文根據(jù)對已有算法的不足的分析,針對道路網環(huán)境,以實際應用場景為基礎,研究道路網上的高效skyline查詢算法,主要研究內容如下:(1)考慮靜態(tài)LBS查詢中定位設備精度和用戶隱私保護的問題,研究了基于位置范圍的道路網skyline查詢。首先提出了一種基本的查詢算法,根據(jù)范圍邊界替換定理將基于位置范圍的skyline查詢轉為基于位置點的查詢來實現(xiàn)。另外,為提高查詢結果的精度,引入了道路網Voronoi單元構建道路網支配路段模型,并基于該模型提出了一種道路網skyline索引結構以及相應的查詢算法,有效地提高了查詢效率和查詢精度。(2)考慮查詢點沿道路網移動中連續(xù)查找距離較近的skyline對象點的問題,研究了道路網連續(xù)K近鄰skyline查詢,并提出了基于K近鄰skyline安全范圍的連續(xù)查詢算法。算法通過引入道路網skyline集合安全范圍和K近鄰穩(wěn)定序列范圍,對當前K近鄰skyline結果集進行維護,當查詢點到達某邊界點即將離開當前安全范圍時觸發(fā)相應的結果集和安全范圍的更新,能夠高效地支持連續(xù)K近鄰skyline查詢,避免連續(xù)快照查詢的重復計算開銷。(3)考慮查詢數(shù)據(jù)集為道路網上的移動對象,研究了針對道路網移動對象的連續(xù)skyline查詢問題,提出了一種基于事件觸發(fā)的連續(xù)查詢算法。首先道路網移動對象的特點建立相關的數(shù)據(jù)模型。之后,算法根據(jù)移動對象之間的距離交叉追蹤對象間的支配關系,從而尋找需要進行結果集更新的時間點,以支持移動對象的連續(xù)查詢。另外,算法中還引入了無效事件剪枝策略,減小了存儲開銷又提高了查詢效率。
【關鍵詞】：道路網 skyline查詢 位置范圍 道路支配路段 K近鄰 安全范圍 連續(xù)查詢 移動對象
【學位授予單位】：南京航空航天大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TP311.13
【目錄】：

• 摘要4-5
• ABSTRACT5-12
• 注釋表12-14
• 第一章 緒論14-20
• 1.1 道路網查詢技術的應用和研究現(xiàn)狀14-16
• 1.2 本文的選題依據(jù)和意義16-17
• 1.3 本文的主要工作17-18
• 1.4 本文的組織結構18-20
• 第二章Skyline查詢處理技術相關工作20-31
• 2.1 Skyline查詢的基本概述20-21
• 2.2 靜態(tài)skyline查詢的經典算法21-25
• 2.2.1 不基于索引的算法21-23
• 2.2.2 基于索引的算法23-25
• 2.3 特殊環(huán)境下的skyline查詢處理技術25-30
• 2.3.1 無線傳感器網絡上的skyline查詢25-26
• 2.3.2 數(shù)據(jù)流上的skyline查詢26-27
• 2.3.3 空間skyline查詢27-29
• 2.3.4 道路網上的skyline查詢29-30
• 2.4 本章小結30-31
• 第三章 基于位置范圍的道路網靜態(tài)skyline查詢31-48
• 3.1 問題描述31-33
• 3.2 對象支配關系分析33-34
• 3.3 基本RNS查詢算法34-36
• 3.4 道路網支配路段模型36-40
• 3.4.1 道路網Voronoi單元36-38
• 3.4.2 道路網支配路段38-40
• 3.5 基于索引的RNS查詢算法40-43
• 3.5.1 SSR-tree索引結構40-42
• 3.5.2 基于SSR-tree索引的RNS查詢算法42-43
• 3.6 實驗與性能評估43-47
• 3.6.1 道路網規(guī)模對查詢性能的影響44
• 3.6.2 POI中對象數(shù)量對查詢性能的影響44-45
• 3.6.3 對象非空間屬性維數(shù)對查詢性能的影響45-46
• 3.6.4 查詢范圍大小對查詢性能的影響46
• 3.6.5 查詢精度的比較46-47
• 3.7 本章小結47-48
• 第四章 道路網連續(xù)K近鄰skyline查詢48-63
• 4.1 問題描述48-50
• 4.2 安全范圍50-56
• 4.2.1 Skyline集合的安全范圍50-53
• 4.2.2 K近鄰穩(wěn)定序列范圍53-55
• 4.2.3 K近鄰skyline復合安全范圍55-56
• 4.3 動態(tài)維護56-58
• 4.3.1 Skyline集合的更新維護56-57
• 4.3.2 穩(wěn)定序列維護57-58
• 4.4 基于安全范圍的連續(xù)K近鄰skyline查詢算法58-59
• 4.5 實驗與性能評估59-62
• 4.5.1 道路網規(guī)模對查詢性能的影響60
• 4.5.2 POI中對象數(shù)量對查詢性能的影響60-61
• 4.5.3 對象非空間屬性維數(shù)對查詢性能的影響61-62
• 4.5.4 參數(shù)k值對查詢性能的影響62
• 4.6 本章小結62-63
• 第五章 道路網移動對象連續(xù)skyline查詢63-75
• 5.1 問題描述63-65
• 5.2 道路網移動對象相關模型65-67
• 5.2.1 數(shù)據(jù)模型65-66
• 5.2.2 道路網移動對象的距離計算模型66-67
• 5.3 基于事件的移動對象連續(xù)skyline查詢算法67-72
• 5.3.1 移動對象skyline的變化分析67-69
• 5.3.2 基于事件的E-MSKY查詢算法69-72
• 5.4 實驗與性能評估72-74
• 5.4.1 移動對象數(shù)據(jù)集大小對查詢性能的影響72-73
• 5.4.2 移動對象非空間屬性維數(shù)對查詢性能的影響73
• 5.4.3 查詢時間長度對查詢性能的影響73-74
• 5.5 本章小結74-75
• 第六章 結束語75-77
• 6.1 本文的主要工作和貢獻75-76
• 6.2 本文的不足和未來的研究方向76-77
• 參考文獻77-82
• 致謝82-83
• 在學期間的研究成果及發(fā)表的學術論文83

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 黃添強;卓飛豹;;移動對象查詢研究進展[J];系統(tǒng)仿真技術;2007年04期

2 李伯權;;基于軌跡不確定的移動對象的預測處理[J];齊齊哈爾大學學報;2008年06期

3 王元芝;鄢來斌;;一種移動對象位置信息的處理方法[J];計算機工程與科學;2009年12期

4 李實吉;秦小麟;施竣嚴;;障礙空間中的移動對象位置預測[J];計算機科學;2014年07期

5 易善楨,張勇,周立柱;一種平面移動對象的時空數(shù)據(jù)模型[J];軟件學報;2002年08期

6 吳勁;盧顯良;;移動對象數(shù)據(jù)模型[J];計算機科學;2002年06期

7 董毅,Edward Chan,黃載祿;LDCQ的距離更新策略[J];華中科技大學學報(自然科學版);2003年12期

8 李國徽;鐘細亞;;一種基于固定網絡的移動對象運動軌跡索引模型[J];計算機研究與發(fā)展;2006年05期

9 盧炎生;查志勇;潘鵬;;一種改進的移動對象時空數(shù)據(jù)模型[J];華中科技大學學報(自然科學版);2006年08期

10 廖巍;唐桂芬;景寧;鐘志農;;基于速度分布的移動對象混合索引方法[J];計算機學報;2007年04期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 翁敬農;;移動對象及其時空模型的研究[A];中國地理信息系統(tǒng)協(xié)會第九屆年會論文集[C];2005年

2 張偉;皮德常;;挖掘移動對象的頻繁運動模式[A];2009年中國智能自動化會議論文集（第三分冊）[C];2009年

3 曹會萍;丁治明;王珊;孟小峰;;移動對象管理的自適應索引方法[A];第十八屆全國數(shù)據(jù)庫學術會議論文集（研究報告篇）[C];2001年

4 胡志智;孟小峰;郭研妍;李本釗;陳繼東;;基于模擬預測的移動對象位置主動更新策略[A];第二十一屆中國數(shù)據(jù)庫學術會議論文集（研究報告篇）[C];2004年

5 陳濱;丁治明;紀鵬程;;基于動態(tài)交通網絡的移動對象的索引[A];第二十三屆中國數(shù)據(jù)庫學術會議論文集（技術報告篇）[C];2006年

6 王波濤;陳賀;馬俊;喜連川優(yōu);王國仁;;基于區(qū)域覆蓋的移動對象索引的設計與實現(xiàn)[A];第26屆中國數(shù)據(jù)庫學術會議論文集（A輯）[C];2009年

7 涂丹丹;向琳;左德承;楊孝宗;;移動對象數(shù)據(jù)庫管理技術[A];黑龍江省計算機學會2007年學術交流年會論文集[C];2007年

8 白蕓;孟小峰;丁銳;楊楠;胡志智;;基于移動對象流的道路索引[A];第二十屆全國數(shù)據(jù)庫學術會議論文集（研究報告篇）[C];2003年

9 劉小峰;陳傳波;劉云生;;移動對象全局K最接近鄰居查詢研究[A];2007年全國開放式分布與并行計算機學術會議論文集(上冊)[C];2007年

10 趙亮;陳犖;景寧;鐘志農;;一種高效的移動對象連續(xù)多范圍查詢處理框架[A];第26屆中國數(shù)據(jù)庫學術會議論文集（B輯）[C];2009年

中國重要報紙全文數(shù)據(jù)庫 前4條

1 中國人民大學信息學院 孟小峰 丁治明;讓數(shù)據(jù)跟隨你移動[N];計算機世界;2001年

2 中國人民大學信息學院 郝興;移動數(shù)據(jù)管理待補課[N];中國計算機報;2008年

3 ;Word中的“微調”技術[N];中國計算機報;2005年

4 四川 余文勇;課件特殊效果巧實現(xiàn)[N];中國電腦教育報;2001年

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

1 吳佩莉;移動對象軌跡數(shù)據(jù)管理關鍵技術研究[D];北京理工大學;2015年

2 楊彬;室內移動對象的數(shù)據(jù)管理[D];復旦大學;2010年

3 葉李;移動對象數(shù)據(jù)庫查詢及處理技術研究[D];電子科技大學;2011年

4 張恒飛;空間數(shù)據(jù)庫中移動對象位置管理技術研究[D];華中科技大學;2012年

5 方穎;移動對象數(shù)據(jù)庫中移動對象索引方法研究[D];武漢大學;2010年

6 廖巍;面向位置服務的移動對象索引與查詢處理技術研究[D];國防科學技術大學;2007年

7 陳楠;時空數(shù)據(jù)庫中移動對象的索引和查詢技術研究[D];浙江大學;2010年

8 趙亮;面向位置服務的移動對象并發(fā)查詢處理技術[D];國防科學技術大學;2010年

9 張鳳荔;移動對象數(shù)據(jù)智能處理模型研究[D];電子科技大學;2007年

10 袁冠;移動對象軌跡數(shù)據(jù)挖掘方法研究[D];中國礦業(yè)大學;2012年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 黃川林;室內移動對象軌跡分析研究[D];中國科學技術大學;2014年

2 王夢冉;蜂窩網中基于頻繁軌跡的越區(qū)切換算法研究[D];西南交通大學;2015年

3 金琨;不確定環(huán)境下移動對象軌跡模式挖掘及路徑規(guī)劃研究[D];西南交通大學;2015年

4 易顯天;面向位置服務的道路網絡下的汽車索引技術研究[D];電子科技大學;2015年

5 畢彥博;優(yōu)化的基于Voronoi圖的移動對象K近鄰查詢算法的研究與實現(xiàn)[D];東北大學;2013年

6 孫清清;面向移動對象間狀態(tài)查詢優(yōu)化算法的研究與實現(xiàn)[D];東北大學;2013年

7 楊雨;面向GPS的移動對象軌跡模式挖掘研究[D];東北大學;2014年

8 張盼盼;融合復合特征的移動軌跡預測方法的研究與實現(xiàn)[D];西安電子科技大學;2014年

9 吳昊;基于路網的移動對象位置管理關鍵技術研究[D];南京郵電大學;2015年

10 李岳昌;基于代價聚簇的城市路網移動對象索引技術[D];南京郵電大學;2015年

，

本文編號：630496