实体解析是数据集成的关键方面, 也是大数据分析与挖掘的必要预处理步骤. 大数据时代, 随着查询驱动的数据应用需求的不断增长, 查询式实体解析成为热点问题. 为了提升查询-解析效率, 研究了面向实体缓存的多属性数据索引技术. 涉及两个核心问题: (1) 如何设计多属性数据索引? 设计了基于R-树的多属性索引结构. 为了满足实体缓存在线生成需求, 提出了基于空间聚类的在线索引构建方法. 提出了基于“过滤-验证”的多维查询方法, 利用多属性索引有效地过滤掉不可能命中的记录, 然后采用相似性函数或距离函数逐一验证候选记录. (2) 如何将不同的字符串属性插入到树形索引中? 解决思路是, 将字符串映射到数值空间. 针对Jaccard相似性和编辑相似性, 提出了基于
Entity resolution is a key aspect of data integration, and also is a necessary preprocessing step of big data analytics and mining. In big data era, more and more query-driven data analytics applications come out, and query-based entity resolution becomes a hot topic. This work studies multi-attribute data indexing technology for entity cache in order to promote query-resolution efficiency. There are two core problems. One is how to design the multi-attributeindex. An R-tree based multi-attributeindex is designed. Entity cache is produced online, so an online index construction method is proposed based on spatial clustering. A filter-verify based multi-dimensional query method is proposed. It filters impossible records by the multi-attributeindex, and then verifies each candidate record with similarity functions or distance functions. The other ishow to insert different string attributes into the tree index. The basic solution is mapping strings into integer spaces. For Jaccard similarity and edit similarity, a q-gram based mapping method is proposed, and is improved by vector dimension reduction and z-order, which achieves high mapping qualities. Finally, the proposed hybrid index is experimentally evaluated on two datasets. Its effectiveness is validated, and moreover, different aspects of the multi-attribute index are also tested.
实体解析(entity resolution, ER)是数据集成和数据预处理的重要环节, 也是大数据分析与挖掘的基础工作[
当前, 查询式实体解析有着广泛的应用前景. 比如, 反恐信息系统收集来自多个数据源的不同方面的个人信息, 包括公安居民信息数据库、出入境信息数据库、犯罪信息数据库、火车票务数据库以及移民信息数据库等. 当进行嫌疑恐怖分子信息定位时, 需要从这些数据源中查询-解析出关于该嫌疑恐怖分子的所有数据记录, 从而协助案情侦测. 再比如, 小型公司获得较大量的数据, 然而只关心一小部分与自己商业运营有关的数据, 因此只需要查询-解析出自己感兴趣的数据记录即可.
查询式实体解析中近似实时的效率需求离不开有效的实体缓存机制, 而实体缓存的核心在于高效的索引技术. 数据记录包含多个属性, 以字符串为主, 还有少量数字串, 并且不同属性通过不同类型的相似性(比如Jaccard、编辑距离、数值的差值等)衡量, 这就构成多属性多相似性空间——一种特殊的多维空间, 每个维度对应特定的属性类型和相似性类型. 实体缓存需要支持多属性多相似性空间搜索, 因此需要设计面向多属性多相似性空间的索引, 称为多属性数据索引. 然而, 已有的字符串索引大部分是一维的[
本文提出了基于R-树的多属性数据索引技术来解决实体缓存查询问题. R-树是B-树在多维空间的拓展, 解决了多维空间搜索问题[
本文的主要贡献如下:
● 提出了基于R-树的多属性数据索引技术. 设计了基于R-树的多属性索引结构; 提出了基于空间聚类的小批量式在线索引构建方法; 提出了基于“过滤-验证(filter-verify)”的多维查询方法;
● 提出了一组“字符串→数值”映射方法. 首先提出了基于
● 在两个数据集上进行了充分的实验评价, 通过与已有工作的对比, 验证了本文提出的索引技术的有效性, 并且测试了索引技术自身的各个方面.
本文第1节进行研究概述, 包括查询式实体解析、实体缓存机制和问题定义. 第2节介绍基于R-树的多属性数据索引, 包括索引结构、索引构建和多维查询. 第3节详述“字符串→数值”映射, 包括基于
如
查询式实体解析架构
查询式实体解析(query based entity resolution, Q-ER)采用“过滤-验证”策略.
(1) 分块(离线)与块查询. 离线时, 对脏数据集进行多路分块, 得到块集合[
(2) 匹配可能性搜索. 利用分块来计算查询记录与候选记录的匹配可能性[
(3) 实体解析. 根据匹配可能性, 对查询记录与候选记录依次进行实体解析, 所有匹配的记录组成一个记录类簇[
一方面, 实体解析的时间开销较大, 并且候选记录对的数量较多, 因此导致查询-解析的时间开销较大, 影响查询-解析响应速度; 另一方面, 已有的查询-解析结果具有复用价值. 为了提升查询-解析效率, 应设计高效的缓存机制来协助Q-ER.
实体缓存收集已有的查询-解析结果, 以便后续相似的查询到来时直接返回结果. 记录类簇(即查询-解析结果)包含多条记录, 通过数据融合[
输入: 查询记录
输出: 查询-解析结果
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
实体缓存机制的核心问题之一是如何实现高效、准确的记录查询. 实体解析中, 数据记录通常包含多个不同特点的字符串属性及数值属性, 不同的字符串属性可能对应不同的字符串相似性函数和阈值, 比如姓名对应编辑距离、工作单位对应Jaccard相似性、年份对应差值, 阈值分别为2、0.75和1. 已有的多维索引主要面向数值型数据, 字符串索引通常是一维的, 都无法满足上述需求. 为此, 需要设计支持多维查询的索引, 这是本文的研究主题.
数据记录集合
(1) 基于编辑的相似性: 通过衡量两个字符串之间的字符级变换来计算相似性, 也称为基于字符(character)的相似性. 以编辑距离(edit distance, ED)为例,
其中, |*|表示字符串长度. 同类型的相似性还有Jaro、Jaro-Winkler等;
(2) 基于集合的相似性: 将字符串处理成标识集合, 然后利用集合相似性函数来计算字符串相似性, 也称为基于标识(token)的相似性. 以Jaccard为例:
其中,
其中,
属性相似性衡量方式分为两类, 对应两类约束:
将采用“过滤-验证”策略来解决面向数据记录的多维查询问题: (1) 过滤阶段, 通过多属性索引过滤掉不可能满足查询约束的记录, 生成候选记录集合; (2) 验证阶段, 调用各种相似性函数或距离函数计算候选记录是否满足查询约束. 查询的效率和精确性主要依赖于多属性索引的过滤能力, 为此, 将研究基于R-树的多属性索引.
实体缓存索引应满足以下要求: ①支持多维多类型(以字符串和数值为主)属性; ②针对不同的属性, 支持不同的相似性函数, 如编辑相似性或Jaccard相似性; ③支持多维查询, 每个维度上满足各自阈值的约束; ④支持查询时在各个维度自由地设定阈值, 而不必在构建索引时就固定阈值. 为此, 设计了基于R-树的多属性数据索引.
R-树是一种高效的多维索引, 支持快速的多维查询、更新代价较小、支持外存, 但只适用于数值, 而不适用于字符串, 因此将改进R树以设计多属性索引. 如例1所示, 多维树形索引中, 每个非叶子节点包含多个成员, 每个成员包含一个最小临界矩形(minimum bounding rectangle, MBR)和指向孩子节点的指针; 叶子节点存储一组数据记录. MBR是多维索引的核心, 它表示多维空间中一块区域, 在每个维度上限定一个取值范围. 其中, 对于R树中根节点以外的节点来说, 其节点中数据量满足范围约束[
例1: 如
高度为3的三维索引
多属性索引的插入和删除操作都依赖于可比较性, MBR每个维度都必须具有可比较性. 相似性上界计算的效率和有效性将决定索引的过滤能力. 一方面, 基于树形索引的多维查询是一个自顶向下的过程, 在每一层都要执行多次相似性上界计算, 因此上界计算的效率将影响多维查询的效率; 另一方面, 如果相似性上界计算不准确, 可能导致过度调用字符串相似性函数
查询式实体解析中查询-解析结果在线地生成, 需要近似实时地加入缓存. 传统的R-树构建过程包含频繁的插入和分裂操作[
多属性索引在线构建的基本思想是: 将增量数据进行聚类, 以类簇为单位进行best-effort插入. 如算法2所示, 多属性索引在线构建流程如下.
● 将数据记录转换为多维数值空间内的点(第1行), 数据空间的维度取决于多属性索引的维度|
● 利用GDBSCAN算法[
● 从
● 当遍历完
● 循环执行上述操作(第4−14行), 直到
需要说明的是: 在迭代过程, 一旦被GDBSCAN算法判别为离群点数据, 后续就不会被GDBSCAN算法再次处理(第3行、第13行), 而是最后被逐个插入到
输入: 新增(小批量)数据记录集合
输出: 更新后的多属性索引
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
输入: 多属性索引
输出: 剩余记录类簇
1.
2. 将
3. 执行
4. 执行
5. 执行树增高操作, 如果
6.
整体而言, 多维查询将采用“过滤-验证”策略: 先利用多属性索引过滤掉不可能命中的记录, 得到候选记录集合; 然后采用相似性函数或距离函数逐一验证候选记录, 最后返回符合查询约束的记录. 多维查询将基于树的深度优先遍历进行, 利用递归实现. 给定|
(1) 叶子节点查询(第2−4行). 对当前叶子节点
(2) 子树查询(第6−8行). 对当前非叶子节点
输入: 查询记录
输出: 查询结果
1.
2.
3.
4.
5.
6.
7.
8.
输入: 查询记录
输出: 范围验证结果.
1.
2.
3.
4.
5.
6.
7.
输入: 查询记录
输出: 重叠验证结果.
1.
2.
3.
4.
5.
6.
7.
多维查询的调用方式为
为了将字符串插入到树形索引, 需要将字符串映射到数值空间, 将映射记作
字符串相似性分为两类: 基于编辑的相似性(如编辑相似性)和基于集合的相似性(如Jaccard相似性). 这两类字符串相似性都与
如例2所示,
例2:
对于基于
证明: 字符串的编辑距离与其
其中,
其中, 编辑相似性上界的计算复杂度为O(|
证明: Jaccard相似性本身就是根据
为了降低存储开销和相似性上界计算开销, 可以将超高维标识向量转换为低维向量. 有两种降维思路: 基于哈希的降维和基于频率分类的降维[
● 基于哈希的降维. 如例3(1)所示, 利用一个哈希函数将全局
● 基于频率分类的降维. 如例3(2)所示, 将全局
例3:
(1) 基于哈希的降维,
(2) 基于频率分类的降维,
基于哈希的映射和基于频率分类的映射显然都满足可比较性; 它们分别满足编辑相似性上界可计算和Jaccard相似上界可计算, 具体参考引理4−引理7. 本质上, 基于降维的优化是用索引过滤的有效性(相似性上界的精确度)来换取过滤开销, 作为可调节参数,
证明: 给定两个字符串
那么, 编辑相似性满足:
其中, 编辑相似性上界的计算复杂度为O(
证明: 根据Jaccard相似性定义及基于哈希的降维原理, Jaccard相似性满足:
其中, Jaccard相似性上界的计算复杂度为O(
引理6与引理4的证明类似, 引理7与引理5的证明类似, 不再赘述.
● 动态数据环境讨论.
基于哈希的降维, 与
基于降维向量的映射还有进一步的优化空间. 给定两个正整数, 将它们转换为二进制进行比较, 需要从高位到低位依次比较, 如果高位出现不相等的情况, 则剩余位数不必再作比较[
例4: 如
基于
给定相似性
以基于低维向量的映射为基础, 基于
输入: 查询字符串
输出:
1. 计算
2. 计算
3.
4.
5.
6. 计算
7.
实验代码通过C++实现; 编译环境: GCC 4.8; 运行环境: 处理器3.2 GHz Intel (R) E5-2667, 8核, 内存64 GB; 操作系统: Red Hat Linux.
● 数据集.
https://dblp.uni-trier.de/)数据库抓取引文记录, 选中某些记录以概率方式生成重复记录, 最终得到200k条引文记录, 其中包含136 941对重复记录, 通过标题、作者、期刊/会议、年份这4个属性描述; (2) 个人信息数据集FB, 利用Febrl数据生成器构建一个合成的个人信息数据集[
● 索引设置.
对于DBLP数据, 构建三维索引: 标题基于Jaccard相似性, 第一作者基于编辑相似性, 年份基于差值. 对于FB数据, 构建三维索引: 姓名基于编辑相似性, 州+城市基于Jaccard相似性, 出生年基于差值. 降维优化中, 通过实验测定
多维查询阈值
Jaccard | 0.8 | 0.7 | 0.7 | 0.7 | 0.6 | 0.6 |
ES | 0.8 | 0.8 | 0.7 | 0.7 | 0.7 | 0.6 |
差值 | 1 | 1 | 1 | 2 | 2 | 2 |
针对本文提出的多属性索引技术的多个方面进行测试, 包括参数测试、索引构建、映射方法、伸缩性和存储开销等方面.
(1) 参数测试.
降维优化中, 参数
DBLP数据集上参数
FB数据集上参数
DBLP数据集上参数
FB数据集上参数
在DBLP数据上, 进行5k次随机抽样, 并利用抽样记录进行5k次多维查询; 在FB数据上, 进行25k次随机抽样, 并利用抽样记录进行25k次多维查询. 分别对多维查询的候选记录集合规模和时间开销取均值作为测试结果.
(2) 索引构建.
在查询式实体解析中需要在线构建索引, 为此, 将索引构建场景设定如下: 缓存记录以小批量(每次500条)的形式产生,
DBLP数据集上小批量式在线构建测试
FB数据集上小批量式在线构建测试
(3) “字符串→数值”映射.
本小节比较不同的映射方法: MRT-hs采用基于哈希的降维; MRT-hs-z采用基于哈希的降维, 并进行
DBLP数据集上映射方法对比
FB数据集上映射方法对比
(4) 可伸缩性.
本小节测试多属性索引MRT-fc-z的可伸缩性(scalability). 对于DBLP数据, 在40k、80k、120k、160k和200k的数据规模上, 分别进行1k、2k、3k、4k和5k次随机抽样, 并利用抽样记录分别进行1k、2k、3k、4k和5k次多维查询, 每次多维查询的时间开销取均值后得到的结果如
DBLP数据集上可伸缩性测试
FB数据集上可伸缩性测试
(5) 存储开销.
本小节测试多属性索引MRT-fc-z的存储开销. 对于DBLP数据, 在40k、80k、120k、160k和200k的数据规模上, 分别进行索引构建并测量其存储开销, 得到的结果如
DBLP数据集上存储开销测试
FB数据集上存储开销测试
将本文提出的多属性索引技术记作MRT-fc-z, 采用基于频率分类的降维, 并进行
DBLP数据集上与已有工作对比
FB数据集上与已有工作对比
实体解析也称为实体匹配、记录链接等, 是数据集成和数据预处理的一个重要方面[
索引是查询处理中常用的数据过滤工具. 字符串相似性搜索中常用的索引有倒排索引、基于B树的索引、字典树等, 大部分都是一维索引[
基于树的空间索引(如R-树、KD-树和四分树等)支持多维索引[
传统的实体解析依赖于经典的字符串相似性方法和数值相似性方法[
针对查询式实体解析中的缓存查询需求, 本文提出了基于R-树的多属性数据索引技术MRTree. 设计了树形的多属性索引结构, 通过“字符串→数值”映射将字符串属性插入索引, 在此基础上定义多维查询. 针对Jaccard相似性和编辑相似性, 提出了一组“字符串→数值”映射及优化方法, 保证多属性索引的过滤能力. 未来的工作将从以下几个方面展开.
1) 将研究适用于其他字符串相似性的“字符串→数值”映射方法, 并将探索实体缓存调度问题;
2) 将研究面向语义相似性的多属性数据索引技术;
3) 将对“字符串→数值”映射中的相关方法加以进一步探索: 将基于频率分类的降维方法推广到动态数据上; 针对降维后的向量的可比较性, 探索更准确的衡量指标; 研究理论化的
Elmagarmid AK, Ipeirotis PG, Verykios VS. Duplicate record detection: A survey. IEEE Trans. on Knowledge and Data Engineering, 2007, 19(1): 1-16. [doi: 10.1109/TKDE.2007.250581]
Sun CC, Shen DR, Li YK, Xiao YY, Ma JH. Research on record pair ranking for entity resolution with time constraint. Ruan Jian Xue Bao/Journal of Software, 2020, 31(3): 695-709 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5900.htm [doi: 10.13328/j.cnki.jos.005900]
孙琛琛, 申德荣, 李玉坤, 肖迎元, 马建红. 时间约束的实体解析中记录对排序研究. 软件学报, 2020, 31(3): 695-709. http://www.jos.org.cn/1000-9825/5900.htm [doi: 10.13328/j.cnki.jos.005900]
Ramadan B, Christen P, Liang H, Gayler RW. Dynamic sorted neighborhood indexing for real-time entity resolution. Journal of Data and Information Quality (JDIQ), 2015, 6(4): 15.
Yu M, Li G, Deng D, Feng J. String similarity search and join: A survey. Frontiers of Computer Science, 2016, 10(3): 399-417.
Zhang Z, Hadjieleftheriou M, Ooi BC, Srivastava D. Bed-tree: An all-purpose index structure for string similarity search based on edit distance. In: Proc. of the 2010 ACM SIGMOD Int'l Conf. on Management of Data. 2010. 915-926.
Zhang Y, Li X, Wang J, Zhang Y, Xing C, Yuan X. An efficient framework for exact set similarity search using tree structure indexes. In: Proc. of the 33rd IEEE Int'l Conf. on Data Engineering (ICDE). 2017. 759-770.
Li G, He J, Deng D, Li J. Efficient similarity join and search on multi-attribute data. In: Proc. of the 2015 ACM SIGMOD Int'l Conf. on Management of Data. 2015. 1137-1151.
Gaede V, Günther O. Multidimensional access methods. ACM Computing Surveys (CSUR), 1998, 30(2): 170-231.
Guttman A. R-trees: A dynamic index structure for spatial searching. In: Proc. of the 1984 ACM SIGMOD Int'l Conf. on Management of Data. 1984. 47-57.
Shao J, Wang Q, Lin Y. Skyblocking for entity resolution. Information Systems, 2019, 85: 30-43.
Christen P. A survey of indexing techniques for scalable record linkage and deduplication. IEEE Trans. on Knowledge and Data Engineering, 2012, 24(9): 1537-1555.
Hassanzadeh O, Chiang F, Lee HC, Miller RJ. Framework for evaluating clustering algorithms in duplicate detection. Proc. of the VLDB Endowment, 2009, 2(1): 1282-1293.
Li Y, Gao J, Meng C, Li Q, Su L, Zhao B, Fan W, Han J. A survey on truth discovery. SIGKDD Explorations, 2015, 17(2): 1-16.
Tian H, Sheng W, Shen H, Wang C. Truth finding by reliability estimation on inconsistent entities for heterogeneous data sets. Knowledge-based Systems, 2020, 187: 104828.
Sun CC, Shen DR, Kou Y, Nie TZ, Yu G. A related data oriented joint entity resolution approach. Chinese Journal of Computers, 2015, 38(9): 1739-1754 (in Chinese with English abstract).
孙琛琛, 申德荣, 寇月, 聂铁铮, 于戈. 面向关联数据的联合式实体识别方法. 计算机学报, 2015, 38(9): 1739-1754.
Kamel I, Faloutsos C. Hilbert R-tree: An improved R-tree using fractals. In: Proc. of the 20th VLDB. 1994. 500-509.
Roussopoulos N, Kelley S, Vincent F. Nearest neighbor queries. In: Proc. of the ACM SIGMOD. 1995. 71-79.
Li C, Rupesh C, Elke AR. Merging R-trees: Efficient strategies for local bulk insertion. GeoInformatica, 2002, 6(1): 7-34.
Lee T, Moon B, Lee S. Bulk insertion for R-trees by seeded clustering. Data & Knowledge Engineering, 2006, 59(1): 86-106.
Sander J, Ester M, Kriegel HP, Xu X. Density-based clustering in spatial databases: The algorithm GDBscan and its applications. Data Mining and Knowledge Discovery, 1998, 2(2): 169-194.
Kondrak G. N-gram similarity and distance. In: Proc. of the 2005 Int'l Symp. on String Processing and Information Retrieval. 2005. 115-126.
Ukkonen E. Approximate string-matching with
Gravano L, Ipeirotis PG, Jagadish HV, Koudas N, Muthukrishnan S, Srivastava D. Approximate string joins in a database (almost) for free. Proc. of the VLDB Endowment, 2001, 1: 491-500.
Christen P. Automatic record linkage using seeded nearest neighbour and support vector machine classification. In: Proc. of the 14th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. 2008. 151-159.
Ardalan A, Doan A, Akella A. Smurf: Self-service string matching using random forests. Proc. of the VLDB Endowment, 2018, 12(3): 278-291.
Ramadan B, Christen P, Liang H, Gayler RW, Hawking D. Dynamic similarity-aware inverted indexing for real-time entity resolution. In: Proc. of the 2013 Pacific-Asia Conf. on Knowledge Discovery and Data Mining. 2013. 47-58.
Altwaijry H, Mehrotra S, Kalashnikov DV. Query: A framework for integrating entity resolution with query processing. Proc. of the VLDB Endowment, 2015, 9(3): 120-131.
Dragut EC, Ouzzani M, Elmagarmid AK. Query-time record linkage and fusion over Web databases. In: Proc. of the 31st IEEE Int'l Conf. on Data Engineering (ICDE). 2015. 42-53.
Jagadish HV, Koudas N, Srivastava D. On effective multi-dimensional indexing for strings. ACM SIGMOD Record, 2000, 29(2): 403-414.
Mudgal S, Li H, Rekatsinas T, Doan A, Park Y, Krishnan G, Deep R, Arcaute E, Raghavendra V. Deep learning for entity matching: A design space exploration. In: Proc. of the 2018 Int'l Conf. on Management of Data. 2018. 19-34.