• / 10
  • 下載費用:30 金幣  

一種基于動態索引結構的海量數據實時查詢方法.pdf

關 鍵 詞:
一種 基于 動態 索引 結構 海量 數據 實時 查詢 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
摘要
申請專利號:

CN201310648180.X

申請日:

2013.12.04

公開號:

CN103678550A

公開日:

2014.03.26

當前法律狀態:

授權

有效性:

有權

法律詳情: 專利權的轉移IPC(主分類):G06F 17/30登記生效日:20190314變更事項:專利權人變更前權利人:南京郵電大學變更后權利人:朗坤智慧科技股份有限公司變更事項:地址變更前權利人:210003 江蘇省南京市鼓樓區新模范馬路66號變更后權利人:210009 江蘇省南京市鼓樓區山西路67號世貿中心大廈A808室|||授權|||實質審查的生效IPC(主分類):G06F 17/30申請日:20131204|||公開
IPC分類號: G06F17/30 主分類號: G06F17/30
申請人: 南京郵電大學
發明人: 陳丹偉; 莊俊
地址: 210003 江蘇省南京市鼓樓區新模范馬路66號
優先權: 2013.09.09 CN 201310408184.0
專利代理機構: 南京知識律師事務所 32207 代理人: 胡玲
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201310648180.X

授權公告號:

|||||||||

法律狀態公告日:

2019.04.02|||2017.02.08|||2014.04.23|||2014.03.26

法律狀態類型:

專利申請權、專利權的轉移|||授權|||實質審查的生效|||公開

摘要

本發明公開一種基于動態索引結構(DC-Tree)的海量數據實時查詢方法,該方法是將海量多維數據集降維,支持高空間效率低查詢時間的方法,并支持分布式冗余存儲,從而提升了傳統分布式機制中數據分配的效率,適應大規模數據的處理;該方法包括:多維數據記錄DR通過MasterNode中Z?Curve映射函數fz,生成降維結果集S;MasterNode選定k個哈希函數,通過Bloom?Filter對結果集S進行映射,生成節點集NN;更新數據記錄DR,對節點集NN中每個元素實行動態構建;用戶User查詢MDS結果,通過步驟1、步驟2獲得節點集NN,啟用并行查詢方法;用戶User對節點集NN中所有訪問節點的結果集進行聚合,得到最終查詢結果Rset。

權利要求書

權利要求書
1.  一種基于動態索引結構的海量數據實時查詢方法,其特征在于,所述方法包含如下步驟:
步驟1:多維數據記錄DR通過MasterNode中Z Curve映射函數fz,生成降維結果集S;
步驟2:MasterNode選定k個哈希函數,通過Bloom Filter對結果集S進行映射,生成節點集NN;
步驟3:更新數據記錄DR,對節點集NN中每個元素實行動態構建;
步驟4:用戶User查詢MDS結果,通過步驟1、步驟2獲得節點集NN,啟用并行查詢方法;
步驟5:用戶User對節點集NN中所有訪問節點的結果集進行聚合,得到最終查詢結果Rset。

2.  根據權利要求1所述的一種基于動態索引結構的海量數據實時查詢方法,其特征在于:所述方法中建立了實時查詢模型,將海量多維數據集降維。

3.  根據權利要求1所述的一種基于動態索引結構的海量數據實時查詢方法,其特征在于:所述方法中建立了具有概念層次化結構的多維數據樹。

4.  根據權利要求1所述的一種基于動態索引結構的海量數據實時查詢方法,其特征在于,所述方法中包括:MDS(最小描述子集)分解、Z curve降維處理、Bloom Filter定位、DC-Tree索引及結果聚合。

5.  根據權利要求1所述的一種基于動態索引結構的海量數據實時查詢方法,其特征在于:所述方法是基于動態索引結構。

說明書

說明書一種基于動態索引結構的海量數據實時查詢方法
技術領域
本發明涉及計算機大數據查詢技術領域,特別涉及一種基于動態索引結構的海量數據實時查詢方法。
背景技術
隨著互聯網的飛速發展,社交網絡、移動應用等日趨火熱,我們看到網絡信息的數據量在日益增多,大數據作為一種新興數據概念而被定義,數據作為信息的載體,起著舉足輕重的作用。數據的爆炸式增長使得我們進入了大規模數據分析的時代,其特點是計算強度大,并且要求大規模并發存儲和處理能力。如何快速地處理海量數據,及時有效地從海量數據中提取有價值的信息,是急需解決的技術問題。
目前,大規模數據分析有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映射函數fz,生成降維結果集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(最小描述子集)分解
MDS(最小描述子集)表現形式為(M1,...,Md),其中不妨設Mi={ai1,ai2,...,aik},其中1≤i≤d,aik∈Di,則此MDS(最小描述子集)對應的多維數據記錄集為{(a11,a21,...,ad1),...,(a1k,a2k,...,adk)},記為MM。
2.Z curve降維處理
根據上述步驟1中所得結果集MM,運用Z Curve方法進行降維操作,設Z Curve映射函數為fz(p,m,n),其中p∈MM,m為Z Curve階數,n為多維模型的維度數,不妨設映射函數fz返回值為yp。該映射函數計算過程偽代碼如下:
(1)yp=0;
REPEAT
REPEAT
(2)yp=yp+2n(i-1)+j-1aji
UNTIL j≥n
UNTIL i≥m
(3)RETURN yp
由于n維m階Z Curve的映射函數空間復雜度為O(n),所以上述結果需要長度為n的數組來存放結果集yp,不妨設此結果集為S。
3.Bloom Filter定位
根據上述步驟2中所得降維處理后的結果集S={y1,...,yn},再根據相關工作中對Bloom Filter的闡述,此時需要選擇k個哈希函數HFi,其中1≤i≤k,由于Bloom Filter本身存在一定的錯誤率,為了能夠減少這種正向性錯誤,本發明在構建哈希函數時運用了Knuth論證:兩個哈希函數HF1和HF2通過下面的形式可以生成更多的哈希函數:
HFi=[HF1+HF2+f(i)]mod r
其中1≤i≤k,r為Bloom Filter數組長度,HF1和HF2是兩個相互獨立的哈希函數。當f(i)=0時,采用雙哈希函數機制,否則就為擴展哈希函數機制,這樣產生的哈希函數保持了正向性錯誤率不變,并且提高了系統的計算效率。
選定k個函數函數后,對集合S中數據進行映射,返回一個DataNode節點集,不妨設為NN。并將此集NN返回至用戶。
4.DC-Tree索引及結果聚合
用戶根據上述步驟3中所得集合NN,定位到所需進行索引的DataNode,DataNode采用 DC-Tree索引方法進行查找。在每個DataNode上進行查找后,會將索引結果發送到一個索引結果集中,不妨設為RSet,此時再對該索引結果集進行聚合,獲得最終查詢結果。
有益效果:
1、本發明提高了數據分配的效率,適應大規模數據的處理,降低了單一屬性查詢時的聚合工作量。
2、本發明實現了大規模數據高效并發處理和實時性功能。
附圖說明
圖1是本發明的系統架構圖。
圖2是本發明的動態插入方法流程圖。
圖3是本發明的并行查詢方法流程圖。
具體實施方式
下面通過結合說明書附圖,進一步說明本發明的技術方案。
實施例1
如圖2和圖3所示,本發明提出一種基于動態索引結構(DC-Tree)的海量數據實時查詢方法,該方法包括如下步驟:
步驟1:多維數據記錄DR通過MasterNode中Z Curve映射函數fz,生成降維結果集S;
步驟2:MasterNode選定k個哈希函數,通過Bloom Filter對結果集S進行映射,生成節點集NN;
步驟3:更新數據記錄DR,對節點集NN中每個元素實行動態構建;
步驟4:用戶User查詢MDS結果,通過步驟1、步驟2獲得節點集NN,啟用并行查詢方法;
步驟5:用戶User對節點集NN中所有訪問節點的結果集進行聚合,得到最終查詢結果Rset。
本發明是基于動態索引結構將海量多維數據集降維,支持高空間效率低查詢時間的方法,并支持分布式冗余存儲,從而提升了傳統分布式機制中數據分配的效率,適應大規模數據的處理。本發明建立了具有概念層次化結構的多維數據樹,打破傳統的單一屬性查詢方法,使帶有多維功能屬性的數據集分成不同維度進行構建,大大降低了單一屬性查詢時的聚合工作量。
本發明的一個新的多維數據記錄DR,通過MasterNode快速定位查詢節點集NN,并動態添加到相應DC-Tree,用戶User通過MDS查詢節點集NN,聚合返回查詢結果。
則其具體實施方式為:
(1)多維數據記錄DR通過MasterNode中Z Curve映射函數fz,生成降維結果集S;
(2)MasterNode選定k個哈希函數,通過Bloom Filter對結果集S進行映射,生成節點集NN;
(3)更新數據記錄DR,對節點集NN中每個元素實行動態構建;
動態插入:為根節點D申請加鎖LOCK;更新目錄結點的Measure值;如果DR僅僅包含在D的一個孩子的MDS中,那么令D置為這個目錄孩子結點;如果DR包含在多個D的孩子的MDS中,那么找出這些孩子中包含最少數據結點的那個孩子,并將D置為這個目錄孩子結點;如果DR不包含在D的任何一個孩子的MDS中,首先拷貝一份D,不妨設為D’,將DR添加到D的每一個孩子結點中,計算添加后的重疊值,選擇重疊值最小的那個孩子結點,并將其設為D;將數據記錄DR插入到D中,并更新D的Measure值;如果D的容納空間已經達到最大,則調用分裂函數SPLIT,將D作為參數傳遞;更新D的父親結點的Measure和MDS;令D指向D的父親結點,如果D沒有更新或者D不是根節點,則重新將數據記錄DR插入到D中,并更新D的Measure值,繼續執行,否則結束;為根節點D申請解鎖UNLOCK;
(4)用戶User查詢MDS結果,通過步驟1、步驟2獲得節點集NN,啟用并行查詢方法;
并行查詢:對節點集NN中所有節點,如果該節點沒有上鎖,則并發訪問所有在NN中節點;為根節點D申請加鎖LOCK;對D的每一次孩子結點C,對C的任何一個維度,如果與查詢MDS不在同一維度層次上,則將兩者中較低維度層次轉換為較高維度層次;如果C的_MDS包含在查詢MDS中,則將該_MDS及其Measure Values加入到結果集中;如果C的_MDS和查詢MDS有重疊但并不包含在查詢MDS中,則將該孩子結點C設為D,遞歸調用并行查詢函數PARALLEL QUERY,繼續及NN中節點執行同樣操作;如果C為葉子結點,則訪問結束;為根節點D申請解鎖UNLOCK;
(5)用戶User對節點集NN中所有訪問節點的結果集進行聚合,得到最終查詢結果Rset;
(6)全過程結束。
實施例2
如圖1所示,本發明給出海量數據實時查詢系統的體系架構,該系統由以下四部分組成:數據管理節點(Master Node)、動態索引樹(DC-Tree)、數據存儲節點(Data Node)及用戶(User)。MasterNode負責數據查詢/更新的定位,主要運用降維和快速查詢技術。DC-Tree主要是用于動態構建多維屬性數據查詢樹,提供實時查詢效果。DataNode負責具體數據的存儲。用戶(User)向MasterNode發送查詢請求,MasterNode將對查詢請求內容處理,確定所 查詢內容在部分DataNode上,并將這些符合要求的DataNode提交給用戶。完成這個操作之后,用戶將于MasterNode斷開連接,并主動訪問提交的DataNode進行查詢。
本發明的海量數據實時查詢方法由以下四個操作部分組成,包括:MDS(最小描述子集)分解、Z curve降維處理、Bloom Filter定位、DC-Tree索引及結果聚合。

關于本文
本文標題:一種基于動態索引結構的海量數據實時查詢方法.pdf
鏈接地址:http://www.pqsozv.live/p-6180857.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
钻石光影