[發(fā)明專(zhuān)利]一種高維環(huán)境中模糊數(shù)據(jù)的概率窗口查詢(xún)方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201110437136.5
• 申請(qǐng)日: 2011-12-23
• 公開(kāi)（公告）號(hào): CN102609439A
• 公開(kāi)（公告）日: 2012-07-25
• 發(fā)明（設(shè)計(jì)）人: 胡天磊;壽黎但;陳剛;陳珂;馬春洋
• 申請(qǐng)（專(zhuān)利權(quán)）人: 浙江大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30;H03M7/30
• 代理公司: 杭州求是專(zhuān)利事務(wù)所有限公司 33200
• 代理人: 林懷禹

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)庫(kù)系統(tǒng)、信息檢索、高維模糊數(shù)據(jù)的壓縮和查詢(xún)技術(shù)，特別是涉及一種高維環(huán)境中模糊數(shù)據(jù)的概率窗口查詢(xún)方法。

背景技術(shù)

在越來(lái)越多的應(yīng)用中，數(shù)據(jù)都展現(xiàn)了模糊性。并且，很多模糊數(shù)據(jù)都處于一個(gè)高維環(huán)境當(dāng)中。這樣的應(yīng)用數(shù)據(jù)包括傳感器數(shù)據(jù)庫(kù)中多維數(shù)據(jù)、城市人口普查數(shù)據(jù)、以及圖像處理數(shù)據(jù)等。這一類(lèi)型的應(yīng)用中，每個(gè)物體由一個(gè)模糊區(qū)域和一個(gè)概率分布函數(shù)來(lái)表示。概率分布函數(shù)可以為連續(xù)的概率分布函數(shù)，也可以是離散的概率分布函數(shù)。

在實(shí)際應(yīng)用當(dāng)中，窗口查詢(xún)是最為基礎(chǔ)且最為重要的查詢(xún)類(lèi)型。此外，窗口查詢(xún)還經(jīng)常被用作各種復(fù)雜的多維查詢(xún)?cè)诓樵?xún)處理時(shí)的過(guò)濾機(jī)制。一個(gè)概率窗口查詢(xún)指定一個(gè)查詢(xún)窗口和一個(gè)概率閾值，它從數(shù)據(jù)庫(kù)中查找處于該查詢(xún)窗口的概率大于給定閾值的所有物體。

現(xiàn)有的可以處理概率窗口查詢(xún)的方法多針對(duì)低維環(huán)境中的數(shù)據(jù)所設(shè)計(jì)，無(wú)法在數(shù)據(jù)維度較高時(shí)仍保持良好的查詢(xún)性能。而傳統(tǒng)的能夠在高維情況下仍保持良好查詢(xún)性能的方法都無(wú)法在模糊數(shù)據(jù)集上使用。

在這種情況下，設(shè)計(jì)一種可以有效管理各種海量高維數(shù)據(jù)的索引結(jié)構(gòu)和概率窗口查詢(xún)處理方法是十分重要。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種高維環(huán)境中模糊數(shù)據(jù)的概率窗口查詢(xún)方法。

本發(fā)明解決其技術(shù)問(wèn)題采用的技術(shù)方案的步驟如下：

1)將物體的模糊區(qū)域信息用網(wǎng)格劃分方法進(jìn)行壓縮；

2)將物體的概率分布函數(shù)信息用柱狀圖方法進(jìn)行壓縮；

3)將步驟2)中的柱狀圖的信息用小波變換方法進(jìn)行壓縮；

4)將步驟1)和步驟3)中每一個(gè)物體的全部壓縮信息保存在索引文件中；

5)在查詢(xún)處理時(shí)，利用每一個(gè)物體的全部壓縮信息計(jì)算每一個(gè)物體成為查詢(xún)結(jié)果的概率的上界；

6)利用每一個(gè)物體的概率上界對(duì)不合格的物體進(jìn)行剪枝，從而得到一個(gè)候選答案集合；

7)根據(jù)候選答案集合中每一個(gè)候選物體的未被壓縮的模糊區(qū)域信息和概率分布函數(shù)信息，判斷每一個(gè)候選物體是否是真正的查詢(xún)結(jié)果。

所述的步驟1)利用網(wǎng)格劃分方法對(duì)物體的模糊區(qū)域信息進(jìn)行壓縮，從而使用比特值來(lái)表示物體的模糊區(qū)域。

所述的步驟2)利用柱狀圖方法對(duì)物體的概率分布函數(shù)信息進(jìn)行壓縮，得到一個(gè)概率的序列。

所述的步驟3)中對(duì)步驟2)中得到的概率的序列進(jìn)行小波變換，然后從得到的所有小波系數(shù)中刪除絕對(duì)值大于零的小波系數(shù)。

所述的步驟4)中將每一個(gè)物體的全部壓縮信息保存在索引文件中，使得物體在索引文件中的存儲(chǔ)順序和物體在數(shù)據(jù)庫(kù)中的存儲(chǔ)順序相同。

所述的步驟5)中利用每一個(gè)物體的全部壓縮信息，計(jì)算每一個(gè)物體出現(xiàn)在概率窗口查詢(xún)的查詢(xún)窗口中的概率的最緊上界。

所述的步驟6)中如果一個(gè)物體的概率的最緊上界小于概率窗口查詢(xún)指定的概率閾值，則該物體是不合格物體，將在這一步驟中被剪枝掉。

所述的步驟7）中根據(jù)候選答案集合中每一個(gè)候選物體的未被壓縮的模糊區(qū)域信息和概率分布函數(shù)信息，計(jì)算每一個(gè)候選物體出現(xiàn)在概率窗口查詢(xún)的查詢(xún)窗口中的精確概率；如果一個(gè)候選物體的精確概率大于概率窗口查詢(xún)指定的概率閾值，則這個(gè)候選物體成為最終的查詢(xún)結(jié)果。

本發(fā)明具有的有益效果是：

本發(fā)明充分利用了數(shù)據(jù)庫(kù)和信息檢索的現(xiàn)有研究和實(shí)現(xiàn)成果，基于已有的壓縮方法的擴(kuò)展和融合可以非常方便快捷的提供模糊數(shù)據(jù)的概率窗口查詢(xún)能力，并且不依賴(lài)于模糊數(shù)據(jù)的維度，為使用者提供最好的性能。本發(fā)明可以用于多維傳感器數(shù)據(jù)、城市人口普查數(shù)據(jù)、以及圖像數(shù)據(jù)等各種海量數(shù)據(jù)的管理與查詢(xún)。

附圖說(shuō)明

圖1是概率窗口查詢(xún)方法示意圖。

圖2是用網(wǎng)格劃分方法壓縮物體模糊區(qū)域信息的示意圖。

圖3是用柱狀圖方法壓縮物體概率分布函數(shù)信息的示意圖。

具體實(shí)施方式

下面結(jié)合附圖和具體實(shí)施例對(duì)本發(fā)明作進(jìn)一步說(shuō)明。

本發(fā)明具體實(shí)施過(guò)程和工作原理，如圖1所示：

1)將物體的模糊區(qū)域信息用網(wǎng)格劃分方法進(jìn)行壓縮；

2)將物體的概率分布函數(shù)信息用柱狀圖方法進(jìn)行壓縮；

3)將步驟2)中的柱狀圖的信息用小波變換方法進(jìn)行壓縮；

4)將步驟1)和步驟3)中每一個(gè)物體的全部壓縮信息保存在索引文件中；

5)在查詢(xún)處理時(shí)，利用每一個(gè)物體的全部壓縮信息計(jì)算每一個(gè)物體成為查詢(xún)結(jié)果的概率的上界；

6)利用每一個(gè)物體的概率上界對(duì)不合格的物體進(jìn)行剪枝，從而得到一個(gè)候選答案集合；