[發明專利]一種根據閾值快速篩選重要區間的方法

在審

• 申請號: 201710027127.6
• 申請日: 2017-01-15
• 公開（公告）號: CN106874395A
• 公開（公告）日: 2017-06-20
• 發明（設計）人: 馬會心;楊智慧;何震瀛;王曉陽
• 申請（專利權）人: 復旦大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海正旦專利代理有限公司31200
• 代理人: 陸飛,陸尤

技術領域

本發明屬于關系數據庫技術領域，具體涉及一種在多維數據集根據閾值快速篩選重要區間的方法。

背景技術

數據探索是近年來研究較多的領域。當用戶對于數據內容缺乏了解時，需要有一個不斷嘗試并修改查詢的過程，才能最終得到想要的結果，數據探索即在這一過程中對用戶進行引導，以減小所需的時間與精力開銷。

傳統的數據探索方式都要求冗長的交互過程，但在服務器端本身已經具有所有數據的情況下，可以幫助用戶完成大量粗略的工作，給用戶提供一個較優的探索起點，但這一操作需要以增加計算資源為代價。

多維數據集的容量一般較大，為了節約計算資源，需要更加高效的算法。尤其是對于重要區間的篩選，在查詢中十分常見頻繁，對其進行優化能夠有效提高整個流程的執行效率。

發明內容

本發明的目的是提出一種從多維數據集中快速篩選出符合給定閾值的重要區間的方法，以協助整體上的數據探索工作。

本發明提出的根據閾值快速篩選重要區間的方法，包括：

給定數據集D中的數據分布于維度A，對于A上任一區間[l,r]，可以得到D在其上的相關程度score([l,r])。

要解決的問題可以嚴格描述如下：

給定閾值k，找出所有的區間[l,r]滿足如下條件：

score([l,r])≥k∧score([l-1,r])<k∧score([l,r+1])<k

計算方法如下：

對于每一個右邊界r，計算出符合條件的左邊界LB_r，以確保score([LB_r,r])≥k且score([LB_r-1,r])<k。

根據上一步計算得到的數組LB，將右邊界r從大到小遍歷，如果對應的左邊界LB_r比之前輸出過的所有值都小，就將[LB_r,r]作為結果輸出。

這里，數組LB用于根據右邊界直接定位到滿足條件的相應左邊界，從而根據邊界確定重要區間的位置，使得整體計算中的這一子操作可以直接查表得到，以達到較優的時間復雜度。具體說來，圖5中每一行左邊界的求解就是通過數組LB得到。

對于數組LB的求解，一種方案如下：

(2.1)將右邊界r從小到大遍歷來依次計算相應的LB_r數值；

(2.2)對于當前已經訪問過的數據，將其位置和值記錄下來成為<p,v>的格式，說明當前到達左邊界p且超過閾值所需要的最小的數值為v，對于LB_r的計算即轉化為傳統的二分查找問題，從而在O(logn)時間內完成；

(2.3)于步驟(2.2)中的<p,v>的數組，應當確保其單調性使得二分查找的條件成立，即對于相應的<p_i,v_i>,<p_i+1,v_i+1>應當滿足：

(p_i<p_i+1)∧(v_i<v_i+1)

(2.4)每當右邊界r改變時<p,v>數組也作相應更新；作為線段樹的一種退化情形，為所有數組中的值維護一個基底，對全部值的同時加減操作在基底進行，即可在O(1)時間內完成更新。

當僅改變閾值k而不改變數據集D時，計算LB的更快速方法如下：

(3.1)在預處理階段，計算讓區間[l,r]能夠被選出的最大閾值MT([l,r])，將其作為二維數組記錄下來；

(3.2)將數組MT中必定不會停留的地點去掉，以維持單調性，在該處加入指向左邊第一個停留點的指針以防止重復經過。滿足如下性質的區間[l,r]稱為不停留點：

MT([l,r])<MT([l-1,r])

(3.3)每次用戶給出一個閾值k時，將右邊界r從大到小遍歷，同時在數組MT中從上次輸出的左邊界l′開始尋找最靠左的滿足MT([l,r])≥k的區間[l,r]，若l<l′就將[l,r]輸出，由于左右邊界都只會不斷減小，其運算總時間為O(n)。

附圖說明

圖1為前一種數組LB計算的樣例數組。

圖2為原始數組不具備單調性的演示。

圖3為修改后的位置和值記錄。

圖4為后一種計算的樣例數組。

圖5為給出閾值后一次詳細的計算過程。

具體實施方式