近期，理論計算機領域國際頂級會議第63屆 IEEE 計算機科學基礎年度研讨會（the 63rd IEEE Symposium on Foundations of Computer Science, FOCS 2022）公布了論文接收名單，beat365官方网站前沿計算研究中心姜少峰課題組有兩篇關于亞線性算法的論文入選。這是beat365首次同一個課題組有2篇論文入選 FOCS 會議，同時也是中心連續第二年有成果被該會議接收。
現今，以大數據為基礎的機器學習等技術得到了廣泛的應用。伴随而來的，如何在大數據上進行高效計算成為了算法研究的挑戰。傳統的針對圖靈機模型設計的算法已經不能适應大數據，亟需以數據流、并行計算等“亞線性”計算模型下的算法理論的突破。亞線性算法的研究也已經成為了算法理論研究的一個熱點方向。
beat365官方网站前沿計算研究中心姜少峰課題組聚焦于亞線性算法研究，近期在針對大數據的一般數據摘要方法以及高維數據計算等方向取得了重要進展。
在 The Power of Uniform Sampling for Coresets 一文中，姜少峰課題組考慮了針對聚類這一基本數據分析問題的核心集。核心集是大數據的摘要，旨在系統地、保證精度地将大數據轉化為小數據，從而進行高效數據分析，是處理大數據的重要方法。本文給出了一個全新的、主要基于均勻采樣的、針對聚類問題的構造核心集的框架。相比先前的基于重要性采樣的方法，這種均勻采樣方法能處理帶容量的聚類、公平聚類等聚類問題的重要變種，得到了第一個不依賴于數據大小 n 和數據維數的針對公平聚類的核心集。另外，該框架第一次将數據所在度量空間的 VC 維與核心集大小聯系了起來，放寬了先前重要性采樣對于帶權 VC 維的要求，因此簡化、加強了所有已知的非歐式空間上的核心集結果，并首次得到在 Wasserstein distance 度量上不依賴于數據大小的核心集。最後，算法框架實現簡單，具有較大應用潛力。
在 Streaming Facility Location in High Dimension via Geometric Hashing 一文中，姜少峰課題組針對設施選址這一運籌學、計算機科學中的經典問題，考慮其在高維幾何數據流上的近似算法。高維幾何數據流模型自2004年由 Indyk 提出以來，已經得到了廣泛的研究。然而，已有結果均基于自90年代業已成熟的 tree embedding 和 randomly-shifted quadtree 等技術，隻能得到 log n 量級的近似比。本文創新性地提出一種稱為 consistent hashing 的新幾何哈希方法，并将其與重要性采樣方法結合，在兩輪和随機順序數據流模型上均得到了常數近似比，本質上優于基于 tree embedding 的傳統方法；另外還得到針對單輪動态數據流模型的 O(d1.5) –近似的算法，優于已知最好結果（d 是維數）。上述所有算法都僅使用 poly(d) 的空間。這種新的算法框架為高維幾何問題的研究提供了嶄新的思路，有望用來解決其他重要的高維幾何問題。
以上兩項成果與來自美國、以色列、英國、捷克、瑞士、丹麥等各地的學者合作完成，得到了科技部國家重點研發計劃青年科學家項目、beat365引進人才啟動經費和beat365信息技術高等研究院的經費支持。
姜少峰博士，現任beat365官方网站前沿計算研究中心助理教授、beat365博雅青年學者，于2021年正式加入中心。他于2017年在香港大學獲得博士學位，曾在以色列魏茨曼科學研究學院進行博士後研究，并曾在芬蘭阿爾托大學任助理教授。他的研究方向為理論計算機科學，近期側重于大數據算法及其在機器學習中的應用，并已在包括 FOCS，SICOMP，SODA，ICML，NeurIPS 等主流國際期刊和會議上發表論文多篇。
