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.     

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

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

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

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

MapReduce模型下基于R树索引的Skyline查询算法

提出一种MapReduce并行计算模型下基于R树索引的Skyline查询算法, 解决了海量空间数据集下执行Skyline查询效率低的问题. 通过建立R树索引实现空间数据不同粒度的范围剪枝, 有效降低了分布式Skyline查询需扫描的数据规模, 提高了在MapReduce模型下Skyline查询的执行效率. 在不同数据分布下进行对比实验的结果表明, 该方法比已有算法在执行效率上更具优势.     

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

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

无线传感器网络中基于划分的二维轮廓监控算法

针对传统数据库领域的轮廓查询算法无法直接移植到无线传感器网络领域问题,提出了一种基于划分的二维轮廓监控算法(P2S).P2S算法利用轮廓查询的特点将二维平面进行划分,为每个传感器节点分配一个矩形区域作为过滤器来减少网络中的数据传输,达到降低节点的能量消耗的目的.实验结果表明,P2S算法可以过滤传感器节点的大量不必要的数据,有效地减少了节点向基站发送的消息数量,使得节点有限的电能得到更加合理的利用,从而极大地延长了无线传感器网络的使用寿命.     

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

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

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

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

基于聚类的逆向Skyline查询算法

逆向Skyline查询能够应用到诸如决策支持、用户偏好支持以及市场行为分析等方面。由于参考对象q的存在,在执行逆向Skyline查询的过程中数据空间被划分成许多分区。然而,存在的算法都没有考虑这个问题的影响,直接使用原始数据集建立索引结构。本文提出了一种新的逆向Skyline查询方法CRSQ,它考虑了这个问题。CRSQ首先根据查询对象q对数据进行聚类,然后建立R-tree索引,最后利用高效修剪策略修剪索引搜索空间。实验结果表明CRSQ算法是有效的,它相对于没有聚类技术的算法获得了50%以上的性能提高。     

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

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

数据流上的轮廓查询算法

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

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通过先分组再建索引的方法能够进一步提高计算效率.最后,用大量的实验证明本文所提算法的正确性和高效性.     

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

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

近似质心在区间二型模糊聚类中的应用

针对现有质心求解算法仍具有较高计算复杂度,导致区间二型模糊 C 均值聚类算法(Interval Type-2 Fuzzy C-Means, IT2FCM)运行速度不理想问题,提出了半数迭代法和一次迭代法两种近似质心求解算法。 首先,在直接 求解转换点问题质心求解算法 ( A Direct Approach for Determining the Switch Points in the Karnik – Mendel Algorithm, DA)的基础上,借助二分查找思想,构造出基于二分查找的质心求解算法;接着,以该算法为基础,通过 限制查找范围,考虑两个转换点之间关系的性质和计算差值的技巧得到半数迭代法;最后,考虑只进行一次查找得 到一次迭代法。 在 UCI 上的 5 个数据集上(IRIS、SEEDS、WINE、WIFI_LOCALIZATION 和 HTRU2)验证了两种算法 的聚类性能并没有因为求解的是近似质心而降低;进一步在 ANURAN CALLS 数据集上构造了 8 组数据量递增数 据用于验证基于不同质心求解算法的 IT2FCM 和基于提出的近似质心求解算法的 IT2FCM 运行速度,实验结果表 明:基于近似质心求解算法的 IT2FCM 运行速度较快,所以提出的近似质心求解算法能够在一定程度上缓解 IT2FCM 复杂度过高的问题。     

更新环境下多样K-支配轮廓查找方法

现有的多样-支配轮廓查询算法仅仅关注属性值不变的静态数据集,如何求出属性值更新时的多样-支配轮廓是多样K-支配轮廓查询领域一个新的研究问题。数据集的属性值变化包括单一数据和若干个数据的属性值变化的两种情况。对于这两种情形,利用现有的多样K-支配轮廓,本文提出了两种不同的查找算法。证明了算法的正确性和有效性,并且通过实验对算法进行了分析和验证。     

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.     

基于用户相似度的随机游走社交网络事件推荐算法

针对基于社交网络的事件推荐覆盖性和准确性不够高的问题,提出了基于用户相似度Si-user Walker算法.该算法利用基于事件的社交网络特征,将线上用户群组数据抽象为图,以重启随机游走算法为基础,改变了传统的完全基于图的拓扑结构进行随机游走的策略.根据地理位置划分事件类型,提出了新的用户相似度计算方法,然后根据用户相似度矩阵作为随机游走的转移概率,既保留了图的传递性,又保证了图节点游走的真实性.与其他推荐算法在真实的数据集上实验表明,该算法在均方根误差、准确率及覆盖率上均得到提升.     

传感器网络中基于过滤的概率Skyline查询算法

针对感知数据固有的不确定性问题,研究了无线传感器网络中概率Skyline查询的处理与优化技术.首先分析了概率Skyline查询的性质,证明了概率Skyline查询的不可分解性,因而无法直接利用网内计算方法求解;进而提出了无线传感器网络中基于过滤的概率Skyline查询处理算法(filter basedprobabilisticSkylinequeryprocessingalgorithminWSN,FPSP).FPSP算法将感知数据划分为候选数据、相关数据和无关数据;只需要候选数据和相关数据即可求得概率Skyline查询结果,可以在传感器节点过滤无关数据以避免大量的数据网内传输.仿真实验结果表明,FPSP算法可以有效降低传感器节点的数据传输量,极大地延长了无线传感器网络的使用寿命.     

基于VC++的改进的图像边缘检测算法研究

对4种常用的图像边缘检测算子的特点进行了分析和比较。在此基础上,针对LOG算子存在的一些缺点,运用选取阈值的方法,将Sobel算子和LOG算子结合起来,提出了一种新的图像边缘检测方法。基于VC＋＋语言,研究了该方法的设计并得以实现。实验结果表明,相对于单纯的LOG算子,该方法更具有实用性和有效性。     

基于时间约束的人气最优路径搜索

当旅游景点数目庞大,而限定时间不足以访问任何路径中的所有景点时,现有的搜索方法找不到事实上存在满足条件的路线.提出了一种高效的最优路径近似搜索算法PSScaling,使用修整参数δ,将景点的人气分数调整为一个整数,然后利用路径标签上缩放后景点的人气分数和子路径的时间代价选择最优的子路径向终点扩展,在同一路径中挑选最佳的访问景点组合.最后,通过实验分析,验证了本文提出的算法能够在很高的执行效率下找到近似的最优路线.