大數(shù)據(jù)近似分析方法綜述

張美范 王宏志

摘 要： 大數(shù)據(jù)分析旨在從大量復雜的數(shù)據(jù)中獲取價值。查詢驅(qū)動的數(shù)據(jù)分析是大數(shù)據(jù)分析中最主要的部分。由于數(shù)據(jù)量的龐大，在大數(shù)據(jù)上獲取準確的分析結(jié)果將帶來極大的存儲和計算代價。為解決這一困難，大數(shù)據(jù)近似分析方法應(yīng)運而生。本文將主要針對大數(shù)據(jù)近似分析中的頻率估計問題、近似查詢處理問題、查詢選擇性估計問題近十年的解決方法進行總結(jié)和歸納。不同于以往以數(shù)據(jù)庫為主視角的分析方法的總結(jié)，本文中將涵蓋近幾年應(yīng)用或結(jié)合機器學習方法來處理上述問題的新方法。

關(guān)鍵詞： 大數(shù)據(jù)分析; 頻率估計; 近似查詢處理; 查詢選擇性估計

文章編號： 2095-2163（2021）03-0061-06 中圖分類號：TP391.41 文獻標志碼：A

【Abstract】Big data analytics aims to obtain value from a large amount of complex data. Query-driven data analytics is the most important part of big data analytics. Due to the huge amount of data， obtaining accurate analysis results on big data will bring great storage and calculation costs. To solve this problem， big data approximate analysis methods came into being. This article mainly summarizes the frequency estimation methods， approximate query processing methods， and query selectivity estimation methods in big data analytics in the past ten years. Different from the previous summary of analysis methods based on the database perspective only， this article will cover the new methods of applying or combining machine learning methods to deal with the above problems in recent years.

【Key words】 big data analysis; frequency estimation; approximate query processing; query selectivity estimation

0 引 言

大數(shù)據(jù)中蘊含著海量的信息和巨大的價值，然而數(shù)據(jù)的龐大復雜使得人們不能或難以直接從數(shù)據(jù)中獲得有價值的信息。大數(shù)據(jù)分析就是從大量復雜的數(shù)據(jù)中有目標地獲取價值的過程。傳統(tǒng)的數(shù)據(jù)分析方法難以應(yīng)對極速增長的數(shù)據(jù)量，滿足快速響應(yīng)的需求。為解決這一問題，一系列近似方法應(yīng)運而生，本文主要針對近些年大數(shù)據(jù)近似分析中頻率估計、近似查詢處理、查詢選擇性估計這三種基礎(chǔ)分析任務(wù)的方法進行了總結(jié)。隨著機器學習、人工智能領(lǐng)域的不斷發(fā)展，近些年研究者們嘗試將機器學習方法和大數(shù)據(jù)分析相結(jié)合，利用機器學習模型的推理預測能力，提高大數(shù)據(jù)分析方法的性能。

本文歸納并總結(jié)了近些年有代表性的大數(shù)據(jù)近似分析方法，同時涵蓋了近些年將機器學習方法應(yīng)用到大數(shù)據(jù)分析領(lǐng)域的新方法。

1 大數(shù)據(jù)頻率估計

數(shù)據(jù)頻率是數(shù)據(jù)最基本的統(tǒng)計量，同時也是網(wǎng)絡(luò)監(jiān)控、異常檢測中的重要指標。然而，在大規(guī)模數(shù)據(jù)上統(tǒng)計準確的數(shù)據(jù)頻率會占用極大的空間，為此，研究者們提出通過亞線性空間的草圖來近似存儲和估計數(shù)據(jù)頻率。數(shù)據(jù)草圖具有體積小、精度高、查詢高效的特征，被廣泛應(yīng)用于頻率估計和流數(shù)據(jù)處理上。此外，一些研究者致力于頻繁元素查找及頻率估計方法，頻繁元素查找對應(yīng)大數(shù)據(jù)管理中十分重要的Top-k查詢，同時頻繁元素頻率在網(wǎng)絡(luò)安全監(jiān)控中常作為某些異常事件的衡量指標。

1.1 基于數(shù)據(jù)草圖的頻率估計

Count-Min（CM）[1]是最廣泛應(yīng)用的草圖，其結(jié)構(gòu)為一個二維數(shù)組，二維數(shù)組每行對應(yīng)一個哈希函數(shù)。CM通過哈希函數(shù)將數(shù)據(jù)映射到每行的相應(yīng)位置，并增加這些位置的計數(shù)器來記錄數(shù)據(jù)的頻數(shù)?；贑M的某元素頻率估計值為該元素通過每個哈希函數(shù)映射到位置中的計數(shù)值中的最小值，根據(jù)CM的結(jié)構(gòu)特征，其估計結(jié)果為過量估計。CM草圖同時支持插入和刪除操作。CU草圖[2]和CM草圖的結(jié)構(gòu)相同，不同之處在于CU草圖在每次插入時只增加哈希映射位置中計數(shù)值最小的計數(shù)器的值，CU相比于CM草圖準確性更高，但是并不支持刪除操作。

以單個二維數(shù)組為結(jié)構(gòu)的CM和CU草圖中的估計誤差來自于哈希沖突。當不同數(shù)據(jù)被映射到同一位置，其頻數(shù)在計數(shù)器中累加，造成極大的估計誤差。這種沖突可以通過增加二維數(shù)組的大小來緩解，然而，這樣會增大草圖的空間代價，同時降低查詢效率。為提高準確性和查詢效率，多層結(jié)構(gòu)的草圖被提出。ASketch[3]在CM的基礎(chǔ)上增加了一個過濾器，用于存儲高頻數(shù)據(jù)的頻數(shù)，將高頻數(shù)據(jù)和低頻數(shù)據(jù)分開處理，提高了高頻數(shù)據(jù)頻率估計的準確性。SF-sketch [4]建立了2層分別稱為Slim層和Fat層的結(jié)構(gòu)，F(xiàn)at層為CM草圖，Slim層為一個尺寸更小的草圖，每次插入時根據(jù)Fat層的觀察結(jié)果更新Slim層，只有當Slim層中的計數(shù)小于Fat層估計值時才在計數(shù)器上加1。由于SF-sketch的查詢只在尺寸小的Slim層上進行，因此查詢效率很高。由于數(shù)據(jù)頻率分布不均勻，數(shù)據(jù)中大部分數(shù)據(jù)為低頻數(shù)據(jù)，少量數(shù)據(jù)頻率極高，因此，相同的計數(shù)器位數(shù)會造成極大的空間浪費或不準確的頻率估計。為此，研究者們提出了可調(diào)節(jié)位數(shù)的計數(shù)器。Pyramid Sketch[5]為一種金字塔形狀的多層結(jié)構(gòu)草圖，主要思想是隨著頻數(shù)的增長增加計數(shù)器的位數(shù)，采用共享計數(shù)器高位技術(shù)降低空間代價。ABC [6]在計數(shù)器位數(shù)溢出時通過向相鄰的計數(shù)器借用位數(shù)的方法利用大量的小計數(shù)器來完成頻率估計。

這里將近些年有代表性的頻率估計草圖的結(jié)構(gòu)和支持的操作做了全面的總結(jié)詳見表1，這些草圖能夠估計存在于數(shù)據(jù)集或不存在于數(shù)據(jù)集中任意元素的頻率，且為避免錯過頻繁元素，這些草圖的估計誤差均為單向誤差，即估計結(jié)果不小于真實結(jié)果。

1.2 基于計數(shù)器的頻繁數(shù)據(jù)檢測及頻率估計

頻繁數(shù)據(jù)檢測在數(shù)據(jù)管理、推薦系統(tǒng)、網(wǎng)絡(luò)安全監(jiān)控等領(lǐng)域都有重要意義。為此，一些研究者將關(guān)注點放在頻繁熱點數(shù)據(jù)上，提出了一些只針對高頻熱點數(shù)據(jù)的頻率估計方法，不同于數(shù)據(jù)草圖能夠估計所有數(shù)據(jù)的頻率，這些方法只能估計頻繁元素的頻率，但這些方法對頻繁元素估計的準確性和效率通常優(yōu)于數(shù)據(jù)草圖對頻繁數(shù)據(jù)的估計。

其中，Space-Saving[7]是最有代表性的方法，通過有限個計數(shù)器來尋找Top-k個頻繁數(shù)據(jù)并估計其頻率，當新元素到來且能夠存儲的元素已滿時將新元素和最小計數(shù)器對應(yīng)的元素交換并增加計數(shù)器中頻數(shù)。該方法能夠在O（1）時間內(nèi)完成插入和查詢。由Space-Saving衍生出Compact Space-Saving（CSS）[8]、Scoreboard Space-Saving（SSS）[9]等變種。CCS提出了一種較Space-Saving更緊湊的結(jié)構(gòu)，能夠避免使用大量的指針，節(jié)省空間。SSS利用計數(shù)布隆過濾器預測一個數(shù)據(jù)是否為頻繁數(shù)據(jù)，根據(jù)預測值將數(shù)據(jù)分為高頻數(shù)據(jù)、潛在高頻和低頻三種，并只向Space-Saving中存儲高頻數(shù)據(jù)，避免了將低頻數(shù)據(jù)存入Space-Saving結(jié)構(gòu)引起的誤差。

1.3 基于機器學習模型的頻率估計

近些年，研究者們嘗試將機器學習方法和數(shù)據(jù)庫領(lǐng)域相結(jié)合，利用機器學習模型的推理、預測能力改進數(shù)據(jù)分析方法。文獻[10]提出了一種基于機器學習模型改進的布隆過濾器，是在傳統(tǒng)布隆過濾器的基礎(chǔ)上增加了一個機器學習模型來預測數(shù)據(jù)是否存在在集合中，對于被預測不在集合中的元素通過插入傳統(tǒng)的布隆分類器進行判斷。以此為啟發(fā)，研究者們將機器學習模型和數(shù)據(jù)草圖相結(jié)合提出了學習草圖。文獻[11]利用機器學習模型分類高頻和低頻數(shù)據(jù)，為高頻數(shù)據(jù)分配單獨的存儲單位，將低頻數(shù)據(jù)存入CM草圖中。文獻[12]利用機器學習模型從歷史數(shù)據(jù)中學習高頻數(shù)據(jù)的頻率，利用CM草圖估計低頻數(shù)據(jù)的頻率，能夠有效提高輕量級草圖的準確性。

2 大數(shù)據(jù)近似查詢處理

大數(shù)據(jù)近似查詢處理的目標在于高效獲取查詢目標的近似結(jié)果。研究將大數(shù)據(jù)近似查詢處理的方法分為在線查詢和線下查詢兩類。其中，線上近似查詢處理主要基于在線樣本進行，線下近似查詢處理則基于線下樣本、直方圖、草圖等數(shù)據(jù)概要進行。近年來，研究者們將機器學習方法應(yīng)用到大數(shù)據(jù)的近似查詢處理中，以提高大數(shù)據(jù)近似查詢處理的性能。本文將近些年有代表性的大數(shù)據(jù)近似查詢處理方法分類總結(jié)如下。

2.1 基于在線樣本的近似查詢處理

本文將在查詢時抽樣的近似查詢處理和在線聚集都歸納為基于在線樣本的近似查詢處理。在查詢時抽樣的近似查詢處理方法在執(zhí)行查詢時將抽樣加入查詢計劃中，并根據(jù)樣本上的查詢處理結(jié)果估計整體數(shù)據(jù)上的查詢處理結(jié)果。在線樣本需針對每一個查詢建立，且無需預先獲取數(shù)據(jù)分布等先驗知識。文獻[13]中對查詢時抽樣的方法進行了總結(jié)。

在線聚集起源于文獻[14]，通過增加樣本量逐步提高結(jié)果準確性，當結(jié)果準確性滿足需求后，可以提前中止查詢。Join[15]通過在基于連接關(guān)系建立的連接圖上隨機游走的方式獲取多表樣本進行在線聚集。此外，文獻[13，16]中介紹了多種在線聚集方法。

2.2 基于線下數(shù)據(jù)概要的近似查詢處理

線下數(shù)據(jù)概要形式主要包括線下樣本、直方圖、草圖、小波、數(shù)據(jù)方塊或預查詢等。直方圖、草圖、小波多用于查詢選擇性估計，且近些年基于這些方法進行近似查詢處理的研究不多。因此，本節(jié)著重介紹基于線下樣本、數(shù)據(jù)方塊和預聚集查詢的近似查詢處理。

線下樣本可基于數(shù)據(jù)分布或統(tǒng)計信息建立，相較于線上樣本獲取耗時更多、準確性更高，且可以存儲用于多個查詢。通常簡單的隨機抽樣方法并不能夠為均勻分布以外的數(shù)據(jù)分布提供高質(zhì)量的樣本。為提高估計結(jié)果的準確性，近似查詢處理系統(tǒng)如BlinkDB [17]、VerdictDB [18]均應(yīng)用了分層抽樣的方法。

文獻 [19]提供了一種基于學習的分層抽樣方法，是從樣本中學習分類器用于評價數(shù)據(jù)元組對復雜查詢的貢獻得分，并根據(jù)與預測得分相關(guān)的概率進行分層抽樣。該研究在利用機器學習方法提高復雜查詢執(zhí)行效率的同時，能夠和抽樣方法一樣為結(jié)果提供置信區(qū)間。文獻 [20]提出了一種通過深度生成模型學習數(shù)據(jù)分布生成樣本來代替?zhèn)鹘y(tǒng)抽樣方法進行近似查詢的方法，該方法在模型訓練完畢后能夠?qū)崿F(xiàn)不接觸原數(shù)據(jù)進行采樣，從而避免從大數(shù)據(jù)中采樣的代價，提高采樣效率。

數(shù)據(jù)方塊或預查詢通過存儲預先計算的特定范圍的聚集查詢結(jié)果來估計未來的查詢結(jié)果。文獻 [21]提出了一種方法，將查詢結(jié)果視為變量，從而根據(jù)舊查詢估計新查詢，該方法能夠以低誤差估計稀有數(shù)據(jù)。AQP++[22]將抽樣與數(shù)據(jù)方塊相結(jié)合，根據(jù)預計算的聚集查詢結(jié)果和由抽樣估計的新舊查詢的差值來估計新查詢的結(jié)果。

2.3 結(jié)合機器學習模型的近似查詢處理

研究中將結(jié)合機器學習模型的近似查詢處理方法分為2類。第一類是數(shù)據(jù)驅(qū)動的機器學習模型，第二類是查詢驅(qū)動的機器學習模型。

數(shù)據(jù)驅(qū)動的機器學習模型在于通過歷史數(shù)據(jù)或樣本數(shù)據(jù)模擬數(shù)據(jù)分布或數(shù)據(jù)之間的關(guān)系。上述基于機器模型獲取樣本的方法[19- 20]均可歸類于數(shù)據(jù)驅(qū)動的機器學習模型。此外，DBEst [23]通過樣本數(shù)據(jù)建立密度模型和回歸模型進行近似查詢處理，但是并不能像抽樣方法一樣提供估計結(jié)果的置信區(qū)間。DeepDB [24]通過和積網(wǎng)絡(luò)模型模擬數(shù)據(jù)分布概率模型。EntropyDB [25]基于最大熵模型建立數(shù)據(jù)摘要，通過在模型上進行概率推斷來回答查詢。查詢驅(qū)動的機器學習模型在于模擬歷史查詢中查詢和結(jié)果之間的關(guān)系。ML-AQP [26]不需要接觸數(shù)據(jù)或數(shù)據(jù)樣本，僅根據(jù)歷史數(shù)據(jù)建立模型，能夠高效估計查詢結(jié)果。

文中將近些年有代表性的基于機器學習模型的近似查詢處理方法及其用到的模型類別、是否提供置信區(qū)間、是否需要訪問數(shù)據(jù)和歷史查詢這四方面特征做了總結(jié)，參見表2。

3 大數(shù)據(jù)查詢選擇性估計

查詢選擇性（基數(shù)）是指滿足查詢謂詞的元組占整體數(shù)據(jù)的比例。查詢選擇性估計是查詢優(yōu)化過程中的必要環(huán)節(jié)，查詢選擇性估計的準確性將影響查詢計劃的效率。綜述 [27]中介紹了基于樣本、直方圖、小波、草圖等數(shù)據(jù)概要進行查詢選擇性估計的方法。直方圖和抽樣是近些年的查詢選擇性估計的主要手段，此外，近些年也提出了一些基于機器學習的新方法。本文將近些年有代表性的大數(shù)據(jù)查詢選擇性估計方法分類總結(jié)如下。

3.1 基于直方圖的查詢選擇性估計

直方圖是查詢選擇性估計最常用的手段。直方圖將數(shù)據(jù)分成多個桶并存儲每個桶的邊界和桶內(nèi)的統(tǒng)計信息。直方圖根據(jù)不同的劃分方式分為等寬直方圖、等高直方圖、V-optimal直方圖等等。其中，等寬直方圖將數(shù)據(jù)范圍等分為若干份，等高直方圖每個桶內(nèi)的數(shù)據(jù)量相同，V-optimal直方圖的數(shù)據(jù)分布和原始數(shù)據(jù)分布之間的L2距離最接近。直方圖用于近似查詢處理的優(yōu)勢在于查詢效率高;但其不足在于僅能應(yīng)用于數(shù)值類型的數(shù)據(jù)，且多維數(shù)據(jù)獲得合適的劃分方式的難度大。一維等寬直方圖、等高直方圖、V-optimal直方圖等在綜述[27]中均有介紹。多維直方圖的構(gòu)建相對于一維直方圖更為復雜，原因在于隨著維度的增長，劃分數(shù)據(jù)的自由度增加了，不同于一維直方圖只需確定一個維度上桶邊界的位置，多維直方圖需確定多個維度上的劃分位置、數(shù)量以及不同維度的處理順序。不同于數(shù)據(jù)驅(qū)動的直方圖，查詢驅(qū)動的直方圖通過負載中的查詢反饋自適應(yīng)地建立直方圖[28- 29]。查詢驅(qū)動的直方圖不需要根據(jù)數(shù)據(jù)建立，提高了構(gòu)建效率，同時對負載中查詢范圍內(nèi)的查詢的準確性較高，但無法準確估計負載查詢范圍以外的查詢。

3.2 基于抽樣的查詢選擇性估計

抽樣作為處理大數(shù)據(jù)分析任務(wù)的重要手段之一，也被應(yīng)用在查詢選擇性估計及連接結(jié)果大小估計問題上。數(shù)據(jù)表的連接結(jié)果大小估計可以視為一種特殊的選擇性估計，其估計的是多表根據(jù)相同屬性連接后得到的表的大小。文獻 [30-32] 基于抽樣對連接結(jié)果的大小進行估計。核密度估計作為一種基于樣本的估計方法被許多研究者采用，文獻[33]提出了一種GPU加速的核密度估計模型，能夠自適應(yīng)地處理數(shù)據(jù)及查詢的變化。文獻[34]提出了一種將抽樣和數(shù)據(jù)概要相結(jié)合估計合取查詢選擇性的方法。文獻[35]通過實驗評估了基于抽樣和基于直方圖的空間大數(shù)據(jù)查詢選擇性估計方法。

3.3 基于機器學習的查詢選擇性估計

本文總結(jié)了近些年將機器學習方法應(yīng)用到查詢選擇性估計中的有代表性的工作[36-39]。用到的機器學習的方法主要分為有監(jiān)督學習和無監(jiān)督學習兩種。其中，有監(jiān)督學習通常需要提前收集查詢結(jié)果作為訓練數(shù)據(jù)，無監(jiān)督的方法通常需要從數(shù)據(jù)本身中學習概率分布模型。對此可做研究闡釋如下。

（1）有監(jiān)督學習模型：QuickSel [36]是一個查詢驅(qū)動的查詢選擇性學習框架，相比于查詢驅(qū)動的直方圖效率更高。文獻 [37]提出了一種基于多集卷積網(wǎng)絡(luò)（MSCN）的基數(shù)估計算法，能夠解決沒有樣本滿足查詢謂詞的問題，顯著提高估計質(zhì)量。

（2）無監(jiān)督學習模型：文獻[38]提出了一種基于MADE模型無監(jiān)督學習樣本的聯(lián)合概率分布的方法以及一個有監(jiān)督的從查詢負載中獲得的回歸模型。文獻[39]提出了一種被稱為Naru的基于無監(jiān)督深度自回歸模型的查詢選擇性估計方法。無監(jiān)督的學習方法直接從數(shù)據(jù)中學習模型，不需要像有監(jiān)督的模型一樣收集大量的查詢結(jié)果用于訓練，因此獲得模型的效率更高。

4 結(jié)束語

大數(shù)據(jù)分析發(fā)展迅速，研究成果日新月異。本文對近些年大數(shù)據(jù)分析中頻率估計、近似查詢處理、查詢選擇性估計這三種重要的近似分析任務(wù)進行了歸納總結(jié)。

參考文獻

[1] ??CORMODE G， MUTHUKRISHNAN S . An improved data stream summary： The count-min sketch and its applications[J]. J Algorithms，2005， 55（1）：58-75.

[2] ESTAN C， VARGHESE G. New directions in traffc measurement and accounting： Focusing on the elephants， ignoring the mice[J]. ACM Trans. Comput. Syst.， 2003，21（3）：270-313.

[3] ROY P， KHAN A， ALONSO G. Augmented sketch： Faster and more accurate stream processing[M]//ZCAN F， KOUTRIKA G， MADDEN S. Proceedings of the 2016 International Conference on Management of Data， SIGMOD Conference 2016. San Francisco， CA， USA：ACM， 2016：1449-1463.

[4] LIU Lingtong， SHEN Yulong， YAN Yibo ，et al. Sf-sketch： A two-stage sketch for data streams[J]. IEEE Trans. Parallel Distrib. Syst.， 2020，31（10）：2263-2276.

[5] YANG Tong， ZHOU Yang， JIN Hao， et al. Pyramid sketch： A sketch framework for frequency estimation of data streams[J]. Proc. VLDB Endow.， 2017，10（11）：1442-1453.

[6] GONG Junzhi， YANG Tong， ZHOU Yang， et al. ABC： A practicable sketch framework for non-uniform multisets[C]//NIE Jianyun， OBRADOVIC Z， SUZUMURA T， et al. 2017 IEEE International Conference on Big Data， BigData 2017. Boston， MA， USA： IEEE Computer Society，2017：2380-2389.

[7] METWALLY A， AGRAWAL D， ABBADI A El. An integrated effcient solution for computing frequent and top-k elements in data streams[J]. ACM Trans. Database Syst.，2006， 31（3）：1095-1133.

[8] BEN-BASAT R， EINZIGER G， FRIEDMAN R， et al. Heavy hitters in streams and sliding windows[C]// 35th Annual IEEE International Conference on Computer Communications， INFOCOM 2016. San Francisco， CA， USA：IEEE， 2016：1-9.

[9] GONG Junzhi， TIAN Deyu， YANG Dongsheng， et al. SSS： An accurate and fast algorithm for fnding top-k hot items in data streams[C]// 2018 IEEE International Conference on Big Data and Smart Computing， BigComp 2018. Shanghai， China：IEEE， 2018：106-113.

[10]KRASKA T， BEUTEL A， CHI E H， et al. The case for learned index structures[M]// DAS G， JERMAINE C M， BERNSTEIN P A. Proceedings of the 2018 International Conference on Management of Data， SIGMOD Conference 2018. Houston， TX， USA：ACM， 2018：489-504.

[11]HSU C Y， INDYK P， KATABI D， et al. Learning-based frequency estimation algorithms[C]// 7th International Conference on Learning Representations， ICLR 2019. New Orleans， LA， USA：OpenReview.net， 2019.

[12]ZHANG Meifan， WANG Hongzhi， LI Jianzhong， et al. Learned sketches for frequency estimation[J]. Inf. Sci.， 2020，507：365-385.

[13]CHAUDHURI S， DING Bolin， KANDULA S. Approximate query processing： No silver bullet[M]//SALIHOGLU S， ZHOU Wenchao， CHIRKOVA R， et al. Proceedings of the 2017 ACM International Conference on Management of Data， SIGMOD Conference 2017. Chicago， IL， USA：ACM， 2017：511-519.

[14]HELLERSTEIN J M， HAAS P J， WANG H J. Online aggregation[M]// PECKHAM J. SIGMOD 1997， Proceedings ACM SIGMOD International Conference on Management of Data. Tucson， Arizona， USA：ACM， 1997：171-182.

[15]LI Feifei， WU Bin， YI Ke， et al. Wander join： Online aggregation via random walks[C]// ZCAN F， KOUTRIKA G， MADDEN S. Proceedings of the 2016 International Conference on Management of Data， SIGMOD Conference 2016. San Francisco， CA， USA：ACM， 2016：615-629.

[16]LI Kaiyu， LI Guoliang. Approximate query processing： What is new and where to go？ - A survey on approximate query processing[J]. Data Science and Engineering， 2018，3（4）：379-397.

[17]AGARWAL S， MOZAFARI B， PANDA A， et al. Blinkdb： queries with bounded errors and bounded response times on very large data[C]// Eighth Eurosys Conference 2013， EuroSys 13. ?Prague， Czech Republic：dblp， 2013： 29-42.

[18]PARK Y， MOZAFARI B， SORENSON J， et al. Verdictdb： Universalizing approximate query processing[M]// DAS G， JERMAINE C M， BERNSTEIN P A. Proceedings of the 2018 International Conference on Management of Data， SIGMOD Conference 2018. Houston， TX， USA：ACM， 2018：1461-1476.

[19]WALENZ B， SINTOS S， ROY S， et al. Learning to sample： Counting with complex queries[J]. Proc. VLDB Endow.， 2019，13（3）：390-402.

[20]THIRUMURUGANATHAN S， HASAN S， KOUDAS N， et al. Approximate query processing for data exploration using deep generative models[C]//36th IEEE International Conference on Data Engineering， ICDE 2020. Dallas， TX， USA：IEEE， 2020：1309-1320.

[21]GALAKATOS A， CROTTY A， ZGRAGGEN E， et al. Revisiting reuse for approximate query processing[J]. Proc. VLDB Endow.，2017， 10（10）：1142-1153.

[22]PENG Jinglin， ZHANG Dongxiang， WANG Jiannan， et al. AQP++： Connecting approximate query processing with aggregate precomputation for interactive analytics[C]//Proceedings of the 2018 International Conference on Management of Data， SIGMOD Conference 2018. Houston， TX， USA：ACM， 2018：1477-1492.

[23]MA Qingzhi， TRIANTAFLOU P. Dbest： Revisiting approximate query processing engines with machine learning models[M]//BONCZ P A， MANEGOLD S， AILAMAKI A， et al. ?Proceedings of the 2019 International Conference on Management of Data， SIGMOD Conference 2019. ?Amsterdam， The Netherlands：ACM，2019：1553-1570.

[24]HILPRECHT B， SCHMIDT A， KULESSA M . Deepdb： Learn from data， not from queries！ [J]. Proc. VLDB Endow.， 2020， 13（7）：992-1005.

[25]ORR L J， BALAZINSKA M， SUCACMIU D. Entropydb： A probabilistic approach to approximate query processing[J]. VLDB J.，2020， 29（1）：539-567.

[26]SAVVA F， ANAGNOSTOPOULOS C， TRIANTAFLLOU P. ML-AQP： Query-driven approximate query processing based on machine learning[J]. CoRR， abs/2003.06613， 2020.

[27]CORMODE G， GAROFALAKIS M N， HAAS P J， et al. Synopses for massive data： Samples， histograms， wavelets， sketches. Foundations and Trends in Databases， 2012，4（1-3）：1-294.

[28]BRUNO N， CHAUDHURI S， GRAVANO L. Stholes： A multidimensional workload-aware histogram[C]//Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data. Santa Barbara， CA， USA：ACM， 2001：211-222.

[29]KHACHATRYAN A， MLLER E， BHM K， et al. Improving accuracy and robustness of self-tuning histograms by subspace clustering[C]// 32nd IEEE International Conference on Data Engineering， ICDE 2016. Helsinki， Finland：IEEE， 2016：1544-1545.

[30]VENGEROV D，MENCK ?A C， ZAT M， et al. Join size estimation subject to flter conditions[J]. Proc. VLDB Endow.， 2015，8（12）：1530-1541.

[31]CHEN Yu， YI Ke. Two-level sampling for join size estimation[M]// SALIHOGLU S， ZHOU Wenchao， CHIRKOVA R， et al. Proceedings of the 2017 ACM International Conference on Management of Data， SIGMOD Conference 2017. Chicago， IL， USA：ACM， 2017：759-774.

[32]WANG Taining， CHAN C Y. Improved correlated sampling for join size estimation[C]//36th IEEE International Conference on Data Engineering（ ICDE 2020）. Dallas， TX， USA：IEEE， 2020：325-336.

[33]HEIMEL M， KIEFER M， MARKL V. Self-tuning， gpu-accelerated kernel density models for multidimensional selectivity estimation[M]// SELLIS T K， DAVIDSON S B， IVES Z G. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. Melbourne， Victoria， Australia：ACM， 2015：1477-1492.

[34]MLLER M， MOERKOTTE G， KOLB O. Improved selectivity estimation by combining knowledge from sampling and synopses[J]. Proc. VLDB Endow.，2018， 11（9）：1016-1028.

[35]CHASPARIS H， ELDAWY A. Experimental evaluation of selectivity estimation on big spatial data[M]//BOUROS P， SARWAT M. Proceedings of the Fourth International ACM Workshop on Managing and Mining Enriched Geo-Spatial Data. Chicago， IL， USA：ACM， 2017： 8：1-8：6.

[36]PARK Y， ZHONG Shucheng， MOZAFARI B. Quicksel： Quick selectivity learning with mixture models[M]// MAIER D， POTTINGER R， ?DOAN A， et al. Ngo， editors， Proceedings of the 2020 International Conference on Management of Data， SIGMOD Conference 2020. Portland， OR， USA：ACM， 2020： 1017-1033.

[37]KIPF A， KIPF T， RADKE B， et al. Learned cardinalities： Estimating correlated joins with deep learning[C]// 9th Biennial Conference on Innovative Data Systems Research（CIDR 2019）. Asilomar， CA， USA：www.cidrdb.org， 2019：1-7.

[38]HASAN S， THIRUMURUGANATHAN S， AUGUSTINE J， et al. Deep learning models for selectivity estimation of multi-attribute queries[M]//MAIER D， POTTINGER R， DOAN A， et al. Proceedings of the 2020 International Conference on Management of Data， SIGMOD Conference 2020. Portland， OR， USA：ACM， 2020： 1035-1050.

[39]YANG Zongheng， LIANG E， KAMSETTY A， et al. Deep unsupervised cardinality estimation[J]. Proceedings of the VLDB Endowment， 2019， 13（3）：279-292.