前言：想要寫出一篇引人入勝的文章？我們特意為您整理了元數據分級索引算法飲水安全工程論文范文，希望能給你帶來靈感和參考，敬請閱讀。

1引言

2011年張繼紅發表的《海量交通安全數據的元數據管理研究》等。現有的水利行業的元數據研究主要集中于水利元數據的應用，并沒有涉及到飲水安全工程元數據。如2012年孟令奎等人發表的《面向水文數據共享的水文核心元數據模型研究及應用》，該文著重描述水利元數據在水利共享平臺中的應用；2011年馮鈞等人發表的《水利信息資源元數據管理方法研究》主要研究水利元數據的管理。本文利用水利行業現行的元數據標準作為參考，提出飲水安全工程核心元數據的概念，規范飲水安全工程元數據的定義，利用元數據分級索引算法來查找飲水安全工程數據，著重解決飲水安全工程數據種類多、數據標準化程度低、關聯復雜、數據量大的問題，提高農村飲水安全工程信息的規整性，加快檢索速度。

2飲水安全工程數據的特點

與一般的科學數據相比，飲水安全工程數據具備以下兩個特點：

（1）地理分布性。作為基本數據，國家農村飲水安全工程數據庫包括了國內各省（直轄市）、市（州）、縣（市、區）、鄉鎮內供水水廠的集中式工程數據，包括工程建設信息、實時監測信息，遍布全國，因此飲水安全工程數據具備地理空間的分布特性。

（2）數據要素多。飲水安全工程數據包括了地圖數據，供水工程專題數據，省、市州、縣區、鄉鎮專題基礎信息，水質、管壓安全監測信息，政務信息等。而且每類數據又包括多種要素的數據，如供水工程專題數據包括專題地理信息和專題建設信息，監測數據包括余氯、濁度、水壓、流量等測量數據。整體來說，飲水安全工程數據是描述飲水安全工程的數據，數據量大，且與日俱增，專業性強，具有時間維上的有效性，且數據區域性強，不同市縣統計的數據不交叉，數據存儲形式多樣，以小文件居多。

3飲水安全工程核心元數據

3．1元數據定義

首先，介紹幾個關于元數據的定義。元數據：關于數據的數據。元數據元素：元數據的基本單元，元數據元素在元數據實體中是唯一的。元數據實體：一組說明數據相同特性的元數據元素，元數據實體可以包含一個或一個以上的元數據實體。元數據子集：元數據的子集合，由相關的元數據實體和元素組成。數據集：可以標識的數據集合。通常在物理上可以是更大數據集較小的部分。從理論上講，數據集可以小到更大數據集內的單個要素或要素屬性，一張硬拷貝地圖或圖表均可以被認為是一個數據集。飲水安全工程核心元數據指的是標識飲水安全工程信息所需要的最小元數據元素和元數據實體，為元數據元素集的子集。其次，本文采用UML類圖方法描述飲水安全工程信息元數據。在元數據結構上采用《水利信息核心元數據》的結構作為本標準的基本結構，在內容上對元數據的特征，包括子集／實體名、元素名、英文名、英文縮寫、定義、約束／條件、出現次數、類型和值域進行詳細描述。

3．2飲水安全工程核心元數據結構

飲水安全工程元數據分為元數據元素、元數據實體和元數據子集三層。飲水安全工程核心元數據由一個元數據實體和四個元數據子集構成。其中，標識信息、數據質量為必選子集，內容信息、參照系信息為可選子集。每個子集由若干個實體（UML類）和元素（UML類屬性）構成。

3．3飲水安全核心元數據內容

3．3．1飲水安全核心元數據信息

飲水安全工程元數據信息實體描述飲水安全工程信息的全部元數據信息，用必選實體MD＿元數據表示，由以下元數據實體和元數據元素構成：元數據實體：MD＿標識、DQ＿數據質量、RS＿參照系、MD＿分發、MD＿內容描述；元數據元素：元數據創建日期、聯系單位、元數據名稱、字符集、元數據使用的語言、元數據標準名稱、元數據標準版本。

3．3．2標識信息

標識信息包含唯一標識數據的信息，用MD＿標識實體表示，是必選實體。MD＿標識是下列實體的聚集：MD＿關鍵詞、MD＿數據集限制、EX＿時間范圍信息、MD＿聯系單位或聯系人、MD＿維護信息。MD＿標識實體本身包含如下元素：名稱、行政區編碼、字符集、摘要、日期、狀況、數據表示方式。

3．3．3數據質量信息

數據質量信息包含對數據資源質量的總體評價，用DQ＿數據質量實體表示。應包括與數據生產有關的數據志信息的一般說明。DQ＿數據質量實體包括兩個條件必選的實體，DQ＿數據質量說明和DQ＿數據志。DQ＿數據質量說明是數據集的總體質量信息。DQ＿數據志是從數據源到數據集當前狀態的演變過程說明。包括數據源信息實體和處理過程信息實體。

3．3．4內容信息

內容信息包含提供數據內容特征的描述信息，用MD＿內容描述實體表示。

3．3．5空間參照系信息

參照系信息包含對數據集使用的空間參照系的說明，是條件必選子集，用RS＿參照系實體表示。是關于地理空間數據集的坐標參考框架的描述信息，它反映了現實世界的空間框架模型化的過程和相關的描述參數。RS＿參照系由三個條件必選的實體構成：SI＿基于地理標識的空間參照系、SC＿基于坐標的空間參照系、SC＿垂向坐標參照系。

4元數據分級索引算法

本文根據飲水安全工程數據的區域性特點，選取分布式NameNode模型，改進目錄子樹分區算法和哈希算法，利用BloomFilter原理設計符合飲水安全工程信息的元數據分級索引算法。

4．1概念與公式

行政區劃請求量：表示該行政區劃所需的農村飲水安全工程元數據的請求量，用Request表示。由于請求量的具體數值難以確定，工程元數據的請求量與工程的數量有直接關系，而飲水工程的數量與行政區劃的人口密度存在一定的換算關系。每個工程所涉及的文件包括招標文件、合同、工程規劃、預算、管網圖、廠區布置圖、每年的運營報表等多種文件。因此，第m個行政區劃的請求量Requestm為：Requestm＝Densitym×f×Naverage（1）其中，Densitym代表第m個行政區劃的人口密度，f表示飲水安全工程數量與人口密度的轉換因子，Naverage代表每個工程文件的平均值。

4．2BloomFilter基本思想元數據分級索引算法

包括三部分：一部分是元數據請求被分配到哪個普通NameNode節點上，第二部分是分配到NameNode節點的哪個目錄，最后根據NameNode節點中的目錄信息查找元數據文件在DataNode中的具體位置。本文采用BloomFilter與Key－Value的存儲位置對應表，來確定元數據文件在DataNode中的存儲位置。BloomFilter的基本思想是使用一個比特的數組保存信息，初始狀態時，整個數組的元素全部為0，采用k個獨立的Hash函數，將每個元數據文件對應到｛1，…，m｝的位置，當有飲水安全元數據文件存儲請求時，k個獨立的Hash函數將以元數據標識信息中的元數據文件名為變量，得到k個哈希值，然后將比特數組中的相應位置更改為1，即：hashi（x）＝1（1≤i≤k）（2）其中，x是元數據文件名。數組中的某一位置被置為1后，只有第一次有效，以后再置為1將不起作用。所示，假設k＝3，x1先通過哈希函數，將數組中的三個位置置為1，在x2通過哈希函數得到的數組位置，將是0的位置置為1，已經是1的位置則不重復置1。判斷某元素y是否屬于這個集合，需對y應用k次哈希函數，如果所有的位置都是1（1≤i≤k），那么就認為y是集合中的元素，否則就認為y不是集合中的元素。如圖3所示，y1可能是集合中的元素，y2則不屬于這個集合。BloomFilter能高效地判斷某個元素是否屬于一個集合，但這種高效是有代價的，是存在一定的錯誤率，因為它有可能會把不屬于這個集合的元素判定為屬于此集合。為簡化計算，假設kn＜m并且各哈希函數完全隨機。當某個目錄中的所有元數據文件全部存儲，即所有元素都被哈希函數映射到比特數組中去，這個數組中某一位置是0代表kn次哈希操作都沒有被置為1，因此概率為：p＝（1－1m）kn≈e－kn／m（3）其中第二次近似計算是因為：limx→m（1＋1n）n＝e（4）令ρ代表比特數組中0的比例，則ρ的數學期望E（ρ）＝p，則ρ≈p，因此：pfalse＝（1－ρ）k≈（1－p）k（5）

4．3元數據分級索引算法

元數據分級索引算法包括三個步驟：一是選NameNode節點，二是選目錄，三是分配存儲位置。

4．3．1選取NameNode節點分布式

NameNode模型有一個主NameNode節點，一個主SecondaryNameNode和n個普通NameNode節點。其中，主SecondaryNameNode是主NameNode的快照，防止單點失效。算法的基本思想如下：（1）計算行政區劃請求數。在本文中所涉及的飲水安全工程指的是湖北省的農村飲水安全工程，因此在普通NameNode節點上分布的是以市級為單位的元數據信息。在這一步中，根據公式（1）給每個市級行政區劃的請求賦值，用Requestm表示。（2）分配NameNode節點。若n為奇數，則將其中一個NameNode節點作為備用節點，n＝n－1；若n為偶數，則n不變。分配NameNode節點，得出市級行政區劃與NameNode節點映射表。（3）第二次分組。將偶數個NameNode兩兩分成組，互為SecondaryNameNode節點，分組的原則為請求量較大的NameNode節點與請求量較小的NameNode節點一組。

4．3．2選擇目錄

分配完NameNode節點后，須設定每個Nam－eNode節點的目錄，根據市級行政區劃與Name－Node節點映射表設定一級目錄。然后根據一級目錄的編碼，設定二級目錄，二級目錄為對應市及所管轄縣級行政區劃的目錄。在飲水安全工程項目中，所涉及的數據類型分為圖片類型、視頻類型、文本類型等，所以將三級目錄按文件類型進行劃分，即每個二級目錄下對應的三級目錄為pic、video、txt等。

4．3．3分配存儲位置

當用戶要查找某個飲水安全元數據時，系統首先根據待查找元數據的行政區劃編碼，從市級行政區劃與NameNode節點映射表中找到其對應的NameNode節點；然后，主NameNode節點將用戶請求轉發給此NameNode節點，收到轉發的用戶請求的NameNode節點同樣將行政區編碼進行處理，轉化為市級編碼，找到其一級目錄；然后在一級目錄下，根據編碼找到二級目錄，再根據用戶請求的元數據類型，定位到三級目錄，在三級目錄下根據哈希表，找到對應存儲位置并提交給主Name－Node節點，由主NameNode節點返回給用戶。飲水安全元數據檢索結果分為兩種情況，第一種是查找成功，第二種是查找失敗。一次飲水安全元數據成功檢索過程的檢索時間包括主NameNo－de節點并發處理延遲、主NameNode節點找到對應的NameNode節點的時間、轉發用戶請求與普通NameNode節點的通信時間、普通節點執行查找目錄的時間、查找Hash表讀取元數據的時間和返回查找結果給主NameNode的時間。一次失敗的檢索包含兩種情況，一是定位到目錄后，通過BloomFilter過濾后，判定要查找飲水安全工程元數據哈希表不屬于該目錄；二是通過BloomFilter過濾后，判定其屬于該目錄，但是通過查詢Key－Value表，發現匹配錯誤，即上文提到的BloomFilter自身的錯誤率。第一種情況，根據BloomFilter的原理，可知經過k次獨立的哈希函數后，如果得到的位置不是全為1，則返回查找失敗，要查找的元數據請求不在此目錄中，時間復雜度為O（1）。第二種情況是BloomFilter自身的缺陷，但是由于有對應的Key－Value表，即使經過k次哈希操作得到的位置在比特數組中全為1，通過查找對應的鍵值，如果發現元數據名稱不能與之匹配，則返回檢索不成功，時間復雜度也為O（1），在用戶可以接受的范圍內。

5實驗結果

本文通過實驗仿真驗證飲水安全工程元數據模型的元數據分級索引算法在元數據檢索上的性2226ComputerEngineering＆Science計算機工程與科學2014，36（11）能，并與目錄子樹分區算法和哈希算法在檢索成功時間和檢索失敗時間進行對比。第一組實驗，測試三種算法檢索成功的平均檢索時間，其中用戶數為10，請求數為1000，在定位NameNode節點的時間上來說，目錄子樹分區算法能夠根據用戶請求中的類型定位節點，哈希算法是通過特定的Hash函數，算出用戶請求元數據所在的節點。而本文設計的元數據分級索引算法，將市級行政區劃和NameNode節點編號存儲在一張靜態的表中，查找時間與Name－Node節點個數有關，時間復雜度為O（n）。在本文的應用中，至多會有14個NameNode節點，三種算法的定位時間基本相同，在查找NameNode節點的步驟上所用時間可以近似算作相等。定位目錄的時間復雜度，三種算法也相同，可認為是O（1）。在最后一步定位元數據文件存儲位置上，由于BloomFilter查找成功的時間復雜度是O（1），而目錄子樹分區算法和哈希算法沒有考慮定位物理位置，查找目錄下的元數據名稱，時間復雜度為O（n），目錄下的元數據文件越多，查找速度越慢。第二組實驗，測試三種算法檢索失敗的平均檢索時間，其中用戶數為10，請求數為1000，仿若是檢索不在目錄下的文件，BloomFilter將文件名進行Hash運算，可以判定被請求的文件名不在目錄中，時間復雜度為O（1）。而另外兩種算法，則會遍歷目錄中的所有文件，直至遍歷完，找不到所請求的文件，時間復雜度為O（n）。對比三種算法在飲水安全工程元數據檢索上的應用情況，由于元數據分級算法使用了BloomFilter，檢索效率比其它兩種算法效率高，尤其是檢索失敗的檢索請求。

6結束語

本文分析了飲水安全工程核心元數據的基本特點，并根據相關的標準提出了一種飲水安全工程核心元數據框架，提出了元數據分級索引算法。建立飲水安全工程核心元數據框架和元數據分布算法是統一管理飲水安全工程數據的基礎，只有很好地對飲水安全數據進行描述和檢索，才能有效地對飲水安全數據進行管理。由于飲水安全工程數據具有地理分布廣、時間有效性和數據要素多的特點，而且數據量與日俱增，所以本文提出的飲水安全工程核心元數據結構和算法不一定適用于所有的情況，該結構仍然需要不斷地完善。

作者：胡薇　蔡朝暉　梁甜　涂國慶　單位：武漢大學計算機學院