• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      數(shù)字圖書館聯(lián)盟中概率數(shù)據(jù)集成系統(tǒng)上的top-k查詢

      2014-02-27 13:16:24
      網(wǎng)絡安全技術與應用 2014年4期
      關鍵詞:元組虛線排序

      潘 林

      (青島港灣職業(yè)技術學院 山東 266404)

      0 引言

      數(shù)字圖書館是虛擬的圖書館,其目的是在網(wǎng)絡環(huán)境下構建共享的可擴展的知識網(wǎng)絡系統(tǒng),提供超大規(guī)模的,分布式異構數(shù)字化信息的智能檢索和服務的知識中心[1]。

      由于單一的數(shù)字圖書館提供的資源有限,不能滿足每個用戶的訪問需求,所以理想的方式是為用戶提供可以一次請求訪問多個數(shù)字圖書館資源的途徑。于是人們提出了聯(lián)盟數(shù)字圖書館(Digital Library Federation簡稱DLF)的概念[2]。

      在一個數(shù)據(jù)集成的系統(tǒng)中,一個查詢在中介模式上提交后,查詢會產(chǎn)生若干帶有概率的重寫形式。這樣結果中的每個元組都會具有不同的概率,我們可以采用 top-k算法來獲得最近似的k個結果。在一個DLF中,最終用戶會希望獲得結果中最符合其偏好且概率最高的結果。這樣,在傳統(tǒng)的 top-k算法中,需要同時考慮依據(jù)偏好形成的得分函數(shù)與概率直接的關系。

      1 數(shù)字圖書館聯(lián)盟DLF的概率的信息集成模型

      Lenzerini 等[3]提出了一種數(shù)據(jù)集成的理論模型,基于該模型,本文定義了概率性的數(shù)據(jù)集成模型,其形式化描述如下:

      一個數(shù)據(jù)集成系統(tǒng)Δ 是一個四元組 ,

      其中G是全局模式,用使用了一組相關字母表Ag的邏輯理論來表達

      S是源數(shù)據(jù)的模式,用使用了一組相關字母表As的邏輯理論來表達

      對于映射mi∈M來說,我們可以定義為屬性的對應關系,一個屬性對應可表達為Cij=(Si,Ti),其中Si是模式S中一個源屬性,Ti是模式T中一個目標屬性。

      在圖書館聯(lián)盟中,由于每個DL的自治性,適于利用LAV表達映射關系,其形式化描述為:

      ? x( s( x) → qg( x ))當qg?s時

      ? x( s( x) ≡ qg( x ))當 g≡qs

      ? x( q g( x) →s( x ))當s ? qg時

      其中s是S的一個元素,gq 是在G上一個查詢。

      2 模式映射的概率

      2.1 映射的概率

      在進行模式的自動映射時,可能會產(chǎn)生幾種候選的模式對應關系,每一種都有其出現(xiàn)的概率,其元組的概率分布情況分為兩類:

      (1)在所有的數(shù)據(jù)上會采用一種相同的映射關系,稱為by-table 映射,這是本文所關注的。

      (2)在源數(shù)據(jù)的關系中,會出現(xiàn)多個元組的子集采用不同的映射關系 稱為by-tuple映射。

      2.2 查詢

      當從G上提交查詢時,會按照各種映射形式形成多個查詢的重寫形式,對于每個返回的結果,其概率是不同的。

      對于在G上的一個查詢Q,按照其與某個局部模式S可能會有的映射形式,可重寫成 Q….Q,對于 Q( i ∈ [1,k])中的元組 t∈ans( Q),t有如下形式 t={t1,….tj}, t1∈ R,… t j ∈ R, R( λ∈[1,j])為與t相關的具有概率的關系模式,我們定義與t相關的布爾表達式:

      即Q的查詢結果中每個元組的概率為包含該元組的查詢重寫的概率之和。

      根據(jù)計算,我們得出如下的圖示:

      圖1 概率

      3 Top-k 查詢回答

      3.1 U-kRanks查詢的定義

      以下是對U-kRanks的定義:

      D為一個具有可能的實例集I= {I1,I2,….In}的概率數(shù)據(jù)庫,且∑r(Ii)=1。對于i=1….k,讓{ t,… t}為一個元組集,其中每個元組會在一個非空的實例I()中根據(jù)得分函數(shù)F出現(xiàn)在位置i。一個在F上的U-kRanks查詢,會返回結果{ t*; i=1….k},其中

      3.2 狀態(tài)的概率的定義

      假定以得分函數(shù)F訪問一個數(shù)據(jù)庫D,在訪問了m個元組后,這些元組會形成若干個狀態(tài),設sm,l為其某個狀態(tài),其中l(wèi)(l<=m)個元組出現(xiàn)在該狀態(tài)中,表示為sl,未出現(xiàn)的(m-l)個元組表示為 Im,則狀態(tài) sm,l的概率為 ρ(sm,l)=Pr(sl∩ ls?),例如假若已經(jīng)檢索出的元組為{t1,t2,t3,t4},對于其中某個狀態(tài)s(4,3)=,可計算其概率為ρ(s4,3)=Pr({t1,t2,t3,t4}∩?{t3})= Pr(t1∧t2∧?t3∧t4)= Pr(t1)*Pr(t2)*Pr(?t3)*Pr(t4).

      3.3 利用狀態(tài)樹對opt_U-kRanks算法的討論

      首先本文采用樹結構來闡述opt_U-kRanks查詢。假設得分排序的元組向量為(t1,t2....tn)(見圖1),每個節(jié)點代表一種具有一定概率的狀態(tài),其值代表了該狀態(tài)的長度,即位次。節(jié)點i和j組成的邊表明通過添加一個新的元組狀態(tài)(出現(xiàn)或不出現(xiàn)),狀態(tài)i可以變成另一個狀態(tài)j。形如t1t2....ti的從根節(jié)點到一個非根節(jié)點i的路徑正好表達了狀態(tài)i。

      圖2 狀態(tài)數(shù)

      如圖1表示了位置(rank)為3,當前元組集為{t1,t2,t3,t4}時的狀態(tài)圖,根到虛線矩形內的元素形成的路徑為符合要求的狀態(tài)集即{t1,t2,?t3,t4}{t1,?t2,t3,t4}{?t1,t2,t3,t4},新加入的元組可在剩余的路徑中形成符合要求的狀態(tài)集(即根到虛線橢圓內元素形成的路徑)

      當新元組t5后,位置(rank)為3時符合要求的狀態(tài)都是從根到虛線橢圓內元素形成的路徑集合中選擇子集加入新元素(元組t5)后形成的

      正如圖2描述,虛線矩形內的節(jié)點表示了排序元素個數(shù)為3的狀態(tài),橢圓內節(jié)點表示了加入元組t4后排序元素個數(shù)小于3(包括0,1,2)的節(jié)點。從圖中可以看出,只有在長度為i-1的狀態(tài)上添加元組t才能保證其出現(xiàn)在排序i上。這時我們可以計算t4按照排序函數(shù)出現(xiàn)在位置3的概率為:

      根據(jù)圖1,我們可以推到一個可使計算快速收斂的不等式。

      對于位置k,由于任何一個事件的概率都不會大于1,所以在圖1中有 P5,3<= S= ∑ ρ(s4,2)。

      不失一般性,對于任意元組 tm,不等式 Pm,k<= S=∑ρ(sm?1,k?1)(k is a rank position)都是成立的。如果我們要求tm為在排序位k時的概率,我們應該保證,mkP 是所有的里面最大者。從前面的討論,我們也可以推斷出即使用如所提出的Pm,k> S代替 Pm,k> Pm+1,k的方案,也不能保證 Pm,k比 Pm+2,k'or....or,nkP (n>i)大。下面,我們來簡化該不等式。

      如圖1所描述的,我們有:

      當k>=2時,我們有:

      當k=1時,我們有:

      綜上,我們可以得到一個近似的條件,即Pr(tm)>= 1/2,該條件可快速評估tm是否是在位置上的適合的解。

      [1]E.A.Fox.Source Book on Digital Libraries.Technical Report TR-93-35 Virginia Polytechnic Institute and State University,1993.

      [2]S.P.Harter.W hat is a Digital Library? Definitions,Content,and Issues.In KOLISS,1996.

      [3]Birm ingham B.,et al.EU-NSF digital library working group on interoperability between digital libraries.http://www.iei.pi.cnr.it/DELOS/NSF/interop.htm,2001-10-15.

      猜你喜歡
      元組虛線排序
      排序不等式
      Python核心語法
      電腦報(2021年14期)2021-06-28 10:46:22
      幼兒畫刊(2020年4期)2020-05-16 02:53:14
      恐怖排序
      海量數(shù)據(jù)上有效的top-kSkyline查詢算法*
      大牛
      幼兒畫刊(2019年2期)2019-04-08 01:23:46
      節(jié)日排序
      刻舟求劍
      兒童繪本(2018年5期)2018-04-12 16:45:32
      基于減少檢索的負表約束優(yōu)化算法
      面向數(shù)據(jù)流處理的元組跟蹤方法
      電信科學(2013年10期)2013-08-10 03:41:54
      四平市| 新泰市| 清新县| 花莲市| 千阳县| 阿勒泰市| 阿拉尔市| 容城县| 四子王旗| 长岛县| 清徐县| 绥化市| 财经| 余干县| 永年县| 东辽县| 古浪县| 象州县| 静乐县| 苍梧县| 镇康县| 永修县| 抚松县| 开平市| 祁东县| 永善县| 和田县| 光泽县| 宾阳县| 莱西市| 荃湾区| 定州市| 房山区| 安达市| 绿春县| 吉安市| 南澳县| 湘潭市| 和平县| 双江| 桂平市|