本文選題：空間網(wǎng)絡(luò) + 關(guān)鍵字查詢�。� 參考：《北京郵電大學》2017年博士論文

【摘要】：基于位置的服務(wù)是通過網(wǎng)絡(luò)運營商的無線網(wǎng)絡(luò)或外部定位系統(tǒng)獲取移動終端用戶的位置信息,在地理信息系統(tǒng)平臺的支持下,為用戶提供相應(yīng)的服務(wù)。隨著移動互聯(lián)網(wǎng)的快速發(fā)展和帶有定位模塊的智能設(shè)備的廣泛普及,基于位置的服務(wù)已經(jīng)逐漸滲透到人們?nèi)粘Ｉ畹姆椒矫婷?為人們的生活帶來了極大的便利。例如,人們經(jīng)常利用社交網(wǎng)絡(luò)應(yīng)用來查找附近的人,或使用地圖軟件來進行路線導航。作為位置服務(wù)中的一種重要應(yīng)用,基于空間網(wǎng)絡(luò)的關(guān)鍵字查詢受到學術(shù)界和工業(yè)界的廣泛關(guān)注。基于空間網(wǎng)絡(luò)的關(guān)鍵字查詢是根據(jù)用戶輸入的關(guān)鍵字,查詢空間網(wǎng)絡(luò)中該關(guān)鍵字所匹配的興趣點信息。為提供優(yōu)質(zhì)的關(guān)鍵字查詢服務(wù),需要研究高效的基于空間網(wǎng)絡(luò)的關(guān)鍵字查詢方法,在滿足用戶查詢需求的同時,保證查詢結(jié)果的準確性和查詢過程的高效性。隨著社會的發(fā)展和人們生活水平的提高,用戶的查詢需求日趨多樣化。例如,覆蓋多個關(guān)鍵字的最受歡迎的區(qū)域查詢,或基于多個用戶的查詢。然而,現(xiàn)有的研究在滿足用戶需求的多樣化、查詢結(jié)果的準確性以及查詢時間的高效性等方面仍存在不足。因此,本文針對用戶復雜查詢需求(最受歡迎的多關(guān)鍵字興趣點查詢、滿足多用戶的多關(guān)鍵字區(qū)域查詢和滿足多用戶的關(guān)鍵字路徑查詢),對基于空間網(wǎng)絡(luò)的關(guān)鍵字查詢問題進行了深入研究,并取得了以下創(chuàng)新性成果:(1)提出了一種基于空間網(wǎng)絡(luò)的最受歡迎的多關(guān)鍵字興趣點查詢方法。首先,將該查詢問題定義為找到既能覆蓋用戶需求關(guān)鍵字又能滿足用戶輸入的約束條件(即查詢范圍約束以及分布范圍約束)的最受歡迎的一個或多個興趣點。然后,將帶有興趣點的空間網(wǎng)絡(luò)數(shù)據(jù)建模為一個空間網(wǎng)絡(luò)圖。其中,每個帶有坐標信息的節(jié)點表示一個興趣點或一個交叉口(例如,路口等),每個興趣點附著一個或多個關(guān)鍵字,每個關(guān)鍵字包含一個對應(yīng)的評分用來表示其受歡迎程度;每一條邊表示一段路徑,邊的權(quán)重表示路徑長度。其次,針對小規(guī)模和大規(guī)模的空間網(wǎng)絡(luò),分別設(shè)計出精確的解決方案和啟發(fā)式解決方案。為了進一步提高查詢效率,分別提出了兩個優(yōu)化技術(shù)。其中,第一個是評分最大值預(yù)測技術(shù),用來減少搜索空間。另一個是冗余計算減少技術(shù),用來避免一些不必要的計算開銷。最后,基于兩個真實的數(shù)據(jù)集開展了實驗,實驗結(jié)果表明,針對大規(guī)模空間網(wǎng)絡(luò)數(shù)據(jù)設(shè)計的查詢算法不僅能夠返回高精度的查詢結(jié)果,而且隨著數(shù)據(jù)規(guī)模的增大,其查詢效率仍具有良好的可擴展性。(2)提出了一種基于空間網(wǎng)絡(luò)的多用戶多關(guān)鍵字區(qū)域查詢方法。首先,將該查詢定義為找到一個能夠覆蓋用戶需求關(guān)鍵字的多個興趣點組成的區(qū)域,且該區(qū)域滿足與所有的用戶之間的距離近和其中的興趣點分布密集兩個約束條件。然后,將帶有興趣點的空間網(wǎng)絡(luò)數(shù)據(jù)建模為一個加權(quán)無向圖。圖中每一個節(jié)點表示一個興趣點或一個交叉口(例如,路口等),它包含坐標信息;每一條邊表示一段路徑,邊的權(quán)重表示該段路徑的距離開銷�；谠搱D模型,利用最短路徑樹算法和距離預(yù)測技術(shù),建立高效的索引。其次,基于用戶組分治技術(shù),提出一個近似因子為5的高效算法,用來快速找到一個可行解,利用該可行解有效限制搜索空間。基于動態(tài)剪枝技術(shù)進一步提出了一個精確算法,和一個近似因子為7/15的近似算法。最后,基于兩個真實的數(shù)據(jù)集開展了實驗,實驗結(jié)果表明,提出的近似查詢算法不僅保證了查詢結(jié)果的精確度,而且大幅度提高了查詢效率。(3)提出了一種基于空間網(wǎng)絡(luò)的多用戶多關(guān)鍵字路徑查詢方法。首先,將該查詢定義為找到一條能夠順序覆蓋用戶需求關(guān)鍵字且距離開銷最小的路徑。然后,提出了兩個近似因子分別為n+3和n+1的近似算法,以快速找到第一個可行解,其中,n表示需求關(guān)鍵字的個數(shù)。利用該可行解的成本開銷可以有效限制之后算法的搜索空間。其次,基于限制的搜索空間,提出了兩個精確算法和一個貪心算法。其中,第一個精確算法是通過枚舉出搜索空間中所有的可行解來找出最優(yōu)解。為了提高搜索效率,基于成本函數(shù)的分離屬性和動態(tài)剪枝技術(shù)提出了一個優(yōu)化的精確算法。最后,基于兩個真實的數(shù)據(jù)集開展了實驗,實驗結(jié)果表明,該算法在保證查詢結(jié)果精確性的同時,滿足了用戶實時查詢的要求。
[Abstract]:The invention provides a space network based keyword query method , which is based on a keyword query of a user input and a query result of a plurality of users . ( 2 ) A multi - user multi - key region query method based on spatial network is proposed . First , the query is defined as a region composed of multiple points of interest that can cover the user ' s demand key , and the region satisfies the distance between all users .
【學位授予單位】：北京郵電大學
【學位級別】：博士
【學位授予年份】：2017
【分類號】：TP391.3

【參考文獻】

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

1 劉東;張名揚;陳川;;信息化背景下沿海船舶邊防治安管理研究[J];河北公安警察職業(yè)學院學報;2016年04期

2 任星怡;宋美娜;宋俊德;;基于位置社交網(wǎng)絡(luò)的上下文感知的興趣點推薦[J];計算機學報;2017年04期

3 羅由平;周召敏;周桐;劉婷;;基于警務(wù)位置云平臺的城市交通管理與服務(wù)體系研究[J];中國新技術(shù)新產(chǎn)品;2016年15期

4 曹政;;一種基于位置服務(wù)項目的風險管理流程研究[J];經(jīng)營管理者;2014年10期

5 張復山;;位置服務(wù)融入企業(yè)信息化[J];中國計算機用戶;2009年10期

6 胡加艷;陳秀萬;吳雨航;吳才聰;;移動位置服務(wù)在應(yīng)急救援中的應(yīng)用[J];中國應(yīng)急救援;2008年05期

，

本文編號：2117620