一种基于区间预留编码的XML关键字查询算法

近年来,随着XML数据的爆炸式增长,对XML关键字查询技术的研究日益受到关注。数据编码是关键字查询的基础,目前主要有2种方式--基于路径的编码及区间编码。区间编码可更好地适应对查询中的XML数据进行动态的更新,因而具有更多的优势。本文研究基于区间编码的关键字查询问题,提出一种新的查询算法。该算法首先根据预留的区间值建立索引,再根据最小范围值对索引进行选择遍历,减少了不必要的比较,达到了提高查询效率的目的。研究发现,预留空间的选择对查询效率有一定的影响。为此,本文设计一种基于节点自身进行区间预留的编码方式（Interval Reservation Based on Node, IRBN）,为节点设置权值,并根据权值进行区间值的设定,形成根据节点自身分配区间的较为均衡的编码。实验表明,IRBN编码是合理的,有较高的查询效率。     

基于MapReduce的XML结构连接处理

可扩展标记语言(extensible markup language,XML)已经成为Web上数据表达和数据交换的事实标准,Hadoop已成为云计算和大数据处理典型支撑框架之一,基于Hadoop MapReduce来实现XML查询处理十分必要。为了实现基于MapReduce的XML查询处理,首先实现了区间编码、前缀编码和层次编码等3种不同的XML数据编码方式,以此为基础来研究和实现基于MapReduce的XML结构连接处理。为查询处理建立了代价模型,通过代价估算获得优化的查询计划树。最后开展了XML查询处理实验评估,结果表明相对其他两种XML编码方式,区间编码方式下实现的查询处理速度较快,基于代价估算的优化方法能进一步有效地提高XML查询处理性能。     

基于位运算的固件代码变量区间分析法

变量区间分析是程序代码数据流分析的重要部分。固件反汇编代码存在字节运算和位运算两类运算,当变量取值范围较大时,依次迭代法不能高效地分析经位运算后的结果的取值区间。提出一种快速位运算方法,即根据变量取值区间范围,先将变量转化为不确定位形式再进行位运算;提出一种区间生成算法,即把不确定位形式转化为区间来实现字节运算。实验结果表明,该基于位运算的固件代码变量区间分析方法在程序变量取值范围较大时效率远远高于依次迭代法,而且在各种变量取值区间范围内所需时间稳定,并随着区间范围的增大,其有略微下降趋势。     

一种基于过滤器的无线传感器网络近似kNN查询优化算法

在无线传感器网络中进行感知数据查询,必须考虑传感器节点能量受限的特性.提出了一种基于过滤器的无线传感器网络近似一维K-NN查询优化算法FAKNN. FAKNN算法利用样本数据为每一个节点设置一个经验取值区间,并针对查询选择样本数据均值距离查询点最近的部分节点构成候选结果集.由于用户对查询结果的满意度与候选节点的个数和越界概率有关,因此需要通过计算节点的越界概率来确定最终候选结果集,并将候选节点的经验取值区间作为过滤器随查询请求发送到全网.节点利用过滤规则阻止数据发送,从而节省节点能量.仿真实验表明,FAKNN算法在保证查询准确率的同时,可大幅降低查询通信量.     

基于区间编码的GML索引与查询

GML很好地解决了不同GIS系统间地理数据的共享、交换和集成问题,已逐步成为空间数据编码、传输、存储和发布的国际标准.随着GML的广泛应用,如何有效地管理GML数据已成为亟待解决的问题.本文提出一种基于区间编码的方法对GML文档中的元素、属性、文本、几何体等要素进行编码,对非空间特性信息建立B树以实现值查询,对空间特性信息建立R树索引或四又树索引以进行空间分析.在查询处理中,采用以xQuery为基础的GQL查询语言,以实现对GML文档的非空间查询、空间查询及混合查询.实验证明这种方法能够有效地处理在GML文档上进行的值查询和空间分析操作.     

基于人工免疫系统的数据简化

针对数据简化中的实例选择问题,基于抗体克隆选择学说提出了一种免疫克隆数据简化算法.利用马尔可夫理论证明了该算法能以概率1 收敛.通过对7 个具有代表性的标准UCI 数据集的简化实验证明了该算法的有效性.通过实验分析了权值参数λ的取值变化对算法性能的影响,确定了其最佳取值区间.针对海量数据集简化时算法收敛较慢的问题,引入分层编码策略.通过对7 个大规模及海量数据集的简化实验表明了在进化代数不变的情况下,新的编码方式能够极大地提高算法的收敛速度,得到更为理想的结果.通过对Letter 和DNA两个数据集的实验给出了分层编码中层数t的最佳取值区间.     

基于抽象域和数值熵协同的数值程序分析

在软件日益丰富的信息时代,程序的正确性验证问题需要深入地研究。提出了基于抽象解释和数值熵协同的数值程序正确性分析方法。利用抽象解释理论框架对数值程序进行抽象解释分析,提取不变量的抽象域区间;在抽象域区间上进行数值熵运算;运行程序获取数值变量的实际取值,计算数值熵;将抽象域区间数值熵和实际数值熵信息进行对比分析,准确地判断程序的正确性等性质。单纯的抽象解释分析只可以近似得到数值变量的取值范围,而引入数值熵算法,在取值范围的基础上对程序静态分析的准确性进一步检验,同时也做到了对程序的正确性验证。通过C语言程序实例,对抽象解释基础上的熵值分析方法进行了验证,证明了该分析方法的可行性和正确性。     

两层传感网隐私保护的不完全数据Skyline查询协议

感知节点感知数据易受外界环境影响,使得不完全数据广泛存在于无线传感器网络中,且感知数据面临严重的隐私威胁。针对两层传感器网络不完全数据查询过程中存在的隐私泄露问题,提出一种基于置换和桶技术的两层传感器网络隐私保护的不完全数据Skyline查询协议（PPIS）。为了实现对不完全数据的Skyline查询,PPIS将缺失属性值置换为数据域的上界值,并将不完全数据映射到桶中;为了保证数据隐私性,PPIS首先将桶区间转化为前缀编码,然后将前缀编码加载到Bloom过滤器中,保证存储节点在无需数据和桶区间明文的前提下执行查询处理;为了保证查询结果的完整性,PPIS采用Merkle哈希树构造完整性验证编码,实现对查询结果的完整性验证。理论分析和仿真实验验证了PPIS的安全性和有效性,与现有隐私保护Skyline查询协议SMQ和SSQ相比,PPIS通信能耗节省了70%以上。     

一种新的基于区域的动态XML编码方案

在区间编码和前缀编码的基础上,提出了一种区间编码的改进的编码方案RSD（region-string-dinary）,采用二进制编码策略,可顺序友好的插入位串;提出了新的位串插入算法,可生成有序位串,且不影响已经存在位串的顺序。描述了R S D中节点间结构关系的判定方法。该二进制编码方案和位串插入算法是有效进行查询处理和避免更新时重新编码的基础。实验表明R S D使得更新时完全可避免重新编码,显示出合理的查询处理性能。     

两层传感网中能量高效的隐私保护范围查询方法

具有隐私保护能力的范围查询处理方法是当前无线传感器网络（wireless sensor networks , WSNs）数据管理应用技术中具有挑战性的研究内容。针对2层传感器网络环境,提出了一种能量高效的隐私保护范围查询处理方法（energy‐efficient and privacy‐preserving range query ,EPRQ ）。在数据存储阶段,感知节点对其采集的数据进行加密处理,并利用0‐1编码和 Hash消息身份认证编码机制计算各采集数据的最小化比较因子,然后将密文和编码数据上传至存储节点。在查询处理阶段,基站计算用户查询的目标范围区间的比较因子,并作为查询指令发送给存储节点;再由存储节点利用0‐1编码验证机制的数值比较特性,实现无需明文数值参与下的数据大小比较,进而确定查询结果密文数据集,并返回基站;基站解密密文数据,获得最终的查询结果。理论分析和实验结果表明,该方法能够实现对感知数据、查询结果和目标范围区间的隐私保护,且与现有方法相比具有更高的能耗效率。     

一种支持动态插入的XML文档树编码IFED

XML文档树编码用来标识节点在文档树中的位置,XML文档查询算法通常通过编码来判断节点的祖先后代和兄弟关系,编码的好坏对查询效率影响很大.目前提出的编码主要分为两大类:区间编码和前缀编码,最近提出的扩展的前缀编码-Extended Dewey,由于通过单个节点的编码能够得到节点对应的路径,所以它支持有效的查询,但不支持动态插入.提出了一种新的XML文档树编码-IFED,它由Extended Dewey编码改进而来,既支持高效地查询,又支持动态插入.     

一种新的XML数据编码方案

如何对XML文档进行高效的查询,特别是包含查询处理,越来越受到研究界的关注。一种好的XML文档树编码方案可以很好地支持在XML文档上进行包含查询。为了加快XML数据的处理,利用完全二叉树的特性,提出了一种新的编码方案BTC。与区间编码和前缀编码相比,该编码具有简单和长度短的优点,实践证明该编码是有效的。     

机械公差数据库查询系统的设计与实现

本文通过运用数据库和程序设计软件，实现了机械公差与配合的计算机辅助查询；并且介绍了公差与配合查询、基孔（轴）制常用、优先配合的查询与选择等界面的形成及其实现过程，从而达到了提高产品设计和编制工艺文件工作效率的目的。[编者按]     

一种关于数据流区间Disjoint查询的快速处理算法

在关于数据流子序列相似性匹配的研究中,Disjoint查询是很重要的一类,在传感网络和数据挖掘等方面都发挥着非常重要的作用.但现有的研究并没有关注到定长区间上的Disjoint查询问题.直接对每个区间内成员使用Spring算法是解决该问题的NAIVE算法,但是因为NAIVE算法不具有增量计算的特点,所以存在冗余运算.针对NAIVE算法冗余运算的处理问题,提出了边界路径技术.边界路径技术很好地使用了Spring算法在相邻前一区间上的执行结果,使得Spring算法无需对当前区间上每个成员执行,就可以得到Disjoint查询在该区间的查询结果.使用该技术对NAIVE算法进行改造,设计并实现了快速区间Disjoint查询处理算法(fast section Disjoint query processing algorithm,FSDQ),该算法具有增量计算的特点.实验证明FSDQ算法可以有效减少NAIVE算法所具有的冗余运算,是处理数据流上区间Disjoint查询的有效方法.     

对左兄弟／右兄弟结构连接算法的研究与改进

结合区间编码和结点模型映射方法提出一种用于关系数据库的扩展存储模式。通过按结点编码中的广度遍历序号建立聚集索引，实现左兄弟／右兄弟关系结构连接算法的改进。改进后的算法降低了内存空间的开销，缩小了列表的扫描范围，明显提高了查找匹配速度，达到了查询优化的目的。     

一种XML数据流小枝模式查询算法

针对传统XML文档小枝模式查询算法系统开销大的问题,提出一种XML数据流小枝模式查询算法。该算法结合SAX数据流解析技术,将层次关系队列结构应用于XML文档查询中,采用动态生成区间编码的方式,免除建立编码索引文件的步骤。实验结果表明,在对相关数据集进行查询时,该算法可减少I/O操作,缩短查询响应时间,提高查询效率。     

一种无线传感器网络中的多维K-NN查询优化算法

提出了一种基于过滤器的无线传感器网络多维K-NN查询优化算法PREDICTOR.过滤器是设置在节点端的取值分布区间,用来屏蔽节点发送属于区间内的数据,从而节省节点能耗.在服务器端保存有各节点的历史样本数据,根据K-NN查询请求和样本数据的分布范围为节点定义过滤器.提出了3种优化策略:(1) 过滤器覆盖区间大小分配策略的动态调整方法,使得进入最终查询结果可能性小的节点拥有较大的覆盖区间;(2) 节点间过滤器共享方法,使得历史样本数据相近的节点使用相同的过滤器;(3) 过滤器压缩传输方法,减少为不同K-NN查询更新过滤器的代价.通过实验评价,验证了PREDICTOR算法的能量有效性,与朴素算法相比,极大地降低了数据传输量.     

基于互关联后继树的XML索引技术

提出了一种新的根树节点编码方法——基于叶序区间的节点编码(LOINS)．编码方法只需对根树后序遍历一次即可完成,能实现常数时间内对任意两个树节点间前后代关系的判断．同时,结合互关联后继树模型(IRST)的标引性、可压缩性等特点,提出基于IRST的根树索引模型Ist3aRTI-Ⅰ,及对该模型空间优化的索引模型IstBaRTI-Ⅱ．IsBaRTI-Ⅰ,Ⅱ采用树节点名称(标签)及其在根树(XML文档树)中的出现计数索引节点间的父子关系和节点叶序区间编码,实现索引结构和节点编码的相互统一,IsBaRTI-Ⅰ,Ⅱ索引建立时间、空间代价小,可快速查询满足XPath表达式在XML文档树中的节点序列和路径．     

区间约束及其代数查询语言

提出了区间约束和基于区间约束的代数查询语言。区间约束与密序约束相经,增加了简单的加减运算,具有更强的描述能力,同时区间约束元组有简洁,唯一的规范区间表示,文中给出了计算区间约束的规范区间表示的算法,针对区间约束关系,定义了基本代数操作的语法及语义,研究了代数查询语言,并证明代数约束查询语言满足封闭性,最后讨论了区间约束的实现与应用。     

脉冲神经网络图像分割的编码方法

针对脉冲神经网络图像分割中的脉冲编码问题,基于Time-to-First-Spike编码策略提出2种编码方式：线性编码和非线性编码。线性编码方法采用从图像像素值到神经元脉冲发放时间的线性函数对应关系,而非线性编码方法采用Sigmoid函数的对应关系。应用2种方法对图像进行分割,实验结果表明,非线性编码方法的分割结果优于线性编码方法,分割图像具有更大的香农熵值,并且非线性编码方法在图像分割时具有更大的取值区间,更容易对参数进行选择,取得最佳的图像分割结果。