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

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

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

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

【部分圖文】：

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

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

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


本文編號：3507793