PSP：一种高效的偏序域上skyline查询处理方法

为解决偏序域上的skyline查询问题,本文提出一种高效的偏序域上的skyline查询处理方法,来满足人们对查询效率日益增长的需求.首先,为提高偏序域上skyline的查询效率,将倒排索引引入skyline查询,提出一种基于倒排的索引结构.其次,提出基础算法(Basic Partially-ordered Skyline Processing based on inverted index,PSP_B),PSP_B包含两个阶段:第一阶段,能够通过映射将偏序域转化成全序域,并建立倒排索引;第二阶段,通过倒排索引提前找到扫描结束点,得到最终的skyline结果.再次,在PSP_B的基础上,进一步提出优化算法(Improved Partially-ordered Skyline Processing based on inverted index,PSP_I).PSP_I通过先分组再建索引的方法能够进一步提高计算效率.最后,用大量的实验证明本文所提算法的正确性和高效性.     

基于数据广播的空间关键字查询处理

为了解决无线广播环境下空间关键字查询的问题,研究广播环境下空间关键字k近邻查询处理(BkSKQ),设计了一种结合kd树、倒排位图和(1,m)索引机制的空间关键字索引(ISKW)结构,以有效地组织对象的关键字信息、位置信息以及索引信息.该索引结构为客户的查询处理提供有效的指导,使得他们尽可能只下载查询处理所必须的数据信息.在ISKW索引结构的基础上,提出了BkSKQ查询处理算法.最后,通过模拟实验验证了提出的索引结构和算法的性能,实验结果表明所提出方法在访问时间和调谐时间上明显优于基于IR树的方法(BIRM).     

地理社交网中基于范围的星型组查询

针对星型组查询只考虑了用户的位置信息和朋友关系,而没有考虑用户的偏好信息,使得推荐质量不高的问题,本文提出一种基于范围的星型组查询算法(m SG),同时考虑用户的社交关系、文本信息和当前位置信息,在给定范围为用户返回k个得分最高的星型组。为了迅速查找中心点用户,提出带倒排表的网格索引结构。为中心点用户更快速地查找朋友,提出了社交关系和文本信息混合索引结构。最后,通过实验表明,利用所提索引结构减少了查询算法的运行时间。     

基于Term-Query-URL异构信息网络的查询推荐

查询推荐是一种帮助搜索引擎更好的理解用户检索需求的方法.基于查询的上下文片段训练词汇和查询之间的语义关系,同时结合查询和URL的点击图以及查询中的序列行为构建Term-Query-URL异构信息网络,采用重启动随机游走(Random Walk with Restart,RWR)进行查询推荐.综合利用语义信息和日志信息,提高了稀疏查询的推荐效果.基于概率语言模型构造查询的词汇向量,可以为新的查询进行查询推荐.在大规模商业搜索引擎查询日志上的实验表明本文方法相比传统的查询推荐方法性能提升约为3%~10%.     

基于改进NSGA-Ⅲ的文本空间树聚类算法

构建倒排文本空间索引树(IR)分裂聚类多目标模型,对非支配排序遗传算法(NSGA-Ⅲ)的求解过程进行改进,提出一种基于先验初始种群策略的非支配排序遗传算法(PIPS-NSGA-Ⅲ),使其更适应于倒排文本空间对象分裂聚类问题的求解.通过PIPS-NSGA-Ⅲ算法寻求对象最小包围矩形(MBR)之间的重叠与覆盖面积、对象群间平均距离以及语义相似度等目标的最优前端解.通过对比PIPS-NSGA-Ⅲ,NSGA-Ⅱ,NSGA-Ⅲ和SPEA-Ⅱ进化多目标算法,从对象分类时间、效率、查询时间和准确度等多个方面来评估算法的优劣.实验结果表明:PIPS-NSGA-Ⅲ算法对文本空间对象聚类分裂具有较高的效率;相对于简化传统R树(STR树)与R树空间索引结构,基于改进NSGA-Ⅲ文本空间索引的平均查询时间减少24.8%,平均准确度提高3.75%.     

基于时空相关的传感器网络汇聚查询算法

减少网络中的数据传输量是传感器网络节约能量、延长网络生命的重要方法.提出一种基于时空相关的传感器网络汇聚查询算法STCAQ.在STCAQ中,首先通过基于时间相关的预测算法对网络中节点采样数据进行汇聚;然后依据节点采样数据汇聚结果,通过基于空间相关判定算法查询空间相关区域信息.仿真结果表明,STCAQ在能量消耗、查询质量和网络数据量等方面优于ESA算法.     

一种社交网络环境下并行短文本查询算法

随着移动社交网络的迅速发展,如何从海量带有时间属性和地理位置属性的短文本信息中快速查询到有效信息具有重要意义.社交网络环境下传统短文本查询算法忽略时间维度,并且在海量数据下无法满足用户快速响应的需求.针对以上问题,提出一种社交网络环境下并行短文本查询算法.提出的算法设计了基于MapReduce模型下的查询框架,该框架使用了基于滑动窗口下的多版本时空索引(MVSTR-tree),保证了查询过程中融合了时间和空间属性,实现了对海量数据高效查询的目标.最后,通过真实数据集的实验证明该算法能有效缩短查询时间.     

基于位置的web搜索索引研究

针对基于位置的web搜索需要将网页中位置信息和文本信息相结合进行索引的应用需求,提出了先倒排表再R-tree索引和先R-tree再倒排表索引两种混合索引结构,同时处理文本和位置信息.大规模真实数据集上的实验表明,这两种方法在查询效率上明显优于已有的倒排表和R-tree相互独立的索引模式.     

一种建立在对客户端浏览历史进行LDA建模基础上的个性化查询推荐算法

现代搜索引擎普遍采用简单的关键词形式来表达查询,这为用户带来便利的同时也增加了准确获取信息的难度.搜索引擎很难基于少量的几个关键词准确捕捉用户的信息需求.查询推荐作为缓解上述问题的关键技术,已经开始应用于目前主流的搜索引擎.然而,绝大多数现有的查询推荐技术基于群体智慧,以搜索引擎日志为数据源,从中挖掘用户群体在构造查询方面的习性及查询之间的语义关联性,未考虑不同用户个性化的信息喜好,而且在搜索引擎服务器端进行查询推荐计算也会影响搜索引擎的响应效率和查询吞吐率.为此,本文提出一种运行于客户端的个性化查询推荐策略,该策略以用户浏览历史为数据源,采用LDA模型,并从中学习用户的信息喜好,在此基础上利用原始查询被主题模型生成的概率确定用户的查询意图,以词条与查询意图之间的关联来度量词条作为扩展查询被推荐的强度,最后选择Top N强度最强的词条作为查询推荐的结果.以人工标注的测试数据对本文所提出的算法进行了实验验证,结果表明,该算法在推荐扩展查询的准确率方面明显优于单纯基于词条与原始查询语义相关的方法     

一种面向XML数据的SLCA求解算法

针对现有方法计算SLCA语义时存在冗余计算问题,提出了一种基于列存储的倒排索引,并结合哈希查找,以自顶向下的方式查询处理的算法TDCOL-HS,来避免现有算法"公共祖先重复处理"的问题。算法以最短倒排表作为处理对象,将检测给定结点是否包含其他关键字的操作转化为哈希查找操作,其时间复杂度为×1,最后通过比较各种指标,从不同角度对算法的性能进行了验证.     

一种实时有效的蜂群模式挖掘算法

针对实时相关运动模式挖掘应用的需求,提出了一种实时地发现关闭蜂群模式的簇重组算法(CLUR).该算法维护一个候选蜂群模式列表,在每个时间戳采用基于密度的聚类算法对移动目标进行聚类,根据聚类结果组合所有的最大移动目标集,记录相应的时间集,然后构建候选蜂群模式,并更新到候选列表.算法给出了三种更新规则和一种插入规则,用于实现候选蜂群模式列表的更新,同时降低了候选列表的冗余度,提高了算法的效率.在每个时间戳结束时可通过关闭检测规则实时地发现当前时刻的关闭蜂群模式.在合成数据上的综合实验验证了CLUR算法的正确性、实时性和高效性,CLUR算法适用于实时相关运动模式挖掘系统.     

用互关联后继树模型实现一个局部相似性比对算法

对基因数据库的一种常见操作是找到与待查询序列相似的序列.目前常使用的是BLAST算法,但是这种启发式算法有时会漏解.如果使用精确匹配算法,例如Smith-Waterman(S-W)算法,计算代价又会太大.OASIS算法是一种高效并且精确的生物序列局部相似性比对算法,而且互关联后继树模型的空间效率很高,因此使用互关联后继树实现了OASIS,并命名为OASISirst算法,其比对结果和OASIS一样按照得分降序排列,并且当目标序列和查询序列均较长时,时间优势明显.     

一种改进的SLCA语义查询算法

在XML关键字查询处理中,寻找最小最低公共祖先SLCA（Smallest Lowest Common Ancestor）是一个重要问题.分析了基于SLCA语义查询处理算法的特点,在关键字和Dewey编码的倒排索引的基础上,利用栈结构实现了SLCA算法.     

一种基于混沌理论的数据流连续聚集查询预测算法

为了有效地预测聚集查询的未来聚集值,提出了一种基于混沌理论的数据流连续聚集查询预测未来聚集值算法——CSPA算法.数据流看作是以数据到达时间为序的一个时间序列,借鉴传统时间序列分析技术探讨了连续聚集查询的未来聚集值预测问题,但由于数据流序列与传统时间序列在时间间隔和数据集的处理上存在很大差别,于是采用流滑动窗口技术加以处理.其次,针对目前数据流聚集查询预测领域已有的一些研究结果都未考虑流数据内在的复杂非线性动力学特征对预测的影响问题,该算法又利用了混沌理论中的局域预测思想解决了这一不足.实验结果表明,利用该算法进行预测具有很好的准确性.     

基于关键词的RDF数据查询方法

在建立关键词倒排索引和路径索引的基础上,提出一个利用量化均衡规则和等距规则的启发式查询算法,并按照查询结果的大小排序返回最相关的前k个结果.通过建模RDF数据为RDF句子图,将文本信息封装到句子节点,同时将查询结果建模为包括所有查询关键词并且叶节点是关键词节点的无根树,将关键词查询问题转化为斯坦纳树问题.假设RDF句子图包括n个节点,最坏情况下索引占用的空间是3n2.假设关键词节点数为k,查询算法的时间复杂度为O(kn).该方法不需要依赖RDF数据的模式信息,支持对数据中的属性和关系名进行关键词查询.实验证明该方法能够快速而有效地实现RDF数据的关键词查询.     

基于小波和动态时间弯曲的时间序列相似匹配

提出了一种基于小波和动态时间弯曲(DTW)距离的时间序列索引和相似匹配方法. 该方法采用小波变换进行数据降维,利用R·-tree建立多维索引结构. 给出了查询序列的DTW距离边界和其在小波空间的查询超矩形的计算方法,从而将原始空间的基于DTW距离的相似匹配转换为小波空间基于欧氏距离的相似匹配. 证明了此匹配方法不会产生漏报,给出了基于DTW距离的范围查询算法和近邻查询算法. 实验结果表明该方法具有较高匹配精度和其较低的计算代价.     

基于中间商品兴趣度加权的内容推荐算法

内容推荐算法是在电子商务网站中应用比较广泛的推荐技术之一,主要针对商品之间属性相似度和用户对商品兴趣度建模.但传统的内容推荐算法不能及时反映用户对商品兴趣度的时间变化,基于这点提出一种基于中间商品兴趣度加权的内容推荐算法.改进算法增加了兴趣度时间权重函数和商品时间权重函数,可以提高商品推荐准确率,仿真试验结果证明该算法是有效的.     

一种基于XML前缀编码的路径查询

为了解决XML文档树子结点过多时前缀编码长度增加的问题,提出一种改进的XML前缀编码——IPE编码.基于IPE编码,结合倒排索引表,给出XPath路径查询算法,可以有效地提高XML文档的查询速度.     

基于多粒度Top-k查询的流式数据事件获取方法

流式数据中事件的查询及获取是研究流式数据各类操作的基础.现有流式数据系统中的事件查询只针对流中的异常数据点进行查询,而在实际情况下,流式数据中的事件多为一段连续时间的异常,包含时间、空间位置等多种信息,因此,传统的阈值查询方法无法从不同的时间及空间角度对事件进行全面分析,查询准确性极低,导致无法获取事件的全部信息.针对这些问题,本文提出一种基于多粒度Top-k查询的流式数据事件获取方法.该方法首先在监测区域内构建基于投影分区的区域监测簇;在此基础上,提出一种改进的多粒度空间Top-k查询方法对点进行查询,获取异常事件发生的空间位置信息;其次,基于事件峰谷点信息,对流式数据进行时间多粒度Top-k查询,找出异常事件的触发点和终止点,从而获得事件的完整信息.实验表明,本文提出的方法在系统资源开销、查询效率等方面均具有很大优势.     

面向推荐系统的多目标决策优化算法

针对推荐系统利用多目标决策技术进行位置信息的查询与推荐时,由于查询者位置的移动和空间障碍物的位置变化导致传统多目标决策技术的查询效率较低的问题,提出了一种基于范围的障碍空间连续Skyline查询算法。首先,根据静态Skyline点的特征对由空间数据对象信息组成的初始数据集进行约减;然后,根据障碍空间中查询者的位置移动的特点构建距离相交模型,利用距离相交模型和数据对象的属性提出了剪枝策略,再根据剪枝策略过滤掉当查询者的位置移动时对查询结果无影响的数据对象,从而精减了冗余数据,得到过滤后的候选数据集;最后,根据数据对象的非空间属性和相互间的支配关系特征得出影响候选数据集的事件,利用影响候选数据集的事件再对候选数据集进行精炼计算,从而减少了冗余计算,查询出当前时刻的结果集。理论研究与实验结果表明：所提算法在查询者位置移动和空间障碍物位置变化时,能提升多目标决策技术的查询效率;相对传统对比算法,在数据集规模、障碍物数量、查询范围增大时,所提查询算法的平均效率提升约13%;针对多维度数据信息的查询,所提查询算法的平均效率提高了约11%。