Skyline代表点的选择*

Skyline查询在多维决策和数据挖掘等方面发挥重要作用,然而随着数据属性维度的增大, Skyline集变得非常庞大.为克服该不足,提出Skyline代表点查询.文中提出新的评价函数改进Skyline点的得分计算方法以选择k个具有代表性的Skyline点.在二维空间提出动态规划算法(DPBA),利用覆盖圆的性质确定非代表点与代表点间的覆盖距离,迭代计算评价函数值,从而得到k个代表点;在高维空间针对NP-hard问题提出一个基于aR-tree结构的近似解决方法,遍历索引结构中的节点,通过与候选Skyline集比较判断是否被支配进行剪枝,降低计算开销.大量基于合成数据与真实数据的实验证明该算法的有效性.     

大规模复杂网络下重叠社区的识别

随着网络规模的不断扩大,经典的复杂网络重叠社识别算法已不能高效处理现有的大规模网络图数据.本文在GraphLab并行计算模型上提出了基于重要节点扩展的重叠社区识别算法DOCVN (Detecting the Overlapping Community algorithm based on Vital Node Expanding in GraphLab).算法选取网络中PageRank值大的节点作为重要节点,计算其他节点归属于重要节点的节点归属度,并以重要节点为中心形成核心社区及扩展社区,最后根据重要节点间的连接紧密度合并核心社区及扩展社区,并计算出每个节点在所属社区里的节点重要度,实现了大规模网络的重叠社区识别.实验表明该算法与PD (Propinquity Dynamics)等现有并行算法相比更能有效地识别大规模网络的重叠社区结构.     

SLSB-forest:高维数据的近似k近邻查询

近似k近邻查询的研究一直受到广泛关注,局部敏感散列(LSH)是解决此问题的主流方法之一.LSH及目前大部分改进版本都会面临以下问题:数据散列以后在桶里分布不均匀;无法准确计算对应参数k的查询范围建立索引.基于此,将支持动态数据索引的LSH和B-tree结合,构建新的SLSB-forest索引结构,使散列桶里的数据维持在一个合理的区间.针对SLSB-forest提出了两种查询算法:快速查找和准确率优先查找,并通过理论和实验证明查找过程中查询范围的动态变化.     

改进的分布式关联规则安全挖掘算法

以往各种分布式数据挖掘隐私保护算法无法有效解决串通问题,从而限制了其大规模应用,针对上述问题,在Clifton分布式关联规则安全挖掘算法的基础上,提出AKCA算法。采用各站点联合建立并求解方程组的安全多方求和方法。结果证明经过改进的算法能够抵御串通攻击,不借助签名验证也能发现恶意篡改。     

面向时空数据的区块链研究综述

时空数据包括时间和空间2个维度,常被应用于物流、供应链等领域。传统的集中式存储方式虽然具有一定的便捷性,但不能充分满足时空数据存储及查询等要求,而区块链技术采用去中心化的分布式存储机制,并通过共识协议来保证数据的安全性。研究现有区块链1.0、2.0和以Block-DAG为代表的3.0体系架构及性能特点,分析三代区块链架构应用于时空数据时的性能支持度、优化方式以及局限性,并对区块链技术在时空数据领域的应用前景、存在的问题和未来的研究方向进行展望。     

基于高阶相似性的属性网络表示学习

现有的网络表示学习方法缺少对网络中隐含的深层次信息进行挖掘和利用。对网络中的潜在信息做进一步挖掘,提出了潜在的模式结构相似性,定义了网络结构间的相似度分数,用以衡量各个结构之间的相似性,使节点可以跨越不相干的顶点,获取全局结构上的高阶相似性。利用深度学习,融合多个信息源共同参与训练,弥补随机游走带来的不足,使得多个信息源信息之间紧密结合、互相补充,以达到最优的效果。实验选取Lap、DeepWalk、TADW、SDNE、CANE作为对比方法,将3个真实世界网络作为数据集来验证模型的有效性,进行节点分类和链路重构的实验。在节点分类中针对不同数据集和训练比例,性能平均提升1.7个百分点;链路重构实验中,仅需一半维度便实现了更好的性能,最后讨论了不同网络深度下模型的性能提升,通过增加模型的深度,节点分类的平均性能增加了1.1个百分点。     

基于MapReduce的连续Skyline查询

随着Web网络和无线传感器网络的不断发展,大数据的出现对数据查询和处理产生了挑战。研究了MapReduce框架下移动对象的并行Skyline计算问题,采用基于角度划分的方法解决负载平衡问题,并提出了一种过滤策略进行剪枝提高计算效率,在此基础上分别实现了静态Skyline算法和基于事件跟踪的MR-Track算法。最后通过对比实验验证了算法的有效性。     

延迟容忍网络中基于邻居信息精确度的查询算法

与传统网络不同,延迟容忍网络(DTN)具有节点移动性、网络间歇连通性,并且能够容忍适当的延迟。随着移动设备的普及,如何在延迟容忍网络中充分利用这些移动设备进行数据查询及信息分享成为值得研究的问题。一般网络可以采用泛洪的方法进行信息的查询,然而这类方法会消耗较多的网络通信资源及移动设备电池能量。针对这一问题,模仿社会网络中人的自然行为特点,充分利用信息精确度(IA)机制提高网络查询成功率。实验结果表明,基于IA的方法具有高效性和稳定性。     

大型数据库中基于邻域连接的层次聚类算法

提出了一种基于邻域连接的层次聚类算法HANL,该算法首先采用分割的方法将数据集划分为若干个子簇,通过对子簇间的连接的分析,建立子簇间的连接构成图,图中带权的边代表了子簇间的连接紧密度。合并连接紧密度高的结点,得到最后的聚类结果。该算法适用于高维数据集,能够对任意形状的簇进行聚类,无论对于数值属性的数据库还是分类属性的数据库都是一个有效的聚类方法。同时这种方法聚类速度快,效率高,具有良好的伸缩性。     

基于索引的子图查询技术研究进展

图作为表示实体间的数据结构，在社区发现、生物化学分析、社会安全分析等数据关联性要求较高的领域有着广泛的应用。对于大规模数据下进行实时的图查询问题，通过构建合适的索引可以有效降低查询响应时间，提高查询精确度。首先介绍基于索引的子图查询算法的基本结构；然后按索引的构建方式将主流算法分为基于枚举的方法和基于频繁模式挖掘的方法两大类，分别从索引特征、索引结构、应用数据集等方面进行介绍和分析；最后对基于索引的子图查询算法面临的主要问题进行总结和分析，阐述了最新的分布式系统下图查询技术，并对未来趋势进行展望。