日(rì)前（6月20日(rì) – 25日(rì)），數據庫頂級會議(yì)2021 ACM SIGMOD在西安舉行，四川省計算機研究院科(kē)研團隊及其合作(zuò)者發表的4篇論文被大(dà)會收錄。作(zuò)爲數據庫領域公認最具影(yǐng)響力的國(guó)際性學術(shù)會議(yì)，SIGMOD與ICDE、VLDB并稱爲國(guó)際數據庫三大(dà)頂級會議(yì)，其收錄論文代表了數據庫相(xiàng)關技術(shù)的最高水平，也是未來(lái)技術(shù)發展的重要風(fēng)向标。這4篇論文分(fēn)别在選擇性估算、圖的無損壓縮方案、增量圖算法、交互式搜索Top-k數據等數據庫相(xiàng)關研究領域實現了創新突破，彰顯了深算院在大(dà)數據領域強大(dà)的核心人(rén)才儲備、科(kē)研文化底蘊和技術(shù)創新能力。

一、Consistent and Flexible Selectivity Estimation for High-Dimensional Data

作(zuò)者：Yaoshu Wang , Chuan Xiao , Jianbin Qin , Rui Mao, Makoto Onizuka, Wei Wang, Rui Zhang, Yoshiharu Ishikawa

關鍵詞：selectivity estimation；high-dimensional data；piecewise linear function；deep neural network

摘要：選擇性估算的目的是在數據庫中估計(jì)滿足給定選擇标準的數據數量，這對于密度估計(jì)、異常檢測、查詢優化和數據整合等許多應用都(dōu)至關重要并富有挑戰性。本文提出了一種新的基于深度學習的模型，可(kě)以靈活地拟合任意距離(lí)函數和查詢對象的選擇性曲線，同時保證模型的輸出在阈值增加的時候不會減少。爲了提高大(dà)規模數據下估算的準确性，本文提出了将數據劃分(fēn)爲多個不相(xiàng)交的子集并在每個子集上建立一個局部模型的簡潔高效策略。經真實數據集實驗，本文提出的模型在準确度上始終優于最新的模型，且具有很好的實用性。

論文鏈接：https://dl.acm.org/doi/10.1145/3448016.3452772

二、Making Graphs Compact by Lossless Contraction

作(zuò)者：Wenfei Fan, Yuanhao Li, Muyang Liu, Can Lu

關鍵詞：graph data management；graph contraction；graph algorithms

摘要：本文中提出了一種将大(dà)圖化爲小圖，并能夠作(zuò)爲多個應用程序同時在同一個圖上運行的通用且無損的優化壓縮方案。該方案将過期數據、星、團和路(lù)徑壓縮爲超點，超點爲每個查詢類Q攜帶一個概要SQ，此概要抽象了被壓縮部分(fēn)的核心特征，并以此來(lái)回答Q中的查詢。該方案還(hái)能夠優先處理(lǐ)圖中最新的數據。此外，我們可(kě)以移植現有的查詢算法，在可(kě)能的情況下通過使用概要來(lái)計(jì)算精确的答案（精确解），并且僅在必要的情況下解壓縮超點。實驗結果表明，該方案能将圖大(dà)小平均減少了71.2%，使查詢的計(jì)算效率分(fēn)别提高了1.53倍、1.42倍和2.14倍。

論文鏈接：https://doi.org/10.1145/3448016.3452797

三、Incrementalizing Graph Algorithms

作(zuò)者：Wenfei Fan，Chao Tian，Ruiqi Xu，Qiang Yin，Wenyuan Yu，Jingren Zhou

關鍵詞：incrementalization；boundedness；fixpoint algorithm

摘要：增量算法對動态圖分(fēn)析起到重要作(zuò)用，但(dàn)其編寫和分(fēn)析較困難。已有增量圖算法較少，其中能夠提供性能保證的算法更少。本文朝着增量圖算法邁進了一步，提出了對現有批處理(lǐ)算法進行增量化的方法，确定了一類不動點算法是可(kě)增量化的。展示了如(rú)何從(cóng)算法A 推導相(xiàng)對有界的增量算法A∆。本文提供了保證正确的和相(xiàng)對有界的一般條件(jiàn)，推導出的算法∆通過采用與A相(xiàng)同的邏輯和數據結構，最多使用時間戳作(zuò)爲附加的輔助結構就(jiù)能夠滿足該條件(jiàn)。在此基礎上，證明了各種圖中心的算法可(kě)以增量化并确保相(xiàng)對有界地。通過實驗驗證了該增量算法的可(kě)擴展性和有效性，推導出A∆與專門(mén)設計(jì)的增量算法相(xiàng)比在效率和空間上表現更好。

論文鏈接：https://doi.org/10.1145/3448016.3452796

四、Interactive Search for One of the Top-k

作(zuò)者：Weicheng Wang，Raymond Chi-Wing Wong，Min Xie

關鍵詞：top-k query；user interaction；data analytics

摘要：傳統的top-k查詢根據用戶的偏好查找最佳的k個數據（即top-k數據）。但(dàn)用戶很難明确地指定他(tā)/她的偏好，且用戶也不希望逐個讀(dú)取所有數據來(lái)找到最滿意的數據。本文研究了通過用戶交互增強top-k查詢，并實現減少用戶所耗費的精力。爲此，在二維空間中，本文提出了2D-PI算法，該算法對問(wèn)題的數量是漸近最優的；在高維空間中，提出了兩種算法RH和HD-PI，分(fēn)别在算法執行時間和提問(wèn)的問(wèn)題數上都(dōu)有很好的效果。大(dà)量的實驗表明，本文的算法可(kě)以比現有的算法在更短(duǎn)時間内提出更少問(wèn)題，并返回用戶滿意的結果。

論文鏈接：https://doi.org/10.1145/3448016.3457322

數讀(dú)研究院科(kē)研成果：

截至2021年(nián)7月8日(rì)，研究院共發表/錄用高水平論文54篇，其中CCF A類44篇；申請(qǐng)專利/PCT共23項，授權發明專利2項。科(kē)研成果比肩全球任何一支大(dà)數據學術(shù)團隊。