胡 薇，蔡朝暉，梁 甜，涂國慶

(武漢大學(xué)計(jì)算機(jī)學(xué)院，湖北 武漢 430072)

飲水安全工程信息的元數(shù)據(jù)分級(jí)索引算法*

胡 薇，蔡朝暉，梁 甜，涂國慶

(武漢大學(xué)計(jì)算機(jī)學(xué)院，湖北 武漢 430072)

分析了當(dāng)前飲水安全工程數(shù)據(jù)的發(fā)展趨勢(shì)和主要類型，根據(jù)飲水安全工程數(shù)據(jù)的特點(diǎn)，提出了一種應(yīng)用型的飲水安全核心元數(shù)據(jù)模型，設(shè)計(jì)了飲水安全工程核心元數(shù)據(jù)的結(jié)構(gòu)和內(nèi)容，將飲水安全工程核心元數(shù)據(jù)分為標(biāo)識(shí)信息、數(shù)據(jù)質(zhì)量信息、內(nèi)容信息、空間參照系信息和分發(fā)信息五個(gè)部分，并且分別描述了五個(gè)部分的結(jié)構(gòu)。同時(shí)，設(shè)計(jì)了符合飲水安全工程元數(shù)據(jù)的元數(shù)據(jù)分級(jí)算法，比較了元數(shù)據(jù)分級(jí)算法和目錄子樹分區(qū)算法以及哈希算法的實(shí)驗(yàn)結(jié)果。

飲水安全工程；分布式NameNode模型；元數(shù)據(jù)分級(jí)算法

1 引言

飲水安全工程數(shù)據(jù)是在建設(shè)農(nóng)村飲水安全工程的過程中產(chǎn)生的數(shù)據(jù)信息，是衡量水質(zhì)、水量和用水方便程度等綜合因素的一種特殊水利信息。飲水安全工程數(shù)據(jù)要素多，主要包括地圖基礎(chǔ)地理信息、供水工程信息、行政單位基礎(chǔ)數(shù)據(jù)和監(jiān)測數(shù)據(jù)等，數(shù)據(jù)形式多種多樣，如地理信息空間數(shù)據(jù)、圖像、文本等。在傳統(tǒng)的農(nóng)村飲水安全工程建設(shè)中，數(shù)據(jù)的多元化和數(shù)據(jù)形式的多樣化給飲水安全工程數(shù)據(jù)的存儲(chǔ)和檢索帶來了不便，現(xiàn)有的非結(jié)構(gòu)化的組織形式已經(jīng)不能適應(yīng)飲水安全工程數(shù)據(jù)發(fā)展的要求。為此，本文提出了飲水安全工程核心元數(shù)據(jù)的概念以及元數(shù)據(jù)分級(jí)索引算法。

元數(shù)據(jù)是描述數(shù)據(jù)的數(shù)據(jù)[1]，只有對(duì)數(shù)據(jù)進(jìn)行統(tǒng)一描述，才能有效地管理數(shù)據(jù)。規(guī)范的元數(shù)據(jù)描述有利于建立各數(shù)據(jù)間的關(guān)聯(lián)和信息的發(fā)現(xiàn)，能夠提高檢索的效率[2]。由于飲水安全工程信息化是近兩年提出的概念，并沒有學(xué)者專門對(duì)飲水安全工程數(shù)據(jù)進(jìn)行研究，但在其它領(lǐng)域的數(shù)據(jù)研究已經(jīng)比較成熟，如2005年王國復(fù)[3]發(fā)表的《氣象元數(shù)據(jù)標(biāo)準(zhǔn)與信息發(fā)布技術(shù)研究》、國土資源信息核心元數(shù)據(jù)標(biāo)準(zhǔn)(TD/T1016-2003)[4]、2011年張繼紅[5]發(fā)表的《海量交通安全數(shù)據(jù)的元數(shù)據(jù)管理研究》等。現(xiàn)有的水利行業(yè)的元數(shù)據(jù)研究主要集中于水利元數(shù)據(jù)的應(yīng)用，并沒有涉及到飲水安全工程元數(shù)據(jù)。如2012年孟令奎等人[6]發(fā)表的《面向水文數(shù)據(jù)共享的水文核心元數(shù)據(jù)模型研究及應(yīng)用》，該文著重描述水利元數(shù)據(jù)在水利共享平臺(tái)中的應(yīng)用；2011年馮鈞等人[7]發(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)測信息，遍布全國，因此飲水安全工程數(shù)據(jù)具備地理空間的分布特性。

(2)數(shù)據(jù)要素多。飲水安全工程數(shù)據(jù)包括了地圖數(shù)據(jù)，供水工程專題數(shù)據(jù)，省、市州、縣區(qū)、鄉(xiāng)鎮(zhèn)專題基礎(chǔ)信息，水質(zhì)、管壓安全監(jiān)測信息，政務(wù)信息等。而且每類數(shù)據(jù)又包括多種要素的數(shù)據(jù)，如供水工程專題數(shù)據(jù)包括專題地理信息和專題建設(shè)信息，監(jiān)測數(shù)據(jù)包括余氯、濁度、水壓、流量等測量數(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ù)[2]。

元數(shù)據(jù)元素：元數(shù)據(jù)的基本單元，元數(shù)據(jù)元素在元數(shù)據(jù)實(shí)體中是唯一的[9]。

元數(shù)據(jù)實(shí)體：一組說明數(shù)據(jù)相同特性的元數(shù)據(jù)元素，元數(shù)據(jù)實(shí)體可以包含一個(gè)或一個(gè)以上的元數(shù)據(jù)實(shí)體[8]。

元數(shù)據(jù)子集：元數(shù)據(jù)的子集合，由相關(guān)的元數(shù)據(jù)實(shí)體和元素組成[6]。

數(shù)據(jù)集：可以標(biāo)識(shí)的數(shù)據(jù)集合。通常在物理上可以是更大數(shù)據(jù)集較小的部分。從理論上講，數(shù)據(jù)集可以小到更大數(shù)據(jù)集內(nèi)的單個(gè)要素或要素屬性，一張硬拷貝地圖或圖表均可以被認(rèn)為是一個(gè)數(shù)據(jù)集[8]。

飲水安全工程核心元數(shù)據(jù)指的是標(biāo)識(shí)飲水安全工程信息所需要的最小元數(shù)據(jù)元素和元數(shù)據(jù)實(shí)體，為元數(shù)據(jù)元素集的子集[9,10]。

其次，本文采用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ù)、類型和值域[7]進(jìn)行詳細(xì)描述。

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

飲水安全工程元數(shù)據(jù)分為元數(shù)據(jù)元素、元數(shù)據(jù)實(shí)體和元數(shù)據(jù)子集三層[9,11]。飲水安全工程核心元數(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模型[12]，改進(jìn)目錄子樹分區(qū)算法[13～15]和哈希算法[16]，利用Bloom Filter原理設(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.2 Bloom Filter基本思想

元數(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中的具體位置。本文采用Bloom Filter與Key-Value的存儲(chǔ)位置對(duì)應(yīng)表，來確定元數(shù)據(jù)文件在DataNode中的存儲(chǔ)位置。

Bloom Filter的基本思想是使用一個(gè)比特的數(shù)組保存信息[17]，初始狀態(tài)時(shí)，整個(gè)數(shù)組的元素全部為0，如圖1所示。

Figure 1 Initial data for Bloom Filter
圖1 Bloom Filter初始數(shù)組

采用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將不起作用。如圖2所示，假設(shè)k=3，x1先通過哈希函數(shù)，將數(shù)組中的三個(gè)位置置為1，在x2通過哈希函數(shù)得到的數(shù)組位置，將是0的位置置為1，已經(jīng)是1的位置則不重復(fù)置1。

Figure 2 Run of Bloom Filter圖2 Bloom Filter運(yùn)行過程

判斷某元素y是否屬于這個(gè)集合，需對(duì)y應(yīng)用k次哈希函數(shù)，如果所有的位置都是1(1≤i≤k)，那么就認(rèn)為y是集合中的元素，否則就認(rèn)為y不是集合中的元素。如圖3所示，y1可能是集合中的元素，y2則不屬于這個(gè)集合。

Figure 3 Search process of Bloom Filter圖3 Bloom Filter查找過程

BloomFilter能高效地判斷某個(gè)元素是否屬于一個(gè)集合，但這種高效是有代價(jià)的，是存在一定的錯(cuò)誤率，因?yàn)樗锌赡軙?huì)把不屬于這個(gè)集合的元素判定為屬于此集合。為簡化計(jì)算，假設(shè)kn

(3)

其中第二次近似計(jì)算是因?yàn)?

(4)

令ρ代表比特?cái)?shù)組中0的比例，則ρ的數(shù)學(xué)期望E(ρ)=p，則ρ≈p，因此：

(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è)NameNode節(jié)點(diǎn)的目錄，根據(jù)市級(jí)行政區(qū)劃與NameNode節(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ǔ)位置并提交給主NameNode節(jié)點(diǎn)，由主NameNode節(jié)點(diǎn)返回給用戶。

飲水安全元數(shù)據(jù)檢索結(jié)果分為兩種情況，第一種是查找成功，第二種是查找失敗。一次飲水安全元數(shù)據(jù)成功檢索過程的檢索時(shí)間包括主NameNode節(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ù)檢索上的性能，并與目錄子樹分區(qū)算法和哈希算法在檢索成功時(shí)間和檢索失敗時(shí)間進(jìn)行對(duì)比。

第一組實(shí)驗(yàn)，測試三種算法檢索成功的平均檢索時(shí)間，其中用戶數(shù)為10，請(qǐng)求數(shù)為1 000，仿真結(jié)果如圖4所示。

Figure 4 Comparison of average time for successful retrieval圖4 三種算法檢索成功的平均檢索時(shí)間

在定位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í)間與NameNode節(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ǔ)位置上，由于Bloom Filter查找成功的時(shí)間復(fù)雜度是O(1)，而目錄子樹分區(qū)算法和哈希算法沒有考慮定位物理位置，查找目錄下的元數(shù)據(jù)名稱，時(shí)間復(fù)雜度為O(n)，目錄下的元數(shù)據(jù)文件越多，查找速度越慢。

第二組實(shí)驗(yàn)，測試三種算法檢索失敗的平均檢索時(shí)間，其中用戶數(shù)為10，請(qǐng)求數(shù)為1 000，仿真實(shí)驗(yàn)結(jié)果如圖5所示。

Figure 5 Comparison of average time for failure rerieval圖5 三種算法檢索失敗的平均檢索時(shí)間

若是檢索不在目錄下的文件，Bloom Filter將文件名進(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í)算法使用了Bloom Filter，檢索效率比其它兩種算法效率高，尤其是檢索失敗的檢索請(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)仍然需要不斷地完善。

[1] Geng Qing-zhai, Zhu Xing-ming. Research and construction of standard system of scientific data sharing of water resources[J]. Journal of Hydrolic Engineering, 2007, 38(2):233-238.(in Chinese)

[2] Guo Shi-ming, Jing Ji-peng. The metadata function of network information resource organization and retrieval[J]. Information Science, 2004,22(12):1455-1457.(in Chinese)

[3] Wang Guo-fu,Xu Feng,Wu Zeng-xiang.Technology research of meteorological metadata standard and information release[J]. Journal of Applied Meteorological Science, 2005,16(1):114-121.(in Chinese)

[4] TD/T 1016-2003,Core metadata standard for land and resources information[S].Beijing:Ministry of Land and Resources of the People’s Republic of China,2003.(in Chinese)

[5] Zhang Ji-hong, Chen Xiao-quan. Research of metadata management for large-scale traffic security data[J]. Journal of Computer Research and Development,2011,48(1):74-77.(in Chinese)

[6] Meng Ling-kui, Li San-xia, Zhang Wen, et al. Research and application of hydrological core metadata model for hydrological data sharing[J]. Journal of China Hydrology, 2012, 32(1):1-5.(in Chinese)

[7] Feng Jun, Tang Zhi-xian, Huang Ru-chun, et al. Study on water conservancy information resources metadata management method[J]. Water Resource Informatioin, 2011(5):1-4.(in Chinese)

[8] Guo Chun-yi, Gang Qiang. Hydrological information sharing and its security analysis based on spatial data warehouse[J]. Jilin Water Resources, 2009(5):38-40.(in Chinese)

[9] SL 473—2010, Core metadata of water resources information[S]. Beijing:Ministry of Water Resources of the People’s Republic of China, 2010.(in Chinese)

[10] Yao Yan-min, Jiang Zuo-qin, Yan Tai-lai. A study of core metadata for land and resource information[J]. Acta Geodaeticaet Cartographica Sinica, 2001, 30(4):349-354.(in Chinese)

[11] Gu Ji-rong, Miao Fang, Wang Cheng-shan. Research of metadata information sharing system[J]. Computing Techniques for Geophysical and Geochemical Exploration, 2006, 28(1):75-79.(in Chinese)

[12] Li Kuan. Research of the model of distributed NameNodes in HDFS[D]. Guangzhou:South China University of Technology, 2011.(in Chinese)

[13] Morris J H, Satyanarayanan M, Conner M H, et al. Andrew:A distributed personal computing environment[J]. Communications of the ACM, 1986, 29(3):184-201.

[14] Satyanarayanan M, Kistler J J, Kumar P, et al. Coda:A highly available file system for a distributed workstation environment[J]. IEEE Transactions on Computers, 1990, 39(4):447-459.

[15] Weil S A, Pollack K T, Brandt S A, et al. Dynamic metadata management for petabyte-scale file systems[C]∥Proc of the 2004 ACM/IEEE Conference on Supercomputing, 2004:4.

[16] Corbett P F, Feitelson D G. The Vesta parallel file system[J]. ACM Transactions on Computer Systems(TOCS), 1996, 14(3):225-264.

[17] Niu De-jiao, Cai Tao, Zhan Yong-zhao, et al. Hierarchical metadata indexing algorithm of mass storage system[J]. Application Research of Computers, 2012, 29(2):510-517.(in Chinese)

附中文參考文獻(xiàn):

[1] 耿慶齋,朱星明.水利科學(xué)數(shù)據(jù)共享標(biāo)準(zhǔn)體系研究與構(gòu)建[J].水利學(xué)報(bào),2007,38(2):233-238.

[2] 過仕明,靖繼鵬.元數(shù)據(jù)在網(wǎng)絡(luò)信息資源組織與檢索中的作用[J].情報(bào)科學(xué),2004,22(12):1455-1457.

[3] 王國復(fù),徐楓,吳增祥.氣象元數(shù)據(jù)標(biāo)準(zhǔn)與信息發(fā)布技術(shù)研究[J].應(yīng)用氣象學(xué)報(bào),2005,16(1):114-121.

[4] TD/T 1016-2003,國土資源信息核心元數(shù)據(jù)標(biāo)準(zhǔn)[S].北京:

中華人民共和國國土資源部,2003.

[5] 張繼紅,陳小全.海量交通安全數(shù)據(jù)的元數(shù)據(jù)管理研究[J].計(jì)算機(jī)研究與發(fā)展,2011,48(1):74-77.

[6] 孟令奎,李三霞,張文,等.面向水文數(shù)據(jù)共享的水文核心元數(shù)據(jù)模型研究及應(yīng)用[J].水文,2012,32(1):1-5.

[7] 馮鈞,唐志賢,黃如春,等.水利信息資源元數(shù)據(jù)管理方法研究[J].水利信息化,2011(5):1-4.

[8] 郭純一, 冮強(qiáng).基于空間數(shù)據(jù)倉庫的水文信息共享及其安全性淺析[J].吉林水利,2009(5):38-40.

[9] SL 473—2010,水利信息核心元數(shù)據(jù)[S].北京:中華人民共和國水利部,2010.

[10] 姚艷敏,姜作琴,嚴(yán)泰來.國土資源信息核心元數(shù)據(jù)的研究[J].測繪學(xué)報(bào),2001, 30(4):349-354.

[11] 辜寄蓉, 苗放, 王成善. 基于元數(shù)據(jù)的信息共享機(jī)制研究[J]. 物探化探計(jì)算技術(shù), 2006, 28(1):75-79.

[12] 李寬.基于HDFS的分布式NameNode節(jié)點(diǎn)模型的研究[D].廣州:華南理工大學(xué),2011.

[17] 牛德姣,蔡濤,詹永照,等.海量存儲(chǔ)系統(tǒng)中的元數(shù)據(jù)分級(jí)索引算法[J].計(jì)算機(jī)應(yīng)用研究,2012,29(2):510-517.

HUWei,born in 1989,MS candidate,her research interest includes computer architecture.

蔡朝暉(1968),女,湖北黃岡人，博士，副教授，研究方向?yàn)榉植际叫畔⑻幚?。E-mail:zhcai@whu.edu.cn

CAIZhao-hui,born in 1968,PhD,associate professor,her research interest includes distributed information processing.

梁甜(1988),女,河北石家莊人，碩士生，研究方向?yàn)樾畔⒋鎯?chǔ)。E-mail:441493972@qq.com

LIANGTian,born in 1988,MS candidate,her research interest includes information storage.

Ametadataclassificationindexingalgorithmfordrinkingwatersafetyprojectinformation

HU Wei,CAI Zhao-hui,LIANG Tian,TU Guo-qing

(School of Computer,Wuhan University,Wuhan 430072,China)

The current developmental trends and the main types of the drinking water safety project data are analyzed.Considering the characteristics of the drinking water safety project data,a core metadata model applied in the drinking water safety is proposed, and the structure and content of the core metadata of the drinking water safety project are designed.The core metadata of the drinking water safety project can be divided into five parts:identity information, data quality information, content information, space reference information and distribution information whose construction is described respectively. A metadata classification algorithm is designed, which conforms to the drinking water safety project data.The metadata classification indexing algorithm improves the management and work efficiency of rural drinking water safety compared with the subtree partitioning algorithm and the Hash algorithm.

drinking water safety project;distributed NameNode model;metadata classification algorithm

1007-130X(2014)11-2223-06

2014-06-05;

：2014-08-21

TP311.13

：A

10.3969/j.issn.1007-130X.2014.11.028

胡薇(1989),女,湖北武漢人，碩士生,研究方向?yàn)橛?jì)算機(jī)系統(tǒng)結(jié)構(gòu)。E-mail:380476943@qq.com

通信地址：430072 湖北省武漢市武漢大學(xué)計(jì)算機(jī)學(xué)院

Address:School of Computer,Wuhan University,Wuhan 430072,Hubei,P.R.China