大數(shù)據(jù)時(shí)代下,數(shù)據(jù)呈多維化、海量化的特征,查詢趨于個(gè)性化,用戶對(duì)結(jié)果的準(zhǔn)確度、查詢效率要求更高。傳統(tǒng)的多維數(shù)據(jù)查詢方法存在不能高效地解決靜態(tài)和空間屬性相結(jié)合、動(dòng)態(tài)的多用戶查詢以及分類域上的個(gè)性化查詢等問題,因此研究在度量空間中的多用戶查詢以及分類域上的用戶偏好獲取對(duì)于找出高質(zhì)量的結(jié)果集具有十分重要的意義。多維Skyline查詢根據(jù)對(duì)象數(shù)據(jù)點(diǎn)的屬性值特性主要分成兩類:數(shù)值域和分類域。本文重點(diǎn)關(guān)注空間數(shù)值屬性查詢和分類域?qū)傩越换栴},設(shè)計(jì)并提出高效的多用戶Skyline查詢交互算法,主要研究?jī)?nèi)容如下:（1）歐式空間中Skyline查詢大多僅對(duì)空間屬性進(jìn)行探究,而忽略了與靜態(tài)屬性相結(jié)合的問題,本文基于Voronoi圖、R-tree、凸包等結(jié)構(gòu)的性質(zhì),提出查詢區(qū)域的概念,給出Voronoi R-tree Search算法。該算法通過對(duì)數(shù)據(jù)集剪枝、分階段支配比較等方式,有效減少了距離計(jì)算和數(shù)據(jù)點(diǎn)間的支配檢驗(yàn)次數(shù)。在真實(shí)和模擬數(shù)據(jù)集中驗(yàn)證了該算法的有效性。（2）基于道路網(wǎng)的Skyline查詢?cè)趧?dòng)態(tài)屬性上存在僅考慮距離,并未考慮用戶速度對(duì)查詢結(jié)果影響的問題。本文給出能處理用戶速度變化的查詢算法Exi... 

【文章來源】：南京航空航天大學(xué)江蘇省 211工程院校

【文章頁數(shù)】：74 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

Nassau海灘旅館的Skyline如圖1.1是Skyline查詢領(lǐng)域中的一個(gè)經(jīng)典示例

圖 2.1 空間支配關(guān)系示例義 2.10 （完全支配） 對(duì)于給定的m維數(shù)據(jù)集 POI， 、∈POI，給定用以下兩個(gè)必要條件時(shí)，稱 完全支配 ，記為 q ： ns s 。文將分別針對(duì)這三類 Skyline 查詢的相關(guān)工作進(jìn)行詳細(xì)闡述。靜態(tài)屬性上的 Skyline 查詢 Skyline 研究中受到關(guān)注最早，并且研究最多的工作為對(duì)象數(shù)據(jù)集中僅包含靜line 查詢操作。按是否構(gòu)建索引可將經(jīng)典算法分為兩類，如表 2.4 所示。表 2.4 經(jīng)典算法不基于索引 基于索引塊嵌套循環(huán)（BNL）算法[7]邊際貢獻(xiàn)（EAPSQ）算法[41]分治（D&C）算法[7]最近鄰（NN）算法[40]排序過濾（SFS）算法[25]Index 算法[28]

南京航空航天大學(xué)碩士學(xué)位論文 窗口中存在點(diǎn)被 p 支配：將 存入窗口，剔除窗口中 所支配的 窗口中的點(diǎn)和 不可相互支配：如果窗口還可以繼續(xù)寫入，則將 ，將 存入文件，在下一次處理時(shí)調(diào)用。處理結(jié)束后，可將窗口中的對(duì)象點(diǎn)直接輸出，其是 Skyline 結(jié)果集的環(huán)迭代中，再用上述方法將磁盤臨時(shí)文件中的對(duì)象數(shù)據(jù)點(diǎn)進(jìn)行支配比數(shù)為零時(shí)則停止迭代，此時(shí)的結(jié)果集即為最終的 Skyline 結(jié)果集。可于數(shù)據(jù)規(guī)模較小的查詢。最差情況下的時(shí)間復(fù)雜度為 2O n ，最好度為 O n 。icki 等[25]基于 BNL 提出了 SFS 算法（SortFilter Skyline）。該算法首先序處理，保證后面的點(diǎn)無法支配排序在其前面的所有點(diǎn)，由此可以判的對(duì)象點(diǎn)一定都屬于 Skyline 結(jié)果集。由此可得，SFS 既加快了計(jì)算 BNL 算法簡(jiǎn)單通用的優(yōu)勢(shì)。

【參考文獻(xiàn)】：
期刊論文
[1]空間Skyline查詢處理:應(yīng)用、研究與挑戰(zhàn)[J]. 余未,鄭吉平,王海翔,王永閣,陳嘉良,江順青.  計(jì)算機(jī)科學(xué). 2017(02)
[2]基于位置范圍的道路網(wǎng)skyline查詢[J]. 施常月,秦小麟,許建秋,胡彩平.  計(jì)算機(jī)科學(xué). 2014(09)
[3]一種處理Skyline查詢的有效方法[J]. 黃震華,向陽,薛永生,劉嘯嶺.  計(jì)算機(jī)研究與發(fā)展. 2010(11)
[4]Skyline查詢處理[J]. 魏小娟,楊婧,李翠平,陳紅.  軟件學(xué)報(bào). 2008(06)
[5]Skyline計(jì)算研究綜述[J]. 朱琳,關(guān)佶紅,周水庚.  計(jì)算機(jī)工程與應(yīng)用. 2008(06)

碩士論文
[1]道路網(wǎng)skyline查詢處理技術(shù)研究[D]. 施常月.南京航空航天大學(xué) 2015



本文編號(hào)：3340154