基于关系数据库的位置相关查询处理

随着无线通信技术以及全球定位技术的发展,位置相关的查询处理及基于位置的信息服务技术已经成为一个热点研究领域,作为支持位置相关查询的一项关键技术,位置相关数据的处理也正在引起人们日益广泛的关注,对位置相关数据处理中的关键技术进行了分析,提出了一种基于关系数据库的位置相关数据的存储及表示方法,同时提出了一种可变粒度格栅索引方法用于对位置相关数据的数据区域进行索引,在此基础上,研究了相应的查询处理算法,为了测试相应算法的性能,设计并实现了一个原型系统,实验结果表明,所提出的方法具有灵活的表示能力、快捷的查询性能以及良好的可扩充性。     

数据广播环境下实时查询处理

现有的实时数据广播研究中,只考虑了具有截止期约束的单个数据请求的调度问题,而支持实时查询处理的数据广播技术尚未得到足够的关注。该文研究在on-demand数据广播环境下,如何有效地处理实时查询问题,提出一种新的数据调度算法(QSA)。通过仿真实验与目前最为有效的数据请求调度算法SIN进行了比较,结果显示QSA具有更低的错过截止期比率,在最好的情况下,QSA比SIN降低了17.45%。     

基于位置范围的道路网skyline查询

随着无线通信和定位技术的发展,道路网skyline查询在基于位置的服务等方面越来越重要。考虑到现今道路网中位置隐私保护和定位设备的精度问题,用户在道路网上的位置通常用一个范围来表示。但是,已有的道路网skyline研究都是基于单一查询点。针对这一问题,研究了一种新的查询——基于位置范围的道路网skyline查询(RNS),提出了一种基于边界点替换的有效查询处理算法。另外,针对已有的道路网skyline查询中复杂的道路网距离计算对查询效率的影响问题,通过计算兴趣点在道路网上的有效skyline路段,将其与道路网信息融合,建立了道路网skyline模型。基于该模型设计了一种能有效支持RNS查询的道路网skyline索引SSR-tree,提出了基于索引的RNS查询处理算法。通过大量实验验证了所提方法的有效性,并比较了基于索引的算法在查询效率和精度上的提高。     

已知时间的空间文本skyline查询

现有的空间文本skyline查询忽略了地理空间对象的时间信息;考虑到时间信息对应用的重要性;将时间信息应用到空间文本skyline查询中;提出了一种新的查询;即已知时间的空间文本skyline查询（Time-aware Spatial-Textual Skyline Query;TSTSQ）。TSTSQ中skyline对象的筛选依赖于三个条件:文本相关性、空间邻近和有效时间。分别设计了对象的空间文本相关性和时间文本相关性的计算函数;构建时空信息和文本信息的对象索引结构TKR-Tree;通过构造高效的裁剪策略实现了TSTSQ的查询算法。通过实验数据的分析和对比;验证了TSTSQ查询的有效性。     

基于垂直划分的隐私保护skyline查询

Skyline查询是一种重要的数据分析方法,在推荐系统中有着广泛的应用。近年来,随着隐私保护需求的不断增长,分布式数据集上的隐私保护skyline查询问题受到越来越多的关注。然而,现有的分布式数据集上的隐私保护skyline查询方案大多只适用于水平分布数据集,不能满足垂直分布数据集上的skyline查询需求。为此,深入研究了垂直分布式数据集上保护隐私的skyline查询问题,提出了一种基于保序加密的垂直分布数据集上的隐私保护skyline查询算法,可以在保护数据隐私的同时,有效支持skyline查询过程。理论分析证明了提出协议的正确性和安全性,并通过理论分析和模拟实验对协议运行效率进行了评估,结果显示新方案具有较高的运行效率。     

嵌入式移动数据库系统中的数据查询

数据库技术一直在随着计算的发展而不断进步,凡是有数据的地方,就要用到数据库来协助管理数据。本文介绍了位置相关查询优化和数据广播两种普遍用于移动数据库查询的方法,并结合移动数据库中的缓存技术,提出了嵌入式移动数据库的查询优化方法。     

On-Demand数据广播环境下实时有序查询处理

在On-Demand数据广播环境下,广播服务器基于用户发送的数据请求等信息进行调度决策来满足用户的数据访问需求。在很多实际应用中,用户的数据请求需要在一定时间段内得到满足,即数据请求是有截止期的。现有研究只考虑了具有截止期约束的单个数据请求的调度问题,而实时查询处理即用户以查询为单位依次发送多个数据请求的研究尚未得到足够的关注。本文重点研究了On-Demand数据广播环境下如何有效地处理实时有序查询这一问题。基于对该问题的分析,定义了一类新的调度问题ROBS并证明了ROBS的Off-Line版本是NP-Hard的;提出了一种新的考虑查询语义的On-Line调度算法OL-ROBS,该算法通过综合考虑数据请求个数、查询截止期和查询剩余数据请求个数来确定待广播数据项的优先级;为提高OL-ROBS的执行效率,设计了一种裁减算法,用以减少调度决策的搜索空间。模拟实验将OL-ROBS与目前最为有效的实时数据请求调度算法Sinθ-进行了比较,结果显示OL-ROBS具有更低的错过截止期比率。     

位置相关查询中基于最小访问代价的缓存替换方法

在位置相关查询（LDQ）中由于用户的移动性和数据的位置相关性,给缓存替换策略带来了新的挑战。在详细分析位置相关数据(LDD)的空间位置特性和几种典型的位置相关缓存替换策略的基础上,提出一种基于最小访问代价的缓存替换策略（PLAC）,一些重要的缓存替换因素如访问概率、更新频率、数据距离和有效范围等都包含在代价函数里,PLAC根据代价函数值的大小来决定被替换的数据,由此来保证有限缓存的最大使用率。通过实验对比,PLAC比其他位置相关缓存替换策略更为有效地提高了缓存命中率,缩短了查询平均响应时间。     

基于不确定数据的查询处理综述

不确定数据在一些重要应用领域中是固有存在的,如传感器网络和移动物体追踪。在不确定数据上使用传统的查询方法会使查询结果出现偏差,不能满足用户的需求。因此,基于不确定数据的查询处理受到了越来越多的关注。与在确定数据上查询不同,不确定数据上的研究工作将概率引入到数据模型中来衡量不确定对象成为结果集中元素的可能性。由于问题定义和数据模型的不同,不确定数据上的查询类型也多种多样。从问题定义、数据模型、剪枝策略和算法等角度,对基于不确定数据的范围查询、top-k查询以及skyline查询进行了介绍。     

无线数据广播环境下路网最近邻居节点的查询

针对大规模用户数量,首次提出结合无线数据广播技术,在路网环境中进行最近邻居节点查询.该方法使用基于Voronoi图的算法转化路网信息,将处理后的路网信息作为广播数据,不仅提高了用户的查询效率,还减少广播数据中的冗余信息.在数据调度上,采用Hilbert曲线对数据排序,从而保持广播数据的空间临近性.实验表明,上述方法在为用户提供高效查询的情况下有效减少了访问时间.     

一种分布式环境中的二分式多层网格skyline算法

skyline计算在数据挖掘、多标准决策和数据库可视化等领域有着非常重要的作用,这些年已经得到了广泛的关注,以往对于skyline查询的研究大多集中在处理集中的数据集上,即集中式skyline查询,已经得到了很多的研究成果。然而,实际情况是：相关数据几乎分散在几个不同的服务器上,因此在分布式环境中的skyline查询计算需要从各个服务器收集大量的数据;现有的在分布式环境中的skyline查询方法有两个主要问题：一是skyline查询的处理时间较慢;二是在网络中服务器之间传输了很多不必要的重叠数据。提出了一种二分式多层网格法（DMLG）,可以有效地处理在分布式环境中的skyline查询。该方法利用网格的方法,借鉴二分法,最大限度地减少了不必要的重叠数据传输,基于不同的数据集的实验表明,这种方法优于现有的方法。     

基于网格索引的数据流子空间概率轮廓查询

在数据流子空间上的连续概率轮廓查询(CPSQS)基础上,提出一种基于网格索引结构的概率轮廓查询算法。采用适合于子空间轮廓计算的网格索引结构,将数据空间划分成若干个格,利用格间的支配关系,减少对象之间的比较次数。同时挖掘全空间与子空间上格的概率上下界关系,设计有效的剪枝策略提高CPSQS算法的性能。理论分析和实验结果表 明,该算法能满足实际应用中用户的个性化查询要求,降低查询响应时间。     

Skyline查询处理数据立方体代数

维空间的Skyline查询处理技术是近年来数据库技术领域的一个研究重点和热点.目前所有的研究工作都是直接在原始数据表上执行关系查询代数操作来获得最终的结果集,然而,随着原始数据表的数据量和维目标个数的增大,这些研究工作将不再适用.基于此,首次研究Skyline集合上的查询代数操作,使得Skyline查询处理的输入数据来自于小规模的Skyline结果集,而非海量的原始数据表.并且,首次给出一个集成多维对象集合和该对象集合上的Skyline结果集的形式化模型,该模型适合目前Skyline查询计算的应用,并在该模型的实例上研究Skyline集合的查询代数操作.同时,给出查询代数体系的代价评估模型.实验表明,给出的数据模型和查询代数体系具有有效性和实用性.     

不确定数据流上的概率反轮廓查询处理

反轮廓查询在制定有效的市场决策方面具有重要的作用,随着数据流特征和不确定性的表现日益明显,不确定数据流上概率反轮廓查询已经成为一个新的研究课题.为了高效解决不确定数据流上概率反轮廓查询问题,首先,通过对实际应用需求进行分析,提出了不确定数据流上概率反轮廓查询的定义,并根据相关概念,提出了不确定数据流上概率反轮廓查询的索引模型;其次,通过对不确定数据流上概率反轮廓的性质进行深入分析,提出了一种新颖高效的基于R-tree的不确定数据流上概率反轮廓查询算法RT2RS,该算法运用了高效的剪枝策略,避免了大量的无效运算;最后,通过大量的仿真实验对RT2RS性能进行了验证.实验结果表明,RT2RS是解决不确定数据流上概率反轮廓查询的有效方法,大大减少了不确定数据流上概率反轮廓查询的运行时间,能够满足实际应用需求.     

数据仓库中雪花模式的Skyline-Join查询

Skyline查询能够有效地实现多目标最优化,而数据仓库中的OLAP也是针对多维数据进行分析,因此,针对Skyline查询在数据仓库中的应用,提出了数据仓库中雪花模式的Skyline-Join查询算法.该算法首先将子维表M-Join父维表,然后渐进选择式地对事实表和父维表进行连接.每次连接之前都对事实表进行分组和组内Skyline计算,删除组内非Skyline元组,这样可以减少许多不必要的连接操作,使得查询效率大大提高.通过实验证明,在事实表元组数量逐渐变大和维表个数逐渐增多的情况下,提出的算法比先Join后Skyline计算的naive算法效率上有明显改善.     

高效的Top-k相互Skyline查询算法

Top-k相互Skyline查询返回相互Skyline查询中的前k个对象.这种查询是数据分析者寻找有意义对象进行决策支持的一种重要直觉工具.然而,这种查询还没有引起研究社区足够的注意力.介绍了几种新颖的算法,包括Topk-TBBS,Topk-dMBBS,Topk-wMBBS.主要的思想是信息重用和高效的修剪策略.特别地,Topk-wMBBS算法由于完全重用了搜索中的节点信息,并利用了最好优先BF搜索策略.因而它获得了最好的性能.同时证明了该算法有最优的I/O访问效率.最后,使用了2个真实数据集和4个服从不同分布的合成数据集进行了集中实验.实验结果表明,提出的算法无论是变化参数k的大小、数据集的尺寸和Cache尺寸都是有效的,且具有很高的效率,尤其Topk-wMBBS具有最小的I/O访问次数.     

高效处理分布式数据流上skyline 持续查询算法

基于非共享策略,围绕着降低系统反应延迟与通信负荷的目标,提出了一种分两阶段渐进求解的分布式算法BOCS(based on the change of skyline),并对算法的关键实现环节,如协调站点与远程站点间的通信、skyline 增量的计算等进行了系统优化,使算法在通信负荷与反应延迟上达到了较好的综合性能.理论分析证明,在所有基于非共享策略的算法中,BOCS 算法通信最优.大量的对比实验结果也表明,所提出的算法高效、稳定且具有良好的可扩展性.     

不确定数据库中的阈值轮廓查询处理

传统轮廓查询算法都没有考虑不确定数据的特殊性质,因而不能直接应用到不确定数据应用中.深入地研究了不确定数据库中的轮廓查询处理技术.首先,提出了不确定数据库中阈值轮廓查询的定义;其次,通过对其性质的分析,提出了基于R一树索引的基本的阈值轮廓算法(BPS);接着,通过对其性质的进一步分析,在BPS算法的基础上,增加了有效的过滤策略,提出了改进的阈值轮廓算法(IPS).实验结果表明,IPS算法可以有效地减少阈值轮廓的计算时间,从而满足实际应用的性能需求.