ethsn-of-n模型下基于指數(shù)劃分的一種數(shù)據(jù)流大綱維護算法(編輯修改稿)
2025-07-17 06:17 本頁面
【文章內(nèi)容簡介】 綱，從中能夠得到最近（）個時刻的大綱。在模型下，無論是對于窗口大小固定還是窗口大小可變的滑動窗口，我們必須很快地從大綱中得到相關(guān)信息。本文中的算法是以基于元組數(shù)目的模型為研究對象的，將其擴展到基于時間的模型也是可行的。. 指數(shù)劃分技術(shù)數(shù)據(jù)流是具有時間特性的，越老的數(shù)據(jù)，其重要性越低。因此，我們需要引入老化因子來體現(xiàn)這種時間特性[]。若在時刻，流上的數(shù)據(jù)為：，則加入老化因子的流數(shù)據(jù)為：。這種指數(shù)式衰減的老化技術(shù)實際上是削弱了過時數(shù)據(jù)對當前狀態(tài)的影響，因為對于大多數(shù)實時應(yīng)用來講，都不會對過期數(shù)據(jù)的概要感興趣，在我們的中使用這種劃分技術(shù)還有一個非常重要的原因，就是它對桶的數(shù)目是可約束的，（ ）在額定空間內(nèi)能夠更有效地體現(xiàn)數(shù)據(jù)的時間特性，這對于空間的有效使用是必須的。若相對誤差為，令，我們稱為指數(shù)劃分的閾值（），在由和組成的簡單數(shù)據(jù)流上，當新數(shù)據(jù)到來時，若新數(shù)據(jù)為，則等待下一個數(shù)據(jù)的到來；若新數(shù)據(jù)為，刪除已過期的桶，創(chuàng)建一個大小為的新桶，以該數(shù)據(jù)的時間戳作為新桶的時間戳，從當前桶開始往前遍歷已存在的桶，如果大小為的桶的個數(shù)超過，則將最老的兩個大小為的桶合并為一個大小為的桶，以前者中最老的時間戳作為后者的時間戳，大小為的桶的合并會導(dǎo)致大小為的桶個數(shù)超過，從而引起級聯(lián)合并。在中，桶的個數(shù)至多為，每個桶所需的內(nèi)存至多為位。每到來一個新元素，可在時間，最壞情況下時間內(nèi)完成處理。. 直方圖我們用指數(shù)劃分技術(shù)將數(shù)據(jù)流上最近個元素劃分為一系列子區(qū)間，在每個子區(qū)間中構(gòu)建直方圖。這里，我們假設(shè)屬性的值集合為，是的子集。令，其中，時有。我們用表示的頻率，則的數(shù)據(jù)分布為。屬性上的直方圖是根據(jù)某種劃分規(guī)則將劃分到個互不相交的子集中，也即所謂的桶 []。不失一般性，我們假設(shè)每個桶中元素的屬性值是“均勻分布”的，通過取桶頻率的平均值來近似每個元素的頻率[]。這里，若，我們用表示桶中不同元素的數(shù)目，于是可以表示為。本文中的直方圖，其劃分方式是等深的。我們需要計算個桶的邊界：，在統(tǒng)計學(xué)上，又稱為分位數(shù)（），分位數(shù)是中位于的數(shù)據(jù)元素。我們需要找到這樣的數(shù)據(jù)元素來作為桶的邊界點。計算分位數(shù)的一個簡單方法[]是對關(guān)系中的所有元組在屬性上以升序進行排序，并從中選擇（包括第一個和最后一個）個位置，使得任意相鄰的兩個位置之間的元組數(shù)目相同。顯然，這些位置為，其中。我們選擇位于這些位置的元組的屬性值作為桶的邊界，從而完成等深直方圖的構(gòu)造。從這個直方圖中，我們可以很容易地得到屬性的選擇度估算值，與實際值相比，若位于兩個分位數(shù)之間，則其最大誤差為，若位于分位數(shù)上，則其最大誤差為。顯然，若想減少誤差，只需增大桶的數(shù)目。然而，桶的數(shù)目增多，占用的內(nèi)存也會增加，因此，需要折中確定值。.我們在前面的章節(jié)中討論了直方圖，這種直方圖面向的是簡單的、數(shù)據(jù)流，要想將其擴展到整個實數(shù)域上，還有很多問題。如何動態(tài)地根據(jù)數(shù)據(jù)集的改
外語相關(guān)推薦
鄂ICP備17016276號-1