数据流中随机型分形维数计算方法研究

第３８卷　第４期 ２０１１年４月 计 算 机 科 学 Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ Ｖｏｌ．３８Ｎｏ．４ Ａｐｒ　２０１１ 到稿日期：２０１０－０５－１３　返修日期：２０１０－０８－０４　　本文受国家自然科学基金（７０８７１０３３，７０８０１０２５），国家高技术研究发展 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 （８６３）（２００７ＡＡ０４ Ｚ１１６），合肥工业大学校科学研究发展基金（２００９ＨＧＸＪ００４０）资助。 倪志伟（１９６３－），男，教授，博士生导师，主要研究方向为人工智能、机器学习；公维峰（１９８６－），男，硕士生，主要研究方向为分形与数据挖掘； 周之强（１９８７－），男，硕士生，主要研究方向为联机 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 挖掘。 数据流中随机型分形维数计算方法研究 倪志伟　公维峰　周之强　唐李洋 （合肥工业大学管理学院　合肥２３０００９）　（过程优化与智能决策教育部重点实验室　合肥２３０００９） 　 摘　要　分形维数能够有效地描述数据集，反映复杂数据集中隐含的规律性，基于分形理论的数据挖掘算法通常都涉 及到分形维数的计算。但是现有的分形维数计算方法的时间复杂度和空间复杂度都比较高，大大降低了算法的效率， 使算法很难适应高速、海量的数据流环境。因此， 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 分析了现有的几种分形维数计算方法，并提出一种随机型方法， 利用固定的内存空间快速估计数据流的关联维数。最后通过与现有算法进行对比实验，证明了这一随机型算法的有 效性。 关键词　分形，分形维数，数据流 中图法分类号　ＴＰ３０１．６　　　文献标识码　Ａ 　 Ｒｅｓｅａｒｃｈ　ｏｆ　Ｓｔｏｃｈａｓｔｉｃ　Ｆｒａｃｔａｌ　Ｄｉｍｅｎｓｉｏｎ　Ｃａｌｃｕｌａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　ｉｎ　Ｄａｔａ　Ｓｔｒｅａｍ ＮＩ　Ｚｈｉ－ｗｅｉ　ＧＯＮＧ　Ｗｅｉ－ｆｅｎｇ　ＺＨＯＵ　Ｚｈｉ－ｑｉａｎｇ　ＴＡＮＧ　Ｌｉ－ｙａｎｇ （Ｓｃｈｏｏｌ　ｏｆ　Ｍａｎａｇｅｍｅｎｔ，Ｈｅｆｅｉ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈｅｆｅｉ　２３０００９，Ｃｈｉｎａ） （Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｐｒｏｃｅｓｓ　Ｏｐｔｉｍｉｚａｔｉｏｎ　ａｎｄ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｄｅｃｉｓｉｏｎ－ｍａｋｉｎｇ，Ｍｉｎｉｓｔｒｙ　ｏｆ　Ｅｄｕｃａｔｉｏｎ，Ｈｅｉｆｅｉ　２３０００９，Ｃｈｉｎａ） 　 Ａｂｓｔｒａｃｔ　Ｆｒａｃｔａｌ　ｄｉｍｅｎｓｉｏｎ　ｃａｎ　ｄｅｓｃｒｉｂｅ　ｔｈｅ　ｄａｔａ　ｓｅｔ　ｅｆｆｅｃｔｉｖｅｌｙ　ａｎｄ　ｃａｎ　ｒｅｆｌｅｃｔ　ｔｈｅ　ｈｉｄｄｅｎ　ｒｅｇｕｌａｒｉｔｙ　ｏｆ　ｔｈｅ　ｃｏｍｐｌｅｘ　ｄａ－ ｔａ　ｓｅｔ．Ｄａｔａ　ｍｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｂａｓｅｄ　ｏｎ　ｆｒａｃｔａｌ　ｔｈｅｏｒｙ　ａｒｅ　ｕｓｕａｌｌｙ　ｒｅｌａｔｅｄ　ｔｏ　ｔｈｅ　ｃａｌｃｕｌａｔｉｏｎ　ｏｆ　ｆｒａｃｔａｌ　ｄｉｍｅｎｓｉｏｎ．Ｂｕｔ ｍｏｓｔ　ｏｆ　ｔｈｅ　ｅｘｉｓｔｉｎｇ　ｆｒａｃｔａｌ　ｄｉｍｅｎｓｉｏｎ　ｃａｌｃｕｌａｔｉｏｎ　ａｌｇｏｒｉｔｈｍｓ　ａｒｅ　ｗｉｔｈ　ｈｉｇｈ　ｔｉｍｅ　ｃｏｍｐｌｅｘｉｔｙ　ａｎｄ　ｓｐａｃｅ　ｃｏｍｐｌｅｘｉｔｙ，ｗｈｉｃｈ ｇｒｅａｔｌｙ　ｒｅｄｕｃｅｓ　ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ａｎｄ　ｉｓ　ｎｏｔ　ａｐｐｌｉｃａｂｌｅ　ｆｏｒ　ｄａｔａ　ｓｔｒｅａｍ　ｗｉｔｈ　ｈｉｇｈ－ｓｐｅｅｄ　ａｎｄ　ｍａｓｓｉｖｅ　ｄａｔａ．Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｓｅ－ ｖｅｒａｌ　ｅｘｉｓｔｉｎｇ　ｆｒａｃｔａｌ　ｄｉｍｅｎｓｉｏｎ　ｃａｌｃｕｌａｔｉｏｎ　ａｌｇｏｒｉｔｈｍｓ　ｗｅｒｅ　ａｎａｌｙｚｅｄ　ａｎｄ　ａ　ｓｔｏｃｈａｓｔｉｃ　ｆｒａｃｔａｌ　ｄｉｍｅｎｓｉｏｎ　ｃａｌｃｕｌａｔｉｏｎ　ａｌｇｏ－ ｒｉｔｈｍ　ｗｅｒｅ　ｐｒｏｐｏｓｅｄ　ｔｏ　ｆａｓｔ　ｅｓｔｉｍａｔｅ　ｔｈｅ　ｃｏｒｒｅｌａｔｉｏｎ　ｄｉｍｅｎｓｉｏｎ　ｉｎ　ｆｉｘｅｄ　ｓｐａｃｅ．Ｔｈｅ　ｃｏｍｐａｒａｔｉｖｅ　ｅｘｐｅｒｉｍｅｎｔ　ａｎｄ　ａｎａｌｙｓｉｓ ｄｅｍｏｎｓｔｒａｔｅ　ｔｈｅ　ｅｆｆｅｃｔｉｖｅｎｅｓｓ　ｏｆ　ｔｈｉｓ　ｓｔｏｃｈａｓｔｉｃ　ｆｒａｃｔａｌ　ｄｉｍｅｎｓｉｏｎ　ｃａｌｃｕｌａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ　Ｆｒａｃｔａｌ，Ｆｒａｃｔａｌ　ｄｉｍｅｎｓｉｏｎ，Ｄａｔａ　ｓｔｒｅａｍ 　 １　引言 分形理论是现代非线性科学研究中十分活跃的一个数学 分支，它利用整体与局部间具有的自相似性，揭示复杂现象中 所蕴含的规律。分形维数是描述具有分形特征物体的重要指 标，可以定量地分析分形集的复杂程度。近几年，许多学者的 研究表明［２－５］分形维数在数据挖掘领域有着非常特殊的作用， 将分形技术应用于数据挖掘领域能够更好地克服传统数据挖 掘技术的不足，有效地解决在结构复杂、高维数据集上的数据 挖掘问题［１］。目前，对于快速到达、潜在无限的数据流环境的 挖掘已经成为数据挖掘的一个重要的研究方向，而分形维数 计算的低效使得在数据流挖掘中应用分形理论面临着困难。 在数据流的挖掘中，用精度换取效率是一种常用的方法。同 时，准确的分形维数很难得到，人们往往更关心分形维数的相 对大小和分形维数的变化情况，计算分形维数时常用的盒计 数法（ｂｏｘ－ｃｏｕｎｔｉｎｇ）计算出来的分形维数本身就是对分形维 数的一种估计。因此，在数据流环境中，对分形维数进行高效 和准确的估计具有重要的意义。 ２　相关研究 分形是自然界中普遍存在的现象。分形体具有自相似 性，即局部与整体相似。大量实际数据集具有分形特征，即数 据集的部分分布与整体分布有相似的结构或属性。在实际数 据集中，这种自相似性一般表现为统计意义上的自相似性。 分形理论的创始人 Ｍａｎｄｅｌｂｒｏｔ认为分形集这类奇异集合的 性质不能用欧氏测度来衡量，但维数恰是此类集合尺度变化 下的不变量，因此主张用维数来刻画这类集合。 定义１（分形维数）　对于一个在区间［ｒｍｉｎ，ｒｍａｘ］（无标度 区间）内呈现统计自相似特征的Ｅ维数据集，数据点落在边 长为ｒ的Ｅ 维单元格内的概率为ｐｉ，则分形维数为 Ｄｑ＝ １ ｑ－１ ｌｏｇ∑ ｉ ｐｑｉ ｌｏｇｒ ｒ∈ ［ｒｍｉｎ，ｒｍａｘ］ （１） 当ｑ＝０时为豪斯道夫维数，ｑ→１时为信息维，而ｑ＝２时 为关联维。 计算一个Ｅ维数据集的分形维数时，首先将数据集划分 为Ｌ层网格结构。第一层对每一维２等分，得到２Ｅ 个Ｅ 维 ·９０２· 网格；第二层对每一维４等分，得到２２Ｅ个Ｅ 维网格；直到第Ｌ 层，对每一维Ｌ等分，得到２ＬＥ个Ｅ 维网格。然后计算每一层 划分中数据点落入每一非空网格的概率ｐｉ＝ｃｉ／ｎ，其中ｃｉ 为 第ｉ个网格中落入的数据点数，ｎ为总数据点数。根据式（１） 拟合得到分形维数。 对于实时的、连续的、潜在无界的事件序列构成的数据 流，由于不能将快速到达的数据全部存在主存中，因此与计算 静态数据集分形维数相比，要求其算法时间和空间上更高效。 此外，数据流上计算分形维数还要满足以下几点要求： １）新到达的数据可能超出了原有的数据取值范围，要能 够进行简单快速的调整使取值范围适应新数据。 ２）能够满足人们的查询要求，根据输入的查询参数输出 指定查询范围内的分形维数。 基于分形理论的数据挖掘算法一般都离不开分形维数的 计算，研究者们在提出算法的同时也提出了不同分形维数的 计算方法。同时有研究者专门针对分形维数的计算方法进行 了研究。这些算法可以分为两大类：一类是确定型算法，另一 类是随机型算法。 确定型算法是指在计算分形时能准确得到落入每个非空 网格中的数据点的个数。文献［２－６］中的算法都属于确定性 算法。文献［２－５］中的算法只适用于静态数据集，其中文献 ［２，３］中的方法比较具有代表性，前者利用树结构存储所有非 空网格信息，后者利用基于Ｚ－ｏｒｄｅｒｉｎｇ编码的网格结构存储 所有非空网格信息。文献［６］在树结构的基础上引入了滑动 窗口，使算法适用于数据流环境，但只能支持较小的窗口。 这些确定型算法的共同点在于最终都得到了每个非空网 格中的数据点数，区别主要是使用了不同的数据结构。每一 层网格结构中，这类算法要保存非空网格中的数据点数，至少 需要Ｏ（ｎ＊ｌｏｇｎ）的空间，其中ｎ为非空网格个数；还要保存 每个网格的坐标，需要Ｏ（Ｅ）的空间，其中Ｅ为数据集维数。 在海量的数据流中，非空网格的数量也将非常巨大，因此确定 型算法计算数据流的分形维数只能通过一个较小的滑动窗口 来实现，对数据流的考察范围比较有限。 随机型算法是指在划分出来的每一层网格结构中，使用 一些随机算法来估计∑ｆｑｉ，其中ｆｉ为落入每个非空网格中的 数据点数。为达到这一目的，一般构建随机变量Ｘ，使Ｅ（Ｘ） ＝ ∑ｆｑｉ，Ｄ（Ｘ）较小，通过切比雪夫不等式可知，得到的估计 值在较大概率下与真实值的误差可以满足阈值要求。文献 ［７］中的方法属于随机型算法，使用固定的空间估计关联维 数，其理论来源为文献［８］的ｔｕｇ－ｏｆ－ｗａｒ思想。但是算法不够 灵活，只能计算整个数据流的分形维数，而且更新数据时要同 时更新所有ｓ１＊ｓ２ 个计数器。 确定型算法和随机型算法比较： １）确定型算法计算出的分形维数更准确，但需要较高的 时间复杂度和空间复杂度。 ２）随机型算法只需要固定的空间和较低的时间复杂度， 更适用于数据流环境。 ３）确定型算法对于ｑ的取值不敏感，使用相同的数据结 构可以计算出ｑ取不同值时的分形维数；随机型算法在ｑ≤２ 时比较简单，随着ｑ增大算法复杂度明显提高。 ３　基于窗口计数器的多层ＣｏｕｎｔＳｋｅｔｃｈ结构 为了可以根据输入的查询参数估算指定查询范围内的分 形维数，本文引入了基于窗口计数器的多层ＣｏｕｎｔＳｋｅｔｃｈ结 构，使用到的基本定义如下。 定义２（ｋ－ｕｎｉｖｅｒｓａｌ哈希 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 ［９－１１］）　首先定义［ｎ］＝｛０， １，…，ｎ－１｝，如果一组从［ｎ］映射到［ｍ］的哈希函数为ｋ－ｕｎｉ－ ｖｅｒｓａｌ哈希函数族，则满足以下条件：对任意不相等的ｘ０，ｘ１， …，ｘｋ－１∈［ｎ］和任意的ｖ０，ｖ１，…，ｖｋ－１∈［ｍ］， Ｐｒｈ∈Ｈ｛ｈ（ｘｉ）＝ｖｉ，ｉ∈［ｋ］｝＝１／ｍｋ 定义３（窗口计数器）　窗口计数器是这样的一种数据结 构：它包含计数器最后一次更新的时标Ｔｕ 和循环列表Ｌｉｓｔ， 并采用延迟更新机制来避免频繁的维护，即在更新计数器或 输出结果时，将过期窗口对应的数据设为０，再将当前窗口对 应的信息保存到Ｌｉｓｔ的相应位置。 定义４（改进的ＣｏｕｎｔＳｋｅｔｃｈ结构）　改进的ＣｏｕｎｔＳｋｅｔｃｈ 结构是由ｔ×ｍ 个窗口计数器ｃｏｕｎｔｅｒ、ｔ个包含ｍ 个桶的哈 希表和ｔ个从对象到｛１，…，ｍ｝的４－ｕｎｉｖｅｒｓａｌ哈希函数组成的 数据结构。其中ｔ个哈希表的每个元素是一个窗口计数器。 与文献［１２］中定义的ＣｏｕｎｔＳｋｅｔｃｈ结构相比，该结构减 少了ｔ个从对象映射到｛１，－１｝的４－ｕｎｉｖｅｒｓａｌ哈希函数，并且 使用窗口计数器代替了整数计数器。 对于一个支持ｗ个基本窗口的窗口计数器，其循环列表 Ｌｉｓｔ包含ｗ 个元素，每个元素可以对应一个大小为Ｓｉｚｅｂ 的 基本窗口。如果单独使用具有窗口计数器的ＣｏｕｎｔＳｋｅｔｃｈ结 构，面临的问题是如果基本窗口过小，要支持较大的查询粒度 时就需要多个窗口，这使得计数器占用的空间变大，更新速度 变慢。同样，如果使用的基本窗口过大，又降低了查询的精 度。为了解决这一矛盾，提出了基于窗口计数器的多层Ｃｏｕ－ ｎｔＳｋｅｔｃｈ结构。其基本结构如图１所示。 图１　多层ＣｏｕｎｔＳｋｅｔｃｈ结构图 不难发现ＣｏｕｎｔＳｋｅｔｃｈ结构具有可加性，即对于连续的 数据流段Ｓ１，Ｓ２，…，Ｓｎ，其所对应的 ＣｏｕｎｔＳｋｅｔｃｈ结构为 ＣＳ１，ＣＳ２，…，ＣＳｎ。如果其参数都相同，则将ＣＳ１，ＣＳ２，…， ＣＳｎ 对应位置相加，得到新的ＣｏｕｎｔＳｋｅｔｃｈ结构ＣＳ，则ＣＳ与 数据流Ｓ＝｛Ｓ１，Ｓ２，…，Ｓｎ｝产生的具有相同参数的 Ｃｏｕ－ ｎｔＳｋｅｔｃｈ结构相同。因此可以使用分层结构，根据输入的参 数建立起Ｐ层具有相同参数的ＣｏｕｎｔＳｋｅｔｃｈ的分层结构。每 一个ＣｏｕｎｔＳｋｅｔｃｈ结构中使用包含ｗｉ 个大小为ｂｉ 的基本窗 口的窗口计数器，其中ｉ∈｛１，２，…，Ｐ｝。只有最底层的Ｃｏｕ－ ｎｔＳｋｅｔｃｈ需要ｔ个哈希函数处理原始数据流，其它层不需要 哈希函数。在除最高层以外的任何一层中，如果一个窗口过 期，则作为上一层的一个点将这个窗口中的数据加到上一层 对应位置的计数器中。当需要输出结果时，将查询参数Ｎ 分 解，得到所有包含在查询范围内的窗口。将各层查询范围内 窗口中的数据相加，合并成一个单一的ＣｏｕｎｔＳｋｅｔｃｈ结构。 ４　基于多层ＣｏｕｎｔＳｋｅｔｃｈ结构的随机型关联维数算 法 　　随机型算法计算关联维数时，划分完Ｌ层网格结构后， ·０１２· 需要计算每一层划分中∑ ｉ ｐ２ｉ的值。由于∑ ｉ ｐ２ｉ＝∑ ｉ Ｃ２ｉ Ｎ２＝ １ Ｎ２∑ｉ Ｃ２ｉ，Ｃｉ为每个非空网格中落入的数据点数，Ｎ 为总点数。其 中Ｎ 可以通过计数的方式获得，因此需要估计的是Ｆ２＝∑ ｉ Ｃ２ｉ。４．１节介绍在每一层网格结构中，如何基于窗口计数器 的多层ＣｏｕｎｔＳｋｅｔｃｈ结构估计Ｆ２。４．２节介绍如何通过Ｆ２ 的估计算法估计数据流的关联维数。 ４．１　Ｆ２ 估计算法 定义５（Ｆ２ 的（ε，δ）估计）　对于给定的参数０＜ε＜１和 ０＜δ＜１，得到Ｆ２ 的估计值Ｆ ∧ ２，使得Ｐｒ（｜Ｆ ∧ ２－Ｆ２｜＞εＦ２）＜ １－δ，叫做Ｆ２ 的（ε，δ）估计。即以大于δ的概率保证估计值 Ｆ ∧ ２ 与真实值Ｆ２ 之间的误差不超过εＦ２。 通过输入不断到达的数据的坐标，可以得到Ｆ２ 的（ε，δ） 估计。具体过程如下： Ｓｔｅｐ１　建立多层ＣｏｕｎｔＳｋｅｔｃｈ结构，参数为ｔ和ｍ。ｈ１， ｈ２，…，ｈｔ为相互独立的从坐标到｛１，…，ｍ｝的４－ｕｎｉｖｅｒｓａｌ哈 希函数。 Ｓｔｅｐ２　插入数据，执行Ｓｔｅｐ３；输出结果，执行Ｓｔｅｐ４。 Ｓｔｅｐ３　ｔ个哈希函数ｈｊ，ｊ∈（１，ｔ）分别将数据坐标ｇｉ＝ ｛ｇｉ１，ｇｉ２，…，ｇｉＥ｝映射到｛１，２，…，ｍ｝，更新最底层 Ｃｏｕ－ ｎｔＳｋｅｔｃｈ结构中的ｔ个计数器，使ｃｏｕｎｔｅｒｈｊ（ｇｉ）＋＝１。 Ｓｔｅｐ４　多层结构输出结果，即所有包含在查询范围内的 窗口合并成一个ＣｏｕｎｔＳｋｅｔｃｈ结构。由其中的ｔ个哈希表根 据式（２）计算出ｔ个估计值Ｘ１，Ｘ２，…，Ｘｔ，返回它们的中位数 作为估计结果。 Ｘ＝ｍ＋１ｍ ∑ｉ∈［ｍ］ｃｏｕｎｔｅｒ ２ ｉ－１ｍ （∑ ｉ∈［ｍ］ ｃｏｕｎｔｅｒｉ）２ （２） 式中，ｃｏｕｎｔｅｒｉ为哈希函数映射到哈希表第ｉ个位置的元素个 数。用ａ，ｂ代表任意可能的非空网格，ｆａ，ｆｂ 为其中落入的 点数，可知 ∑ ｉ∈［ｍ］ ｃｏｕｎｔｅｒ２ｉ＝ ∑ ｈ（ａ）＝ｈ（ｂ） ｆａｆｂ ＝∑ ａ＝ｂ ｆ２ａ＋ ∑ ａ≠ｂ∧ｈ（ａ）＝ｈ（ｂ） ｆａｆｂ（∑ ｉ∈［ｍ］ ｃｏｕｎｔｅｒｉ）２ ＝∑ ａ，ｂ ｆａｆｂ ＝∑ ａ＝ｂ ｆ２ａ＋ ∑ ａ≠ｂ∧ｈ（ａ）＝ｈ（ｂ） ｆａｆｂ＋ ∑ ｈ（ａ）≠ｈ（ｂ） ｆａｆｂ 于是Ｘ＝Ｆ２＋ ∑ ａ≠ｂ∧ｈ（ａ）＝ｈ（ｂ） ｆａｆｂ－１ｍ ∑ｈ（ａ）≠ｈ（ｂ）ｆａｆｂ 。根据ｋ－ｕｎｉ－ ｖｅｒｓａｌ哈希函数的概念，可以得出［９］ Ｅ（Ｘ）＝Ｆ２，Ｄ（Ｘ）＝２ｍ （Ｆ２２－Ｆ４） Ｐｒ（｜Ｘ－Ｆ２｜＞εＦ２）＜Ｄ （Ｘ） ε２　Ｆ２２＜ ２Ｆ２２ ｍε２　Ｆ２２ 令ｍ＝ ２ ε２（１－δ） ，可以得到Ｘ为Ｆ２ 的（ε，δ）估计。 ４．２　随机型关联维数算法 为了计算关联维数，首先将Ｅ维数据流Ｘ 划分为Ｌ层网 格结构。设Ｘ的第ｊ维的最大值为 ｍａｘｊ，最小值为 ｍｉｎｊ，则 Ｘ第ｊ维的取值空间长度Ｒｊ＝ｍａｘｊ－ｍｉｎｊ。对于一个新到 的数据点ｘｉ＝｛ｘｉ１，ｘｉ２，…，ｘｉＥ｝，计算其在每一层网格结构中 的坐标。在第ｋ层划分中，ｋ∈｛１，２，…，Ｌ｝，网格的边长ｒｋｊ＝ Ｒｊ／２ｋ－１，ｘｉ坐标编码为（ｇ１，ｇ２，…，ｇＥ），ｇｉ 根据式（３）得到。 将计算出的数据点在每一层网格结构中的坐标作为Ｆ２ 估计 算法的输入，计算出每层网格结构中Ｆ２ 的估计值，进而根据 式（１）拟合得到关联维数的估计值。 ｇｉ＝ ｘｉｊ－Ｍｊ ｒｋｊ （３） 式中，Ｍｊ＝Ｍｉｎｊ＋ Ｒ ２ 。 数据流中，计算一个新到达的数据点在每一层网格结构 中的坐标时，可能出现数据点取值超出原有取值范围的情况， 这需要对取值空间进行调整。具体方法如下： 输入：每一维的最大值ｍａｘｊ，最小值ｍｉｎｊ，数据点ｘｉ 输出：调整后的ｍａｘｊ，ｍｉｎｊ，Ｌ Ｗｈｉｌｅ（点超出取值空间） ｛ Ｆｏｒ　ｊ＝１ｔｏ　Ｅ 　Ｉｆ（ｘｉｊ＞ｍａｘｊｏｒ　ｘｉｊ＜ｍｉｎｊ） 　　Ｌ＝Ｌ＋１； 　　Ｆｏｒ　ｋ＝１ｔｏ　Ｅ 　　　　ｍｉｎｋ＝ｍｉｎｋ－Ｒｋ／２； 　　　　ｍａｘｋ＝ｍａｘｋ＋Ｒｋ／２； 　　　　Ｒｋ＝２＊Ｒｋ 　　Ｅｎｄ　ｆｏｒ 　Ｅｎｄ　ｉｆ Ｅｎｄ　ｆｏｒ ｝ 综上所述，基于多层ＣｏｕｎｔＳｋｅｔｃｈ结构的随机型关联维 数算法的具体过程如下： Ｓｔｅｐ１　初始化算法，得到每一维初始的最大值和最小 值。 Ｓｔｅｐ２　将Ｅ维空间划分为Ｌ层网格结构。 Ｓｔｅｐ３　为每一层网格结构构建估计Ｆ２ 所需的多层 ＣｏｕｎｔＳｋｅｔｃｈ结构。 Ｓｔｅｐ４　对于每一个新到达的数据点，检查其是否超出取 值范围，超出取值范围时做相应调整。计算出数据点在每一 层网格结构中的坐标。 Ｓｔｅｐ５　将坐标插入每一层网格结构的多层ＣｏｕｎｔＳｋｅｔｃｈ 结构中。 Ｓｔｅｐ６　计算出每一层网格结构中Ｆ２ 的估计值。 Ｓｔｅｐ７　由每一层网格结构中Ｆ２ 的估计值计算出∑ ｉ ｐ２ｉ， 根据式（１）拟合得到结果。 ５　实验验证 实验部分将本文的算法与文献［６］中的ＳＩＤ－ｍｅｔｅｒ算法、 文献［３］中的ＺＢＭＦＤ算法以及文献［７］中的ＴＯＷ 算法进行 了对比。其中ＴＯＷ 算法属于随机型算法，其余两种算法属 于确定型算法。５．１节主要进行计算结果精度方面的对比。 ＳＩＤ－ｍｅｔｅｒ和ＺＢＭＦＤ属于确定型算法，它们输出的分形维数 相同。这一结果是应用中最常用到的。通过将这一结果与本 文算法代表的随机型算法的计算结果进行比较，证明了本文 的随机型算法的计算结果与确定型算法的计算结果很接近。 ５．２节主要进行几种算法的时间空间效率的对比。 ５．１　结果精度对比实验 实验１　在Ｓｉｅｒｐｉｎｋｓｋｉ三角数据集对算法进行了测试， 并与确定型算法进行了比较。首先生成５０００个点的Ｓｉｅｒ－ ｐｉｎｋｓｋｉ数据集，并将所有点包含在窗口内。随机生成５个４－ ｕｎｉｖｅｒｓａｌ哈希函数。输出的５组估计值和确定型算法输出的 ·１１２· 估计值如图２所示。从图中可以看出确定型算法输出值的实 线被多条虚线覆盖，只有一条虚线产生了较大的偏差。对５ 组输出数据取中位数，去除了偏差曲线的影响，输出的分形维 数为１．５５８０，ＳＩＤ－ｍｅｔｅｒ和ＺＢＭＦＤ算法输出的结果相同，为 １．５５７８，ＴＯＷ算法得到的结果为１．５２０，Ｓｉｅｒｐｉｎｋｓｋｉ理论上的 分形维数为ｌｏｇ２３。几种算法的计算结果与理论值相差不大。 实验２　为了进一步测试对数据流分形维数的计算，合 成了这样一个数据流，其前１０００００条数据产生于科赫曲线， 后１０００００条数据产生于Ｓｋｉｅｒｐｉｎｋｓｋｉ三角。每隔４００００计算 一次分形维数，考察分形维数随数据流动而产生的变化。实 验结果如图３所示。 　图２　Ｓｉｅｒｐｉｎｋｓｋｉ数据集ｌｏｇ－ｌｏｇ 比较图 　图３　合成数据流分形维数变化 比较图 实验３　使用中国深市１９９１年４月３日至２００９年１０月 ２６日每天开盘、收盘、最高价、最低价、交易量、交易金额组成 的６维数据集进行了测试，由确定型算法和随机型算法分别 计算出每一层网格结构Ｆ２ 的估计值，考察Ｆ２ 的估计值和真 实之间的差距，结果如图４所示。可以看出２条曲线基本重 合，两者之间差距很小。每隔５００条数据计算一次分形维数， 结果如图５所示。 图４　股票数据集ｌｏｇ－ｌｏｇ比较图 　图５　股票数据集分形维数变化 比较图 实验４　使用 ＵＣＩ数据集Ｃｈａｒａｃｔｅｒ　Ｔｒａｊｅｃｔｏｒｉｅｓ前４００ 个样本中的６５０００条数据进行实验的结果如图６所示。实验 分别取数据集中的前两个属性和全部３个属性进行，可以看 出，随着属性的增加，分形维数增大。 图６　Ｃｈａｒａｃｔｅｒ　Ｔｒａｊｅｃｔｏｒｉｅｓ数据集ｌｏｇ－ｌｏｇ比较图 ５．２　算法效率分析 在算法效率方面，随机型算法时间和空间效率明显高于 确定型算法，且本文算法优于已有的随机型算法ＴＯＷ算法。 空间上，若最大划分层次为Ｌ，Ｌ一般较小，第Ｌ层网格 结构中非空网格个数最多为数据点数ｎ。ＳＩＤ－ｍｅｔｅｒ算法需 要保存整棵分形树，分形树每一层的结点个数最多为ｎ，需要 的空间为Ｏ（ｎ＊Ｌ）。ＺＢＭＦＤ保存的是最底层的网格结构， 相当于保存了分形树最底层的结点，需要的空间为Ｏ（ｎ）。这 两种确定型算法所需空间随着非空网格个数的增加而增大。 而非空网格个数最多等于总数据点数，因此只能通过较小的 滑动窗口来保存有限的数据点。本文算法需要的空间为 Ｏ（ｔ＊ｍ＊Ｐ＊Ｌ），其中Ｐ为多层结构的层次，ｔ和ｍ为Ｃｏｕｎｔ Ｓｋｅｔｃｈ结构的两个参数，相对于ｎ而言，所需的空间为Ｏ（１）， 与保存的数据点的个数无关。ＴＯＷ 算法所需的空间为为Ｏ （ｓ１＊ｓ２＊Ｌ），其中ｓ１＊ｓ２ 为所用的计数器的个数，相对于ｎ 而言所需的空间同样为Ｏ（１）。 时间上，计算分形维数分为两个阶段：第一阶段为插入数 据点，第二阶段为计算分形维数。若第Ｌ层网格结构中非空 网格个数为ｎ，在插入数据点过程中，ＺＢＭＦＤ算法插入一个 数据点时，需要查找要插入的点是否落入现有的非空网格。 如果落入现有的非空网格，则直接更新该网格信息，否则建立 一个新的非空网格。这一过程需要的时间为Ｏ（ｌｏｇｎ）。ＳＩＤ－ ｍｅｔｅｒ算法每一层网格结构中都需要做这样的判断，且每一 个网格包含的下一层非空网格最多为ｎ，因此需要的时间为 Ｏ（Ｌ＊ｌｏｇｎ）。ＴＯＷ 算法插入一个数据点需要计算ｓ１＊ｓ２＊ Ｌ个哈希函数的值，假定计算哈希函数的时间为 Ｏ（１），则 ＴＯＷ算法需要的时间为 Ｏ（ｓ１＊ｓ２＊Ｌ），对于ｎ而言需要的 时间为Ｏ（１）。本文算法插入一条数据需要计算ｔ＊Ｌ个哈希 函数的值，需要的时间为Ｏ（ｔ＊Ｌ），对于ｎ而言需要的时间同 样为Ｏ（１）。同时由于ｔ小于ｓ１＊ｓ２，因此本文算法优于ＴＯＷ 算法。在第二阶段计算分形维数过程中，ＺＢＭＦＤ算法需要 逐层合并出上层网格，由当前网格映射到上层网格需要的时 间为Ｏ（ｎ＋ｎ＊ｌｏｇｎ），可以认为是Ｏ（ｎ＊ｌｏｇｎ），映射的次数取 决于划分的层数，因此需要的时间为Ｏ（Ｌ＊ｎ＊ｌｏｇｎ）。ＳＩＤ－ ｍｅｔｅｒ算法只需要对分形树遍历进行累加，分形树最多有Ｌ＊ ｎ个结点，需要的时间为Ｏ（Ｌ＊ｎ）。ＴＯＷ 算法需要对ｓ１＊ｓ２ 个计数器进行统计，本文算法需要对ｔ＊ｍ 个计数器进行统 计，两者效率相当，但计数器的个数明显少于数据点数，因此 两种随机型算法的效率要高于两种确定型算法。 因此无论在空间效率还是时间效率，随机型算法 ＴＯＷ 和本文算法都优于确定型算法ＳＩＤ－ｍｅｔｅｒ和ＺＢＭＦＤ。ＴＯＷ 算法和本文算法在空间效率上相当，在时间效率上本文算法 优于ＴＯＷ算法。 结束语　现有的分形维数计算方法大体可以分为确定型 算法和随机型算法两类。本文着重对随机型算法进行研究并 提出了一种灵活高效的随机型分形维数算法。随机型分形维 数算法通过构建一组期望等于各非空网格中数据点数的ｑ次 幂之和且方差较小的随机变量，得到分形维数的估计值。这 一估计值以很高的概率与确定型算法算出的分形维数十分接 近，从而可以有效地估计分形维数且时间复杂度和空间复杂 度明显低于确定型分形维数计算方法，更适合快速、潜在无限 的数据流的挖掘。研究广义分形维数的估算方法和应用随机 型分形维数计算方法挖掘数据流中隐藏的规律，将是今后研 究的重点。 参 考 文 献 ［１］ 倪丽萍，倪志伟，吴昊，等．基于分形维数的数据挖掘技术研究综 述［Ｊ］．计算机科学，２００８，３５（１）：１８７－１８９ 　　　 （下转第２２９页） ·２１２· ＴＰ＝ｍａｘ｛０．３６０２８，０．２５｝＝０．３６０２８（ｓ） 剩下的任务加上这个并行块是顺序的，因此由式（３）可计 算出第３个实例子图的响应时间为 Ｔ３＝０．２５＋０．２＋０．３６０２８＋０．０５３＝０．８６３２８（ｓ） 同样地，其它３个实例子图的响应时间为 Ｔ１＝０．７９５（ｓ），Ｔ２＝０．８２（ｓ），Ｔ４＝１．１５３（ｓ） 最后，整个模型的完成时间为 Ｔ＝０．１２×０．７９５＋０．２８×０．８２＋０．１８×０．８６３２８＋ ０．４２×１．１５３＝０．９６４６５０４≈０．９６（ｓ） 模型的性能分析完毕。 图４　实例子图 结束语　本文将 ＷＦ－ｎｅｔ概念做了延伸，把Ｐｏｉｓｓｏｎ分布 的到达时间和指数分布的服务时间同每个任务联系在一起， 给出了随机良构工作流网的定义。结合排队网络的知识将资 源到达情况及任务执行情况结合起来描述一个任务，推导出 了每个任务的响应时间、每种工作流模式响应时间的计算公 式，结合模型的分解算法推导出了实例子图的响应时间，最终 结合路由率定义计算出了整个ＳＷＷＦ－ｎｅｔ模型的完成时间。 本文最后结合实例给出模型分解算法和相应的分析，推导出 了随机良构工作流网模型的平均响应时间。在今后的研究中 将继续探讨及改进分析算法。 参 考 文 献 ［１］ Ｔａｎ　Ｚｈａｎｇｘｉ，Ｌｉｎ　Ｃｈｕａｎｇ，Ｙｉｎ　Ｈａｏ，ｅｔ　ａｌ．Ａｐｐｒｏｘｉｍａｔｅ　Ｐｅｒ－ ｆｏｒｍａｎｃｅ　Ａｎａｌｙｓｉｓ　ｏｆ　Ｗｅｂ　Ｓｅｒｖｉｃｅｓ　Ｆｌｏｗ　Ｕｓｉｎｇ　Ｓｔｏｃｈａｓｔｉｃ　Ｐｅｔｒｉ Ｎｅｔ［Ｃ］∥Ｐｒｏｃ．ｏｆ　Ｔｈｉｒｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅｍ　Ｇｒｉｄ　ａｎｄ Ｃｏｏｐｅｒａｔｉｖｅ　Ｃｏｍｐｕｔｉｎｇ（ＧＣＣ　２００４）．２００４：１９３－２００ ［２］ Ｓｏｎ　Ｊ　Ｈ，Ｋｉｍ　Ｊ　Ｓ，Ｋｉｍ　Ｍ　Ｈ．Ｅｘｔｒａｃｔｉｎｇ　ｔｈｅ　ｗｏｒｋｆｌｏｗ　ｃｒｉｔｉｃａｌ ｐａｔｈ　ｆｒｏｍ　ｔｈｅ　ｅｘｔｅｎｄｅｄ　ｗｅｌｌ－ｆｏｒｍｅｄ　ｗｏｒｋｆｌｏｗ　ｓｃｈｅｍａ［Ｊ］．Ｊｏｕｒ－ ｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｓｙｓｔｅｍ　Ｓｃｉｅｎｃｅｓ，２００６，７０（１）：８６－１０６ ［３］ ｖａｎ　ｄｅｒ　Ａａｌｓｔ　Ｗ，ｖａｎ　Ｈｅｅ　Ｋ．Ｗｏｒｋｆｌｏｗ　Ｍａｎａｇｅｍｅｎｔ：Ｍｏｄｅｌｓ， Ｍｅｔｈｏｄｓ，ａｎｄ　Ｓｙｓｔｅｍｓ［Ｍ］．Ｔｈｅ　ＭＩＴ　Ｐｒｅｓｓ，２００２：２７１－２７２ ［４］ Ａａｌｓｔ　Ｗ．Ｗｏｒｋｆｌｏｗ　Ｖｅｒｉｆｉｃａｔｉｏｎ：Ｆｉｎｄｉｎｇ　Ｃｏｎｔｒｏｌ－ｆｌｏｗ　Ｅｒｒｏｒｓ Ｕｓｉｎｇ　Ｐｅｔｒｉ－ｎｅｔ－ｂａｓｅｄ　Ｔｅｃｈｎｉｑｕｅｓ［Ｍ］．Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２０００： １６１－１８３ ［５］ Ｓａｄｉｑ　Ｗ，Ｏｒｌｏｗｓｋａ　Ｍ ．Ａｐｐｌｙｉｎｇ　Ｇｒａｐｈ　Ｒｅｄｕｃｔｉｏｎ　Ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ　Ｉｄｅｎｔｉｆｙｉｎｇ　Ｓｔｒｕｃｔｕｒａｌ　Ｃｏｎｆｌｉｃｔｓ　ｉｎ　Ｐｒｏｃｅｓｓ　Ｍｏｄｅｌｓ［Ｃ］∥Ｐｒｏ－ ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１１ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ａｄｖａｎｃｅｄ　Ｉｎ－ ｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍｓ　Ｅｎｇｉｎｅｅｒｉｎｇ．１９９９：１９５－２０９ ［６］ Ｗｏｒｋｆｌｏｗ　Ｍａｎａｇｅｍｅｎｔ　Ｃｏａｌｉｔｉｏｎ　Ｔｅｒｍｉｎｏｌｏｇｙ　ａｎｄ　Ｇｌｏｓｓａｒｙ（ＷＦ－ ＭＣ－ＴＣ－１０１１）［Ｒ］．Ｗｏｒｋｆｌｏｗ　Ｍａｎａｇｅｍｅｎｔ　Ｃｏａｌｉｔｉｏｎ，Ｂｒｕｓｓｅｌｓ， １９９６ ［７］ Ｓａｄｉｑ　Ｗ，Ｏｒｌｏｗｓｋａ　Ｍ　Ｅ．Ａｎａｌｙｚｉｎｇ　ｐｒｏｃｅｓｓ　ｍｏｄｅｌｓ　ｕｓｉｎｇ　ｇｒａｐｈ ｒｅｄｕｃｔｉｏｎ　ｔｅｃｈｎｉｑｕｅｓ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍｓ，２０００，２５（２）：１１７－ １３４ ［８］ Ｌｉ　Ｊｉａｎｑｉａｎｇ，Ｆａｎ　Ｙｕｓｈｕｎ，Ｚｈｏｕ　Ｍｅｎｇｃｈｕ．Ｐｅｒｆｏｒｍａｎｃｅ　Ｍｏｄｅ－ ｌｉｎｇ　ａｎｄ　Ａｎａｌｙｓｉｓ　ｏｆ　Ｗｏｒｋｆｌｏｗ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｓｙｓ－ ｔｅｍｓ，Ｍａｎ，ａｎｄ　Ｃｙｂｅｒｎｅｔｉｃｓ，２００５，３４（２）：２２９－２４２ ［９］ Ｋｌｅｉｎｒｏｃｋ　Ｌ．Ｑｕｅｕｅｉｎｇ　Ｓｙｓｔｅｍｓ：Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ］． ＮｅｗＹｏｒｋ：Ｗｉｌｅｙ，１９７４ ［１０］Ｔｒｉｖｅｄｉ　Ｋ　Ｓ．Ｐｒｏｂａｂｉｌｉｔｙ　ａｎｄ　Ｓｔａｔｉｓｔｉｃｓ　ｗｉｔｈ　Ｒｅｌｉａｂｉｌｉｔｙ，Ｑｕｅ－ ｕｉｎｇ，ａｎｄ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　Ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ］．Ｐｒｅｎｔｉｃｅ－Ｈａｌｌ， Ｉｎｃ．，１９８２ （上接第２１２页） ［２］ 鲍玉斌，王琢，孙焕良，等．一种基于分形维的快速属性选择算法 ［Ｊ］．东北大学学报：自然科学，２００３，２４（６）：５２７－５３０ ［３］ 闫光辉，李战怀，党建武．基于多重分形的聚类层次优化算法 ［Ｊ］．软件学报，２００８，１９（６）：１２８３－１３００ ［４］ Ｔｒａｉｎａ　Ｃ，Ｔｒａｉｎａ　Ａ，Ｗｕ　Ｌ，ｅｔ　ａｌ．Ｆａｓｔ　ｆｅａｔｕｒｅ　ｓｅｌｅｃｔｉｏｎ　ｕｓｉｎｇ ｆｒａｃｔａｌ　ｄｉｍｅｎｓｉｏｎ［Ｃ］∥Ｐｒｏｃ．ＸＶ　Ｂｒａｚｉｌｉａｎ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｄａｔａ－ ｂａｓｅｓ．２０００ ［５］ ＢａｒｂａｒáＤ，Ｃｈｅｎ　Ｐ．Ｕｓｉｎｇ　ｔｈｅ　Ｆｒａｃｔａｌ　Ｄｉｍｅｎｓｉｏｎ　ｔｏ　Ｃｌｕｓｔｅｒ Ｄａｔａｓｅｔｓ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｓｉｘｔｈ　ＡＣＭ　ＳＩＧＫＤＤ．Ｉｎｔｅｒ－ ｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．２０００ ［６］ ｄｅ　Ｓｏｕｓａ　Ｅ　Ｐ　Ｍ，Ｔｒａｉｎａ　Ａ　Ｊ　Ｍ，Ｔｒａｉｎａ　Ｊ　Ｃ．ＳＩＤ：Ｃａｌｃｕｌａｔｉｎｇ　ｔｈｅ Ｉｎｔｒｉｎｓｉｃ　Ｄｉｍｅｎｓｉｏｎ　ｏｆ　Ｄａｔａ　Ｓｔｒｅａｍｓ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ ２００６ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ａｐｐｌｉｅｄ　Ｃｏｍｐｕｔｉｎｇ．２００６ ［７］ Ｗｏｎｇ　Ａ，Ｗｕ　Ｌ　Ｊ，Ｇｉｂｂｏｎｓ　Ｐ　Ｂ，ｅｔ　ａｌ．Ｆａｓｔ　Ｅｓｔｉｍａｔｉｏｎ　ｏｆ　Ｆｒａｃｔａｌ Ｄｉｍｅｎｓｉｏｎ　ａｎｄ　Ｃｏｒｒｅｌａｔｉｏｎ　Ｉｎｔｅｇｒａｌ　ｏｎ　Ｓｔｒｅａｍ　Ｄａｔａ［Ｊ］．Ｉｎｆａｏ－ ｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ　Ｌｅｔｔｅｒｓ，２００５，９３（２）：９１－９７ ［８］ Ａｌｏｎ　Ｎ，Ｍａｔｉａｓ　Ｙ，Ｓｚｅｇｅｄｙ　Ｍ．Ｔｈｅ　ｓｐａｃｅ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ａｐｐｒｏｘｉ－ ｍａｔｉｎｇ　ｔｈｅ　ｆｒｅｑｕｅｎｃｙ　ｍｏｍｅｎｔｓ［Ｃ］∥１９９６ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ．Ｐｈｉｌａｄｅｌｐｈｉａ，１９９６：２２－２４ ［９］ Ｔｈｏｒｕｐ　Ｍ，Ｚｈａｎｇ　Ｙｉｎ．Ｔａｂｕｌａｔｉｏｎ　Ｂａｓｅｄ　４－Ｕｎｉｖｅｒｓａｌ　Ｈａｓｈｉｎｇ ｗｉｔｈ　Ａｐｐｌｉｃａｔｉｏｎｓ　ｔｏ　Ｓｅｃｏｎｄ　Ｍｏｍｅｎｔ　Ｅｓｔｉｍａｔｉｏｎ［Ｃ］∥Ｐｒｏｃｅｅ－ ｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｆｉｆｔｅｅｎｔｈ　Ａｎｎｕａｌ　ＡＣＭ－ＳＩＡＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｄｉｓ－ ｃｒｅｔｅ　Ａｌｇｏｒｉｔｈｍｓ．２００４，１８：６０８－６１７ ［１０］Ａｎｎａ　Ｏ，Ｒａｓｍｕｓ　Ｐ．Ｕｎｉｆｏｒｍ　Ｈａｓｈｉｎｇ　ｉｎ　Ｃｏｎｓｔａｎｔ　Ｔｉｍｅ　ａｎｄ Ｌｉｎｅａｒ　Ｓｐａｃｅ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ａｎｎｕａｌ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ．２００３：６２２－６２８ ［１１］Ｃａｒｔｅｒ　Ｊ　Ｌ，Ｗｅｇｍａｎ　Ｍ　Ｎ．Ｕｎｉｖｅｒｓａｌ　Ｃｌａｓｓｅｓ　ｏｆ　Ｈａｓｈ　Ｆｕｎｃｔｉｏｎｓ ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｓｙｓｔｅｍ　Ｓｃｉｅｎｃｅｓ，１９７９，１８（２）： １４３－１５４ ［１２］Ｃｈａｒｉｋａｒ　Ｍ，Ｃｈｅｎ　Ｋ，Ｆａｒａｃｈ－Ｃｏｌｔｏｎ　Ｍ．Ｆｉｎｄｉｎｇ　Ｆｒｅｑｕｅｎｔ　Ｉｔｅｍｓ ｉｎ　Ｄａｔａ　Ｓｔｒｅａｍｓ［Ｊ］．Ｔｈｅｏｒｅｔｉｃａｌ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，２００４，３１２ （１）：３－１５ ·９２２·