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

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

【參考文獻(xiàn)】

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

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

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

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

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

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

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

，

本文編號(hào)：2117620