[發明專利]基于條件生成模型的近似查詢處理算法

有效

• 申請號: 202110487805.3
• 申請日: 2021-04-30
• 公開（公告）號: CN113177078B
• 公開（公告）日: 2022-06-17
• 發明（設計）人: 白文超;韓希先;何京璇
• 申請（專利權）人: 哈爾濱工業大學（威海）
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06K9/62;G06N3/04;G06N3/08
• 代理公司: 青島華慧澤專利代理事務所(普通合伙) 37247
• 代理人: 馬千會

本發明屬于信息檢索技術領域，具體涉及一種近似查詢處理算法?；跅l件生成模型的高效近似查詢處理算法，包括：采用聚集預計算獲得用戶查詢的預聚集值；對用戶查詢進行處理，獲得估計用戶查詢與預聚集范圍之間差異的新查詢newQ以及選擇的預聚集值；構建基于Wasserstein的條件變分生成對抗網絡模型，利用訓練完成的模型為新查詢newQ生成數據樣本；對生成的數據樣本進行過濾，并將過濾后的數據樣本與選擇的預聚集值相結合，計算得到最終的查詢估計值。本發明的方法構建了一種高效的深度生成模型，并引入Wasserstein距離作為誤差衡量，消除模型坍塌；將該模型應用于近似查詢，并與聚集預計算相結合，同時采用表決算法，降低近似查詢誤差。

技術領域

本發明屬于信息檢索技術領域，具體涉及一種近似查詢處理算法。

背景技術

隨著信息技術的快速發展，數據量呈爆炸性的速度持續增長，使得傳統的數據庫系統軟件難以在交互式響應時間內回答用戶的聚集查詢。而在具體的決策分析任務中，用戶通常只需要從數據中獲取大致的趨勢，不要求精確的結果。而且，在實際情況中，數據分布并不均勻，存在嚴重的偏斜問題。因此，如何在海量的偏斜數據中以更快的響應速度獲取精度較高的查詢結果具有重要的意義。

近似查詢處理(Approximate Query Processing,AQP)算法(CHAUDHURI S,DINGB,KANDULA S.Approximate query processing:no silver bullet[C]//Proceedings ofthe 2017ACM International Conference on Management of Data,Chicago,May 14-19,2017.New York:ACM,2017:511-519.)以犧牲一定的精度為代價來換取更快的查詢響應速度，保證了用戶的交互性需求，成為了近年來數據庫查詢領域的一大研究熱點。目前，近似查詢處理方法大致可分為三類。第一類是基于抽樣的近似查詢處理(Sampling-basedApproximate Query Processing,SAQP)(LI K Y,LI G L.Approximate queryprocessing:what is new and where to go？[J].Data Science and Engineering,2018,3(4):379-397.)，它以抽樣的方法創建一個隨機的數據樣本，并將該樣本作為原始數據的摘要，估計查詢結果。SAQP方法原理簡單，適用于大多數通用查詢，但該方法生成的樣本往往不能代表總體數據集，尤其在面臨高度偏斜的數據時，基于隨機抽樣的SAQP算法不能為稀有數據生成足夠的樣本，影響估計結果的準確性(OLKEN F,ROTEM D.Random samplingfrom databases:a survey[J].Statistics and Computing,1995,5(1):25-42.)?；诜謱映闃拥腟AQP算法可以克服數據偏斜問題，但分層抽樣依賴于對數據分布的先驗知識，只適用于特定數據的查詢，不具有一般性(PANAHBEHAGH B.Stratified and rankedcomposite sampling[J].Communications in Statistics-Simulation andComputation,2020,49(2):504-515.)。另一類是聚集預計算(Aggregate Precomputation,AggPre)(ESCOBAR P,CANDELA G,TRUJILLO J,et al.Adding value to linked open datausing a multidimensional model approach based on the RDF data cubevocabulary-science direct[J].Computer StandardsInterfaces,1994,5(1):25-42.)，該方法預先計算一些聚集查詢的結果，之后使用該結果快速地回答用戶查詢。但AggPre方法的查詢效率取決于預聚集值的計算，有限數量的預聚集值很難提供足夠準確的查詢結果，而預先計算較多的聚集值卻將花費大量的存儲空間。