[發(fā)明專利]一種面向不確定數(shù)據(jù)的概率查詢質(zhì)量優(yōu)化方法

在審

• 申請?zhí)枺?/td>: 201710039240.6
• 申請日: 2017-01-19
• 公開（公告）號: CN106897375A
• 公開（公告）日: 2017-06-27
• 發(fā)明（設(shè)計）人: 高云君;苗曉曄;周琳琳;陳剛;郭素
• 申請（專利權(quán)）人: 浙江大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州求是專利事務(wù)所有限公司33200
• 代理人: 邱啟旺

1.一種面向不確定數(shù)據(jù)的概率查詢質(zhì)量優(yōu)化方法，其特征在于：該方法包括如下步驟：

步驟(1)：給定概率查詢φ(q,S)，q是查詢對象，S是不確定數(shù)據(jù)集，對于不確定數(shù)據(jù)集中結(jié)果對象集構(gòu)建ASI索引；維護一個最大的查詢結(jié)果質(zhì)量及相應(yīng)的清洗對象集合。

步驟(2)：基于用戶給定的清洗預(yù)算，通過剪枝策略在不確定數(shù)據(jù)集中找到候選的清洗對象集合，并將候選清洗對象集合放入清洗對象集合列表中。

步驟(3)：對于步驟(2)中得到的清洗對象集合列表中的集合，計算其查詢期望質(zhì)量，并更新維護的最大查詢結(jié)果質(zhì)量及相應(yīng)的清洗對象集合，利用期望質(zhì)量單調(diào)性更新清洗對象集合列表。

步驟(4)：重復(fù)步驟(3)直到清洗對象集合列表為空。

步驟(5)：返回最終的最大查詢結(jié)果質(zhì)量及相應(yīng)的清洗對象集合，對期望質(zhì)量最大的清洗對象集合進行清洗，完成了概率查詢的質(zhì)量優(yōu)化。

2.根據(jù)權(quán)利要求1所述的一種面向不確定數(shù)據(jù)的概率查詢質(zhì)量優(yōu)化方法，其特征在于：所述構(gòu)建ASI索引的具體步驟如下：

ASI索引是一個哈希表，以結(jié)果對象集R為鍵值，每個結(jié)果對象集存儲其相應(yīng)的結(jié)果元組集r；對每個r，存儲概率值Pr(r)，以及概率向量概率向量中每一項表示結(jié)果元組集r相對于數(shù)據(jù)對象o的關(guān)聯(lián)概率P(o,r)；

利用ASI索引能夠直接計算出每個結(jié)果對象集的概率，使得計算查詢期望質(zhì)量時無需遍歷所有可能世界。

3.根據(jù)權(quán)利要求1所述的一種面向不確定數(shù)據(jù)的概率查詢質(zhì)量優(yōu)化方法，其特征在于：所述步驟(2)中通過剪枝策略在不確定數(shù)據(jù)集中找到候選清洗對象集合具體如下：如果不確定數(shù)據(jù)集中的對象成為結(jié)果對象的概率為0，那么對象能夠被剪枝；反之，不確定數(shù)據(jù)集中的對象加入到候選清洗對象集合中。

4.根據(jù)權(quán)利要求1所述的一種面向不確定數(shù)據(jù)的概率查詢質(zhì)量優(yōu)化方法，其特征在于：所述步驟(3)中計算其查詢期望質(zhì)量具體步驟如下：

給定對象集合O_c，針對每一個O_c清洗后可能變成的集合T_c，計算變成T_c的概率Pr(T_c)，再計算出清洗成T_c后的對應(yīng)的查詢質(zhì)量κ(φ|T_c)，O_c的查詢期望質(zhì)量則利用公式計算得到；

所述步驟(3)中更新清洗對象集合列表采用如下三種清洗對象優(yōu)選算法中的一種：

(3.1)B&B算法，算法步驟包括：

(3.1.1)清洗對象集合列表用堆實現(xiàn)，表示一棵分支界限樹；

(3.1.2)彈出堆頂對象集合O，若該集合的清洗代價不大于給定預(yù)算值且未訪問過，則計算其期望質(zhì)量，并記錄最大期望質(zhì)量及對應(yīng)對象集合；若該集合的清洗代價大于給定預(yù)算值，則將O的未被訪問且未被剪枝的第i個子集O_i加入堆中且O_i滿足|O_i|＝|O|-1；

(3.1.3)若堆不為空，則返回步驟(3.1.2)執(zhí)行，若堆為空，結(jié)果元組記錄最大期望質(zhì)量及對應(yīng)對象集合，算法結(jié)束；

(3.2)Greedy算法采用貪心策略，每次選擇候選對象集合中滿足最大單位代價期望質(zhì)量的對象，直至給定預(yù)算用完，返回最終的最大查詢結(jié)果質(zhì)量及相應(yīng)的清洗對象集合；

(3.3)HSample算法采用抽樣思想，算法步驟包括：

(3.3.1)從中抽樣m個清洗對象集合，其中B是用戶給定的清洗預(yù)算，avgC是已知的對象清洗代價平均值，是對象個數(shù)為的對象集合的并；

(3.3.2)對每個滿足預(yù)算的樣本對象集合計算期望質(zhì)量，返回最終的最大查詢結(jié)果質(zhì)量及相應(yīng)的清洗對象集合。

5.根據(jù)權(quán)利要求1所述的一種面向不確定數(shù)據(jù)的概率查詢質(zhì)量優(yōu)化方法，其特征在于：所述步驟(5)中對期望質(zhì)量最大的清洗對象集合進行清洗，可用清洗方法包括群智計算、基于規(guī)則的方法、機器學(xué)習(xí)方法等。