基于噪声数据流的高效相似匹配算法

由于在金融分析、环境监测、网络服务等重要领域的良好应用前景,基于数据流的相似匹配算法成为数据库研究的热点之一.在实际应用中,数据流噪声大量存在且难以被完全过滤,因此,处理噪声数据流上的相似匹配问题显得尤其重要.为解决该问题,首先提出了一种新的距离定义,K-Match距离,由于其可以避免噪声数据参与运算,因而具有较强的抗噪性能.在此定义基础上,提出了一种高效的流式匹配算法SKM. SKM通过保留历史信息,能够随着数据流的更新及时返回匹配结果.最后,通过实验进一步证明,该算法能够有效地在噪声数据流中找到相似子序列.     

EDOLOIS:高效准确的子空间局部离群点发现

离群点检测在数据挖掘方面是一项很重要的技术，它是要发现那些行为异常的少量数据，这在数据挖掘的许多领域都有很强的现实意义，如金融欺诈，网络监控等领域．给出了一个高效准确的子空间局部离群点发现的算法(efficient discovery of local outliers in subspaces，简称 EDOLOIS)，来避免距离计算的高代价．算法充分利用了原始LOF的信息和特点，结合子空间和原空间的关系，从而能够精确且高效地算出子空间局部离群系数，进而甄别出离群点．形式的分析和严格证明都揭示了该算法对在高维种属属性的数据集中发现局部离群点是高效精确的.     

基于高维空间的在线高效子空间Skyline算法——CSky

Skyline计算是要发现数据集中不被其他点支配的所有点的集合.近来,它在实时在线服务方面的良好应用前景,使其成为数据库研究领域的一个热点.实际应用中,用户通常期望快速、渐进地返回Skyline计算结果,因此文中主要讨论了高维空间子空间Skyline渐进查询问题.据我们所知,现有的Skyline计算方法都不能直接或者通过简单修改来高效解决该种查询问题.BNL(Blocked Nested Loop)算法是一个可用来进行子空间Skyline计算的算法,但是,该方法低效且非渐进.基于此,文中提出了在线高效子空间Skyline算法--CSky(Count the Skyline).该算法充分利用了一个新颖数据结构--InvertS的特征,即通过对目标数据集进行排序,存放最可能为Skyline点的数据于算法优先扫描的位置,这使得CSky算法能高效计算出任意子空间上的Skyline;同时,CSky每次计算子空间Skyline查询时,至多访问一遍数据库;再有,算法扫描一个点时,只需和当前已发现的Skyline点进行比较即能判断该点是否为Skyline点,保证了算法的渐进性.这样,相比BNL,CSky大大减少了计算开销,具有其他基于索引的Skyline算法计算Skyline时的高效,且这种高效适用于所有子空间.理论分析和实验表明,在解决高维空间子空间Skyline查询问题方面,CSky性能大大优于BNL.