度量空間下的k最近對查詢及變體處理研究

《度量空間下的k最近對查詢及變體處理研究》是依託浙江大學，由高雲君擔任項目負責人的面上項目。

基本介紹

• 中文名：度量空間下的k最近對查詢及變體處理研究
• 依託單位：浙江大學
• 項目負責人：高雲君
• 項目類別：面上項目

項目摘要

查詢/搜尋是計算機科學的基本問題，存在於目前幾乎所有的計算機套用領域；特別是在大數據時代，高效的查詢處理與最佳化技術顯得尤為重要。現有的k最近對查詢主要針對歐氏空間，並利用幾何特性修剪查找空間；但這些幾何特性不適用於度量空間，且在許多實際套用（如數據挖掘）中，對象不能由歐氏空間模型表示，其鄰近關係可能用非歐氏距離（如編輯距離）度量。本項目擬在現有k最近對查詢和度量查詢研究基礎上，結合度量空間特性（如三角不等式），以最小化I/O次數和距離計算次數為最佳化目標，展開一系列能滿足實際套用需求的度量空間下的k最近對查詢及變體處理研究，重點研究度量k最近對查詢、度量自身k最近對查詢、受限度量k最近對查詢、度量k最遠對查詢、無索引度量k最近對查詢、度量多路k最近對查詢和度量獨占最近對連線；設計、實現和評價各自查詢處理算法，並開發相應的展示平台；力爭在相關理論和技術上取得突破，為今後的實際套用奠定堅實基礎。

結題摘要

在大數據時代，“數據在，找不到”現象日益嚴重，因而如何有效地索引與查詢大數據成為了一個巨大的挑戰。度量空間支持多種數據類型和任意（距離）度量方式，並不受數據對象的幾何特性限制，在大數據智慧型查詢方面具有重要的套用價值。本項目圍繞度量空間索引與查詢技術展開了深入地探索，重點研究了度量空間索引技術（如確定/不確定的度量空間數據索引等）、度量空間查詢技術（如度量k最近對查詢及變體、度量全k最近鄰查詢等）以及度量空間查詢結果可用性分析（如度量機率區域查詢上Why-not問題等），並搭建了一個社交圖像檢索與推薦系統。項目組圓滿實現且超出了預期的研究成果，完全達到了預期的研究目標。共培養/畢業博士生8名，碩士生14名，本科生5名，並獲國家獎學金10人次等獎勵；在國內外頂級/重要學術期刊或會議VLDBJ、TKDE、TOIS、TFS、SIGMOD、VLDB、ICDE、DASFAA等發表/錄用論文51篇，其中SCI檢索31篇，EI檢索50篇，CCF A類期刊或會議論文20篇，SCI他引90餘次，Google Scholar他引200餘次；（待）出版相關中英文學術專著3部；實審相關專利4項；部分成果受到了國內外知名專家（如歐洲科學院院士、ACM/IEEE Fellow、TODS主編、丹麥奧爾堡大學Christian S. Jensen教授，IEEE/AAAS Fellow、KAIS主編、美國路易斯安那大學拉斐特分校吳信東教授，IEEE Fellow、TKDE主編、澳大利亞新南威爾斯大學林學民教授，IEEE/RSNZ Fellow、紐西蘭奧克蘭理工大學Nikola Kasabov教授，IEEE Fellow、美國紐約州立大學李克勤教授，IEEE Fellow、美國明尼蘇達大學David hung-Chang Du教授，IEEE Fellow、香港理工大學曹建農教授等）的關注/評價，套用於網易LOFTER與雲音樂，被國內外學術專著、計算機科學專業博/碩士學位論文引用，並獲CCF優秀博士學位論文獎（2017），浙江省優秀博士學位論文提名論文獎（2016）、浙江省優秀碩士學位論文獎（2016）、教育部科技進步一等獎（2016）、國家優秀青年科學基金項目（2015）和ICDE 2015優秀論文等。項目組的成果既豐富了度量空間數據管理方面的研究又促進了數據挖掘和多/跨媒體檢索等相關領域的進一步發展。