集合值索引關鍵技術研究

《集合值索引關鍵技術研究》是依託昆明理工大學，由賈連印擔任項目負責人的地區科學基金項目。

基本介紹

• 中文名：集合值索引關鍵技術研究
• 項目類別：地區科學基金項目
• 項目負責人：賈連印
• 依託單位：昆明理工大學

項目摘要

集合無處不在，集合查詢分為集合包含查詢和集合相似度查詢兩部分，在很多領域有廣泛的套用，但同時面臨集合數據量的不斷增長、查詢日益複雜的挑戰。集合查詢以高效的索引技術為基礎，在基於統計分析、關聯規則挖掘等方法深入分析集合數據統計特性的基礎上，擬從全面、高效及並行化三個角度來研究集合索引結構和算法。首先，擬設計支持多種不同集合查詢謂詞的基於trie和反向索引的混合索引結構，以解決傳統集合值索引結構只支持部分查詢謂詞或效率較低的問題；其次針對反向索引結構，通過物化部分頻繁訪問的反向列表交集結果，解決冪律分布下長列表交集效率低下的問題；最後，研究基於GPU的高效的索引結構和算法的高效實現，設計高效的並行集合查詢架構，以進一步提高集合查詢的效率。項目組擬開發集合數據綜合查詢平台，驗證提出的索引結構和算法的有效性。本項目的研究成果，將對集合數據管理技術的完善和提高提供有益的補充。

結題摘要

集合值處理廣泛套用於資料庫、數據挖掘、信息檢索、生物信息系統等領域，索引對提高集合值處理效率至關重要，但隨著數據量的不斷增長，集合值處理面臨較大的挑戰。本項目從以下方面進行了研究：對集合值索引結構和算法進行了綜述，介紹了常見的過濾技術和算法及其特點等，並指出了本領域存在的挑戰和未來努力的方向，為本領域相關研究提供較為詳盡的參考。採用頻繁模式挖掘等方式對集合數據統計特性進行了分析，提出了Dfimud、UWEFP等頻繁模式挖掘算法，可顯著提升頻繁模式挖掘的效率。該綜述和數據分析有助於設計更高效的索引結構和算法。針對集合包含查詢，基於OpenMP並行原語庫實現高效的並行子集、等值和超集查詢算法，通過for循環並行化來實現查詢間並行執行，通過高效的並行共享數據結構PVEC和CountArr及採用高效的調度策略等方式來提高算法的並行度和集合包含查詢的效率。針對基於trie的集合索引結構，著重研究了雙數組這一時空高效的trie結構。針對雙數組構造效率低的不足，分析發現衝突是構造效率低的主要原因，提出分區雙數組結構，可有效將衝突限制在分區範圍內，從而降低衝突和衝突處理代價。針對倒排索引的最佳化，提出了長度分區的倒排索引結構，通過對倒排索引分區並高效對分區進行組織，可快速過濾不可能滿足相似度的集合，從而提高相似度查詢的效率。針對並行算法，基於GPU平台研究了集合T-覆蓋查詢算法，提出了哈希分段技術，設計了基於GPU的hash分段反向索引結構GHSII並提出高效的T覆蓋查詢算法GSPS，可充分利用GPU中的快速共享記憶體，顯著降低訪問低速設備記憶體的次數，結合啟發式查詢序最佳化來解決負載均衡問題，提高了現有T覆蓋查詢算法的效率。最後，項目組還嘗試了將集合處理技術和空間技術、自然語言處理等技術結合的研究。提出了高效的空間填充曲線編碼算法、研究了基於trie的空間文本索引結構、高效的語義擴展和語義消岐技術、高效的分類算法等，這些為下一步深化集合值索引結構和相關套用打下了堅實的基礎。