信息科技的飛速發(fā)展使得全球數(shù)據(jù)量爆炸增長,在海量數(shù)據(jù)中快速、有效地檢索到目標(biāo)數(shù)據(jù)的top-k查詢方法是當(dāng)前計算機(jī)研究的熱點問題。在海量數(shù)據(jù)中,使用傳統(tǒng)的top-k查詢方法返回精確結(jié)果往往需要很長的響應(yīng)時間。因此,以犧牲精度為代價來換取更快響應(yīng)速度的近似top-k查詢具有重要的研究意義。本文主要從確定性保證和概率性保證兩方面對海量數(shù)據(jù)上的近似top-k查詢算法展開研究。在具有確定性保證的近似top-k查詢研究中,本文提出了基線算法BACG算法,基線算法在經(jīng)典TA算法中加入近似因子?,放寬了閾值界限,使得返回的近似查詢結(jié)果具有確定性保證。為了避免隨機(jī)訪問帶來過大的時空開銷,本文提出了基于有序列表的具有確定性保證的近似top-k查詢算法AQCG算法,AQCG算法包括預(yù)處理、增長階段和收縮階段。在AQCG算法的增長階段加入偏好掃描,使在掃描過程中能跳過屬性列上的不必要元組,盡快收斂到閾值,進(jìn)入收縮階段。為了盡早結(jié)束查詢過程,加入增長剪切和收縮剪切,剪切大部分元組,大大減少了I/O次數(shù)。通過實驗驗證,AQCG算法可以有效計算確定性近似top-k查詢結(jié)果。在具有概率性保證的近似top-k查詢研究中... 

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

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

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

【部分圖文】：

城市酒店數(shù)據(jù)示例圖

哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文-26-寬(bandwidth)，反映了KDE曲線整體的平坦程度，帶寬越大，觀察到的數(shù)據(jù)點在最終形成的曲線形狀中所占比重越小，KDE整體曲線就越平坦，帶寬過大或過小都會影響估計結(jié)果。(a)輪詢掃描(b)偏好掃描圖3-4掃描方式對當(dāng)前的有序列表進(jìn)行分塊，前面一部分用于預(yù)計算，找到一個近似top-k閾值，假設(shè)tscore是top-k預(yù)計算近似結(jié)果分?jǐn)?shù)的下界，根據(jù)屬性的概率分布來掃描有序列表，根據(jù)當(dāng)前元組的PI值，索引哈希表，如果返回null，則表明哈希表中沒有此元組，將此元組插入到哈希表中。若top-k候選集未滿，則將此元組加入top-k候選集，并置=；否則，比較當(dāng)前元組的下界()與堆頂元素tscore的大小，若()>，使用當(dāng)前元組替換堆頂元組，并置=。如果當(dāng)前元組已存在哈希表中，則在哈希表中更新該元組；若top-k候選集未滿，檢查該元組flag值，若=，將該元組插入top-k候選集，否則，根據(jù)PI值在top-k候選集中找到并更新該元組的下界；若top-k候選集已滿，檢查該元組flag值，若=且該元組滿足()>，使用當(dāng)前元組替換堆頂元組，否則，更新top-k候選集中該元組的下界。

哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文-27-圖3-5有序列表掃描示意圖對每一個掃描的元組執(zhí)行此過程，如果哈希表當(dāng)前存儲的元組數(shù)超過了預(yù)設(shè)值，則將哈希表中的數(shù)據(jù)輸出到磁盤上，并且與之前指定的緩存文件合并，然后清空哈希表中的數(shù)據(jù)，繼續(xù)執(zhí)行接下來的操作，通過這個方法實現(xiàn)處理維護(hù)的元組數(shù)量超過內(nèi)存最大值的情況，但是該方法延長了近似top-k增長階段的執(zhí)行時間，因為在兩次文件合并之間，當(dāng)前哈希表存儲的不是增長階段已經(jīng)看到的所有元組信息，而只是上次哈希表清空后看到的部分元組信息，只有當(dāng)下一次文件合并操作時，才可以更新已經(jīng)看到的所有元組信息。在增長階段中，判斷是否要將當(dāng)前元組添加到top-k候選元組集中時，AQCG算法加入了增長剪切，如果當(dāng)前元組的聚合值的上界小于top-k候選集中最小的元組的聚合值的下界，則當(dāng)前元組一定不會是最終的top-k查詢結(jié)果，可以直接剪切這樣的元組，不需要進(jìn)入top-k候選元組集中，這樣可以減少比較次數(shù)，同時降低了需要維護(hù)的候選元組的數(shù)量成本，減少內(nèi)存消耗，大大降低了I/O的次數(shù)。在處理過程中，通過不斷更新當(dāng)前的閾值和top-k候選集中的下界，當(dāng)滿足(1+)×≥時，增長階段結(jié)束，算法進(jìn)入收縮階段，此時哈希表中保存著所有已掃描過的元組。3.2.4收縮剪枝在收縮階段中，通過計算分?jǐn)?shù)上界={(),∈}，分?jǐn)?shù)上界不斷與top-k候選集中最小的元組的聚合值的下界進(jìn)行比較，如果<，將top-k候選集中最小的元組從候選集中剔除，繼續(xù)下一次掃描，直到>，收縮階段結(jié)束，返回堆中的元組作為確定性近似top-k查詢的最終結(jié)果。

【參考文獻(xiàn)】：
期刊論文
[1]分布式網(wǎng)絡(luò)下改進(jìn)的Top-k查詢算法[J]. 楊浩,林喜軍,曲海鵬.  計算機(jī)工程. 2017(02)
[2]基于壓縮的海量不完整數(shù)據(jù)近似查詢方法[J]. 王妍,劉賡浩,王俊陸,宋寶燕.  計算機(jī)研究與發(fā)展. 2016(03)



本文編號：2991825