時空高效的線上動態倒排索引混合更新機制研究

《時空高效的線上動態倒排索引混合更新機制研究》是依託武漢理工大學，由劉小珠擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：時空高效的線上動態倒排索引混合更新機制研究
• 項目類別：青年科學基金項目
• 項目負責人：劉小珠
• 依託單位：武漢理工大學

項目摘要

面對迅猛增長、動態性強、隨機更新的海量數據，索引實時更新、動態調節與線上檢索性能的不足日益凸顯。項目將結合申請人在基於倒排索引的信息檢索關鍵技術方面的前期研究工作和該學科的最新成果，針對線上數據更新的隨機性與動態性導致索引更新性能與系統檢索性能急劇惡化的問題，探索影響線上動態倒排索引更新性能的關鍵因素，揭示索引更新性能與長短列表數量及其存儲模式、索引結構、更新策略之間的內在關係，重點研究時空高效的線上動態倒排索引混合更新技術，包括：基於Zipf定律的長短列表數量預測模型；基於鍊表區分長短列表的統一存儲模型；基於歷史分配空間的自適應學習與分塊均勻性規則的長短列表空間管理機制；基於隨機訪問分塊倒排檔案自索引的立即合併與上限Y相鄰多路合併混合更新機制。取得原創性的科研成果，為實現基於倒排索引的海量數據線上動態更新技術提供科學依據。本課題對進一步研究高性能海量數據管理與維護技術有著重要意義。

結題摘要

結合申請人在基於倒排索引的信息檢索關鍵技術方面的前期研究工作和該學科的最新成果，針對線上數據更新的隨機性與動態性導致索引更新性能與系統檢索性能急劇惡化的問題，探索影響線上動態倒排索引更新性能的關鍵因素，重點研究了時空高效的線上動態倒排索引混合更新技術，同時對無線感測器網路中的數據管理機制等進行了初步研究，取得了一系列的研究成果。主要工作包括： （1）對影響倒排索引線上動態更新性能的因素進行了深入分析。基於Zipf分布定律，通過理論分析對長短列表數量分布進行了合理估計，並給出了長、短列表數量計算的數學表達式。通過對實際套用系統中數據信息動態性與隨機性的有效刻畫，實現了長短列表增量的有效近似預測。 （2）對短列表空間管理機制進行了深入研究。採用索引連續分塊技術，實現了基於線性增長、指數增長、分塊均勻性規則對短列表空間進行管理；將連續的物理空間，按照一定大小分割成位元組數相等的若干部分。 （3）對長列表空間管理機制進行了研究。考慮到網路中長短列表數據分布的差異性，長列表採用動態預分配空間的鍊表結構來存儲；考慮到長列表所占空間大、在物理上分配非連續的物理空間、其大小差異性大的特徵，動態更新所需要的空間進行動態預留剩餘空間，儘可能減少動態更新過程中產生的磁碟讀寫操作次數。 （4）提出了基於鍊表區分長短列表的統一存儲模型。對兩種列表都採用鍊表的形式來管理，對於短列表採用索引連續分塊技術來存儲；對於長列表採用動態預分配空間的鍊表結構來存儲，儘可能減少動態更新過程中產生的磁碟讀寫操作次數。 （5）提出了一種基於分配空間自學習的線上動態索引混合更新機制。在理論分析與統一存儲模型的基礎上，根據長短列表增量數據的各自特點，動態分配相應的空間，實現長短列表空間的有效管理以提高空間性能。採用基於歷史分配空間的自適應學習機制，實現預留空間的有效估計，在減少空間消耗的同時兼顧長列表索引更新與查詢性能。 （6）對無線感測器網路中的數據管理機制進行了初步研究，提出了緊湊數據索引存儲技術、時延有效的可靠備份路由協定等。 相關成果在國內外學術期刊上發表（錄用）學術論文6篇，其中SCI論文3篇，EI論文3篇，獲軟體著作權2項；與合作單位聯合培養博士研究生1名，碩士研究生2名。本課題的研究對進一步研究高效的大數據管理技術具有重要意義。