黄文豪,齐德昱,谢 嵘,刘 宇,张皓同

(1.广东外语外贸大学南国商学院 数字化技术研究院,广东 广州 510545;2.华南理工大学 计算机科学与工程学院,广东 广州 510641)

0 引 言

随着数据量的快速增长,如何定位两个相似数据之间的差异数据,即差异数据定位,也得到了快速的发展。在现有的研究中,学者们多采取数据分块的方式来找出两个相似数据间不同的分块,这些分块则是差异数据。这种方式的工作过程如图1所示。具体的,首先对Data1和Data2按照相同的数据分块算法进行分块,然后比较两组分块之间不同的分块,这些不同的分块所组成的数据即为差异数据。

图1 差异数据定位的过程

学术界关于差异数据分块的研究重点集中在数据分块算法的设计上。数据分块算法的不同将直接影响差异数据定位的效果,比如能否全部定位出不同的数据、定位到的差异数据中相同数据的多少等。

不过学术界提出的数据分块算法都是在实验上验证算法在差异数据定位中起到的作用,并没有从理论上给出数据分块算法能否定位出所有不同的数据,也没有探讨数据分块算法中各参数在差异定位中所起到的作用。因此,该文对差异数据定位的过程进行抽象,推导出了这一过程的正确性。同时,还对数据分块算法中参数与差异数据定位的关系进行了讨论。

1 相关工作

借助数据分块算法来定位差异数据这一方法多用在重复数据删除、数据增量同步等领域。……