Efficient Computation of κ-Medians over Data Streams Under Memory Constraints

In this paper, we study the problem of efficiently computing k-medians over high-dimensional and high speed data streams. The focus of this paper is on the issue of minimizing CPU time to handle high speed data streams on top of the requirements of high accuracy and small memory. Our work is motivated by the following observation: the existing algorithms have similar approximation behaviors in practice, even though they make noticeably different worst case theoretical guarantees. The underlying reason is that in order to achieve high approximation level with the smallest possible memory, they need rather complex techniques to maintain a sketch, along time dimension, by using some existing off-line clustering algorithms. Those clustering algorithms cannot guarantee the optimal clustering result over data segments in a data stream but accumulate errors over segments, which makes most algorithms behave the same in terms of approximation level, in practice. We propose a new grid-based approach which divides the entire data set into cells (not along time dimension). We can achieve high approximation level based on a novel concept called (1-∈)-dominant. We further extend the method to the data stream context, by leveraging a density-based heuristic and frequent item mining techniques over data streams. We only need to apply an existing clustering once to computing k-medians, on demand, which reduces CPU time significantly. We conducted extensive experimental studies, and show that our approaches outperform other well-known approaches.     

一种面向聚类的对数螺线数据扰动方法

面向挖掘应用的隐私保护数据发布要求对数据集进行隐藏的同时维持数据的挖掘可用性,数据扰动是解决该问题的有效方法.现有的面向聚类的数据扰动方法难以兼顾原始数据个体隐私和维持数据聚类可用性,对此提出了一种基于对数螺线的隐私保护数据干扰方法.通过构建面向聚类的隐私保护数据扰动模型,利用对数螺线对原始数据进行扰动隐藏,维持原始数据的k邻域关系稳定,实现数据集聚类可用性的有效维护;进一步提出多重对数螺线扰动的策略,提高隐私保护强度.理论分析和实验结果表明:文中方法能够有效地避免数据隐私泄露,同时维持数据的聚类可用性.     

HilAnchor: Location Privacy Protection in the Presence of Users’ Preferences

Location privacy receives considerable attentions in emerging location based services.Most current practices however either ignore users’ preferences or incompletely fulfill privacy preferences.In this paper,we propose a privacy protection solution to allow users’ preferences in the fundamental query of k nearest neighbors (kNN).Particularly,users are permitted to choose privacy preferences by specifying minimum inferred region.Via Hilbert curve based transformation,the additional workload from users’ preferences is alleviated.Furthermore,this transformation reduces time-expensive region queries in 2-D space to range the ones in 1-D space.Therefore,the time efficiency,as well as communication efficiency,is greatly improved due to clustering properties of Hilbert curve.Further,details of choosing anchor points are theoretically elaborated.The empirical studies demonstrate that our implementation delivers both flexibility for users’ preferences and scalability for time and communication costs.     

标签集约束近似频繁模式的并行挖掘

近似频繁模式衍生于频繁模式,综合了频繁项集与频繁子图的特点。针对该模式的研究集中在无标签图上,其应用场景主要为社交网络、语义网络、智能电网等。近似频繁模式挖掘过程同时涉及频繁项集挖掘和频繁子图挖掘,因此已有的处理频繁模式挖掘算法无法较好地解决近似频繁模式挖掘问题。基于近似频繁模式结构,将其拓展到带标签图中,引入标签集约束,并设计标签集约束近似频繁模式挖掘算法LCPP（Label-Constraint Proximity Pattern）,该算法并行部署在MapReduce计算模型中,弥补了开源pFP算法处理大规模数据时效率不高的缺点。实验结果验证了该算法的有效性和可扩展性,表明了LCPP算法是pFP算法的极佳补充。     

X-Hop:传递闭包的多跳数压缩存储和快速可达性查询

海量图数据上的可达性查询是图数据管理的基本问题。目前解决这个问题的基本方法是对可达关系传递闭包进行压缩存储,再辅以快速查询算法来回答两顶点是否可达。在此基础上,重点研究了稠密图条件下可达传递闭包的高压缩比存储和有效查询算法,提出了多跳(简称为X-Hop)压缩存储方法。通过采用生成树的结构对2-Hop中的中心顶点进行组织,X-Hop存储有效地降低了2-Hop方法中需要记录的索引点数量,从而极大地提高了压缩比。实验证明,X-Hop在索引的规模上要远远小于2-Hop存储,并且在查询效率上也取得优势。     

面向聚类的数据隐藏发布研究

数据隐藏发布在保护数据隐私和维持数据可用性间寻求一种折中,近年来得到了研究者的持续关注.数据隐藏发布的起因和目标都源于数据的使用价值,聚类作为实现数据深层使用价值的一个重要步骤,在数据挖掘领域得到了广泛的研究.聚类对数据个体特征的依赖与隐藏操作弱化个体特征的主导思想间的矛盾,使得面向聚类的数据隐藏发布成为一个难点.对面向聚类的隐私保护数据发布领域已有研究成果进行了总结,从保存聚类特征粒度的角度,分析保存聚类特征粒度与聚类可用性、隐私保护安全性间的关系;从维持数据聚类可用性效果角度对匿名、随机化、数据交换、人工合成数据替换等主要隐藏方法的原理、特点进行了分析.在对已有技术方法深入对比分析的基础上,指出了面向聚类的数据隐藏发布领域待解决的一些难点问题和未来发展方向.     

基于动态试题难度参数的智能组卷策略*

针对网络考试系统的即时性和高效性,提出了基于动态试题难度参数的智能组卷算法的设计策略,利用二项分布函数做难度曲线分布模型,结合目标函数对试题多种参数进行优化。根据试卷的整体难度,以试题难度参数为优先,运用试题选题参数调节知识点之间的平衡,试题曝光参数选取出卷频率比较低的试题,从而确定各种题型不同试题难度数量,实现快速自动组卷的目标。     

基于本体的商品推荐方法

文中主要针对目前大多数推荐系统所存在的冷启动问题和用户兴趣漂移问题提出基于本体的解决方案。该方案首先运用关联规则挖掘算法对已有的用户数据进行挖掘,生成规则库。接着利用推理机结合规则库和商品与客户本体进行推理,从推理结果中选择与当前用户所浏览的商品相比具有较高相似性的商品向用户推荐。该方案考虑到用户个性化的需求,帮助用户找到所需商品,从而将用户从浏览者转变为购买者,提高了用户的忠诚度,给企业带来效益。     

一种向量等价置换隐私保护数据干扰方法

近年来,隐私保护数据发布得到了研究者的广泛关注,聚类与隐藏原理上的差异使得面向聚类的隐藏成为难点.针对现有保距和保分布隐藏难以有效兼顾数据聚类可用性和隐私安全的不足,提出基于保邻域隐藏的扰动算法VecREP(vector equivalent replacing based perturbing method),通过分析数据点邻域组成结构,引入能够保持数据邻域组成稳定的安全邻域定义.进一步基于向量偏移与合成思想,提出有效保持邻域数据分布特征的等价置换弧.对任意数据点,采用随机选取位于其安全邻域内等价置换弧上点替换的策略实现隐藏.将算法与已有的RBT,TDR,Camp-crest和NeNDS算法进行实验比较,结果表明:VecREP算法具有与保距隐藏算法RBT相近的聚类可用性,优于其余算法,能够较好地维持数据聚类的可用性.同时,具有好于其余算法的数据隐私保护安全性.     

一种实时监控最近邻的近似算法

处理分布式环境下高速数据的最大挑战在于如何利用少量网络资源输出高质量的查询结果。对面向分布式环境的最近邻查询问题进行了研究,提出了一种基于过滤器的新方法,不仅能计算精确查询结果,还能够处理五类近似查询。该方法在各个远程站点均安装了智能过滤器,并通过合理设置过滤器的范围来降低数据传输量。理论分析及基于模拟数据集合和真实数据集合的实验报告均表明新方法具有较高的性能。