泛數據雙向包容連線查詢處理關鍵技術研究

《泛數據雙向包容連線查詢處理關鍵技術研究》是依託清華大學，由王朝坤擔任項目負責人的面上項目。

基本介紹

• 中文名：泛數據雙向包容連線查詢處理關鍵技術研究
• 依託單位：清華大學
• 項目負責人：王朝坤
• 項目類別：面上項目

項目摘要

連線及相似連線是數據管理領域的一個基礎而重要的研究問題，學者們已在關係、向量、字元串、樹及圖等眾多類型數據的相似連線方面做了大量研究工作。尤其隨著大數據時代的來臨，海量異構社會化數據的相似連線問題吸引著越來越多人的關注。然而，該方向已有研究成果還遠不能滿足現實中的套用需求。本項目旨在提出並研究泛數據雙向包容連線查詢的概念、技術和方法。設計支持泛數據雙向包容連線查詢的擴展關係代數；提出基於期望域和事實域雙域索引的泛數據雙向包容連線查詢處理算法；基於分治策略的泛數據近似雙向包容連線查詢處理技術，以及基於歸一策略的泛數據近似雙向包容連線查詢處理技術；建立泛數據的自動數據映射模型，提出基於MapReduce的大規模泛數據近似雙向包容連線的有效查詢處理算法。泛數據雙向包容連線問題具有重要的理論研究意義和實際套用價值,本項目的研究成果有望廣泛套用於交友推薦、房屋租賃、求職招聘等社會生產生活關鍵領域。

結題摘要

本項目旨在提出並研究泛數據雙向包容連線查詢處理問題。通過4年的研究工作，課題組在IEEE TKDE、IEEE TIP、IEEE TSIPN、PVLDB、AAAI、IJCAI、《軟體學報》等國內外期刊和會議上發表論文35篇。這些論文包括SCI論文6篇、EI論文15篇、CCF A類長文12篇，申請國家發明專利6項、軟體著作權2項，獲得國內外最佳會議論文獎2項。 課題組深入分析交友、求職等類型的多維複雜數據的匹配問題，通過引入定義在多種數據類型上的滿足操作符和每條數據的獨立閾值，將研究問題凝練形成一種新的相似連線概念——泛化雙向相似連線，擴展了相似連線的套用範圍。這種新的連線支持泛化數據類型(包括數值、數值範圍、枚舉、布爾、字元串等)的事實屬性與對應期望屬性的交叉比較；通過為每個比較對象設定獨立閾值，使得連線結果更加符合用戶客觀需求。針對泛化雙向相似連線查詢處理問題，提出子連線集算法和映射-過濾-驗證算法。對於映射-過濾-驗證算法，還提出了 3 種映射方法，包括單射方法、等步長映射方法和啟發式映射方法。其中，啟發式映射方法在性能上優於單射和等步長映射，能進一步提高算法效率。 在深入分析交友等套用場景的過程中，課題組嘗試針對用戶以及社區進行深入的建模與分析。針對偏好的非傳遞性，提出了用戶的多標準偏好模型，使用多個潛在特徵向量表示同一個用戶，以及該模型的若干種變體，如潛在特徵模型、內容特徵模型和混合特徵模型，適用於不同的套用場景。針對完全非平衡標籤信息下的網路表示學習問題，提出了一種新的半監督網路表示學習方法RSDNE，一方面考慮了網路的結構特性，另一方面通過近似地保證特徵空間中類內相似性與類間差異性來合理利用完全非平衡的標註信息。針對天際線群組問題，提出了最小支配圖結構，包含且僅包含所有的候選點，進而提出兩種不同的深度優先搜尋技術和一種基於組合的最佳化技術，快速找出所有的天際線群組。針對社區發現結果精度較低的問題，提出一種基於深度稀疏自動編碼器的社區發現算法，能夠基於已知網路拓撲結構，提高使用現有經典方法進行社區發現的準確性。針對拓撲不完備情況下的社區發現問題，提出了兩種在非連通圖上進行社區發現的新方法。針對社區搜尋問題，提出了一種結合網路的拓撲結構和節點屬性信息的圖最佳化方法。