跨信任域的联邦k-支配Skyline查询算法

k-支配Skyline查询是一种主流的Skyline查询变种,其在多目标决策与推荐领域有着广泛的应用。随着这些应用规模不断扩大,在由多个参与方组成的数据联邦中进行跨域k-支配Skyline查询的需求日益旺盛。然而,由于数据联邦中的参与方之间彼此不互信,进行跨信任域的查询计算需引入大量安全操作,效率较低。为此提出了一种基于跨域隐私向量聚合的算法,从而实现高效的联邦k-支配Skyline查询,并运用一种密文压缩技术进一步优化查询效率,最后通过充分的实验验证了所提方案的优越性。

基于Flink的k-支配skyline体并行求解算法

k-支配skyline算法弱化了数据点之间的支配关系,更适合高维数据。k-支配skyline体适应于多名用户使用k-支配skyline算法查询,而现有的求解算法在时间效率和代码扩展性方面都有待提高。因此,提出了面向多用户的k-支配skyline体求解优化算法MKSSOA,该算法对每名用户的候选集和中间集分别进行存储,同时在k-支配检查过程中利用2集合中数据点出现的先后次序将候选集中的非k-支配skyline点存储到对应用户的中间集中,以便下一名用户筛选使用,这样可以减少数据点之间的比较次数,避免重复计算,从而提升查询效率。同时,提出了面向多用户的k-支配skyline体并行求解算法MKSPSA,通过Apache Flink并行处理框架有效减少了数据点的比较时间。理论研究和实验结果显示,提出的算法具有较高的效率,能很好地处理多用户k-支配skyline问题。

一种基于索引的高效k-支配Skyline算法

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

一种使用简化预排序的k-支配Skyline查询算法

近年来,Skyline查询在多目标决策、数据挖掘、数据库可视化等方面得到广泛应用.然而在高维空间环境下,skyline查询因为返回的结果集过大而不能提供有用的信息.因此,学术界提出了k-支配skyline查询的概念.它通过弱化数据点之间的支配关系,使数据点间更容易产生支配关系,从而使结果集的大小保持在一个合适的范围内.现有k-支配skyline查询算法分为建立索引和不建立索引两种类型.其中不建立索引的算法在高维空间,反相关数据和渐近输出等方面表现比较差,而基于索引的算法花费大量时间去建立索引,整体性能都不高.本文提出一种基于简化预排序的k-支配skyline查询算法(SPA),实现用O(n)的时间复杂度对数据进行简化预排序.理论论证和实验数据都显示了SPA算法远比国内外现有的最好算法更加高效.

Web服务选择动态Qos情况下的k-支配skyline改进

论文利用Web服务动态Qos属性的统计情况得到各Qos属性的概率密度函数,然后利用概率密度函数研究各Web服务成为skyline服务的概率,用概率大小反映Web服务支配力的大小,同时以概率降序排列建立Web服务的索引来改进k-支配skyline算法,最终得到Web服务选择动态Qos情况下的概率索引算法。

多时间序列k′/k-支配Skyline查询处理

时间序列是各个领域中大量存在的一类数据,有着极广泛的应用.多时间序列是其中常见的一种数据类型,它从多个角度以单时间序列的形式去描述同一个对象.目前关于时间序列的研究主要集中于单时间序列,而多时间序列的研究工作则相对较少,如多时间序列的查询处理等,但是在实际生活中多时间序列的查询却有着非常广泛的应用.首先定义了多时间序列的支配关系,然后在此基础上给出多时间序列k′/k-支配Skyline查询的定义,并提出了GMS和GMI两种查询算法,对算法的正确性和复杂性也进行了证明和分析.合成数据和真实数据上的大量实验表明,两种算法都可以得到较好的查询结果,而GMI算法的查询效率较GMS算法有很大程度地提升.

k~*-支配Skyline查询在实验数据检索中的应用

利用多关键字查询技术可以从大量的实验数据中检索表现突出的数据,Skyline查询是多关键字查询的经典方法之一。在高维空间中,Skyline查询返回的结果集较大,往往没有实际意义。而k-支配Skyline查询虽然可控制结果集的规模,但有可能产生循环支配,导致结果集为空。上述方法都没有考虑用户偏好。在k-支配Skyline查询的基础上,在支配关系中引入用户偏好的优先级,提出了k~*-支配Skyline查询。该查询既可控制结果集的规模,又消除了循环支配的可能性,保证了查询结果集不为空,还能使结果集尽可能满足用户偏好。通过实验,研究并验证了k~*-支配Skyline查询用于实验数据检索系统是可行性的。

采用支配及Skyline法研究中药内服外敷治疗活动期类风湿关节炎的临床疗效

目的:采用支配及skyline法研究分析中药内服外敷治疗类风湿关节炎(RA)的临床疗效。方法:回顾性分析安徽省中医院120例活动期RA患者,根据治疗方法不同分为来氟米特组(LEF组)、雷公藤多苷片组(TPT组)、中药内服组(NF组)以及中药内服联合芙蓉膏外敷组(NF+WF组),每组30例,观察4组治疗前后免疫炎症指标(ESR、RF、hs-CRP、CCP、GPI、IgA、IgG、IgM、C3、C4)、代谢指标(GLU、T-C、ALB)变化及其对比,并采用支配及Skyline两种数理分析方法对结果进行比较分析。结果:通过SPSS软件分析结果显示LEF组、NF+WF组总有效率均高于TPT组及NF组(P<0. 05,P<0. 01);与TPT组及NF组治疗后相比较,NF+WF组关节肿胀指数、关节疼痛指数、关节压痛指数、VAS、DAS28评分差异更显著(P<0. 05);LEF组、NF+WF组ESR、CCP、RF、hs-CRP差异更显著(P<0. 05); NF+WF组C3差异更显著(P<0. 05)。与治疗前对比,仅LEF组及NF+WF组ALB治疗后较治疗前差异具有统计学意义。其中LEF组与NF+WF组及TPT组与NF组相互之间治疗后各指标对比无统计学意义。通过支配及Skyline法结果显示NF+WF组支配率最高,虽在支配率上与LEF组差距不大,但在Skyline线中NF+WF组所占比重最高。结论:中药内服外敷具有抗炎镇痛、免疫调节等作用,能显著改善活动期RA患者的各项免疫炎症指标,同单纯的中药内服及常规西医治疗相比,能更有效改善患者的病情,控制其病情活动,无明显不良反应发生。

基于事件的位置不确定移动对象连续概率Skyline查询

Skyline查询是基于位置服务(Location based service,LBS)的一项重要操作,其目的是发现数据集中不被其他点支配的点的集合.移动对象在运动过程中,其位置信息具有不确定性,导致各数据点间的支配关系不稳定,从而影响Skyline操作.本文针对以位置不确定移动对象为查询点的Skyline查询进行研究,首先,定义了查询点移动时各对象间支配概率,提出了支配概率和Skyline概率的微元计算方法.在此基础上,提出一种面向不确定移动对象进行连续概率Skyline查询的有效算法UCPSC.该算法首先快速计算初始时刻的p-Skyline集合;然后,定义了两类可能引起p-Skyline变动的事件,通过对这些事件的跟踪计算快速更新p-Skyline集合,无需在移动对象的每一运动时刻去遍历整个数据集,实现了对p-Skyline的连续更新操作,大大减少了算法的查找和计算开销,提高了运算效率;最后,提出一种静态算法USPSC,与UCPSC进行了对比试验,实验结果证明了算法的有效性.

基于共享策略的k-支配轮廓体的求解算法

现有的k支-配轮廓算法虽然可以对给定的高维数据集计算出不同k(k≤d)值对应的k-支配轮廓,但是,由于不能共享计算结果,会导致很多冗余操作.提出k-支配轮廓体的概念,即所有的k(k≤d)值对应的k-支配轮廓的集合,在此基础上,提出两种基于共享策略的k-支配轮廓体算法——由下到上算法(BTA)和由上到下算法(TBA).理论分析和实验验证表明,所提算法可有效的减少冗余操作.

基于道路网络不确定移动对象的连续概率Skyline查询

Skyline查询是基于位置服务LBS的一项重要操作,其目的是发现数据集中不被其它点支配的点的集合。对道路网络环境下移动对象的连续概率Skyline查询进行了研究。在对道路网络和移动对象建模的基础上,定义了基于道路网络的数据间支配概率和Skyline概率的表示方式,提出了两类可能引起p-Skyline集合变动的event事件,并提出4条剪枝方案进行优化。在此基础上,设计了对网络受限的不确定移动对象进行连续概率Skyline查询的动态增量算法U-CPSQRN。该算法通过对event的跟踪计算实现了对p-Skyline的连续更新操作,减少了算法的查找和计算开销。实验结果显示了算法的有效性。

MapReduce框架下的Skyline结果优化算法

随着大数据时代的到来,数据量和数据复杂度急剧提高,Skyline查询结果集规模巨大,无法为用户提供精确的信息。MapReduce作为并行计算框架,已广泛应用于大数据处理中。本文提出了MapReduce框架下基于支配个数的结果优化算法(MR-DMN),解决了大数据环境下的Skyline结果集优化问题。大量的实验表明:算法具有良好的时间和空间效率。

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

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

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

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

一种求解动态数据集中k-支配轮廓的算法

在对高维数据集进行轮廓查询时,k-支配轮廓查询算法能够返回较少的轮廓点,有利于用户的决策,但目前的算法都是针对静态数据集设计,无法对动态数据集进行处理.动态数据可分为非数据流数据和数据流数据,本文针对这两种情况提出了相应的增量求解算法,即当数据集发生变化时,以现有的k-支配轮廓为基础,通过对部分数据点进行计算得到新的k-支配轮廓.证明了算法的正确性和有效性,并通过实验对算法进行了分析和验证.

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

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

无线传感器网络中一种能量高效的skyline查询算法

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

Skyline计算在多维排序问题上的分析

Skyline计算是近几年数据库研究领域研究的热点之一.为研究多维排序问题,定义了Skyline点以及相关概念,对Skyline点在多维排序问题上做了深入分析,分析了在最坏情况下的复杂度,并研究了在各个领域中的应用.Skyline计算在多维数据集上的应用十分广泛.

求解最小连通r-跳k-支配集的启发式算法

针对最小连通r-跳k-支配集的求解问题,提出一种基于节点度贪心策略的启发式算法。把网络节点集合作为初始解,从中选出度数最小的节点,通过判断节点的连通性决定是否将该节点从当前可行解中删除,由此逐步缩小连通支配集的规模,直至处理完所有节点。在单位圆盘图上进行算法复杂性分析和模拟实验,结果表明,相比同类算法,该算法得到的连通r-跳k-支配点集更少,且性能稳定。

基于Skyline的搜索结果排序方法

针对现有垂直搜索引擎的排序结果存在多样性差和冗余度高的问题,提出了一种基于Skyline的搜索结果排序方法。该方法通过计算搜索结果的轮廓等级、支配度和覆盖度作为排序依据,并且为加快轮廓等级和支配度的计算,使用了一种基于Bitmap的轮廓等级和支配度计算算法。实验结果表明,该方法的排序结果具有低冗余度和高多样性的优点,并且具有更快的轮廓等级和支配度计算速度。