海量數(shù)據(jù)上的top-k查詢是一項非常重要的查詢類型,top-k查詢是根據(jù)指定的評分函數(shù)返回分數(shù)最高的k個對象給用戶,本文研究top-k查詢的兩種擴展:top-k selection查詢和top-k skyline查詢。Top-k selection查詢是以對象自身屬性值的范圍作為選擇條件,而top-k skyline查詢是以對象與對象間的關(guān)系作為選擇條件;最終返回滿足選擇條件且分數(shù)最高的k個對象,為用戶提供決策支持。首先,在top-k selection研究中,本文提出top-k selection查詢基線算法BASel,BASel算法順序掃描數(shù)據(jù)集,選擇出滿足選擇條件并且分數(shù)最高的k個元組;為了提高top-k selection查詢的速度,本文提出基于預(yù)排序的top-k selection查詢算法PTS,PTS算法對數(shù)據(jù)集進行預(yù)排序,順序掃描有序表獲取top-k selection查詢結(jié)果,根據(jù)數(shù)據(jù)分布的特點,提出早結(jié)束條件,減少I/O次數(shù);為了進一步改善PTS算法的效率,本文提出兩個剪枝方法:選擇剪枝和分數(shù)剪枝;在預(yù)排序的基礎(chǔ)上,PTS算法結(jié)合兩種剪枝策略,進一步提高查詢速度。實驗... 

【文章來源】：哈爾濱工業(yè)大學(xué)黑龍江省 211工程院校 985工程院校

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

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

【部分圖文】：

012-2018年中國在線咨詢量及在線醫(yī)療市場規(guī)模

哈爾濱工業(yè)大學(xué)工程碩士學(xué)位論文-2-數(shù)據(jù)量的劇增引起科學(xué)研究者對處理海量數(shù)據(jù)的興趣；如圖1-2所示，圖中的點表示飯店數(shù)據(jù)庫，橫軸表示飯店的人均消費價格，縱軸表示當(dāng)前查詢用戶位置到飯店的距離；當(dāng)用戶在決定去哪吃飯之前，利用用戶自身的偏好，確定評分函數(shù)，根據(jù)評分函數(shù)返回分數(shù)為top-k的飯店；不同的用戶可能對應(yīng)不同的偏好，那么就對應(yīng)不同的評分函數(shù)；比如：有的用戶比較在意價格，那么對于這一類用戶在為他們進行top-k查詢時，評分函數(shù)中價格的權(quán)重百分比很高，而距離的權(quán)重百分比很小，根據(jù)價格和距離進行綜合評分；而有的用戶在時間很緊迫的時候，希望飯店距離自己的位置越近越好，這樣可以節(jié)省大量時間，這種查詢情況將距離屬性的權(quán)重變高，而價格屬性的權(quán)重百分比很校對于不同的用戶，無法確定用戶對于不同屬性的偏好，所以飯店數(shù)據(jù)庫系統(tǒng)無法直接返回查詢結(jié)果給用戶，而需要用戶指定每個評分屬性的權(quán)重，最后返回top-k查詢結(jié)果給用戶。圖1-2飯店數(shù)據(jù)庫Top-k查詢的應(yīng)用領(lǐng)域非常廣泛，不僅可以應(yīng)用在網(wǎng)頁搜索、信息檢索以及k近鄰近似匹配中，而且可以為用戶提供決策支持，以及在城市導(dǎo)航系統(tǒng)中為用戶提供距離更近的行駛路線，并且與多媒體數(shù)據(jù)庫相似性查詢，skyline查詢，最近鄰搜索等多個研究有關(guān)。由于數(shù)據(jù)量非常大，進行top-k查詢是非常困難的，而且選擇合適的評分函數(shù)也是非常困難的。例如：用戶在購買房子時，房子會具有一些屬性，比如房屋的位置、房屋的層數(shù)、房屋在幾層以及房屋已經(jīng)使用的年限，這些屬性都會影響購買者對房子的評分，因此房屋中介會根據(jù)用戶對這些屬性的偏好，對房屋進行有效評分，這些評分會直接影響返回的房屋查詢結(jié)果；而中介肯定希望返回的查詢結(jié)果盡量滿足購買者的需求；所以選

哈爾濱工業(yè)大學(xué)工程碩士學(xué)位論文-3-擇更加準(zhǔn)確的評分函數(shù)是非常重要的。出于對現(xiàn)實意義的考慮，還是以購買房屋為例，有的購買者是老年人，他們要求房屋所在的樓層是低于或等于3層，并且根據(jù)位置、年限屬性等進行評分；那么購買者提出的“樓層是低于或等于3層”是一個選擇條件，必須在滿足這個條件的基礎(chǔ)上，再根據(jù)評分函數(shù)返回分數(shù)top-k的房屋；上面例子的查詢與傳統(tǒng)的top-k查詢不同，該查詢是基于選擇條件的查詢，這類查詢稱為top-k選擇查詢。Top-k選擇查詢將選擇條件和top-k查詢?nèi)诤显谝黄�，其更符合現(xiàn)在用戶的查詢需求，因為大多數(shù)用戶在進行查詢時，會提出若干個選擇條件，在滿足選擇條件的對象中選擇分數(shù)top-k的對象，所以這類查詢具有重大的理論意義和應(yīng)用價值。上面例子中的選擇條件是利用對象自身的屬性值進行判斷，而另一種選擇條件是根據(jù)對象與對象之間的關(guān)系進行確定，確定滿足選擇條件的子集，這個過程稱為skyline查詢。Skyline查詢是另一種偏好查詢，skyline查詢返回只能支配其余元組，不能被其余元組所支配的元組；skyline查詢的應(yīng)用領(lǐng)域非常廣泛，可以為用戶做出決策等。Borzsonyi等人[1]在2001年首次提出關(guān)于skyline查詢的形象定義，是因為skyline查詢結(jié)果點連接在一起像天際線，故取名為“Skyline查詢”。圖1-3待租房skyline示意圖如圖1-3展示待租房屋的skyline示意圖，表示以價格、與工作地點的距離為skyline屬性，圖中用直線連接的點為skyline查詢結(jié)果。例如：應(yīng)屆畢業(yè)生剛到公司入職時，會選擇在公司的附近租房子，租房網(wǎng)站對房子的數(shù)據(jù)進行統(tǒng)計，篩選出離公司較近和價格更便宜的房屋，給用戶返回一個房屋列表，供用戶進行選擇。然而現(xiàn)實情況下，價格與距離之間可能是相互矛盾的，也就是說，


本文編號：3507793