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

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

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

【學位級別】：碩士

【部分圖文】：

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

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

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

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

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



本文編號：3340154