基于数字签名与Trie的保序子矩阵约束查询

目前,基因芯片技术飞速发展,促使生物学家积累了大量的不同实验条件下的基因表达数据.事实证明,基因芯片数据分析在理解基因功能、基因调控和分子生命过程中发挥着重要作用.保序子矩阵(order-preserving submatrix,简称OPSM)是基因芯片数据分析技术中的一种有效模型,其可以发现在部分基因和不同实验条件下具有相同表达趋势的聚类.在分析基因表达机理的过程中,OPSM的检索无疑节省了生物学家的时间与精力.目前,OPSM的查询主要是基于关键词的检索方法,但是分析者对结果具有微弱的控制力.通常,分析者所能决定的临时的参数设置往往偏离其领域知识,致使检索结果与真实想要的结果相去甚远.为了解决上述问题,提出两类基于数字签名与Trie的OPSM索引与约束查询方法.在真实数据上进行了大量的实验,实验结果表明,所提出的方法具有良好的有效性与可扩展性.

差分隐私的查询一致性约束研究

针对差分隐私直方图发布中区间查询的不一致问题,研究已有需迭代调整的局部最优线性无偏估计算法LBLUE,提出一种不需迭代且满足一致性约束查询的CA算法。通过对1棵添加Laplace噪声的满k-叉区间树进行一致性调整:先利用TDICE算法进行自顶向下的不一致估计,再利用BUCE算法进行自底向上的一致性估计,得到满足一致性约束查询的差分隐私满k-叉区间树,遍历后发布满足一致性约束查询的直方图数据。经过证明和实验分析,一致性调整后的查询区间满足一致性约束查询,且精确度优于Boost-2算法和LBLUE算法的,同时算法的时间效率高于LBLUE算法的。

空间数据库中约束K最接近对查询

定义了满足空间约束的 K 最接近对查询,该查询检索两个数据集在给定约束区域中的 K 最接近对。在空间数据库中,对采用 R 树类型索引存储的数据集给出了三个查询处理算法。其中两阶段的 RJ 和 JR 算法采用了变换范围查询和最接近对查询执行顺序的策略。单阶段基于堆的 SPH 算法采用了最好优先的策略,并利用给出的裁减规则、更新规则和访问顺序规则来提高查询处理效率。实验表明 SPH 具有较好的适用性和性能。

大规模图上标签集约束路径的集合查询

图数据模型被广泛用于社交网络、生物技术、语义网络等开放、异构环境下的数据建模。标签集约束路径查询是基本路径查询问题之一,因其具有路径描述的灵活性而受到目前研究的重视。目前重点研究布尔查询问题:判断给定顶点对间是否有满足标签集约束的路径,返回是或否。现研究布尔查询问题的正交问题,称为集合查询问题:给定标签约束集,返回满足标签集约束可达的顶点对。集合查询问题面临两个困难:1)简单地将集合查询问题简化为布尔查询问题的迭代会陷入穷举困境;2)压缩传递闭包的生成树结构虽然能够有效地回答布尔查询问题,但是,这种压缩结构不能有效支持集合查询,因为集合查询需要搜索满足约束连通的所有顶点对。为此,继续采用生成树来压缩标签路径传递闭包,用倒排索引表来加快集合查询所导致的搜索,并进一步给出两个优化算法。在大规模的数据集上的测试表明,本方法在时间和空间效率方面都具有优势。

一种高效的权值约束可达性查询处理算法

基于权值约束的可达性查询是可达性查询的一种,用于回答在加权图上,给定两个查询的顶点之间是否存在一条路径,该路径上所有边的权值都满足给定的权值约束。现有的基于权值约束可达性查询的相关算法尽管查询响应时间较快,但是其构建的索引规模太大,无法在内存有限的情况下,处理规模较大的数据图。本文提出一种基于顶点的度构建2-hop索引的算法,来支持在有限的内存内高效地处理大规模数据图上的权值约束可达性查询。实验通过多个数据集证明,该方法能够有效降低索引的规模。

基于参考节点嵌入的图可达性查询

针对k步可达性查询算法无法解决带距离约束的图可达性查询问题,提出基于参考节点嵌入的图可达性查询算法。首先,从所有节点中选出极少数有代表性的全局参考节点,预先计算所有节点与全局参考节点之间的最短路径距离;然后,采用最短路径树和范围最小值查询技术求得局部参考节点;接着,利用三角不等式关系得到查询点对距离范围;最后,根据查询条件中的距离值与查询点对距离范围上、下限值的大小关系,可快速得出可达性结论。针对社会关系网络和公路网络数据,将所提算法与Dijkstra算法、K-Reach算法进行实验对比测试。相较于K-Reach算法,其索引建立时间小4个数量级,其索引规模小2个数量级;相较于Dijkstra算法,在公路网络和社会关系网络中,直接得出可达性结论的比例分别为92%和78.6%,其查询时间大大缩短,分别降低了95.5%和92%。实验结果表明:所提算法能够通过使用较小的索引开销,实现在线查询计算复杂度的降低,可很好地解决既适用于有权图又适用于无权图带距离约束的可达性查询问题。

基于MapReduce的OCL的并行查询方法

在单机环境下,基于单节点的OCL(Object Constraint Language)查询方法已经无法高效地完成大规模的查询任务。为了应对大量数据带来的挑战,提高OCL查询的速度,提出一种基于MapReduce的OCL并行查询方法 OPQM(OCL Parallel Query Method)。这种方法通过提取OCL对象属性集合,实现从OCL规则库查询到OCL对象属性查询的转化,并利用MapReduce实现对象属性并行查询,缩短了OCL查询时间。

异质信息网络的互信息最大化社区搜索

针对现有社区搜索方法难以处理复杂多样的搜索要求及在高维稀疏的异质信息网络(HINs)中难以融合网络结构和节点属性来度量节点间相关性的不足,提出异质信息网络互信息最大化社区搜索问题,给出互信息最大化的社区定义,设计相应的搜索方法 (互信息最大化社区搜索,CSMIM).将用户的搜索要求定义为查询约束,利用带查询约束的深度图互信息最大化(QC-DGI)模型融合网络结构、语义和节点属性信息获得节点嵌入,有效地计算节点间的互信息.根据给定的查询信息,利用互信息最大化准则搜索目标社区.为了提高搜索结果的准确率,提出基于用户反馈的优化策略,实现互信息从全局到局部的个性化计算.在真实数据集上进行大量实验,实验结果表明所提方法能够有效地根据搜索要求挖掘出给定节点所在的社区,相比具有代表性的基线方法有更高的准确率.