元數(shù)據(jù)分級(jí)索引算法飲水安全工程論文

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

1引言

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

2飲水安全工程數(shù)據(jù)的特點(diǎn)

與一般的科學(xué)數(shù)據(jù)相比，飲水安全工程數(shù)據(jù)具備以下兩個(gè)特點(diǎn)：

（1）地理分布性。作為基本數(shù)據(jù)，國家農(nóng)村飲水安全工程數(shù)據(jù)庫包括了國內(nèi)各省（直轄市）、市（州）、縣（市、區(qū)）、鄉(xiāng)鎮(zhèn)內(nèi)供水水廠的集中式工程數(shù)據(jù)，包括工程建設(shè)信息、實(shí)時(shí)監(jiān)測(cè)信息，遍布全國，因此飲水安全工程數(shù)據(jù)具備地理空間的分布特性。

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

3飲水安全工程核心元數(shù)據(jù)

3．1元數(shù)據(jù)定義

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

3．2飲水安全工程核心元數(shù)據(jù)結(jié)構(gòu)

飲水安全工程元數(shù)據(jù)分為元數(shù)據(jù)元素、元數(shù)據(jù)實(shí)體和元數(shù)據(jù)子集三層。飲水安全工程核心元數(shù)據(jù)由一個(gè)元數(shù)據(jù)實(shí)體和四個(gè)元數(shù)據(jù)子集構(gòu)成。其中，標(biāo)識(shí)信息、數(shù)據(jù)質(zhì)量為必選子集，內(nèi)容信息、參照系信息為可選子集。每個(gè)子集由若干個(gè)實(shí)體（UML類）和元素（UML類屬性）構(gòu)成。

3．3飲水安全核心元數(shù)據(jù)內(nèi)容

3．3．1飲水安全核心元數(shù)據(jù)信息

飲水安全工程元數(shù)據(jù)信息實(shí)體描述飲水安全工程信息的全部元數(shù)據(jù)信息，用必選實(shí)體MD＿元數(shù)據(jù)表示，由以下元數(shù)據(jù)實(shí)體和元數(shù)據(jù)元素構(gòu)成：元數(shù)據(jù)實(shí)體：MD＿標(biāo)識(shí)、DQ＿數(shù)據(jù)質(zhì)量、RS＿參照系、MD＿分發(fā)、MD＿內(nèi)容描述；元數(shù)據(jù)元素：元數(shù)據(jù)創(chuàng)建日期、聯(lián)系單位、元數(shù)據(jù)名稱、字符集、元數(shù)據(jù)使用的語言、元數(shù)據(jù)標(biāo)準(zhǔn)名稱、元數(shù)據(jù)標(biāo)準(zhǔn)版本。

3．3．2標(biāo)識(shí)信息

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

3．3．3數(shù)據(jù)質(zhì)量信息

數(shù)據(jù)質(zhì)量信息包含對(duì)數(shù)據(jù)資源質(zhì)量的總體評(píng)價(jià)，用DQ＿數(shù)據(jù)質(zhì)量實(shí)體表示。應(yīng)包括與數(shù)據(jù)生產(chǎn)有關(guān)的數(shù)據(jù)志信息的一般說明。DQ＿數(shù)據(jù)質(zhì)量實(shí)體包括兩個(gè)條件必選的實(shí)體，DQ＿數(shù)據(jù)質(zhì)量說明和DQ＿數(shù)據(jù)志。DQ＿數(shù)據(jù)質(zhì)量說明是數(shù)據(jù)集的總體質(zhì)量信息。DQ＿數(shù)據(jù)志是從數(shù)據(jù)源到數(shù)據(jù)集當(dāng)前狀態(tài)的演變過程說明。包括數(shù)據(jù)源信息實(shí)體和處理過程信息實(shí)體。

3．3．4內(nèi)容信息

內(nèi)容信息包含提供數(shù)據(jù)內(nèi)容特征的描述信息，用MD＿內(nèi)容描述實(shí)體表示。

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

參照系信息包含對(duì)數(shù)據(jù)集使用的空間參照系的說明，是條件必選子集，用RS＿參照系實(shí)體表示。是關(guān)于地理空間數(shù)據(jù)集的坐標(biāo)參考框架的描述信息，它反映了現(xiàn)實(shí)世界的空間框架模型化的過程和相關(guān)的描述參數(shù)。RS＿參照系由三個(gè)條件必選的實(shí)體構(gòu)成：SI＿基于地理標(biāo)識(shí)的空間參照系、SC＿基于坐標(biāo)的空間參照系、SC＿垂向坐標(biāo)參照系。

4元數(shù)據(jù)分級(jí)索引算法

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

4．1概念與公式

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

4．2BloomFilter基本思想元數(shù)據(jù)分級(jí)索引算法

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

4．3元數(shù)據(jù)分級(jí)索引算法

元數(shù)據(jù)分級(jí)索引算法包括三個(gè)步驟：一是選NameNode節(jié)點(diǎn)，二是選目錄，三是分配存儲(chǔ)位置。

4．3．1選取NameNode節(jié)點(diǎn)分布式

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

4．3．2選擇目錄

分配完NameNode節(jié)點(diǎn)后，須設(shè)定每個(gè)Nam－eNode節(jié)點(diǎn)的目錄，根據(jù)市級(jí)行政區(qū)劃與Name－Node節(jié)點(diǎn)映射表設(shè)定一級(jí)目錄。然后根據(jù)一級(jí)目錄的編碼，設(shè)定二級(jí)目錄，二級(jí)目錄為對(duì)應(yīng)市及所管轄縣級(jí)行政區(qū)劃的目錄。在飲水安全工程項(xiàng)目中，所涉及的數(shù)據(jù)類型分為圖片類型、視頻類型、文本類型等，所以將三級(jí)目錄按文件類型進(jìn)行劃分，即每個(gè)二級(jí)目錄下對(duì)應(yīng)的三級(jí)目錄為pic、video、txt等。

4．3．3分配存儲(chǔ)位置

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

5實(shí)驗(yàn)結(jié)果

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

6結(jié)束語

本文分析了飲水安全工程核心元數(shù)據(jù)的基本特點(diǎn)，并根據(jù)相關(guān)的標(biāo)準(zhǔn)提出了一種飲水安全工程核心元數(shù)據(jù)框架，提出了元數(shù)據(jù)分級(jí)索引算法。建立飲水安全工程核心元數(shù)據(jù)框架和元數(shù)據(jù)分布算法是統(tǒng)一管理飲水安全工程數(shù)據(jù)的基礎(chǔ)，只有很好地對(duì)飲水安全數(shù)據(jù)進(jìn)行描述和檢索，才能有效地對(duì)飲水安全數(shù)據(jù)進(jìn)行管理。由于飲水安全工程數(shù)據(jù)具有地理分布廣、時(shí)間有效性和數(shù)據(jù)要素多的特點(diǎn)，而且數(shù)據(jù)量與日俱增，所以本文提出的飲水安全工程核心元數(shù)據(jù)結(jié)構(gòu)和算法不一定適用于所有的情況，該結(jié)構(gòu)仍然需要不斷地完善。

作者：胡薇　蔡朝暉　梁甜　涂國慶　單位：武漢大學(xué)計(jì)算機(jī)學(xué)院