[發(fā)明專利]一種自適應(yīng)采樣與查詢方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 202110231990.X
• 申請日: 2021-03-02
• 公開（公告）號: CN112883064B
• 公開（公告）日: 2022-11-15
• 發(fā)明（設(shè)計）人: 王建民;沈恩亞;宋怡然;沈磊賢
• 申請（專利權(quán)）人: 清華大學(xué)
• 主分類號: G06F16/2455
• 分類號: G06F16/2455;G06F16/2457;G06F16/26
• 代理公司: 北京路浩知識產(chǎn)權(quán)代理有限公司 11002
• 代理人: 陳新生

1.一種自適應(yīng)采樣與查詢方法，其特征在于，包括：

基于波動度的余弦距離權(quán)重函數(shù)，計算每一個數(shù)據(jù)點的波動度權(quán)重，并按照所述波動度權(quán)重，基于流式數(shù)據(jù)的特性，使用二分查找算法對累積數(shù)據(jù)進(jìn)行快速自適應(yīng)分桶，使得分桶結(jié)果中所有桶的最大權(quán)重和最小；

對每個分桶結(jié)果中的流式數(shù)據(jù)，通過多種采樣算子提取相同數(shù)目的樣本，以實現(xiàn)自適應(yīng)的采樣密度，得到對應(yīng)的采樣結(jié)果；

基于采樣結(jié)果，從低層級樣本中采樣得到高層級的樣本，構(gòu)建保持層級結(jié)果一致性的層級樣本結(jié)構(gòu)，并根據(jù)所述層級樣本結(jié)構(gòu)，構(gòu)建層級查詢引擎；

基于用戶的查詢參數(shù)，當(dāng)層級查詢引擎查詢到符合采樣粒度的層級后，將保留當(dāng)前層級的樣本作為查詢結(jié)果。

2.根據(jù)權(quán)利要求1所述的自適應(yīng)采樣與查詢方法，其特征在于，所述基于波動度的余弦距離權(quán)重函數(shù)用于計算數(shù)據(jù)點的波動度權(quán)重，其中，所述波動度權(quán)重，為目標(biāo)數(shù)據(jù)點與該目標(biāo)數(shù)據(jù)點相鄰前后兩數(shù)據(jù)點的余弦距離。

3.根據(jù)權(quán)利要求1所述的自適應(yīng)采樣與查詢方法，其特征在于，所述使用二分查找算法對累積數(shù)據(jù)進(jìn)行快速自適應(yīng)分桶，使得分桶結(jié)果中所有桶的最大權(quán)重和最小，包括：

對權(quán)重數(shù)組掃描一次，得到所有數(shù)據(jù)點的權(quán)重和與單個數(shù)據(jù)點權(quán)重的最大值；

將所有數(shù)據(jù)點的權(quán)重和與單個數(shù)據(jù)點權(quán)重的最大值作為桶權(quán)重和的上界與下界，并基于所述上界和所述下界為起點，通過二分查找算法，獲取滿足預(yù)設(shè)條件的桶權(quán)重和。

4.根據(jù)權(quán)利要求1所述的自適應(yīng)采樣與查詢方法，其特征在于，所述基于采樣結(jié)果，從低層級樣本中采樣得到高層級的樣本，構(gòu)建保持層級結(jié)果一致性的層級樣本結(jié)構(gòu)，包括：

將所述層級樣本結(jié)構(gòu)分為最低樣本層級與上層樣本層級，其中，最低樣本層級，用于直接獲取實時更新的原始數(shù)據(jù)，并對原始數(shù)據(jù)進(jìn)行自適應(yīng)分桶采樣；上層樣本層級不斷輪詢下一層級所得到的采樣結(jié)果，并判斷當(dāng)前累計數(shù)據(jù)是否可以滿足分桶條件；

當(dāng)數(shù)據(jù)權(quán)重累計至分出自適應(yīng)桶時，進(jìn)行自適應(yīng)采樣，并將自采樣結(jié)果傳入上一層級，以實現(xiàn)整個層級樣本結(jié)構(gòu)的自底向上更新。

5.根據(jù)權(quán)利要求4所述的自適應(yīng)采樣與查詢方法，其特征在于，所述根據(jù)所述層級樣本結(jié)構(gòu)，構(gòu)建層級查詢引擎，包括：

根據(jù)用戶給定的樣本數(shù)目或者采樣誤差條件，自頂向下查詢層級樣本結(jié)構(gòu)，并返回滿足條件的樣本集合；

若當(dāng)前層級樣本不滿足用戶給定的條件，則確定當(dāng)前層級采樣粒度大于目標(biāo)采樣粒度，并查詢下一層級樣本，直到找到滿足用戶查詢條件的樣本層級。

6.根據(jù)權(quán)利要求5所述的自適應(yīng)采樣與查詢方法，其特征在于，所述當(dāng)層級查詢引擎查詢到符合采樣粒度的層級后，將保留當(dāng)前層級的樣本作為查詢結(jié)果，包括：

當(dāng)所述層級查詢引擎查詢到符合采樣粒度的層級后，保留當(dāng)前層級的樣本作為查詢結(jié)果，并獲取當(dāng)前層級樣本的最新數(shù)據(jù)點；且所述層級查詢引擎將本層級樣本結(jié)果的最新數(shù)據(jù)時間作為時間范圍起始時間，向下一層級進(jìn)行樣本查詢，直到查詢到最低層級樣本。

7.一種自適應(yīng)采樣與查詢系統(tǒng)，其特征在于，包括：

分桶模塊，用于基于波動度的余弦距離權(quán)重函數(shù)，計算每一個數(shù)據(jù)點的波動度權(quán)重，并按照所述波動度權(quán)重，基于流式數(shù)據(jù)的特性，使用二分查找算法對累積數(shù)據(jù)進(jìn)行快速自適應(yīng)分桶，使得分桶結(jié)果中所有桶的最大權(quán)重和最小；

采樣模塊，用于對每個分桶結(jié)果中的流式數(shù)據(jù)，通過多種采樣算子提取相同數(shù)目的樣本，以實現(xiàn)自適應(yīng)的采樣密度，得到對應(yīng)的采樣結(jié)果；

引擎構(gòu)建模塊，用于基于采樣結(jié)果，從低層級樣本中采樣得到高層級的樣本，構(gòu)建保持層級結(jié)果一致性的層級樣本結(jié)構(gòu)，并根據(jù)所述層級樣本結(jié)構(gòu)，構(gòu)建層級查詢引擎；

查詢模塊，用于基于用戶的查詢參數(shù)，當(dāng)層級查詢引擎查詢到符合采樣粒度的層級后，將保留當(dāng)前層級的樣本作為查詢結(jié)果。

8.一種電子設(shè)備，包括存儲器、處理器及存儲在所述存儲器上并可在所述處理器上運行的計算機(jī)程序，其特征在于，所述處理器執(zhí)行所述計算機(jī)程序時實現(xiàn)如權(quán)利要求1至6任一項所述自適應(yīng)采樣與查詢方法的步驟。

9.一種非暫態(tài)計算機(jī)可讀存儲介質(zhì)，其上存儲有計算機(jī)程序，其特征在于，所述計算機(jī)程序被處理器執(zhí)行時實現(xiàn)如權(quán)利要求1至6任一項所述自適應(yīng)采樣與查詢方法的步驟。