首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到17条相似文献,搜索用时 93 毫秒
1.
作为数据流上的一种重要查询,skyline对于很多在线应用都非常重要,包括移动运算环境、网络监控、传感器网络、股票交易等。与大多数数据流skyline处理技术不同,本文着重于约束skyline的处理。约束skyline支持用户定义在某些属性上的偏好,系统中存在多个约束skyline查询,为skyline查询处理技术带来了新的挑战。为了在高速数据流上对约束skyline进行高效处理,本文使用了一种网格索引存储元组,并提出两个算法用于计算和维护skyline集合,我们还为每个查询定义了影响区域,以减少在新元组到达和旧元组失效时需要处理的网格数目。理论分析和实验证明了该方法的有效性。  相似文献   

2.
针对分布式无线传感器网络环境下的skyline查询问题,提出了KSkySenor算法,有效地从传感器网络中获取更有意义的skyline结果;KSkySenor算法对感知数据进行预处理计算每个元组的支配能力,按照支配能力与各维度值之和对其进行排序,设计了一个基于聚簇的结构用于收集所有传感器读数,提出了一个剪枝方法用于渐进的从传感器网中获取skyline结果集;实验中分别改变传感器网络规模大小、数据维度、支配属性个数k,对KSkySensor算法进行测试,实验结果表明KSkySenor算法与先前的skyline查询处理算法相比具有很高效率,减少了无线传感器网络中的数据传输量,延长了网络生命周期。  相似文献   

3.
多维空间的skyline 查询处理是近年来数据库领域的一个研究重点和热点.Vlachou 等人首次考虑如何在P2P 网络中有效进行子空间上的skyline 查询,并提出“扩展skyline 集合”的概念来减少预处理时的网络传输量.然而实验评估表明,扩展skyline 集合只能有限地减少子空间skyline 查询预处理的数据传输量.基于此,提出一种缩减处理时数据传输量的有效方法TPAOSS(three-phase algorithm for optimizing skyline scalar).TPAOSS 算法根据全空间skyline 集合与子空间skyline 集合间的语义关系分3 个阶段来传输必要的数据,其中第1 阶段发送全空间skyline 对象;第2 阶段接收种子skyline 对象;而第3 阶段基于Bloom filter 技术发送种子skyline 对象在子空间上的重复对象.为了降低第2 阶段的数据传输量,给出两种接收种子skyline 对象的有效策略.理论分析和实验评估结果表明,所给出的算法具有有效性和实用性.  相似文献   

4.
Skyline计算研究综述   总被引:6,自引:0,他引:6       下载免费PDF全文
近年来,skyline计算以其在多目标决策、数据挖掘、数据库可视化等方面的潜在应用引起了越来越多研究者的关注。集中式skyline计算作为最早的研究重点得到了深入的研究,许多有效的skyline计算算法被提出来,例如BNL、NN、BBS等等。其中,BBS被认为是当前最佳的集中式skyline计算算法。分布式skyline计算的研究也取得了明显进展,已有的工作分别对面向分布式数据库、移动自组织网络和对等网络等的skyline计算进行了探索。Skyline计算还被扩展为其它更复杂的计算问题,包括任意子空间上的skyline,所有子空间上的skyline,k-支配的skyline,空间skyline计算等等。然而,迄今为止,国内外还没有一篇论文对sky-line计算技术作过全面的分析与评述。对skyline计算技术进行系统的综述。在介绍已有代表性算法的基础上,通过分析它们的特点和比较它们的性能,总结了各算法的优势和不足,并指出了skyline计算的未来发展方向。  相似文献   

5.
一种基于索引的高效k-支配Skyline算法   总被引:1,自引:0,他引:1  
由于在多标准决策支持等应用上具有重要的意义,skyline查询成为近年来数据库和数据挖掘领域的一个研究热点.然而随着数据集维数的增加,数据点之间形成支配关系的可能性越来越小,导致了skyline点数目过多而无法提供任何有效信息.为了在高维数据集中找到更重要和更有意义的skyline点,人们提出了k-支配skyline的定义.但现有的用于k-支配skyline的算法在时间效率、空间复杂度和渐进输出性上都有待提高.该文提出了一种基于索引的高效k-支配skyline算法,通过为数据集建立两个索引,算法可以高效地进行计算,在时间、空间和渐进性上均优于现有的算法.  相似文献   

6.
基于Skyline的QoS感知的动态服务选择   总被引:2,自引:0,他引:2  
服务计算相关技术标准的持续完善和不断成熟推动了基于Web服务重用的分布式应用系统开发方式的迅速普及.而随着服务数量的爆炸性增长,网络上存在着大量功能相似、非功能特性各异的服务,如何在功能相当的服务集中选择质量较优的服务成为一个亟待解决的问题.传统的基于服务质量的服务选择方法,无论是局部最优或是全局最优策略,均面向服务库中的所有服务进行选择,选择效率受服务数量影响较大,因此不适用于基于大规模服务库的服务选择.文中引入数据库查询中的skyline方法,利用skyline中的支配关系,在选择过程中仅考虑skyline之上的服务,从而大大缩小了服务选择的范围,提高了服务选择的效率.同时针对动态Web服务环境,提出一种动态环境下的skyline服务维护算法,并通过一系列仿真实验证明了所提算法的高效性及良好的可扩展性.  相似文献   

7.
skyline查询是近年来数据库领域的一个研究重点和热点.当系统中存在多个不同维空间上的skyline查询时,现有的工作均直接从底层关系表中获取这些skyline查询的结果集.显然,当底层关系表的基数较大且skyline查询的个数较多时,现有方法的处理效率极其低下.基于此,提出一种使用预存储的n个skyline集合{PR1,…,PRn}来回答用户提交的m个不同维空间上的skyline查询{SQ1,…,SQm}的有效方法EAPSQ(efficient algorithm for processing skyline queries).算法充分考虑预存储的skyline集合的编码机制,采用经济学中边际贡献(contribution margin)的概念,使得m个用户提交的skyline查询在n个预存储的skyline集合间的分配达到最佳状态,从而显著提高了处理用户m个skyline查询的效率.实验评估表明,EAPSQ算法具有有效性和实用性.  相似文献   

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

9.
黎玲利  王宏志  高宏  李建中 《软件学报》2012,23(6):1561-1577
利用关键字可以在模式未知的情况下对XML数据进行查询.在当前的XML数据流上的关键字查询处理中,打分函数往往不能都满足各种用户不同的需求.提出了一种基于skyline的XML数据流上的Top-K关键字查询.对于这种查询,不需要考虑影响结果与查询相关性的复杂因素,只需利用skyline挑选与查询最相关的结果.提出了两种XML数据流上的有效的基于skyline的Top-K关键查询处理算法,包括对单查询和多查询的处理算法.通过扩展实验对两种算法的有效性和可扩展性进行了验证.经过实验验证,所提出的查询处理算法的效率几乎不受关键字个数、查询结果数量、查询数量等参数的影响,运行时间和文档大小大致呈线性关系.  相似文献   

10.
skyline查询是数据挖掘一个重要的研究方向,在基于数据的决策支持等应用中有着重要的作用.由于现实应用中存在着大量的不完整数据流,但大多数现有的skyline查询算法都依赖于如下的假设:1)任意数据点的所有维度值都是已知的;2)数据集是稳定、有界的并且可以随意访问.此外,随着数据维度的增加,skyline数据点的个数会变得过多,因此引入了k-支配skyline的概念,但是不完整数据的k-支配关系并不具有传递性,现有的skyline查询算法都无法适用.基于这些问题,考虑到数据流高维、无界、顺序性的特点,并且在某些维度上可能具有缺失值的特性,提出了一种新的基于滑动窗口的不完整数据流的k-支配skyline查询算法,实验结果表明,算法不仅可以支持不完整数据流上的k-支配skyline计算,并能够保证效率和性能.  相似文献   

11.
Two-tier streaming settings are a typical dynamic environment where continuous skylines represent an important semantic indicator for multiple attributes. To monitor skylines over the dynamic data in such settings, one needs to continuously update the skyline query results in order to reflect the new data values. This paper tackles the problem of continuous skyline monitoring on a central query server over dynamic data from multiple data sites. Simply sending the updates of tuple values to the server is cost-prohibitive. Therefore, we propose an approach that allows the central server to collaborate with the data sites to monitor the possible skyline changes. By doing so, the processing load is distributed over all the data sites instead of only on the central server. Furthermore, this collaborative approach minimizes the bandwidth consumption between the server and the data sites, which is often critical in a widely distributed environment such as a wide-area sensor network. We give theoretical upper bounds for the computation costs and communication costs of the proposed collaborative approach. We also conduct extensive experiments on both synthetic and real data sets. The experimental results demonstrate that our collaborative approach is efficient, scalable and well-balanced in terms of communication costs and computation costs.  相似文献   

12.
In many applications involving multiple criteria optimal decision making, users may often want to make a personal trade-off among all optimal solutions for selecting one object that best fits their personal needs. As a key feature, skyline in a multi-dimensional space provides a minimal set of candidates for such purposes by removing every object that is not preferred by any (monotonic) utility/scoring function; that is, the skyline removes all objects not preferred by any user no matter how their preferences vary. Due to its importance, the problem of skyline computation and its variants have been extensively studied in the database literature. In this paper, we provide a comprehensive survey of skyline computation techniques. Specifically, we first introduce the skyline computation algorithms on traditional (exact) data where each object corresponds to a point in a multi-dimensional space. Then, we discuss the skyline models and effcient algorithms to handle uncertain data which is inherent in many important applications. Finally, we briefly describe a few variants of the skyline (e.g., skycube, k-skyband and reverse skyline) in this paper.  相似文献   

13.
轮廓操作和轮廓计算在数据库通信、决策支持、数据可视化以及空间数据库等应用中具有重要作用。该文分析现有方法,指出其在渐进处理、查询高效性和用户后期筛选方便性等方面存在的问题,提出基于轮廓点支配定理、应用空间几何原理的3D动态割面轮廓查询算法。通过实例分析和实验证明其可行性、高效性和准确性。  相似文献   

14.
The skyline search problem has been identified as one of the key problems in database research. None of the developed skyline search algorithms include the use of a filter to facilitate the search process. This paper proposes a novel modification involving the use of skyline filters to reduce the search space of a skyline problem by removing data points that cannot provide a viable skyline result. Three filters based on the concept of neural networks are proposed in this paper. The result is a reduction in execution time achieved through the reduction of the input tuples. The proposed filters may be used in conjunction with any existing skyline search algorithm. This is the first study to apply neural network technology to the skyline problem. Comprehensive simulation results demonstrate the effectiveness of the proposed skyline filtering system.  相似文献   

15.
随着轮廓查询应用的扩展,轮廓查询被扩展为其他更复杂的查询问题,包括k支配轮廓、reverse轮廓、k最多支配轮廓等等.然而,现存的轮廓查询不符合某些用户需求,还需要研究新的轮廓查询及其相关算法.为了满足用户需求,提出k支配能力轮廓的概念,同时提出一种快速的k支配能力排序轮廓查询算法(KRA).由于不确定性数据带有概率,KRA算法不能直接应用于不确定性数据.针对不确定性轮廓查询的特点,提出不确定性k支配能力轮廓的概念,并提出不确定性k支配能力排序轮廓查询算法(KRA_U).实验结果表明,算法KRA和KRA_U均可以高效地计算出k支配能力轮廓.  相似文献   

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

17.
分布式数据流上的Skyline计算   总被引:1,自引:0,他引:1  
为了降低分布式数据流上的连续Skyline计算过程中的通信开销,提出了基于远程过滤的思想并对相关理论基础进行了证明,描述了系统的体系结构并提出了两个过滤模型v_Max和Distance。理论分析和实验结果证明了所提方法在某些数据分布情况下降低通信开销的有效性。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号