泛化双向相似连接-王昶平 , 王朝坤 , 汪浩 , 王萌 , 陈俊.pdf

上善若水

204

18页

0次

2022-05-20

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2017,28(12):3223−3240 [doi: 10.13328/j.cnki.jos.005244] http://www.jos.org.cn

泛化双向相似连接

∗

王昶平

王朝坤

汪

浩

王

萌

陈

俊

(清华大学软件学院,北京 100084)

通讯作者: 王朝坤, E-mail: chaokun@tsinghua.edu.cn

摘要: 相似连接是数据管理领域的一个热门话题,已在社会生产生活中得到广泛应用.然而,现有的相似连接方

法并不能满足真实世界不断增长的客观需求.通过引入定义在多种数据类型上的满足操作符和每条数据的独立阈

值,定义了一种相似连接——泛化双向相似连接.这种连接扩展了相似连接的应用范围.同时,还提出了两种高效的

解决泛化双向相似连接问题的方法:子连接集算法和映射-过滤-验证算法.通过真实与合成数据集上的大量实验,得

出了所提方法的正确性和有效性.

关键词: 双向相似连接;泛化数据;独立阈值;数据映射;过滤验证

中图法分类号: TP311

中文引用格式: 王昶平,王朝坤,汪浩,王萌,陈俊.泛化双向相似连接.软件学报,2017,28(12):3223−3240. http://www.jos.org.cn/

1000-9825/5244.htm

英文引用格式: Wang CP, Wang CK, Wang H, Wang M, Chen J. On generalized bisimilarity join. Ruan Jian Xue Bao/Journal of

Software, 2017,28(12):3223−3240 (in Chinese). http://www.jos.org.cn/1000-9825/5244.htm

On Generalized Bisimilarity Join

WANG Chang-Ping, WANG Chao-Kun, WANG Hao, WANG Meng, CHEN Jun

(School of Software, Tsinghua University, Beijing 100084, China)

Abstract: Similarity join is one of the hottest topics in the field of data management, and it has been widely applied in many fields.

However, existing similarity join methods cannot meet the increasing demands in the real world. This paper define generalized

bisimilarity join as a new similarity join to expend the applications of the similarity join research by introducing the satisfaction operator

on various data types with individual thresholds. Two efficient methods, SJS (sub-join set) and MFV (mapping-filtering- verification), are

proposed to solve this problem. A large amount of experiments conducted on both real-world and synthetic datasets demonstrate the

correctness and the effectiveness of the proposed methods.

Key words: bisimilarity join; generalized data; individual threshold; data mapping; filter and verification

相似连接旨在从两个或一个给定的数据集中找出满足预定连接条件的所有数据对.作为数据库应用中的

一个重要操作,相似连接受到学术界和工业界的普遍关注,并在重复检测

[1]

、同源检索

[2]

和下一代基因测序

[3]

等

众多应用场景中发挥着越来越重要的作用.

数据库研究者已针对不同类型的数据进行了大量的相似连接研究工作,如关系数据

[4]

、实体

[5]

、集合

[6]

以

及字符串

[7]

.近年来,研究者们更是将相似连接问题拓展到图数据等更为复杂的数据类型上

[8]

.然而,现有的相似

连接研究成果仍不能很好地满足现实世界中不断增长的客观需求.

场景 1(交友):假设有两位女士{Alice,Carol}和两位男士{Bob,Dave}希望结交异性.见表 1,他们分别给出了

∗ 基金项目: 国家自然科学基金(61373023)

Foundation item: National Natural Science Foundation of China (61373023)

收稿时间: 2016-08-01; 修改时间: 2016-10-26; 采用时间: 2016-11-19; jos 在线出版时间: 2017-03-24

CNKI 网络优先出版: 2017-03-24 17:11:02, http://kns.cnki.net/kcms/detail/11.2560.TP.20170324.1711.014.html

3224

Journal of Software 软件学报 Vol.28, No.12, December 2017

在各个属性上的自身条件(事实)以及对于交友对象的要求(期望).表中每一列分别对应事实(期望)属性:“◇~★”

表示“从◇到★”.教育属性中,B 代表学士,M 代表硕士,D 代表博士;有房属性中,Y 代表有房,N 代表无房;婚姻属

性中,S 代表单身.例如,Alice 身高事实是 166cm,对于交友对象的身高期望是 168 cm ~172cm.从表 1 可知,事实和

期望可以是数值、数值范围、布尔和枚举等不同类型的数据.同时,假定 Alice 和 Bob 都比较挑剔,他们要求交

友对象的事实完全符合自己的期望,也就是说,匹配程度(在所有属性中,潜在交友对象的事实满足希望交友者

所提对应期望的百分比)是 100%.与此不同的是,Carol 和 Dave 相对友好,仅需要交友对象的事实大部分满足自

己提出的期望.表 1 中,Carol 要求的匹配程度不低于 80%,Dave 的要求类似.

ble 1 Dating information

表 1 交友信息

(a) 男士集合

姓名年龄身高教育有房婚姻阈值

Bob

(21~22)

174

(165~167)

(B|M)

(N)

(S)

100%

Dave

(20~22)

175

(165~169)

(B|M)

(N)

(S)

80%

… … … … … … …

(b) 女士集合

姓名年龄身高教育有房婚姻阈值

Alice

(24~27)

166

(168~172)

(M|D)

(Y)

(S)

100%

Carol

(25~27)

167

(171~173)

(B|M|D)

(Y)

(S)

80%

... … … … … … …

场景 2(求职招聘):求职和招聘是工作市场中的一个重要话题.招聘者会提供薪水、假期和工作地点的事实

以及对于应聘者的专业技能和工作经验等的期望.同时,求职者会对应地提供他们对于薪水、假期、工作地点

的期望以及他们的专业技能和工作经验的事实.与交友场景类似,不同的求职者和招聘者会有着不同的对于匹

配程度的最低标准.

此外,还存在房屋租赁等一系列类似应用场景及问题.显然,现有的相似连接方法不能直接用来解决这些问

题.其主要原因在于:

(1) 现有的相似连接方法通常仅考虑一种数据类型,如字符串或向量,并根据这种数据类型的特点提出特

殊的处理方法以提高连接效率.然而,在上述问题中存在着多种数据类型,如有房属性中的布尔类型

数据,年龄、身高属性中的数值范围和数值类型数据;

(2) 现有的相似连接方法采用全局阈值,但是在场景 1 中,采用全局阈值不能得到{(Carol,Dave)}这样的理

想连接结果.当全局阈值被设置为 100%时,连接结果为空集,而当全局阈值被设置为 60%时,连接结果

为两个集合的笛卡尔积.显然,这两个结果都与理想结果存在差距;

(3) 现有的所有相似连接方法只在同一个属性维度上考虑了两个比较对象的相等关系或者某种偏序关

系.但是在上述场景中,我们需要在事实类属性和对应的期望类属性上考虑上述关系.同时,更复杂的

关系(如“包含”)也可能被考虑.

我们认为,上述问题存在以下 3 个挑战:(1) 每个比较对象

都存在自己独立的匹配标准,虽然这类标准可以

通过阈值进行刻画,但是无法采用当前相似连接查询处理方法中普遍使用的全局阈值;(2) 上述问题涉及数值、

数值范围、枚举、布尔、字符串等多种类型的数据,这使得对象的比较方式更加多样化;(3) 每个比较对象都有

事实类属性和期望类属性,具体比较时,事实属性和期望属性的交叉匹配将取代在同一属性上的简单比较,使得

比较方式更为复杂.

针对以上挑战,本文提出泛化双向相似连接的概念及相关查询处理算法,能够较好地解决上述问题.本文的

主要贡献如下.

of 18

免费下载

软件学报计算机技术

关注

评论