海量数据上有效的top-k Skyline查询算法

在许多应用中,Skyline查询是一种十分重要的查询类型,它在潜在的巨大的数据空间中返回不被其他元组支配的用户感兴趣的元组,但是Skyline查询无法控制返回结果的数量。处理一个新的top-k Skyline查询问题,该查询返回支配分数最大的k个Skyline元组,从而控制了需要向用户返回的查询结果数量。分析发现,大多数现有算法忽略了利用支配分数作为限制Skyline查询的结果数量的度量。提出一个新的基于表扫描的RSTS(ranked Skyline with table scan)算法来有效计算海量数据上的top-k Skyline结果。RSTS算法首先对表执行预排序操作,保证预排序表的元组按照对有序列表的round-robin扫描的顺序排列。RSTS算法包括两个阶段。阶段1利用对预排序表的顺序扫描来获得候选元组。阶段2计算候选元组的支配分数并返回结果。可以证明,RSTS算法具有早结束特性,并给出其扫描深度的理论分析。提出对于候选元组的剪切操作,理论剪切效果表明,绝大多数的Skyline结果可以直接丢弃。实验结果表明,RSTS算法可以有效计算top-k Skyline结果。     

无线传感器网络中基于聚簇结构的Skyline查询方法

现有的基于单服务器的Skyline查询算法已经不能很好地应用于无线传感器网络这类分布式多跳自组织网络中。基于聚簇结构的Skyline查询算法就是针对 这类特定的网络结构而提出的。该算法采用基于聚簇的路由结构,为了减少Skyline查询处理过程中传感器节点的通信开销,挑选具有最大支配力的数据元组作为全局过滤元组来过滤不满足Skyline条件的数据。同时,在Skyline查询处理过程中引入滑动窗口机制,该机制也能有效地降低通信开销。大量的仿真实验结果显示,所提Skyline查询算法在确保能耗的基础上仍然具有很好的性能。     

基于Vague关系数据模型的除操作研究

基于Vague集理论的Vague关系数据库由于其所含信息的模糊性,对应于现实世界的多种状态。为此,基于扩展的Vague关系数据模型,研究一种条件受限的Vague除操作实现方法,并给出相应的操作步骤和算法。实例分析结果表明,该实现方法可直接作用于整个Vague关系数据库,无需对Vague关系数据库对应的所有状态逐一进行扫描即可获得正确的操作结果,具有较高的执行效率。     

含核Vague区域和Vague洞区域关系及蕴涵定理

模糊区域的空间信息表示和区域关系处理在空间数据库、地理信息系统和人工智能等领域具有重要的意义.引入Vague集的概念和理论对含核Vague区域和Vague洞区域关系进行了系统的研究.基于Vague集给出了含核Vague区域、Vague洞区域和区域划分等概念;详细分析了处于不同平面中的含核Vague区域和Vague洞区域关系;给出了基于Vague集的区域关系交集模型和子区域关系间的蕴涵定理和算法;进一步给出了实例分析.研究成果可较好地处理含核Vague区域和Vague洞区域内的模糊点不确定的隶属信息和确定含核Vague区域与Vague洞区域的关系等问题.     

Vague时间段关系与Vague区域关系的表示和复合推理

Vague时间段关系和Vague区域关系的表示和复合推理问题在时空数据库和人工智能等领域具有重要的研究意义.为了处理复杂的Vague时间段关系,基于Vague集形式化给出了Vague时间段、Vague时间段划分等重要概念;给出了基于Vague集的线性Vague时间段关系模型和周期性双向叠合Vague时间段关系模型;进一步提出了Vague时间段关系和Vague区域关系的复合推理策略和推理算法;给出了实验分析和实例模型,对实例模型进行了详细的讨论.研究成果可处理Vague时间段和Vague区域内其时刻点和区域点的不确定的隶属信息,可较好地表示和分析Vague时间段关系和Vague区域关系及其复合推理问题.     

基于Vague数据库的代数查询语言

基于Vague集理论的Vague关系数据库与其他模糊数据库一样,由于所含信息的模糊性,对应着现实世界的多种状态.虽然此类数据库能够更加真实地反映现实世界,但是在基于这些数据库的查询语言的有效性和计算过程的复杂性等方面却存在着一定的问题.本文基于Vague关系数据模型,对其代数查询语言中的选择、投影和连接操作进行了研究,指出基于一般Vague关系数据模型的查询语言中所存在的问题,并提出相应的解决方法,引入一种嵌套机制,对Vague关系模型进行了进一步扩展,进而对新模型查询语言中的三种操作在不同情况下进行了讨论,并给出了相应的定义.     

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

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

高效多子空间Skyline查询处理算法

随着Skyline查询应用的增多,子空间Skyline查询成为热点。针对实际应用中用户从多角度审视某一数据集的需求,充分研究了多子空间Skyline查询问题。在分析现有子空间Skyline查询算法解决该问题不足的基础上,提出了子空间立方体群(subspace skycube group,SSG)结构,并给出了基于该结构的同时计算任意多个子空间Skyline查询的MSSC(multiple subspace skycube)算法。该算法采用子空间候选集(subspace candidate sets,SCS),并充分利用了子空间立方体群结构中各子空间Skyline结果间的共享关系;在此基础上,算法采用求和过滤以及最大值过滤等方法,对数据集进行剪枝和过滤,从而进一步提高算法效率。最后,分别用人造数据和真实数据对算法进行实验,并与现有算法进行比较,结果表明MSSC算法可以高效地解决多子空间Skyline查询问题。     

Vague关系与Vague映射

在系统研究了作为Zadeh模糊集理论重要扩展的Vague关系及其合成运算,并就Vague关系的性质进行了讨论。在此基础上研究了Vague等价关系,给出了Vague映射的概念,讨论了Vague映射的一些性质。     

基于Vague关系数据模型的连接操作

模糊数据库由于其所含信息的模糊性,可分解为现实世界的多种可能性状态。在已有研究的基础上,对基于Vague关系数据模型的Vague连接操作进行研究,并在限定条件下,给出一个Vague外键连接操作计算公式。该公式可直接用于Vague数据库,可避免对Vague数据库对应的所有可能性状态逐一进行操作,且查询结果满足性质rep(q(T))=q(rep(T))。与基于可能性状态的查询方法相比,该方法的查询结果有效且具有较高的执行效率。     

Skyline查询处理

对目前的Skyline查询方法进行分类和综述.首先介绍Skyline查询处理问题产生的背景,然后介绍Skyline查询处理的内存算法,并从带索引和不带索引两个方面对现有的外存Skyline查询处理方法进行分类介绍,在每组算法后,都对该组算法进行了性能评价,然后介绍不同子空间上的多SKyline查询处理模型——SKYCUBE的概念和相关研究.另外,还介绍了不同应用环境下解决Skyline查询处理的策略以及Skyline查询处理问题的扩展,最后归结出Skyline查询处理后续研究的几个方向.     

一种并行处理Skyline查询的有效方法

Skyline查询是近年来数据库领域的一个研究重点和热点, 这主要是因为Skyline查询在许多领域有着广泛的应用. 现有的工作大都集中于单处理机环境, 然而, 由于Skyline查询是CPU敏感的, 因此,在实际应用中, 现有的方法具有很大的局限性. 基于此, 提出一种有效降低处理Skyline查询时间开销的并行算法PAPSQ (Parallel algorithm for processing skyline queries). 算法有机结合多维数据对象的自身特性和通用多处理机系统的实施优点, 以Skyline查询搜索偏序格为底层结构, 利用多维数据对象的同胚评估值和偏序格加权技术来有效提高并行处理Skyline查询的效率. 实验评估表明, PAPSQ算法具有有效性和实用性.     

基于高维空间的在线高效子空间Skyline算法——CSky

Skyline计算是要发现数据集中不被其他点支配的所有点的集合.近来,它在实时在线服务方面的良好应用前景,使其成为数据库研究领域的一个热点.实际应用中,用户通常期望快速、渐进地返回Skyline计算结果,因此文中主要讨论了高维空间子空间Skyline渐进查询问题.据我们所知,现有的Skyline计算方法都不能直接或者通过简单修改来高效解决该种查询问题.BNL(Blocked Nested Loop)算法是一个可用来进行子空间Skyline计算的算法,但是,该方法低效且非渐进.基于此,文中提出了在线高效子空间Skyline算法--CSky(Count the Skyline).该算法充分利用了一个新颖数据结构--InvertS的特征,即通过对目标数据集进行排序,存放最可能为Skyline点的数据于算法优先扫描的位置,这使得CSky算法能高效计算出任意子空间上的Skyline;同时,CSky每次计算子空间Skyline查询时,至多访问一遍数据库;再有,算法扫描一个点时,只需和当前已发现的Skyline点进行比较即能判断该点是否为Skyline点,保证了算法的渐进性.这样,相比BNL,CSky大大减少了计算开销,具有其他基于索引的Skyline算法计算Skyline时的高效,且这种高效适用于所有子空间.理论分析和实验表明,在解决高维空间子空间Skyline查询问题方面,CSky性能大大优于BNL.     

无线传感器网络中一种近似Skyline 查询处理算法

由于无线传感器网络的能源有限,且在许多应用中Skyline 查询的部分结果即可满足用户需求,提出了一 种近似Skyline 查询处理算法,在满足用户查询需求的前提下最大化地节省能量.该算法仅需无线传感器网络中的部 分传感器节点回传其感知数据即可计算出Skyline 查询的一个近似结果集.由于该算法在处理查询时,每个传感器节 点只需考察自身数据信息即可决定是否回传其感知数据,而无须与其他传感器节点的感知数据进行比较,因此可以 避免大量的网内通信开销,从而节省网络能源.模拟环境下的大量实验结果表明,该算法可以根据用户的应用需求, 节能地处理传感器网络中的近似skyline 查询.     

Efficient skycube computation using point and domain-based filtering

Skyline queries have been increasingly used in multi-criteria decision making and data mining applications. They retrieve a set of interesting points from a potentially large set of data points. A point is said to be interesting if it is not dominated by any other point. Skyline cube (skycube) consists of skylines of all possible non-empty subsets of a given set of dimensions. In this paper, we propose two algorithms for computing skycube using bitmaps that are derivable from indexes. The Point-based skycube algorithm is an improvement over the existing Bitmap algorithm, extended to compute skycube. The Point-based algorithm processes one point at a time to check for skylines in all subspaces. The Domain-based skycube algorithm views points as value combinations and probes entire search space for potential skyline points. It significantly reduces bitmap access for low cardinality dimensions. Our experimental study shows that the two algorithms strictly dominate, or at least comparable to, the current skycube algorithm in most of the cases, suggesting that such an approach could be a useful addition to the set of skyline query processing techniques.     

The power of inequality semijoins

Semijoin is a relational operator used in many relational query processing algorithms. Semijoins can be used to “reduce” the database by delimitting portions of the database that contain data relevant to a given query. For some queries, there exist sequences of semijoins that delimit the exact portions of the database needed to answer the query. Such sequences are called full reducers.

This paper considers a class of queries called natural inequality queries (NI queries), and characterizes a subclass for which full reducers exist. We also present an efficient algorithm that decides whether an NI query lies within this subclass, and constructs a full reducer for the query. The NI queries are a subset of the aggregate-free, conjunctive queries of QUEL, and permit join clauses to include <, , =, , >.     

REPS:一种高效的容错并行概率流Skyline查询方法

概率数据流的并行Skyline查询作为当前大数据分析的一个重要方面,在诸多实际应用中发挥着重要作用。针对并行概率流Skyline查询过程中因发生故障而导致查询结果不准确和查询中断等问题,提出了一种基于复制的容错并行Skyline查询方法REPS。该方法选择参与并行处理的计算节点作为副本节点,并采用层次-循环式数据副本放置策略,选择优先级高的副本恢复数据来保证数据恢复的高效性;同时将故障检测、丢失数据恢复和查询过程恢复贯穿于整个查询更新过程中,以减少容错处理的额外通信和计算开销,并实现快速的容错并行查询。实验结果表明,REPS方法不仅在无故障发生和单个节点失效时具有较高的查询处理效率,而且对于多节点失效情形,仍然能够保持较高的查询处理速率且满足查询需求。