[發(fā)明專(zhuān)利]一種根據(jù)閾值快速篩選重要區(qū)間的方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710027127.6
• 申請(qǐng)日: 2017-01-15
• 公開(kāi)（公告）號(hào): CN106874395A
• 公開(kāi)（公告）日: 2017-06-20
• 發(fā)明（設(shè)計(jì)）人: 馬會(huì)心;楊智慧;何震瀛;王曉陽(yáng)
• 申請(qǐng)（專(zhuān)利權(quán)）人: 復(fù)旦大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 上海正旦專(zhuān)利代理有限公司31200
• 代理人: 陸飛,陸尤

1.一種根據(jù)閾值快速篩選重要區(qū)間的方法，其特征在于，具體步驟如下：

（1.1）給定數(shù)據(jù)集D中的數(shù)據(jù)分布于維度A，對(duì)于A上任一區(qū)間，得到D在其上的相關(guān)程度，根據(jù)閾值k篩選區(qū)間即為找出所有且無(wú)法再擴(kuò)展的區(qū)間；

（1.2）首先計(jì)算數(shù)組LB，對(duì)于每一個(gè)右邊界r，確保且；

（1.3）根據(jù)步驟（1.2）中計(jì)算得到的，將右邊界從大到小遍歷，如果對(duì)應(yīng)的左邊界比之前輸出過(guò)的所有值都小，就將作為結(jié)果輸出。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，步驟（1.2）中所述計(jì)算LB的一種方法如下：

（2.1）將右邊界r從小到大遍歷來(lái)依次計(jì)算相應(yīng)的數(shù)值；

（2.2）對(duì)于當(dāng)前已經(jīng)訪問(wèn)過(guò)的數(shù)據(jù)，將其位置和值記錄下來(lái)成為的格式，說(shuō)明當(dāng)前到達(dá)左邊界且超過(guò)閾值所需要的最小的數(shù)值為，對(duì)于的計(jì)算即轉(zhuǎn)化為傳統(tǒng)的二分查找問(wèn)題，從而在時(shí)間內(nèi)完成；

（2.3）于步驟（2.2）中的的數(shù)組，應(yīng)當(dāng)確保其單調(diào)性使得二分查找的條件成立，即對(duì)于相應(yīng)的應(yīng)當(dāng)滿(mǎn)足：

（2.4）每當(dāng)右邊界r改變時(shí)數(shù)組也作相應(yīng)更新；作為線段樹(shù)的一種退化情形，為所有數(shù)組中的值維護(hù)一個(gè)基底，對(duì)全部值的同時(shí)加減操作在基底進(jìn)行，即可在時(shí)間內(nèi)完成更新。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，當(dāng)僅改變閾值k而不改變數(shù)據(jù)集D時(shí)，步驟（1.2）中所述計(jì)算LB的更快速方法如下：

（3.1）在預(yù)處理階段，計(jì)算讓區(qū)間能夠被選出的最大閾值，將其作為二維數(shù)組記錄下來(lái)；

（3.2）將數(shù)組MT中必定不會(huì)停留的地點(diǎn)去掉，以維持單調(diào)性，在該處加入指向左邊第一個(gè)停留點(diǎn)的指針以防止重復(fù)經(jīng)過(guò)；滿(mǎn)足如下性質(zhì)的區(qū)間稱(chēng)為不停留點(diǎn)：

（3.3）參照步驟（1.3）中的過(guò)程，每次用戶(hù)給出一個(gè)閾值k時(shí)，將右邊界r從大到小遍歷，同時(shí)在數(shù)組MT中從上次輸出的左邊界開(kāi)始尋找最靠左的滿(mǎn)足的區(qū)間，若就將輸出。