基于2-hop优化的子图模式匹配算法

讨论大图上有效可达标记2-hop编码,及其构造的图结构信息数据结构在判定两点之间可达性的高效性,基于这些高效结构,提出一种基于栈的DAG全局图模式匹配算法,该算法结合了栈在匹配过程中线性空间开销的优势。实验结果表明,相对于目前主流的图模式匹配算法,该算法具有中间结果小,时间高效的优势。     

信息检索系统中通用查询类的设计

介绍了通用查询类的目标和概览以及辅助类和接口的构建,阐述了SqlQuery类关键方法的实现,提出了使用SqlQuery对象实现查询组件的方法。     

一种更新K-支配轮廓的算法*

k-支配轮廓查询技术在计算高维空间数据集时,解决了查询结果集合过大的问题,更有利于用户决策;然而,现有的算法都是针对静态k值设计的,不适合k值动态变化的情况。为了解决此问题,提出一种思路,即当k值改变以后,以现有的查询结果为基础,通过对可能发生身份变化的数据点进行判断,得到新的k-支配轮廓。在此基础上分别针对k值增大和k值减小这两种情况提出了相应的更新算法。通过理论分析和实验,算法能快速完成运算并返回正确查询结果。     

基于句法特征的冗长查询处理技术

将传统的“词袋”思想进行扩展, 把文档看成由句子组成的“句袋”, 通过依存句法分析得到“句袋”与查询中词间的依存关系。利用两者依存关系的匹配程度, 计算冗长查询和初次检索返回文档之间的相似度, 对初始检索结果进行重排序。通过在TREC标准数据集上的实验, 证明该方法能够较有效地解决查询的冗长导致偏离查询主题和低召回率情况下相关文档排序靠后的问题。特别是对于低召回率的情况, 检索结果的MAP值和P@N都有显著提高。     

Skyline查询应用扩展及其优化算法

Skyline查询处理是近年来信息管理和数据库交叉学科的一个研究重点和热点, 其广泛应用于多标准决策支持系统、城市导航系统、数据挖掘和可视化以及信息推荐系统等领域. 然而, 在实际的联机查询应用中, skyline查询的结果具有固定和多用户共享特性, 因此, 随着时间的推进, 查询结果的可选择性逐步降低, 从而最终导致查询结果无法满足用户的需求. 为此, 提出k-quasi skyline查询, 来丰富传统skyline查询的结果集, 并与目前主流关系数据库产品无缝集成.为了提高任意维空间上k-quasi skyline查询的效率, 设计了基于正规格索引的计算方法EARG (efficient algorithm based on regular grid).EARG算法通过格之间的支配关系来缩减对象间的比较次数, 从而显著降低k-quasi skyline计算的时间开销.理论分析和实验结果表明, EARG算法具有有效性和实用性.     

基于MPB-Tree索引的空间数据多关键词模糊查询算法研究

随着具有定位功能的智能设备的大量使用,产生出海量的空间数据,每条数据中包含的信息越来越多,而以往的查询算法多数仅对单个关键词进行查询,已难以满足用户更为个性化的需求.为此,本文提出一种多空间关键词模糊查询算法,在该算法中,将以往的两维空间距离计算转化为莫顿码匹配提升查询效率,且与模糊查询算法融合支持查询的容错.实验结果表明,该算法的效率及准确性较以往查询算法有较大提高.     

MapReduce模型下基于R树索引的Skyline查询算法

提出一种MapReduce并行计算模型下基于R树索引的Skyline查询算法, 解决了海量空间数据集下执行Skyline查询效率低的问题. 通过建立R树索引实现空间数据不同粒度的范围剪枝, 有效降低了分布式Skyline查询需扫描的数据规模, 提高了在MapReduce模型下Skyline查询的执行效率. 在不同数据分布下进行对比实验的结果表明, 该方法比已有算法在执行效率上更具优势.     

一种基于约束的半监督聚类查询扩展方法

针对伪相关反馈模型反馈文档信息质量差和扩展词选择不适产生的漂移现象等问题,提出了一种基于约束的半监督聚类查询扩展方法。该方法对初检结果的前k个文档进行人工标注,分成相关文档与不相关文档两类;并利用一种半监督聚类算法对初检结果的前”个文档进行分析,提取出与查询相关的文档作为反馈文档。该方法通过对少量标注文档与查询相关性的学习,能够较准确地估计出大量未知文档与查询的相关性,提高反馈文档的质量,从而有效提高检索的查全率和查准率。实验结果表明,该方法比传统的伪相关反馈和基于无监督聚类的伪相关反馈有更优的检索性能。     

Performance Prediction for Performance-Sensitive Queries Based on Algorithmic Complexity

Performance predictions for database queries allow service providers to determine what resources are needed to ensure their performance. Cost-based or rule-based approaches have been proposed to optimize database query execution plans. However, Virtual Machine （VM）-based database services have little or no sharing of resources or interactions between applications hosted on shared infrastructures. Neither providers nor users have the right combination of visibility/access/expertise to perform proper tuning and provisioning. This paper presents a performance prediction model for query execution time estimates based on the query complexity for various data sizes. The user query execution time is a combination of five basic operator complexities： O（1）, O（log（n））, O（n）, O（nlog（n））, and O（n2）. Moreover, tests indicate that not all queries are equally important for performance prediction. As such, this paper illustrates a performance-sensitive query locating process on three benchmarks： RUBiS, RUBBoS, and TPC-W. A key observation is that performance-sensitive queries are only a small proportion （20%） of the application query set. Evaluation of the performance model on the TPC-W benchmark shows that the query complexity in a real life scenario has an average prediction error rate of less than 10% which demonstrates the effectiveness of this predictive model.     

基于地理位置服务的商圈建模方法

针对基于地理位置查询市场的巨大需求,提出一种基于商圈地理位置的建模方法.首先对地理位置查询进行组件拆分与类别划分,形成建模的最小构件,然后采用参数化方法对地理位置定位,通过输入参数值获得符合查询结果的商圈信息,辅助确定用户需要的地理位置,最后采用高德地图的API（Application Progranl Interface）接口实现.