元数据分级索引算法饮水安全工程优秀论文
１引言
２０１１年张继红发表的《海量交通安全数据的元数据管理研究》等。现有的水利行业的元数据研究主要集中于水利元数据的应用，并没有涉及到饮水安全工程元数据。如２０１２年孟令奎等人发表的《面向水文数据共享的水文核心元数据模型研究及应用》，该文着重描述水利元数据在水利共享平台中的应用；２０１１年冯钧等人发表的《水利信息资源元数据管理方法研究》主要研究水利元数据的管理。本文利用水利行业现行的元数据标准作为参考，提出饮水安全工程核心元数据的概念，规范饮水安全工程元数据的定义，利用元数据分级索引算法来查找饮水安全工程数据，着重解决饮水安全工程数据种类多、数据标准化程度低、关联复杂、数据量大的问题，提高农村饮水安全工程信息的规整性，加快检索速度。
２饮水安全工程数据的特点
与一般的科学数据相比，饮水安全工程数据具备以下两个特点：
（１）地理分布性。作为基本数据，国家农村饮水安全工程数据库包括了国内各省（直辖市）、市（州）、县（市、区）、乡镇内供水水厂的集中式工程数据，包括工程建设信息、实时监测信息，遍布全国，因此饮水安全工程数据具备地理空间的分布特性。
（２）数据要素多。饮水安全工程数据包括了地图数据，供水工程专题数据，省、市州、县区、乡镇专题基础信息，水质、管压安全监测信息，政务信息等。而且每类数据又包括多种要素的数据，如供水工程专题数据包括专题地理信息和专题建设信息，监测数据包括余氯、浊度、水压、流量等测量数据。整体来说，饮水安全工程数据是描述饮水安全工程的数据，数据量大，且与日俱增，专业性强，具有时间维上的有效性，且数据区域性强，不同市县统计的数据不交叉，数据存储形式多样，以小文件居多。
３饮水安全工程核心元数据
３.１元数据定义
首先，介绍几个关于元数据的定义。元数据：关于数据的数据。元数据元素：元数据的基本单元，元数据元素在元数据实体中是唯一的。元数据实体：一组说明数据相同特性的元数据元素，元数据实体可以包含一个或一个以上的元数据实体。元数据子集：元数据的子集合，由相关的元数据实体和元素组成。数据集：可以标识的数据集合。通常在物理上可以是更大数据集较小的部分。从理论上讲，数据集可以小到更大数据集内的单个要素或要素属性，一张硬拷贝地图或图表均可以被认为是一个数据集。饮水安全工程核心元数据指的是标识饮水安全工程信息所需要的最小元数据元素和元数据实体，为元数据元素集的子集。其次，本文采用ＵＭＬ类图方法描述饮水安全工程信息元数据。在元数据结构上采用《水利信息核心元数据》的结构作为本标准的基本结构，在内容上对元数据的`特征，包括子集／实体名、元素名、英文名、英文缩写、定义、约束／条件、出现次数、类型和值域进行详细描述。
３.２饮水安全工程核心元数据结构
饮水安全工程元数据分为元数据元素、元数据实体和元数据子集三层。饮水安全工程核心元数据由一个元数据实体和四个元数据子集构成。其中，标识信息、数据质量为必选子集，内容信息、参照系信息为可选子集。每个子集由若干个实体（ＵＭＬ类）和元素（ＵＭＬ类属性）构成。
３.３饮水安全核心元数据内容
３.３.１饮水安全核心元数据信息
饮水安全工程元数据信息实体描述饮水安全工程信息的全部元数据信息，用必选实体ＭＤ＿元数据表示，由以下元数据实体和元数据元素构成：元数据实体：ＭＤ＿标识、ＤＱ＿数据质量、ＲＳ＿参照系、ＭＤ＿分发、ＭＤ＿内容描述；元数据元素：元数据创建日期、联系单位、元数据名称、字符集、元数据使用的语言、元数据标准名称、元数据标准版本。
３.３.２标识信息
标识信息包含唯一标识数据的信息，用ＭＤ＿标识实体表示，是必选实体。ＭＤ＿标识是下列实体的聚集：ＭＤ＿关键词、ＭＤ＿数据集限制、ＥＸ＿时间范围信息、ＭＤ＿联系单位或联系人、ＭＤ＿维护信息。ＭＤ＿标识实体本身包含如下元素：名称、行政区编码、字符集、摘要、日期、状况、数据表示方式。
３.３.３数据质量信息
数据质量信息包含对数据资源质量的总体评价，用ＤＱ＿数据质量实体表示。应包括与数据生产有关的数据志信息的一般说明。ＤＱ＿数据质量实体包括两个条件必选的实体，ＤＱ＿数据质量说明和ＤＱ＿数据志。ＤＱ＿数据质量说明是数据集的总体质量信息。ＤＱ＿数据志是从数据源到数据集当前状态的演变过程说明。包括数据源信息实体和处理过程信息实体。
３.３.４内容信息
内容信息包含提供数据内容特征的描述信息，用ＭＤ＿内容描述实体表示。
３.３.５空间参照系信息
参照系信息包含对数据集使用的空间参照系的说明，是条件必选子集，用ＲＳ＿参照系实体表示。是关于地理空间数据集的坐标参考框架的描述信息，它反映了现实世界的空间框架模型化的过程和相关的描述参数。ＲＳ＿参照系由三个条件必选的实体构成：ＳＩ＿基于地理标识的空间参照系、ＳＣ＿基于坐标的空间参照系、ＳＣ＿垂向坐标参照系。
４元数据分级索引算法
本文根据饮水安全工程数据的区域性特点，选取分布式ＮａｍｅＮｏｄｅ模型，改进目录子树分区算法和哈希算法，利用ＢｌｏｏｍＦｉｌｔｅｒ原理设计符合饮水安全工程信息的元数据分级索引算法。
４.１概念与公式
行政区划请求量：表示该行政区划所需的农村饮水安全工程元数据的请求量，用Ｒｅｑｕｅｓｔ表示。由于请求量的具体数值难以确定，工程元数据的请求量与工程的数量有直接关系，而饮水工程的数量与行政区划的人口密度存在一定的换算关系。每个工程所涉及的文件包括招标文件、合同、工程规划、预算、管网图、厂区布置图、每年的运营报表等多种文件。因此，第ｍ个行政区划的请求量Ｒｅｑｕｅｓｔｍ为：Ｒｅｑｕｅｓｔｍ＝Ｄｅｎｓｉｔｙｍ×ｆ×Ｎａｖｅｒａｇｅ（１）其中，Ｄｅｎｓｉｔｙｍ代表第ｍ个行政区划的人口密度，ｆ表示饮水安全工程数量与人口密度的转换因子，Ｎａｖｅｒａｇｅ代表每个工程文件的平均值。
４.２ＢｌｏｏｍＦｉｌｔｅｒ基本思想元数据分级索引算法
包括三部分：一部分是元数据请求被分配到哪个普通ＮａｍｅＮｏｄｅ节点上，第二部分是分配到ＮａｍｅＮｏｄｅ节点的哪个目录，最后根据ＮａｍｅＮｏｄｅ节点中的目录信息查找元数据文件在ＤａｔａＮｏｄｅ中的具体位置。本文采用ＢｌｏｏｍＦｉｌｔｅｒ与Ｋｅｙ－Ｖａｌｕｅ的存储位置对应表，来确定元数据文件在ＤａｔａＮｏｄｅ中的存储位置。ＢｌｏｏｍＦｉｌｔｅｒ的基本思想是使用一个比特的数组保存信息，初始状态时，整个数组的元素全部为０，采用ｋ个独立的Ｈａｓｈ函数，将每个元数据文件对应到｛１，…，ｍ｝的位置，当有饮水安全元数据文件存储请求时，ｋ个独立的Ｈａｓｈ函数将以元数据标识信息中的元数据文件名为变量，得到ｋ个哈希值，然后将比特数组中的相应位置更改为１，即：ｈａｓｈｉ（ｘ）＝１（１≤ｉ≤ｋ）（２）其中，ｘ是元数据文件名。数组中的某一位置被置为１后，只有第一次有效，以后再置为１将不起作用。所示，假设ｋ＝３，ｘ１先通过哈希函数，将数组中的三个位置置为１，在ｘ２通过哈希函数得到的数组位置，将是０的位置置为１，已经是１的位置则不重复置１。判断某元素ｙ是否属于这个集合，需对ｙ应用ｋ次哈希函数，如果所有的位置都是１（１≤ｉ≤ｋ），那么就认为ｙ是集合中的元素，否则就认为ｙ不是集合中的元素。如图３所示，ｙ１可能是集合中的元素，ｙ２则不属于这个集合。ＢｌｏｏｍＦｉｌｔｅｒ能高效地判断某个元素是否属于一个集合，但这种高效是有代价的，是存在一定的错误率，因为它有可能会把不属于这个集合的元素判定为属于此集合。为简化计算，假设ｋｎ＜ｍ并且各哈希函数完全随机。当某个目录中的所有元数据文件全部存储，即所有元素都被哈希函数映射到比特数组中去，这个数组中某一位置是０代表ｋｎ次哈希操作都没有被置为１，因此概率为：ｐ＝（１－１ｍ）ｋｎ≈ｅ－ｋｎ／ｍ（３）其中第二次近似计算是因为：ｌｉｍｘ→ｍ（１＋１ｎ）ｎ＝ｅ（４）令代表比特数组中０的比例，则的数学期望Ｅ（）＝ｐ，则≈ｐ，因此：ｐｆａｌｓｅ＝（１－）ｋ≈（１－ｐ）ｋ（５）
４.３元数据分级索引算法
元数据分级索引算法包括三个步骤：一是选ＮａｍｅＮｏｄｅ节点，二是选目录，三是分配存储位置。
４.３.１选取ＮａｍｅＮｏｄｅ节点分布式
ＮａｍｅＮｏｄｅ模型有一个主ＮａｍｅＮｏｄｅ节点，一个主ＳｅｃｏｎｄａｒｙＮａｍｅＮｏｄｅ和ｎ个普通ＮａｍｅＮｏｄｅ节点。其中，主ＳｅｃｏｎｄａｒｙＮａｍｅＮｏｄｅ是主ＮａｍｅＮｏｄｅ的快照，防止单点失效。算法的基本思想如下：（１）计算行政区划请求数。在本文中所涉及的饮水安全工程指的是湖北省的农村饮水安全工程，因此在普通ＮａｍｅＮｏｄｅ节点上分布的是以市级为单位的元数据信息。在这一步中，根据公式（１）给每个市级行政区划的请求赋值，用Ｒｅｑｕｅｓｔｍ表示。（２）分配ＮａｍｅＮｏｄｅ节点。若ｎ为奇数，则将其中一个ＮａｍｅＮｏｄｅ节点作为备用节点，ｎ＝ｎ－１；若ｎ为偶数，则ｎ不变。分配ＮａｍｅＮｏｄｅ节点，得出市级行政区划与ＮａｍｅＮｏｄｅ节点映射表。（３）第二次分组。将偶数个ＮａｍｅＮｏｄｅ两两分成组，互为ＳｅｃｏｎｄａｒｙＮａｍｅＮｏｄｅ节点，分组的原则为请求量较大的ＮａｍｅＮｏｄｅ节点与请求量较小的ＮａｍｅＮｏｄｅ节点一组。
４.３.２选择目录
分配完ＮａｍｅＮｏｄｅ节点后，须设定每个Ｎａｍ－ｅＮｏｄｅ节点的目录，根据市级行政区划与Ｎａｍｅ－Ｎｏｄｅ节点映射表设定一级目录。然后根据一级目录的编码，设定二级目录，二级目录为对应市及所管辖县级行政区划的目录。在饮水安全工程项目中，所涉及的数据类型分为图片类型、视频类型、文本类型等，所以将三级目录按文件类型进行划分，即每个二级目录下对应的三级目录为ｐｉｃ、ｖｉｄｅｏ、ｔｘｔ等。
４.３.３分配存储位置
当用户要查找某个饮水安全元数据时，系统首先根据待查找元数据的行政区划编码，从市级行政区划与ＮａｍｅＮｏｄｅ节点映射表中找到其对应的ＮａｍｅＮｏｄｅ节点；然后，主ＮａｍｅＮｏｄｅ节点将用户请求转发给此ＮａｍｅＮｏｄｅ节点，收到转发的用户请求的ＮａｍｅＮｏｄｅ节点同样将行政区编码进行处理，转化为市级编码，找到其一级目录；然后在一级目录下，根据编码找到二级目录，再根据用户请求的元数据类型，定位到三级目录，在三级目录下根据哈希表，找到对应存储位置并提交给主Ｎａｍｅ－Ｎｏｄｅ节点，由主ＮａｍｅＮｏｄｅ节点返回给用户。饮水安全元数据检索结果分为两种情况，第一种是查找成功，第二种是查找失败。一次饮水安全元数据成功检索过程的检索时间包括主ＮａｍｅＮｏ－ｄｅ节点并发处理延迟、主ＮａｍｅＮｏｄｅ节点找到对应的ＮａｍｅＮｏｄｅ节点的时间、转发用户请求与普通ＮａｍｅＮｏｄｅ节点的通信时间、普通节点执行查找目录的时间、查找Ｈａｓｈ表读取元数据的时间和返回查找结果给主ＮａｍｅＮｏｄｅ的时间。一次失败的检索包含两种情况，一是定位到目录后，通过ＢｌｏｏｍＦｉｌｔｅｒ过滤后，判定要查找饮水安全工程元数据哈希表不属于该目录；二是通过ＢｌｏｏｍＦｉｌｔｅｒ过滤后，判定其属于该目录，但是通过查询Ｋｅｙ－Ｖａｌｕｅ表，发现匹配错误，即上文提到的ＢｌｏｏｍＦｉｌｔｅｒ自身的错误率。第一种情况，根据ＢｌｏｏｍＦｉｌｔｅｒ的原理，可知经过ｋ次独立的哈希函数后，如果得到的位置不是全为１，则返回查找失败，要查找的元数据请求不在此目录中，时间复杂度为Ｏ（１）。第二种情况是ＢｌｏｏｍＦｉｌｔｅｒ自身的缺陷，但是由于有对应的Ｋｅｙ－Ｖａｌｕｅ表，即使经过ｋ次哈希操作得到的位置在比特数组中全为１，通过查找对应的键值，如果发现元数据名称不能与之匹配，则返回检索不成功，时间复杂度也为Ｏ（１），在用户可以接受的范围内。
５实验结果
本文通过实验仿真验证饮水安全工程元数据模型的元数据分级索引算法在元数据检索上的性２２２６ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ＆Ｓｃｉｅｎｃｅ计算机工程与科学２０１４，３６（１１）能，并与目录子树分区算法和哈希算法在检索成功时间和检索失败时间进行对比。第一组实验，测试三种算法检索成功的平均检索时间，其中用户数为１０，请求数为１０００，在定位ＮａｍｅＮｏｄｅ节点的时间上来说，目录子树分区算法能够根据用户请求中的类型定位节点，哈希算法是通过特定的Ｈａｓｈ函数，算出用户请求元数据所在的节点。而本文设计的元数据分级索引算法，将市级行政区划和ＮａｍｅＮｏｄｅ节点编号存储在一张静态的表中，查找时间与Ｎａｍｅ－Ｎｏｄｅ节点个数有关，时间复杂度为Ｏ（ｎ）。在本文的应用中，至多会有１４个ＮａｍｅＮｏｄｅ节点，三种算法的定位时间基本相同，在查找ＮａｍｅＮｏｄｅ节点的步骤上所用时间可以近似算作相等。定位目录的时间复杂度，三种算法也相同，可认为是Ｏ（１）。在最后一步定位元数据文件存储位置上，由于ＢｌｏｏｍＦｉｌｔｅｒ查找成功的时间复杂度是Ｏ（１），而目录子树分区算法和哈希算法没有考虑定位物理位置，查找目录下的元数据名称，时间复杂度为Ｏ（ｎ），目录下的元数据文件越多，查找速度越慢。第二组实验，测试三种算法检索失败的平均检索时间，其中用户数为１０，请求数为１０００，仿若是检索不在目录下的文件，ＢｌｏｏｍＦｉｌｔｅｒ将文件名进行Ｈａｓｈ运算，可以判定被请求的文件名不在目录中，时间复杂度为Ｏ（１）。而另外两种算法，则会遍历目录中的所有文件，直至遍历完，找不到所请求的文件，时间复杂度为Ｏ（ｎ）。对比三种算法在饮水安全工程元数据检索上的应用情况，由于元数据分级算法使用了ＢｌｏｏｍＦｉｌｔｅｒ，检索效率比其它两种算法效率高，尤其是检索失败的检索请求。
６结束语
本文分析了饮水安全工程核心元数据的基本特点，并根据相关的标准提出了一种饮水安全工程核心元数据框架，提出了元数据分级索引算法。建立饮水安全工程核心元数据框架和元数据分布算法是统一管理饮水安全工程数据的基础，只有很好地对饮水安全数据进行描述和检索，才能有效地对饮水安全数据进行管理。由于饮水安全工程数据具有地理分布广、时间有效性和数据要素多的特点，而且数据量与日俱增，所以本文提出的饮水安全工程核心元数据结构和算法不一定适用于所有的情况，该结构仍然需要不断地完善。
【元数据分级索引算法饮水安全工程优秀论文】相关文章：
MySQL索引背后的数据结构及算法原理 -电脑资料01-01
浅谈MySQL索引背后的数据结构及算法 -电脑资料01-01
农村饮水安全工程的论文11-19
市饮水安全工程论文11-21
农村饮水安全工程论文11-20
基于matlab的物料大小分级算法的实现07-27
管理农村饮水安全工程论文02-06
农村饮水安全工程管理的论文02-24
农村饮水安全工程建设论文11-20