多样k-支配轮廓查找方法

现有的k-支配轮廓查询算法难以保证查询结果的多样性,限制了结果的选取空间。如何求出一个点的全部k-支配属性,是k-支配轮廓查询领域的一个新问题。针对这一问题,提出了多样k-支配轮廓点的概念,分析了多样k-支配轮廓的性质,给出了两种不同的查找算法,并证明了算法的有效性和正确性。     

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

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

MapReduce框架下k-支配轮廓查询算法

随着维度和数据量的不断增长,已有的轮廓查询方法已无法为用户提供更好的查询支持.本文采用并行处理框架MapReduce 结合k-支配轮廓查询算法来解决此类查询问题.在对输入的数据集进行预排序的基础上,提出了基于MapReduce 的单轮扫描算法和双轮扫描算法,通过在不同维度、数据分布、节点个数等方面的实验测试及对比,验证了算法的有效性.     

一种基数可调整的轮廓查询——模糊轮廓

针对轮廓查询的结果随着数据维度的增加而显著增加的问题,在模糊集理论的基础上,提出了模糊轮廓集的概念,量化了不同数据点对轮廓查询的贡献度.以此为基础,通过在模糊轮廓集中取不同的截集达到了准确控制查询结果数量的目的.同时,提出了有效的FSCA算法来求解任意的模糊轮廓,为用户提供δ个数据点,方便了用户的决策.实验分析的结果表明,模糊轮廓查询是一种有意义的基数可调整的新型轮廓查询,FSCA算法是有效的模糊轮廓求解算法,它们共同为用户决策提供了很好的辅助手段.     

移动环境中的位置依赖连续轮廓查询

针对移动环境中查询点快速移动时连续、高效输出给定搜索区域数据轮廓的问题,提出一种位置依赖连续轮廓查询算法(LDCS).该算法结合数据流技术,首先使用R树快速更新查询数据,然后利用两次连续计算时搜索区域的重叠性构造被动数据流,并对新增和失效数据分别进行处理,从而连续输出轮廓.由于充分利用了已有结果,LDCS的计算量较传统算法有大幅下降.实验结果表明,LDCS特别适合计算频度要求较高的场合,与基于网格索引的算法相比,时间效率随着数据集规模的增大显著提升.     

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

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

一种在无线传感器网络中构造有效连通支配集的算法

构造连通支配集是解决数据收集问题的一种较有效方法,现有算法在构造连通支配集时只考虑支配集的大小,造成支配集有效期短,易产生盲点及传输数据能耗大.针对如上缺陷,综合考虑支配集的大小、节点能量及节点到基站的路径,提出了一个基于广度优先搜索生成树的算法.模拟实验表明,该算法的系统生命期比现有算法提高20%左右,延迟缩短17%左右.     

缓存模式下的轮廓查询优化方法

研究在缓存模式下,利用一组预存储的临时轮廓快照集来高效等价重构用户新提交的轮廓查询Q,并提出一种新颖的缓存模式下轮廓查询处理算法(APSQCM)来完成该任务.APSQCM算法由两阶段组成,第一阶段捕获Q与缓存中临时轮廓快照间的内在关联,进而获取能够用来等价重构Q的所有轮廓基;而在第二阶段中,APSQCM算法使用轮廓基来快速产生Q的正确结果集.实验结果表明,APSQCM算法具有有效性和实用性.     

基于模糊规则的随机缺失属性值数据分类算法

针对缺失属性值数据分类算法中模型分类精度和泛化能力低的问题, 提出一种基于模糊规则的缺失属性值数据分类算法, 即“循环 接收”模型. 该算法不需要对缺失属性值数据进行插补运算, 可直接对该数据集进行分类. 对UCI公开数据集进行模拟仿真实验, 实验结果表明, “循环 接收”模型与其他算法相比具有更高的分类精度和泛化能力.     

数据流上的轮廓查询算法

采用滑动窗口技术对数据流进行近似,提出了两种数据流上的轮廓查询方法:CCS算法和PCS算法.CCS算法能够实时反映数据的变化,内存空间的利用率也较高.PCS算法则适合周期性更新的应用环境,有利于节约CPU资源.实验结果证明所采用的算法是有效的.     

Efficient Processing of Skyline Group Queries over a Data Stream

In this paper, we study the skyline group problem over a data stream. An object can dominate another object if it is not worse than the other object on all attributes and is better than the other object on at least one attribute. If an object cannot be dominated by any other object, it is a skyline object. The skyline group problem involves finding k-item groups that cannot be dominated by any other k-item group. Existing algorithms designed to find skyline groups can only process static data. However, data changes as a stream with time in many applications,and algorithms should be designed to support skyline group queries on dynamic data. In this paper, we propose new algorithms to find skyline groups over a data stream. We use data structures, namely a hash table, dominance graph, and matrix, to store dominance information and update results incrementally. We conduct experiments on synthetic datasets to evaluate the performance of the proposed algorithms. The experimental results show that our algorithms can efficiently find skyline groups over a data stream.     

Sampling-Based Approximate Skyline Query in Sensor Equipped IoT Networks

The ever increasing requirements of data sensing applications result in the usage of Io T networks. These networks are often used for efficient data transfer. Wireless sensors are incorporated in the Io T networks to reduce the deployment and maintenance costs. Designing an energy efficient data aggregation method for sensor equipped Io T to process skyline query, is one of the most critical problems. In this paper, we propose two approximation algorithms to process the skyline query in wireless sensor networks. These two algorithms are uniform samplingbased approximate skyline query and Bernoulli sampling-based approximate skyline query. Solid theoretical proofs are provided to confirm that the proposed algorithms can yield the required query results. Experiments conducted on actual datasets show that the two proposed algorithms have high performance in terms of energy consumption compared to the simple distributed algorithm.     

Computing Skyline Groups:An Experimental Evaluation

Skyline group, also named as combinational skyline or group-based skyline, has attracted more attention recently. The concept of skyline groups is proposed to address the problem in the inadequacy of the traditional skyline to answer queries that need to analyze not only individual points but also groups of points. Skyline group algorithms aim at finding groups of points that are not dominated by any other same-size groups. Although two types of dominance relationship exist between the groups defined in existing works, they have not been compared systematically under the same experimental framework. Thus, practitioners face difficulty in selecting an appropriate definition. Furthermore, the experimental evaluation in most existing works features a weakness,that is, studies only experimented on small data sets or large data sets with small dimensions. For comprehensive comparisons of the two types of definition and existing algorithms, we evaluate each algorithm in terms of time and space on various synthetic and real data sets. We reveal the characteristics of existing algorithms and provide guidelines on selecting algorithms for different situations.     

基于窗口查询的轮廓查询算法

轮廓查询在涉及多标准决策的空间数据库应用中起着非常重要的作用,轮廓的计算在数据库通信方面受到很大关注,特别是无需访问所有的数据文件就能很快的返回轮廓中的点的算法.本文提出一种基于窗口查询的轮廓查询算法,通过不断变换查询窗口来缩减查询空间,所访问的空间数据点数目大大减少,查询结果有很好的健全性和完整性.     

Multi-QoS aware automatic service composition

Almost all current automatic service composition （ASC） algorithms consider only single nonfunctional requirements, namely quality of service （QoS）, which cannot satisfy the real application. This paper proposes MAT （multi-QoS aware top-K ASC） algorithm to realize the high-efficiency exploring and rank- ing of composition scheme by synthesizing more nonfunctional goals. MAT algorithm explores composition schemes by the sky- line technique based on tape model and ranks these schemes by a modified binary tree. Using Web service challenge （WSC） 2009 dataset, we verify the performance of MAT algorithm and the experimental result is even close to the current fastest ASC algo- rithm considering only single QoS.     

一种分布式环境下的skyline查询算法

skyline计算在多标准决策、数据挖掘和数据库可视化等领域具有非常重要的作用.研究了分布式环境下的skyline查询问题.提出通过合并局部skyline集合得到全局skyline集合的思想,在计算全局skyline集合时,先对局部skyline集合进行区域划分和动态编码,然后根据各个区域之间的制约关系进行数据合并.通过实验分析可知,当全局skyline集合的规模较大时,经过区域划分的算法比起直接合并的算法执行效率更好.     

自动生成决策树的通用算法模板

目的 提供自动生成决策树的通用算法模板,从而使算法的设计能够快速验证为解决特定决策问题而设计的新算法。方法 提供智能编辑器供算法设计定义自己的公式,并利用该公式或内置算示来初始化通用算法模板,从而实现连续属性的离散化、采用基于概率分布的方法处理未知属性和噪声数据,利用预剪枝和后剪枝算法进行剪枝。结果与结论 用户能够利用该模板,在系统提供的交互式图形环境中,针对不同的决策问题测试决策树生成算法。