[發明專利]一種基于動態索引結構的海量數據實時查詢方法

有效

• 申請號: 201310648180.X
• 申請日: 2013-12-04
• 公開（公告）號: CN103678550A
• 公開（公告）日: 2014-03-26
• 發明（設計）人: 陳丹偉;莊俊
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京知識律師事務所 32207
• 代理人: 胡玲

技術領域

本發明涉及計算機大數據查詢技術領域，特別涉及一種基于動態索引結構的海量數據實時查詢方法。

背景技術

隨著互聯網的飛速發展，社交網絡、移動應用等日趨火熱，我們看到網絡信息的數據量在日益增多，大數據作為一種新興數據概念而被定義，數據作為信息的載體，起著舉足輕重的作用。數據的爆炸式增長使得我們進入了大規模數據分析的時代，其特點是計算強度大，并且要求大規模并發存儲和處理能力。如何快速地處理海量數據，及時有效地從海量數據中提取有價值的信息，是急需解決的技術問題。

目前，大規模數據分析有2種主流技術：第一種是20世紀80年代開始，以Teradata、Gamma研究項目為代表的并行數據庫逐步發展成熟，它是由一系列操作符組成，前一操作符的輸出流是下個操作符的輸入流，記錄按流水線的方式依次經過這些操作符，具有較高的性能。第2種是以Google為首的基于Map?Reduce和分布式文件系統GFS組成一種“無共享”的簡單函數式編程的并行計算框架，支持其每天億萬次的搜索。Apache的Hadoop是一種Map?Reduce的開源實現。但這些大規模數據處理技術難以滿足實時性要求，更多的是針對離線數據的處理。Hadoop更像是一種ETL工具，兩者的關系不是相互競爭而是互為補充。

另一方面，由Guttman提出的動態索引結構R-Tree及基于R-Tree的變種，其插入、查詢等操作可以同時進行，并且支持多維的模型，在眾多空間索引技術中的優勢非常明顯，但是其針對大規模數據處理時隨著樹高度的增加，其查詢結點重疊度增加，造成查詢效率下降較快。而本發明能夠很好地解決上面的問題。

發明內容

本發明目的在于提供一種基于動態索引結構（DC-Tree）的大規模多維數據實時查詢方法，該方法解決了大規模多維數據處理的滯后性問題，實現了在分布式架構體系上的海量數據實時查詢模型。

本發明解決其技術問題所采用的技術方案是：本發明提出一種基于動態索引結構（DC-Tree）的海量數據實時查詢方法，該方法包括如下步驟：

步驟1：多維數據記錄DR通過MasterNode中Z?Curve映射函數f_z，生成降維結果集S；

步驟2：MasterNode選定k個哈希函數，通過Bloom?Filter對結果集S進行映射，生成節點集NN；

步驟3：更新數據記錄DR，對節點集NN中每個元素實行動態構建；

步驟4：用戶User查詢MDS結果，通過步驟1、步驟2獲得節點集NN，啟用并行查詢方法；

步驟5：用戶User對節點集NN中所有訪問節點的結果集進行聚合，得到最終查詢結果Rset。

本發明是基于動態索引結構將海量多維數據集降維，支持高空間效率低查詢時間的方法，并支持分布式冗余存儲，從而提升了傳統分布式機制中數據分配的效率，適應大規模數據的處理。本發明建立了具有概念層次化結構的多維數據樹，打破傳統的單一屬性查詢方法，使帶有多維功能屬性的數據集分成不同維度進行構建，大大降低了單一屬性查詢時的聚合工作量。

本發明通過將高維數據空間數據映射到一維空間，大大降低了數據管理節點的工作負擔，支持數據存儲節點的動態增加。同時設計了海量數據插入和查詢方法，支持多維屬性數據的動態構建，并支持海量數據查詢的實時性效果，增加了查詢過程訪問鎖機制，適應查詢的并發性需求。

一、系統架構

圖1給出海量數據實時查詢系統的體系架構，該系統由以下四部分組成：數據管理節點（Master?Node）、動態索引樹（DC-Tree）、數據存儲節點（Data?Node）及用戶（User）。MasterNode負責數據查詢/更新的定位，主要運用降維和快速查詢技術。DC-Tree主要是用于動態構建多維屬性數據查詢樹，提供實時查詢效果。DataNode負責具體數據的存儲。用戶（User）向MasterNode發送查詢請求，MasterNode將對查詢請求內容處理，確定所查詢內容在部分DataNode上，并將這些符合要求的DataNode提交給用戶。完成這個操作之后，用戶將于MasterNode斷開連接，并主動訪問提交的DataNode進行查詢。系統整體架構如下圖1所示。

本發明的海量數據實時查詢方案由以下四部分操作組成：MDS(最小描述子集)分解、Z?curve降維處理、Bloom?Filter定位、DC-Tree索引及結果聚合。

二、方法流程

1.MDS(最小描述子集)分解