探索201301

Transcription

1 ISSN CODEN JKYTA8 Journal of Frontiers of Coputer Science and Technology /03/07(0) doi: /j.issn E-ail: Tel: * 相 似 性 连 接 查 询 技 术 研 究 进 展 + 庞 俊, 谷 峪, 许 嘉, 于 戈 东 北 大 学 信 息 科 学 与 工 程 学 院, 沈 阳 089 Research Advance on Siilarity Join Queries PANG Jun, GU Yu, XU Jia, YU Ge + School of Inforation Science and Engineering, Northeastern University, Shenyang 089, China + Corresponding author: E-ail: yuge@ail.neu.edu.cn PANG Jun, GU Yu, XU Jia, et al. Research advance on siilarity join queries. Journal of Frontiers of Coputer Science and Technology, 03, 7():-3. Abstract: Siilarity join query is to find siilar data object pairs for a wide range of applications, such as near duplicate Web page detection, entity resolution, data cleaning and siilar iage retrieval. Nowadays, siilarity join query becoes one of the hot topics in the field of big data processing. This paper discusses the challenges of siilarity join query. Meanwhile, it analyzes and classifies the existing siilarity join queries according to different standards, then suarizes and copares the existing string, set, vector and graph siilarity join algoriths respectively. Finally, it explores the research focus and trend of this area. Key words: siilarity join query; siilarity etrics; assive data 摘 要 : 相 似 性 连 接 查 询, 即 查 找 相 似 的 数 据 对 象 对, 具 有 广 泛 的 应 用 领 域, 例 如 相 似 网 页 检 测 实 体 解 析 数 据 清 洗 和 相 似 图 像 检 索 等 相 似 性 连 接 查 询 当 前 大 数 据 处 理 领 域 的 热 点 问 题 之 一 讨 论 了 相 似 性 连 接 查 询 面 临 的 挑 战 ; 根 据 不 同 的 标 准 对 现 有 的 相 似 性 连 接 查 询 进 行 了 分 类 ; 总 结 并 比 较 了 现 有 的 字 符 串 集 合 向 量 和 图 相 似 性 连 接 算 法 ; 探 讨 了 今 后 的 研 究 重 点 和 发 展 趋 势 关 键 词 : 相 似 性 连 接 查 询 ; 相 似 性 度 量 ; 海 量 数 据 文 献 标 志 码 :A 中 图 分 类 号 :TP39 * The National Natural Science Foundation of China under Grant Nos , 6779 ( 国 家 自 然 科 学 基 金 ); the National Grand Basic Research 973 Progra of China under Grant No. 0CB360 ( 国 家 重 点 基 础 研 究 发 展 规 划 (973)); the Fundaental Research Funds for the Central Universities of China under Grant Nos. N , N ( 中 央 高 校 基 本 科 研 业 务 费 专 项 资 金 ). Received 0-09, Accepted 0-.

2 Journal of Frontiers of Coputer Science and Technology 计 算 机 科 学 与 探 索 03, 7() 引 言 相 似 性 连 接 查 询 (siilarity join query), 即 查 找 相 似 的 数 据 对 象 对, 具 有 广 泛 的 应 用 领 域, 例 如 相 似 网 页 检 测 (near duplicate Web page detection) 实 体 解 析 (entity resolution) 数 据 清 洗 和 相 似 图 像 检 索 等 在 相 似 网 页 检 测 中, 使 用 相 似 性 连 接 等 技 术 识 别 相 似 的 网 页, 不 但 可 以 帮 助 网 页 搜 索 引 擎 执 行 聚 焦 爬 行, 提 高 搜 索 结 果 的 质 量 和 多 样 性, 还 可 以 识 别 垃 圾 [] 邮 件 在 实 体 解 析 中, 使 用 相 似 性 连 接 技 术, 可 以 [] 找 到 企 业 数 据 库 里 相 似 的 顾 客, 匹 配 产 品 报 价 等 在 数 据 清 洗 中, 使 用 相 似 性 连 接 技 术, 可 以 为 不 同 数 [3] 据 源 集 成 提 供 一 致 准 确 的 数 据 在 相 似 图 像 检 索 中, 使 用 相 似 性 连 接 技 术 检 索 出 相 似 的 图 像, 可 以 分 析 图 像 的 来 源, 查 找 高 清 图 像 等 以 下 给 出 相 似 性 连 接 查 询 处 理 主 要 面 临 的 三 大 挑 战 : () 多 模 态 与 多 样 化 相 似 性 连 接 查 询 需 要 处 理 多 种 数 据 类 型 的 数 据 对 象, 包 括 字 符 串 集 合 ( 多 重 集 合 ) 向 量 和 图 同 种 数 据 类 型 对 象 的 相 似 性 度 量 也 有 多 种 针 对 不 同 数 据 类 型 的 对 象, 一 般 需 要 使 用 不 同 的 相 似 性 连 接 算 法 和 不 同 的 相 似 性 度 量 () 模 糊 性 与 灵 活 性 相 对 于 精 确 匹 配, 相 似 性 连 接 查 询 一 般 通 过 相 似 度 计 算 和 验 证, 获 得 更 多 的 结 果 查 询 结 果 的 数 量 和 质 量 受 相 似 性 度 量 和 选 择 的 影 响 而 且 相 似 性 度 量 和 的 选 择 不 确 定 不 变 的, 它 一 般 随 应 用 不 同 而 不 同 因 此, 相 似 性 连 接 算 法 应 具 备 良 好 的 灵 活 性, 通 过 选 择 合 适 的 相 似 性 度 量 和, 可 以 达 到 较 好 的 效 果 (3) 海 量 性 与 可 伸 缩 性 近 年 来, 数 据 规 模 在 不 断 地 扩 大, 以 互 联 网 应 用 为 例, 网 页 的 数 量 快 速 地 增 长 海 量 数 据 (TB PB 级 数 据 ) 所 需 的 存 储 空 间 远 远 大 于 内 存 的 最 大 容 量, 也 超 过 常 用 关 系 数 据 库 的 最 大 存 储 量 (TB 级 数 据 ) 海 量 数 据 不 但 规 模 大, 而 且 结 构 复 杂 ; 不 但 有 结 构 化 数 据, 还 有 大 量 的 半 结 构 化 和 非 结 构 化 数 据, 处 理 起 来 难 度 大 因 此, 相 似 性 连 接 算 法 应 具 备 良 好 的 可 伸 缩 性 本 文 组 织 结 构 如 下 : 第 章 通 过 一 个 例 子 阐 述 了 相 似 性 连 接 查 询 的 定 义, 并 对 相 似 性 连 接 进 行 了 分 类 ; 第 3 章 至 第 6 章 分 别 分 析 和 比 较 了 字 符 串 集 合 ( 包 含 多 重 集 合 ) 向 量 和 图 的 相 似 性 连 接 ; 第 7 章 展 望 了 未 来 相 似 性 连 接 的 研 究 重 点 ; 第 8 章 总 结 全 文 定 义 与 分 类 被 广 泛 使 用 和 面 临 巨 大 挑 战 的 相 似 性 连 接 查 询 技 术 有 很 多 种 定 义 根 据 不 同 的 分 类 标 准 它 可 以 被 分 成 多 个 类 别. 定 义 相 似 性 连 接 查 询 指 从 一 个 或 者 两 个 数 据 集 ( 或 [,4-9] 者 数 据 源 ) 中 查 找 出 所 有 相 似 的 对 象 对 下 面 以 字 符 串 相 似 性 连 接 查 询 为 例 进 行 介 绍 例 已 知 两 个 分 别 由 字 符 串 组 成 的 数 据 集 D 和 D ( 见 表 ), 采 用 基 于 编 辑 距 离 (edit distance) 的 编 辑 相 似 性 (edit siilarity) 作 为 字 符 串 相 似 性 度 量, 记 做 ES(), τ 取 D 和 D 的 相 似 性 连 接 查 询 指 找 出 所 有 满 足 以 下 条 件 的 字 符 串 对 : 字 符 串 分 别 来 自 D 和 D, 并 且 它 们 的 相 似 性 不 小 于 τ D 和 D 组 成 的 所 有 二 元 组 即 { < S S > S Î D S Î D }, 其 相 似 性 计 算 结 果 如 表 所 示 ES(S S ) = - ED(S S ) ax(s S ), ED(S S ) 指 S 和 S 的 编 辑 距 离 显 而 易 见,< r R > < r R > 和 < r 3 R 3 >( 也 就 <,j> <sigod, siod> 和 <,>) τ = 时 的 相 似 性 连 接 结 果 字 符 串 编 号 r r r 3 Table Datasets D and D 数 据 集 D 表 数 据 集 D 和 D 内 容 sigod 字 符 串 标 识 相 似 性 连 接 的 对 象 的 数 据 类 型 不 仅 可 以 字 符 串, 也 可 以 集 合 向 量 和 图 等 这 些 数 据 可 以 存 储 在 数 据 库 关 系 表 中, 也 可 以 存 储 在 分 布 式 文 件 中 相 似 对 象 对 既 可 以 指 相 似 性 大 小 ( 相 似 度 ) 不 小 于 阈 值 的 对 象 对 ( 如 例 ), 又 可 以 按 相 似 性 从 大 到 小 排 序 后 的 前 k 个 对 象 对 ( 如 k =, 例 的 相 似 性 连 接 查 R R R 3 数 据 集 D 内 容 j siod

3 庞 俊 等 : 相 似 性 连 接 查 询 技 术 研 究 进 展 3 Table The calculated edit siilarity between D and D S r r r r r r r 3 r 3 r 3 表 S 内 容 sigod sigod sigod D 和 D 的 编 辑 相 似 性 计 算 结 果 S R R R 3 R R R 3 R R R 3 S 内 容 ED(S, S ) ES(S, S ) τ j siod j siod j siod 询 结 果 为 < r 3 R 3 > 和 < r R >) 从 一 个 数 据 集 中 查 找 出 所 有 的 相 似 对 象 对 称 做 相 似 性 自 连 接 查 询, 使 用 相 似 性 度 量 函 数 计 算 相 似 性 大 小 一 般, 不 同 的 数 据 类 型 对 应 不 同 的 相 似 性 度 量, 字 符 串 集 合 向 量 和 图 的 常 用 相 似 性 度 量 将 在 第 3 章 至 第 6 章 分 别 进 行 介 绍 相 似 性 搜 索 查 询 (siilarity search query) [0-9] 与 相 似 性 连 接 查 询 (siilarity join search) 研 究 的 问 题 不 相 同, 它 指 : 已 知 一 个 数 据 集 相 似 性 度 量 函 数 和 相 似 性, 给 定 一 个 查 询 元 素 ( 或 查 询 集 合 ), 找 出 该 数 据 集 中 所 有 和 查 询 元 素 ( 或 查 询 集 合 中 的 每 个 元 素 ) 相 似 度 不 小 于 的 元 素. 分 类 按 照 不 同 的 分 类 标 准, 相 似 性 连 接 可 以 分 成 不 同 的 类 别 () 按 照 被 连 接 对 象 数 据 类 型 的 不 同, 主 要 分 为 字 符 串 相 似 性 连 接 集 合 或 多 重 集 合 相 似 性 连 接 向 量 相 似 性 连 接 和 图 的 相 似 性 连 接 () 按 照 返 回 结 果 集 大 小 的 不 同, 可 以 分 为 所 有 对 (all-pairs) 相 似 性 连 接 ( 返 回 所 有 相 似 度 不 为 0 的 相 似 对 象 对 ) 相 似 性 连 接 ( 返 回 相 似 度 不 小 于 的 所 有 相 似 对 象 对 ) Top-k 相 似 性 连 接 ( 返 回 最 相 似 的 k 个 对 象 对 ) 和 Top-k 相 似 性 连 接 ( 返 回 相 似 度 不 小 于 的 前 k 个 对 象 对 ) (3) 按 照 数 据 存 储 方 式 的 不 同, 可 以 分 为 数 据 存 放 在 数 据 库 关 系 表 中 的 关 系 表 相 似 性 连 接 和 数 据 存 放 在 数 据 集 ( 文 件 ) 中 的 数 据 集 相 似 性 连 接 (4) 按 照 数 据 源 个 数 的 不 同, 可 分 为 单 数 据 源 双 数 据 源 和 多 数 据 源 相 似 性 连 接 各 分 类 可 以 覆 盖 其 他 分 类 标 准 的 类 别 以 字 符 串 相 似 性 连 接 为 例, 它 可 以 返 回 所 有 的 结 果, 或 者 返 回 相 似 度 不 小 于 的 结 果, 或 者 返 回 最 相 似 的 k 个 结 果 数 据 类 型 不 同 的 对 象, 一 般 使 用 不 同 的 相 似 性 连 接 技 术, 因 此 本 文 将 以 数 据 类 型 分 类 为 主 线 来 阐 述 相 似 性 连 接 的 研 究 进 展 3 字 符 串 相 似 性 连 接 字 符 串 相 似 性 连 接 处 理 对 象 的 数 据 类 型 字 符 串, 其 常 用 的 相 似 性 度 量 包 括 编 辑 距 离 标 准 化 的 编 辑 距 离 (noralized edit distance) 编 辑 相 似 性 和 汉 明 距 离 (Haing distance)( 见 表 3) Table 3 函 数 名 称 编 辑 距 离 标 准 化 的 编 辑 距 离 编 辑 相 似 性 汉 明 距 离 Coonly-used string siilarity etrics 表 3 常 用 的 字 符 串 相 似 性 度 量 公 式 或 定 义 字 符 串 S 和 S 的 编 辑 距 离 定 义 : 把 S 转 化 为 S 所 需 要 的 最 少 的 单 字 符 编 辑 操 作 数, 记 做 ED(S S ) 编 辑 操 作 包 括 :() 增 加 一 个 字 符 ;() 删 除 一 个 字 符 ;(3) 替 换 一 个 字 符 ED(S S ) ax(s S ) - ED(S S ) ax(s S ) 等 长 的 两 个 字 符 串 不 同 字 符 位 置 的 数 目 字 符 串 相 似 性 连 接 技 术, 常 使 用 两 种 框 架 : 过 滤 - 验 证 (filter-and-verify 或 filter-and-refine) 框 架 和 键 树 连 接 (Trie-join) 框 架 框 架 的 步 骤 : 先 用 特 征 码 (signature) 表 示 每 个 字 符 串, 然 后 基 于 这 些 特 征 码, 采 用 倒 排 索 引 和 剪 枝 技 术 产 生 候 选 结 果 集 合 ( 也 叫 中 间 结 果 集 合 ), 最 后 对 候 选 结 果 集 合 进 行 验 证, 计 算 出 最 终 结 果 框 架 的 数 据 流 程 图 见 图 框 架 虽 然 性 能 比 较 好, 并 被 广 泛 使 用 的 框 架, 但 存 在 三 点 不 足 :() 处 理 短 字 符 串 ( 平 均 长 度 不 大 于 30 的 字 符 串 ) 的 效 率 不 高 ;() 如 果 数 据 集 发 生 动 态 更 新, 算 法 处 理 效 率 低 ;(3) 索 引 比 较 大

4 4 Journal of Frontiers of Coputer Science and Technology 计 算 机 科 学 与 探 索 03, 7() 数 据 集 数 据 集 过 滤 器 中 间 结 果 集 验 证 最 终 结 果 Fig. The data flow of filtering-and-verify fraework 图 框 架 数 据 流 程 基 于 键 树 (Trie) 索 引 的 键 树 连 接 框 架 很 好 地 解 决 了 这 些 问 题, 可 以 高 效 地 处 理 短 字 符 串 相 似 性 连 接 查 询 问 题 键 树 一 种 树 结 构, 从 树 的 根 节 点 到 叶 子 节 点 表 示 一 个 字 符 串, 该 路 径 上 的 每 个 节 点 都 用 表 示 字 符 串 的 一 个 字 符 进 行 标 记 例 假 设 一 个 样 例 数 据 集 如 表 4, 则 它 的 键 树 索 引 结 构 如 图 Table 4 Saple dataset 表 4 样 例 数 据 集 字 符 串 编 号 字 符 串 内 容 s s s 3 s 4 s 5 s 6 s i 3 9 g d 4 i 7 sigod icd sigir sigd 0 0 v l d 3 b e i c d o 5 r d 6 Fig. Trie index structure of saple dataset 图 样 例 数 据 集 的 键 树 索 引 结 构 文 献 [0] 提 出 了 在 商 用 数 据 库 上 直 接 完 成 字 符 串 相 似 性 连 接 的 技 术, 使 用 编 辑 距 离 度 量 字 符 串 相 似 性, 解 决 了 两 个 关 系 表 的 字 符 串 相 似 性 连 接 查 询 问 题 它 使 用 计 数 (count) 位 置 (position) 和 长 度 (length) 三 个 过 滤 技 术 对 输 入 数 据 进 行 了 必 要 的 剪 枝, 极 大 地 减 少 了 计 算 次 数, 提 高 了 计 算 效 率 利 用 SQL 查 询 语 句, 计 数 过 滤 由 Having 从 句 的 条 件 实 现, 位 置 过 滤 由 Where 从 句 的 条 件 实 现, 长 度 过 滤 由 Where 从 句 的 附 加 条 件 实 现, 验 证 通 过 用 户 自 定 义 的 函 数 实 现 这 种 方 法 虽 然 精 确, 但 只 能 处 理 保 存 在 数 据 库 中 的 数 据, 因 此 不 适 合 用 来 处 理 其 他 数 据 集 中 的 数 据 文 献 [3] 提 出 了 一 种 新 的 简 单 操 作, 使 用 重 叠 相 似 性 (overlap siilarity) 度 量 字 符 串 相 似 性, 实 现 数 据 库 里 的 字 符 串 相 似 性 连 接 它 把 编 辑 距 离 标 准 化 的 编 辑 距 离 和 杰 卡 德 相 似 性 (Jaccard siilarity) 转 化 为 重 叠 相 似 性, 达 到 支 持 多 种 相 似 性 度 量 的 目 的 它 首 次 实 现 了 数 据 库 字 符 串 相 似 性 连 接 对 多 种 相 似 性 度 量 的 支 持, 但 它 不 能 被 查 询 优 化 器 优 化, 性 能 没 有 得 到 进 一 步 提 升 文 献 [] 提 出 了 编 辑 连 接 算 法 该 算 法 使 用 编 辑 距 离 来 度 量 字 符 串 相 似 性, 解 决 了 单 数 据 集 的 字 符 串 相 似 性 自 连 接 查 询 问 题 ; 利 用 未 匹 配 q-gra 的 位 置 和 内 容, 可 以 减 少 候 选 集 合 的 大 小 该 文 还 提 出 了 两 个 基 于 未 匹 配 q-gra 的 过 滤 技 术, 即 基 于 位 置 的 未 匹 配 过 滤 和 基 于 内 容 的 未 匹 配 过 滤, 并 成 功 地 把 这 两 个 新 过 滤 技 术 集 成 到 所 有 对 (all-pairs) 算 法 [9] 里 得 到 一 个 新 的 算 法 编 辑 连 接 算 法 通 过 增 加 过 滤 条 件, 进 一 步 减 少 候 选 结 果 集 的 大 小, 提 高 了 计 算 效 率 但 它 处 理 存 在 短 字 符 串 的 数 据 集 的 效 率 不 高 [], 因 为 短 字 符 串 不 能 产 生 高 质 量 的 特 征 码, 从 而 造 成 产 生 的 候 选 集 数 量 比 较 大 同 时 它 针 对 单 数 据 集 的, 不 能 直 接 用 于 解 决 多 数 据 集 的 字 符 串 相 似 性 连 接 查 询 问 题 文 献 [6] 提 出 了 一 种 基 于 划 分 的 传 递 连 接 (pass-join) 方 法 该 方 法 能 够 高 效 和 自 适 应 地 解 决 多 数 据 源 中 长 短 字 符 串 的 相 似 性 连 接 查 询 问 题 传 递 连 接 算 法 没 有 使 用 现 有 的 过 滤 技 术, 因 为 这 些 过 滤 技 术 在

5 庞 俊 等 : 相 似 性 连 接 查 询 技 术 研 究 进 展 5 处 理 短 字 符 串 时 会 产 生 数 量 比 较 大 的 候 选 集 合, 其 过 滤 效 果 不 理 想 它 使 用 如 下 字 符 串 相 似 性 必 要 条 件 进 行 过 滤 : 如 果 两 个 字 符 串 S 和 S 相 似, 则 S 的 子 串 必 和 S 的 一 个 分 割 相 匹 配 它 首 先 使 用 平 均 - 划 分 方 法 对 字 符 串 进 行 划 分, 得 到 分 割 集 ; 接 着, 不 考 虑 所 有 子 串, 而 使 用 多 匹 配 感 知 (ulti-atchaware) 方 法 选 择 了 一 部 分 子 串 由 于 编 辑 相 似 性 计 算 代 价 高, 传 递 连 接 算 法 使 用 基 于 字 符 串 长 度 的 过 滤 技 术 长 度 感 知 (length-aware) 过 滤 例 3 假 设 两 个 字 符 串 S 和 S ( 见 表 5),S 与 S 的 杰 卡 德 相 似 性, 记 做 SiJ(S S ) = T T T T = 3 显 然,S 与 S 的 杰 卡 德 相 似 性 值 很 小, 但 它 们 却 很 相 似 因 为 未 匹 配 Token 的 模 糊 匹 配 对 相 似 度 也 有 很 大 的 影 响, 而 杰 卡 德 相 似 性 余 弦 相 似 性 (cosine siilarity) 和 遗 传 相 似 性 (dice siilarity) 度 量 只 考 虑 Token 的 精 确 匹 配, 并 没 有 考 虑 未 匹 配 Token 的 模 糊 匹 配 通 过 考 虑 该 影 响 因 素, 可 以 增 大 S 与 S 的 相 似 度 值, 更 好 地 体 现 它 们 的 相 似 度 大 小 文 献 [3] 提 出 了 快 速 连 接 (fast-join) 方 法, 既 考 虑 了 Token 的 精 确 匹 配, 又 考 虑 了 未 匹 配 Token 的 模 糊 匹 配 该 算 法 通 过 组 合 基 于 Token 的 的 相 似 性 度 量 和 基 于 字 符 串 的 相 似 性 度 量, 得 到 模 糊 Token 的 相 似 性 度 量 ( 见 表 6) 遗 传 余 弦 和 杰 卡 德 相 似 性 度 量 都 模 糊 相 似 性 度 量 的 特 殊 情 况 字 符 串 S S Table 5 String S,S and their Token sets 表 5 字 符 串 S S 和 它 们 的 Token 集 合 字 符 串 内 容 icd 例 4 假 设 S 和 S 两 个 字 符 串,T 和 T 分 别 它 们 的 Token 集 合,T 和 T 的 模 糊 Token 重 叠 (Token overlap) 计 算 方 法 为 : 首 先 分 别 用 编 辑 相 似 性 计 算 Token 字 符 串 之 间 的 相 似 度, 然 后 将 所 有 大 于 或 等 于 的 相 似 度 累 加 得 到 最 终 结 果 以 表 5 为 例, 假 设 τ 取 0.7,Token 对 < k k > 的 编 辑 相 似 性 计 算 结 果 ES(k k ) 见 表 7 相 应 Token 集 标 识 T T 相 应 Token 集 内 容,,icd Table 6 Token 集 编 号 T T T T 表 6 函 数 名 称 遗 传 余 弦 杰 卡 德 Fuzzy dice/cosine/jaccard siilarity etrics 模 糊 遗 传 余 弦 和 杰 卡 德 相 似 性 度 量 一 般 相 似 度 函 数 T T T + T T T T T T T T + T - T T 模 糊 相 似 度 函 数 T ~ τ T T + T T ~ τ T T T T ~ τ T T + T - T T Table 7 Coputing results of ES(k k ) Token (k ) 表 7 Token 集 编 号 T T T T ES(k k ) 的 计 算 结 果 Token (k ) icd icd ES(k, k ) (τ) 因 此,T 和 T 的 模 糊 Token 重 叠 为 7/4, 模 糊 杰 卡 德 相 似 性 为 7/9 显 然, 计 算 结 果 反 映 出 S 和 S 很 相 似 文 献 [3] 提 出 了 新 的 过 滤 技 术 Token 敏 感 (Token-sensitive) 技 术 该 技 术 比 常 用 的 前 缀 过 滤 技 术 的 过 滤 效 果 更 好 文 献 [6] 使 用 长 度 可 变 的 前 缀 过 滤 技 术 和 编 辑 相 似 性 度 量, 解 决 了 多 数 据 集 字 符 串 或 集 合 的 相 似 性 连 接 查 询 问 题, 对 不 同 的 前 缀 长 度 有 不 同 的 过 滤 效 果 和 不 同 的 算 法 性 能 此 外, 还 提 出 了 一 个 代 价 模 型, 来 支 持 每 个 集 合 选 择 合 适 长 度 的 前 缀, 并 采 用 占 用 空 间 更 少 的 Delta 倒 排 索 引, 来 提 高 性 能 该 方 法 不 但 支 持 字 符 串 的 相 似 性 连 接, 还 支 持 集 合 的 相 似 性 连 接 文 献 [] 提 出 了 一 种 新 的 框 架 键 树 连 接, 使 用 编 辑 相 似 性 度 量, 解 决 了 字 符 串 的 相 似 性 连 接 查 询 问 题 它 首 先 使 用 键 树 结 构 对 字 符 串 进 行 索 引, 然 后 基 于 这 个 索 引, 使 用 多 种 剪 枝 技 术, 即 子 键 树 (subtrie) 双 子 键 树 长 度 单 分 枝 和 计 数 剪 枝 技 术, 进 行 短 字 符 串 的 相 似 性 连 接 与 框 架 相 比, 键 树 连 接 方 法 不 用 进 行 验 证, 其 索 引 小, 算 法 处 理 短 字 符 串 的 效 率 高, 处 理 长 字 符 串 的 效 率 低, 因 为 长 字 符 串 的 公 共 前 缀 少 文 献 [,4-5,7,4-5] 分 别 提 出 了 解 决 字 符 串 相 似 性 连 接 否 大 于 否 否

6 6 Journal of Frontiers of Coputer Science and Technology 计 算 机 科 学 与 探 索 03, 7() 查 询 问 题 的 方 法, 将 在 第 4 章 和 第 5 章 中 进 行 介 绍 上 述 字 符 串 相 似 性 连 接 技 术 各 具 特 点, 下 面 从 数 据 类 型 过 滤 条 件 和 数 据 源 等 方 面 进 行 对 比, 结 果 见 表 8 所 示 表 8 中, 第 4 列 数 据 类 型 中 的 字 集 和 向 分 别 表 示 字 符 串 集 合 和 向 量 ; 第 5 列 结 果 数 量 中 的 表 示 返 回 相 似 度 不 小 于 的 结 果, Top-k 表 示 返 回 前 k 个 最 相 似 的 结 果, Top-k 表 示 返 回 相 似 度 不 小 于 的 前 k 个 最 相 似 的 结 果 ; 第 9 列 相 似 性 度 量 中 的 ED 表 示 编 辑 相 似 性, OS 表 示 重 叠 相 似 性, NES 表 示 标 准 化 的 编 辑 相 似 性, JS 表 示 杰 卡 德 相 似 性, EJS 表 示 扩 展 的 杰 卡 德 相 似 性, SCS 表 示 集 合 余 弦 相 似 性, DS 表 示 遗 传 相 似 性, HD 表 示 汉 明 距 离, WJS 表 示 加 权 的 杰 卡 德 相 似 性, CS 表 示 余 弦 相 似 性 第 0 列 运 行 时 间 中 的 比 [ 序 号 ] 快 ( 慢 ) 表 示 比 文 献 [ 序 号 ] 提 出 的 算 法 快 ( 慢 ), 例 如, 比 [] 快 表 示 比 文 献 [] 提 出 的 算 法 快 ; 顺 数 第 4 行 的 Partition-NED 指 划 分 标 准 化 编 辑 距 离 ; 倒 数 第 4 行 的 LSH 指 位 置 敏 感 哈 希 (locality-sensitive-hashing) 方 法, PartEnu 指 部 分 枚 举 方 法 ; 倒 数 第 行 和 第 3 行 的 PPJoin+ 指 位 置 前 缀 增 强 连 接 方 法 4 集 合 和 多 重 集 合 相 似 性 连 接 集 合 和 多 重 集 合 相 似 性 连 接 处 理 对 象 的 数 据 类 型 集 合 和 多 重 集 合, 其 常 用 的 相 似 性 度 量 包 括 重 叠 相 似 性 杰 卡 德 相 似 性 遗 传 相 似 性 和 集 合 余 弦 相 Table 8 Coparison of string/set siilarity join technologies 表 8 字 符 串 和 集 合 相 似 性 连 接 技 术 比 较 否 数 据 结 果 数 据 源 文 献 算 法 名 框 架 过 滤 技 术 相 似 性 度 量 运 行 时 间 精 确 类 型 数 量 数 / 个 [0] [3] [] [3] [6] [6] [] [4] [4] [5] 编 辑 连 接 多 个 传 递 连 接 多 个 多 个 快 速 连 接 探 针 簇 多 个 否 否 字 字 字 字 字 字 集 字 字 集 向 字 集 字 集 Top-k 位 置 前 缀 连 接 前 缀 大 小 [] 字 集 JS OS ED 和 CS PPJoin+ 较 快 呈 抛 物 线 增 长 及 其 增 强 连 接 位 置 和 后 缀 [7] Topk- 连 接 字 集 [5] 字 集 向 Top-k Top-k 或 与 数 据 库 集 成 键 树 - 连 接 计 数 位 置 和 长 度 前 缀 基 于 位 置 和 基 于 内 容 的 未 匹 配 Token 敏 感 分 割 - 子 串 长 度 感 知 前 缀 计 数 子 键 树 双 子 键 树 长 度 和 单 分 枝 附 加 过 滤 器 前 缀 前 缀 大 小 位 置 和 后 缀 ED ED EJS SCS 和 DS ES 与 对 象 相 对 应 OS JS SCS 和 ED HD JS ED 和 WJS 比 [5] 快 Partition-NED 算 法 最 快 对 集 合, 比 [] 快 ; 对 字 符 串, 比 [] [] 快 较 小, 比 [] 快 ; 较 大, 处 理 短 字 符 串 比 [] 快, 否 则 比 [] 慢 较 小,LSH 较 快 ; 较 大, PartEnu 较 快 大 多 数 情 况 下 比 PPJoin+ 快 可 伸 缩 性 ( 平 均 延 迟 ) OS ED NED 和 JS ES 比 [] [] 快 接 近 线 性 ED JS CS DS 和 OS 呈 对 数 增 长 呈 对 数 增 长 接 近 线 性 与 对 象 相 对 应 接 近 线 性

7 庞 俊 等 : 相 似 性 连 接 查 询 技 术 研 究 进 展 7 似 性 ( 见 表 9) 多 重 集 合 可 以 通 过 将 重 复 出 现 的 元 素 都 作 为 新 元 素 的 方 法 转 化 为 集 合, 因 此 多 重 集 合 的 相 似 性 连 接 可 以 转 化 为 集 合 的 相 似 性 连 接, 下 面 将 只 提 集 合 相 似 性 连 接 Table 9 表 9 函 数 名 称 重 叠 相 似 性 杰 卡 德 相 似 性 遗 传 相 似 性 集 合 余 弦 相 似 性 Coon set siilarity etrics 常 用 的 集 合 相 似 性 度 量 A B A B 公 式 A B A B 或 A + B - A B A B A + B A B A B 集 合 相 似 性 连 接 技 术 一 般 使 用 框 架 ( 或 者 类 框 架 ) 文 献 [4] 提 出 了 一 种 新 的 探 针 簇 (probe-cluster) 算 法 该 算 法 使 用 多 种 相 似 性 度 量, 如 重 叠 相 似 性 杰 卡 德 相 似 性 集 合 余 弦 相 似 性 或 者 编 辑 距 离, 解 决 了 数 据 库 单 关 系 表 的 集 合 相 似 性 连 接 查 询 问 题 传 统 的 集 合 相 似 性 算 法, 如 探 针 计 数 (probe-count) [6] 计 数 对 (pair-count) [7] 和 词 群 组 (word-groups) [8], 由 于 基 于 内 存 处 理 且 处 理 效 率 低, 不 适 合 用 来 处 理 海 量 数 据 探 针 计 数 算 法 受 内 存 的 限 制, 处 理 的 数 据 规 模 有 限, 当 处 理 中 等 规 模 数 据 集 时 就 会 失 效 ; 如 果 基 于 外 存, 则 庞 大 的 数 据 量 将 导 致 运 行 时 间 很 长 计 数 对 算 法 虽 然 对 内 存 的 需 求 很 小, 但 它 在 合 并 列 表 时 仍 要 花 费 很 长 的 时 间 词 群 组 算 法 处 理 小 规 模 数 据 集, 效 率 比 较 高, 结 果 比 较 理 想 但 当 数 据 规 模 增 大 时, 该 算 法 对 内 存 的 需 求 急 剧 增 加 文 献 [4] 基 于 重 叠 相 似 性 度 量, 对 传 统 算 法 进 行 了 改 进 和 比 较, 改 进 后 的 探 针 计 数 算 法 效 率 得 到 提 高 但 处 理 大 规 模 数 据 时, 运 行 时 间 还 不 够 理 想 于, 使 用 如 下 三 个 方 法 进 一 步 加 快 算 法 处 理 速 度 : 建 立 单 个 路 径 然 后 哈 希 ; 对 数 据 进 行 预 先 排 序 ; 对 相 关 记 录 进 行 聚 类 考 虑 到 内 存 因 素, 先 划 分 原 数 据 集, 保 证 相 似 的 记 录 对 分 别 落 在 各 个 划 分 里, 并 且 每 个 划 分 足 够 小 然 后 分 别 处 理 每 个 划 分, 得 到 部 分 结 果, 通 过 聚 合 得 到 最 后 的 结 果 同 时, 压 缩 倒 排 索 引, 节 省 算 法 所 需 内 存 空 间, 使 用 附 加 过 滤 器 减 少 计 算 时 间 将 其 他 的 相 似 性 度 量 ( 即 杰 卡 德 相 似 性 集 合 余 弦 相 似 性 和 编 辑 距 离 ) 转 换 为 重 叠 相 似 性 度 量, 支 持 多 种 相 似 性 度 量 在 传 统 算 法 上 进 行 大 量 优 化 得 到 的 探 针 簇 算 法, 使 用 模 型 和 倒 排 索 引 技 术, 不 但 精 确, 而 且 高 效, 它 将 集 合 相 似 性 度 量 从 简 单 的 相 等 和 非 零 重 叠 相 似 性 度 量 扩 展 到 重 叠 距 离 杰 卡 德 相 似 性 集 合 余 弦 相 似 性 和 编 辑 距 离 这 类 基 于 重 复 元 素 的 相 似 性 度 量 该 算 法 虽 然 支 持 多 种 相 似 性 度 量 的 集 合 相 似 性 连 接, 但 针 对 特 定 相 似 性 度 量, 未 必 最 佳 的 选 择 文 献 [5] 提 出 了 多 种 新 算 法 这 些 算 法 分 别 使 用 多 种 相 似 性 度 量, 如 汉 明 距 离 杰 卡 德 相 似 性 编 辑 距 离 或 者 加 权 的 杰 卡 德 相 似 性, 解 决 了 两 数 据 源 的 集 合 相 似 性 连 接 查 询 问 题 这 些 都 精 确 的 算 法, 采 用 了 一 种 类 框 架 :() 为 每 个 数 据 集 的 元 素 产 生 对 应 的 特 征 码 集 合 ;() 如 果 两 个 元 素 相 似, 那 么 它 们 对 应 的 特 征 码 集 合 必 须 至 少 有 一 个 公 共 元 素, 以 此 为 筛 选 条 件 过 滤 得 到 候 选 集 ;(3) 从 候 选 集 得 到 最 后 的 结 果 它 同 时 提 出 四 个 特 征 码 模 式 (signature schee): 划 分 枚 举 部 分 枚 举 (PartEnu) 和 权 重 枚 举 (WtEnu) 其 中, 划 分 的 过 滤 效 果 不 好 ; 枚 举 虽 然 过 滤 效 果 比 较 好, 但 产 生 的 特 征 码 数 量 太 多 ; 部 分 枚 举 方 法 不 但 过 滤 效 果 好, 而 且 产 生 的 特 征 码 较 少 与 部 分 枚 举 算 法 相 比, 权 重 枚 举 算 法 更 适 合 于 进 行 加 权 的 集 合 相 似 性 连 接 该 文 提 出 的 新 算 法 使 用 此 类 框 架 和 部 分 枚 举 特 征 码 模 式, 进 行 未 加 权 的 集 合 相 似 性 连 接, 即 基 于 汉 明 距 离 或 者 杰 卡 德 相 似 性 的 集 合 相 似 性 连 接 ; 并 使 用 权 重 枚 举 特 征 码 模 式 进 行 加 权 的 集 合 相 似 性 连 接 它 也 适 用 于 字 符 串 相 似 性 连 接 该 文 提 出 的 算 法 在 处 理 海 量 数 据 时, 比 传 统 的 精 确 集 合 相 似 性 连 接 算 法 效 率 要 高 不 过 由 于 其 过 滤 条 件 单 一, 影 响 了 过 滤 效 果 文 献 [] 提 出 了 两 种 新 算 法 : 位 置 前 缀 连 接 (PP- Join) 和 位 置 前 缀 增 强 连 接 (PPJoin+) 这 两 种 算 法 支 持 多 种 相 似 性 度 量, 如 杰 卡 德 相 似 性 重 叠 相 似 性 编 辑 距 离 和 余 弦 相 似 性 它 们 使 用 框 架, 均 完 成 了 单 数 据 集 的 集 合 或 字 符 串 相 似 性 连 接 查 询 位 置 前 缀 连 接 算 法 在 所 有 对 算 法 的 基 础 上 集 成 位 置 (positional) 过 滤 技 术 位 置 前 缀 增 强 连 接

8 8 Journal of Frontiers of Coputer Science and Technology 计 算 机 科 学 与 探 索 03, 7() 算 法 在 位 置 前 缀 连 接 算 法 的 基 础 上 集 成 后 缀 过 滤 技 术 位 置 前 缀 连 接 算 法 集 成 位 置 过 滤 技 术, 减 少 了 候 选 集 合 的 大 小, 提 高 了 效 率 ; 位 置 前 缀 增 强 连 接 算 法 集 成 位 置 和 后 缀 过 滤 技 术, 进 一 步 提 高 了 效 率 该 文 通 过 增 加 过 滤 条 件, 进 一 步 减 少 了 候 选 集 合 的 大 小, 从 而 减 少 了 计 算 量, 提 高 了 效 率 位 置 前 缀 增 强 连 接 算 法 不 能 直 接 用 于 非 集 合 数 据 类 型 对 象 的 相 似 性 连 接 查 询 文 献 [7] 提 出 了 一 种 新 的 Topk- 连 接 (Topk-Join) 算 法 该 算 法 使 用 框 架, 查 找 最 相 似 的 k 对 对 象, 使 用 多 种 相 似 性 度 量, 如 杰 卡 德 相 似 性 余 弦 相 似 性 遗 传 相 似 性 或 者 重 叠 相 似 性, 解 决 了 双 数 据 集 的 集 合 或 者 字 符 串 的 Top-k 相 似 性 连 接 查 询 问 题 一 般 的 相 似 性 连 接 算 法 都 找 出 相 似 性 不 小 于 给 定 的 结 果, 但 不 所 有 情 况 下, 都 能 事 先 给 定, 因 为 对 不 同 的 数 据 集, 也 会 不 同 此 时, 需 要 试 验 不 同 的, 导 致 结 果 过 多, 运 行 时 间 过 长 或 者 结 果 为 空 等 问 题 Topk- 连 接 算 法 返 回 最 相 似 的 k 对 对 象, 作 为 查 询 的 结 果 与 相 似 性 连 接 相 比,Top-k 相 似 性 连 接 有 三 个 优 点 :() 不 需 要 指 定 一 个 ;() 以 最 相 似 的 k 对 记 录 作 为 结 果, 支 持 交 互 式 的 相 似 性 检 测 应 用 ;(3) 作 为 结 果 的 k 对 记 录 的 相 [0] 似 性 比 其 余 记 录 对 的 相 似 性 都 高 所 有 对 算 法 使 用 基 于 倒 排 索 引 数 据 结 构 的 前 缀 过 滤 技 术 和 大 小 过 滤 技 术, 先 建 立 倒 排 索 引, 然 后 基 于 倒 排 索 引 得 到 候 选 集 合, 最 后 计 算 候 选 结 果 的 相 似 度, 返 回 不 小 于 阈 值 的 结 果 该 算 法 在 建 立 索 引 的 同 时, 计 算 候 选 结 果, 使 用 一 个 数 组 来 标 识 文 档 否 作 为 候 选 结 果, 避 免 了 候 选 结 果 的 重 复 计 算 先 使 用 前 缀 过 滤 技 术, 然 后 继 续 使 用 大 小 过 滤 技 术, 通 过 减 少 每 个 记 录 的 前 缀 长 度, 来 减 少 候 选 集 合 的 大 小 和 计 算 次 数, 提 高 算 法 的 性 能 所 有 对 算 法 解 决 的 相 似 性 问 题, 不 能 直 接 用 来 解 决 Top-k 相 似 性 问 题 受 所 有 对 算 法 启 发, 文 献 [7] 首 先 提 出 一 种 使 用 框 架 和 前 缀 大 小 过 滤 技 术 的 基 本 算 法 ; 然 后 提 出 索 引 减 少 原 理 (index reduction principle) 来 减 少 记 录 的 索 引 大 小 和 前 缀 大 小, 优 化 索 引 和 验 证 过 程 ; 接 着 使 用 位 置 过 滤 技 术 和 后 缀 过 滤 技 术, 通 过 增 加 过 滤 条 件 来 加 强 过 滤, 减 少 候 选 集 合 的 大 小, 从 而 进 一 步 提 高 算 法 的 效 率 大 规 模 实 际 数 据 集 的 试 验 表 明,Topk- 连 接 算 法 使 用 多 种 优 化 技 术, 其 效 果 非 常 好, 不 但 提 高 了 算 法 的 空 间 效 率, 还 提 高 了 时 间 效 率 Topk- 连 接 算 法 在 大 多 数 情 况 下 比 位 置 前 缀 增 强 连 接 算 法 处 理 速 度 更 快 但,Topk- 连 接 算 法 针 对 的 集 合 对 象, 不 能 直 接 用 来 解 决 向 量 的 Top-k 相 似 性 连 接 查 询 问 题 它 属 于 内 存 算 法, 即 把 数 据 都 读 到 内 存 后 进 行 处 理, 不 能 直 接 用 来 处 理 海 量 数 据 文 献 [6,4-5] 提 出 的 方 法 也 可 以 解 决 集 合 相 似 性 连 接 查 询 问 题, 相 应 算 法 分 别 在 第 3 章 和 第 5 章 进 行 介 绍 上 述 集 合 相 似 性 连 接 技 术 各 具 特 点, 表 8 从 数 据 类 型 过 滤 条 件 和 数 据 源 等 方 面 进 行 了 对 比 5 向 量 相 似 性 连 接 向 量 相 似 性 连 接 处 理 对 象 的 数 据 类 型 低 维 和 高 维 向 量, 其 常 用 的 相 似 性 度 量 包 括 向 量 杰 卡 德 相 似 性 [] 向 量 余 弦 相 似 性 [] 欧 几 里 德 距 离 和 闵 可 夫 斯 基 [] 距 离 ( 见 表 0, 其 中 A B 两 个 向 量 A(a a a ) 和 B(b b b )) Table 0 函 数 名 称 向 量 杰 卡 德 相 似 性 向 量 余 弦 相 似 性 欧 几 里 德 距 离 闵 可 夫 斯 基 距 离 Coonly-used vector siilarity etrics 表 0 常 用 的 向 量 相 似 性 度 量 å (ai ) + 公 式 å ai b i (bi ) - å ai b i å å ai b i å (ai ) 文 献 [9] 使 用 分 而 治 之 的 方 法 和 闵 可 夫 斯 基 距 离 相 似 性 度 量, 解 决 了 高 维 欧 氏 空 间 的 最 近 点 问 题 它 首 先 考 虑 二 维 空 间, 从 二 维 空 间 的 N 个 点 中 找 出 距 离 最 近 的 两 个 点, 再 推 广 到 多 维 空 间 ; 用 一 垂 直 线 把 二 维 平 面 平 均 划 分 成 两 部 分, 每 部 分 包 含 N/ 个 点 ; 然 后 分 别 计 算 找 出 各 部 分 距 离 最 近 的 点, 并 比 较 两 å (bi ) å (ai - b i ) p å (ai - b i ) p

9 庞 俊 等 : 相 似 性 连 接 查 询 技 术 研 究 进 展 9 部 分 最 近 距 离, 取 较 小 的, 记 做 δ ; 计 算 与 垂 直 划 分 线 距 离 为 δ 的 范 围 内 两 点 间 的 距 离, 这 两 个 点 分 别 位 于 垂 直 线 划 分 的 两 部 分, 使 用 L 相 似 性 度 量 ; 如 果 该 距 离 比 δ 小, 则 这 两 个 点 为 所 求, 否 则 δ 对 应 的 两 个 点 为 所 求 ; 然 后 推 广 到 多 维 空 间, 将 d 维 空 间 的 最 近 点 查 找 问 题 转 化 为 两 个 问 题, 即 d 维 空 间 N/ 个 点 的 最 近 点 问 题 和 一 个 d - 维 空 间 N 个 点 的 最 近 点 问 题 与 点 数 目 的 增 加 相 比, 该 算 法 对 多 维 空 间 维 度 的 增 加 更 为 敏 感, 处 理 海 量 数 据 的 效 率 比 较 低 文 献 [30] 使 用 闵 可 夫 斯 基 距 离 相 似 性 度 量, 解 决 了 欧 氏 平 面 的 k 对 最 远 相 似 点 问 题 和 k 对 最 近 或 最 远 色 点 问 题 它 基 于 冯 洛 诺 伊 图 (Voronoi diagra), 首 先 分 别 找 出 每 个 点 的 k 个 最 远 点, 然 后 从 产 生 的 N k 个 中 间 候 选 结 果 中 找 出 最 远 的 k 个 结 果 对 单 数 据 源 的 二 维 向 量 k 最 远 点 方 法 进 行 扩 展, 可 以 解 决 双 数 据 源 的 二 维 向 量 k 最 近 点 和 最 远 点 问 题 它 首 次 研 究 了 单 数 据 源 的 二 维 向 量 k 最 远 点 问 题 双 数 据 源 的 二 维 向 量 Top-k 相 似 性 连 接 查 询 问 题 和 返 回 最 不 相 似 的 k 个 结 果 的 相 似 性 连 接 查 询 问 题 该 算 法 只 适 用 于 二 维 向 量, 不 能 直 接 应 用 于 多 维 向 量 的 k 最 近 点 和 最 远 点 问 题 文 献 [3] 使 用 闵 可 夫 斯 基 距 离 相 似 性 度 量, 解 决 了 单 数 据 集 高 维 向 量 Top-k 相 似 性 连 接 查 询 问 题 现 有 的 算 法 对 高 维 向 量 的 维 度 d 很 敏 感, 随 d 的 增 大, 处 理 时 间 增 长 很 快 ; 该 文 使 用 皮 亚 诺 (Peano) 曲 线, 提 出 了 一 种 近 似 的 解 决 方 法 和 一 种 基 于 近 似 方 法 的 精 确 方 法 精 确 算 法 分 两 步 : 使 用 皮 亚 诺 曲 线 近 似 地 得 到 候 选 结 果, 候 选 结 果 的 大 小 依 赖 于 数 据 的 分 布 ; 在 候 选 结 果 中 找 出 最 终 结 果 该 算 法 对 高 维 向 量 的 维 度 不 敏 感, 但 不 论 近 似 的 方 法 还 精 确 的 方 法, 都 只 适 用 于 单 数 据 源, 不 能 直 接 用 来 解 决 多 数 据 源 问 题 文 献 [4] 提 出 了 快 速 连 接 (QuickJoin) 算 法 该 算 法 用 于 解 决 多 种 数 据 类 型 相 似 性 连 接 查 询 问 题 此 前, 研 究 集 中 在 基 于 闵 可 夫 斯 基 距 离 的 向 量 相 似 性 连 接 查 询 问 题, 非 向 量 数 据 类 型 需 要 转 化 为 向 量 然 后 进 行 处 理 相 应 的 算 法 基 于 多 维 索 引, 首 先 根 据 其 中 一 维 来 划 分 数 据, 然 后 继 续 选 择 另 一 维 进 行 划 分 维 度 的 选 择 对 结 果 影 响 很 大, 而 选 择 一 个 较 好 的 划 分 维 度 比 较 难 此 时, 可 以 使 用 基 于 非 索 引 或 基 于 划 分 的 方 法 快 速 连 接 算 法 一 种 基 于 划 分 的 方 法, 把 数 据 划 分 成 足 够 小 的 部 分, 使 得 各 部 分 的 数 据 可 以 嵌 套 循 环 地 进 行 相 似 性 连 接 根 据 使 用 的 划 分 方 法 的 不 同, 该 算 法 有 多 个 版 本 常 用 的 划 分 方 法 有 球 划 分 和 广 义 的 超 平 面 划 分, 球 划 分 思 想 和 分 [9] 而 治 之 的 思 想 类 似 快 速 连 接 算 法 比 基 于 非 索 引 算 法 ε 网 格 秩 序 算 法 (Epsilon grid order,ego) [3] 和 通 用 外 部 空 间 扫 描 算 法 (general external space scan,gess) [33] 效 率 高, 而 且 支 持 多 种 数 据 类 型 和 相 似 性 度 量, 但 其 计 算 效 率 已 被 文 献 [-] 提 出 的 算 法 所 超 越 文 献 [5] 提 出 了 几 种 数 据 库 操 作 :ε 连 接 (ε-join) k 距 离 连 接 (kd-join) 和 k 最 邻 近 点 连 接 (knn-join) 等, 这 些 操 作 分 别 解 决 了 个 或 个 关 系 表 的 相 似 性 连 接 Top-k 相 似 性 连 接 和 k 最 邻 近 点 连 接 等 问 题 非 数 据 库 操 作 类 方 法, 虽 然 支 持 所 有 的 连 接 类 型, 但 处 理 大 规 模 数 据 集 时 需 要 专 门 的 数 据 结 构 和 机 制, 不 能 和 数 据 库 操 作 进 行 组 合, 也 没 有 利 用 查 询 优 化 器 使 用 数 据 库 基 本 操 作 的 算 法 不 支 持 某 些 连 接 类 型, 对 一 些 连 接 类 型 的 查 询 处 理 比 较 复 杂, 不 能 直 接 利 用 查 询 优 化 器 该 文 提 出 的 操 作 集 成 在 数 据 库 引 擎 中, 不 但 可 以 支 持 所 有 的 连 接 类 型, 重 用 和 扩 展 数 据 库 操 作 和 结 构, 还 可 以 和 其 他 数 据 库 操 作 进 行 组 合, 而 且 可 以 利 用 查 询 优 化 器 该 文 在 PostgreSQL 中 实 现 了 ε 连 接 操 作, 但 处 理 海 量 数 据 的 成 本 比 较 高, 效 率 比 较 低, 可 伸 缩 性 不 好 从 数 据 类 型 过 滤 条 件 和 数 据 源 等 方 面 对 上 述 向 量 相 似 性 连 接 技 术 进 行 比 较, 结 果 见 表 所 示 表 遵 从 表 8 的 说 明, 其 第 5 列 返 回 结 果 数 量 里 的 Top- 表 示 返 回 最 相 似 的 结 果, 第 9 列 相 似 性 度 量 里 的 MD 表 示 闵 可 夫 斯 基 距 离 6 图 相 似 性 连 接 图 相 似 性 连 接 处 理 对 象 的 数 据 类 型 图, 其 最 常 用 的 相 似 性 度 量 图 编 辑 距 离 图 G 和 G 的 编 辑 距 离 定 义 为 : 把 G 转 化 为 G 的 同 构 图 所 需 要 的 最 少 的 编 辑 操 作 数, 记 做 GED(G G ) 图 编 辑 操 作 包 括 : () 增 加 一 个 顶 点 ;

10 0 Journal of Frontiers of Coputer Science and Technology 计 算 机 科 学 与 探 索 03, 7() Table Coparison of vector siilarity join technologies 表 向 量 相 似 性 连 接 技 术 比 较 文 献 [4] [30] [3] [4] [5] 算 法 名 快 速 连 接 否 精 确 一 个, 另 一 个 不 数 据 类 型 二 维 和 高 维 向 量 二 维 向 量 二 维 和 高 维 向 量 字 符 串 集 合 和 向 量 字 符 串 集 合 和 向 量 结 果 数 量 Top- Top-k Top-k 或 Top-k 数 据 源 数 / 个 或 或 框 架 过 滤 技 术 相 似 性 度 量 MD MD MD 与 对 象 相 对 应 与 对 象 相 对 应 运 行 时 间 可 伸 缩 性 ( 平 均 延 迟 ) 呈 对 数 增 长 接 近 线 性 () 删 除 一 个 顶 点 ; (3) 更 改 一 个 顶 点 的 标 签 ; (4) 增 加 一 条 边 ; (5) 删 除 一 条 边 ; (6) 更 改 一 条 边 的 标 签 文 献 [34] 提 出 了 一 种 新 的 GSiJoin 算 法 该 算 法 解 决 海 量 单 个 图 数 据 集 的 相 似 性 自 连 接 查 询 问 题, 使 用 图 编 辑 距 离 相 似 性 度 量 首 先 使 用 过 滤 - 验 证 框 架, 把 图 表 示 为 基 于 路 径 的 q-gra 集 合, 然 后 基 于 q-gra 集 合 进 行 过 滤, 最 后 使 用 编 辑 距 离 相 似 性 度 量 进 行 计 算 和 验 证 采 用 的 过 滤 技 术 包 括 大 小 过 滤 技 术 最 小 编 辑 过 滤 技 术 计 数 过 滤 技 术 局 部 标 签 过 滤 技 术 和 全 局 标 签 过 滤 技 术 最 小 编 辑 过 滤 技 术 一 种 基 于 未 匹 配 q-gra 的 增 强 型 前 缀 过 滤 技 术, 它 减 小 了 传 统 前 缀 技 术 的 前 缀 长 度, 因 而 减 少 了 中 间 结 果 和 计 算 次 数, 加 快 了 算 法 执 行 速 度 局 部 全 局 标 签 过 滤 技 术 也 考 虑 了 未 匹 配 q-gra 的 标 签, 可 进 一 步 增 强 过 滤 效 果 [35] 与 最 优 的 基 于 树 q-gra 的 k 相 邻 树 (k-at) 算 法 相 比,GSiJoin 算 法 的 应 用 不 局 限 于 稀 疏 图, 它 使 用 基 于 路 径 的 q-gra 表 示 图, 增 大 了 q 的 最 大 取 值, 从 而 使 得 候 选 结 果 集 更 小, 图 编 辑 距 离 相 似 性 计 算 次 数 更 少, 执 行 效 率 更 高 不 过,GSiJoin 算 法 使 用 精 确 的 算 法 计 算 图 编 辑 距 离, 因 此 不 适 用 于 节 点 较 多 的 大 图 同 时, 该 算 法 只 适 用 于 单 个 图 数 据 集 的 阈 值 相 似 性 连 接 查 询, 不 能 直 接 用 于 多 个 图 数 据 集 的 相 似 性 连 接 查 询 7 未 来 工 作 展 望 目 前 有 关 相 似 性 连 接 查 询 技 术 的 研 究 工 作 已 经 取 得 了 一 些 成 果, 但 仍 不 能 满 足 当 前 应 用 发 展 ( 如 大 数 据 处 理 ) 的 需 要 以 下 给 出 今 后 的 几 个 研 究 重 点 : () 面 向 不 确 定 数 据 的 相 似 性 连 接 查 询 技 术 目 前, 确 定 数 据 的 相 似 性 连 接 查 询 被 关 注 和 研 究, 但 对 不 确 定 数 据 ( 如 不 确 定 图 ) 的 研 究 工 作 却 很 少 作 为 不 确 定 数 据 处 理 的 一 个 基 本 操 作, 不 确 定 数 据 相 似 性 连 接 查 询 技 术 有 待 于 进 一 步 研 究 () 多 数 据 集 的 相 似 性 连 接 查 询 技 术 单 双 数 据 集 的 相 似 性 连 接 查 询 技 术 已 被 深 入 研 究, 并 取 得 了 很 多 创 新 性 成 果 但, 这 些 技 术 处 理 单 双 数 据 集 的, 不 能 直 接 应 用 于 多 数 据 集 的 相 似 性 连 接 查 询 多 数 据 集 相 似 性 连 接 在 现 实 生 活 中 有 广 泛 的 应 用, 如 在 时 空 数 据 库 中, 使 用 多 数 据 集 相 似 性 连 接 技 术, 可 以 查 找 多 台 交 通 工 具 的 相 同 轨 迹 多 数 据 集 的 连 接 查 询 可 以 转 化 为 多 次 双 数 据 集 的 连 接 查 询, 但 这 种 算 法 的 效 率 未 必 比 一 次 完 成 多 数 据 集 相 似 性 连 接 查 询 的 效 率 高 因 此, 可 以 考 虑 设 计 高 效 率 的 一 次 完 成 多 数 据 集 相 似 性 连 接 的 算 法 (3) 动 态 数 据 的 相 似 性 连 接 查 询 技 术 相 似 性 连 接 技 术 主 要 集 中 在 对 静 态 数 据 的 处 理 上, 对 动 态 数 据 的 研 究 很 少 动 态 数 据 在 现 实 世 界 中 广 泛 存 在 ( 如 时 间 序 列 ), 尤 其 随 着 全 球 数 据 总 量 的 指 数 增 长, 数 据 的 动 态 性 表 现 得 越 来 越 明 显 可 以 考 虑 开 发 增 量 算 法, 来 完 成 动 态 数 据 的 相 似 性 连 接 查 询 (4) 基 于 MapReduce 框 架 的 相 似 性 连 接 查 询 并 行 处 理 技 术 现 有 的 相 似 性 连 接 查 询 算 法, 一 般 不 适 合 处 理 海 量 字 符 串 集 合 和 向 量 的 相 似 性 连 接 查 询 现 有

11 庞 俊 等 : 相 似 性 连 接 查 询 技 术 研 究 进 展 算 法 一 般 使 用 一 台 计 算 机 处 理 存 储 在 数 据 库 中 的 数 据, 面 对 PB 级 的 海 量 数 据, 会 遇 到 数 据 库 容 量 不 够 的 问 题, 同 时 还 会 遇 到 内 存 和 CPU 瓶 颈, 其 处 理 时 间 可 能 远 远 超 出 人 们 的 可 接 受 范 围 新 兴 的 MapReduce 框 架, 使 用 计 算 机 集 群 来 对 海 量 数 据 进 行 并 行 处 理, 把 数 据 存 储 在 集 群 上 的 分 布 式 文 件 系 统 中 最 新 稳 定 版 本 的 Hadoop 系 统 支 持 [36] 台 机 器 今 后, 使 用 MapReduce 框 架 来 进 行 海 量 字 符 串 集 合 和 向 量 相 似 性 连 接 查 询 将 成 为 一 种 趋 势, 并 将 在 相 当 长 的 一 段 时 间 里 占 据 主 导 地 位 (5) 大 规 模 图 的 相 似 性 连 接 查 询 技 术 近 年 来, 数 据 规 模 不 断 扩 大, 处 理 大 规 模 大 图 数 据 的 需 求 强 烈 大 规 模 大 图 的 相 似 性 连 接 查 询 主 要 面 临 两 个 挑 战 : 现 有 方 法 不 适 合 处 理 大 规 模 图 数 据 ; 精 确 算 法 不 适 合 用 来 计 算 大 图 的 相 似 性, 因 为 常 用 于 求 解 图 相 似 性 的 相 似 性 度 量 的 计 算, 即 图 编 辑 距 离, 已 证 明 一 个 NP 难 问 题, 所 消 耗 的 时 间 与 图 的 节 点 数 目 呈 指 数 增 长 目 前, 图 的 相 似 性 连 接 查 询 和 Top-k 相 似 性 连 接 查 询 鲜 见 或 未 见 报 道 可 以 设 计 基 于 MapReduce 框 架 的 大 规 模 图 数 据 的 相 似 性 连 接 查 询 算 法, 同 时 针 对 大 图, 设 计 高 效 的 索 引 结 构, 增 强 过 滤 效 果, 减 少 运 行 时 间, 并 且 开 发 精 度 更 高 且 速 度 更 快 的 近 似 算 法 8 总 结 目 前 数 据 量 以 惊 人 的 速 度 增 长, 海 量 数 据 处 理 成 为 数 据 科 学 领 域 的 一 个 研 究 热 点 海 量 数 据 具 有 多 模 态 和 大 规 模 等 特 性, 给 相 似 性 连 接 查 询 提 出 了 巨 大 的 挑 战 本 文 对 相 似 性 连 接 进 行 了 分 类 ; 对 不 同 数 据 类 型 的 相 似 性 连 接 技 术 的 研 究 现 状 进 行 了 归 纳 和 总 结, 包 括 字 符 串 集 合 向 量 和 图 相 似 性 连 接 ; 并 对 相 似 性 连 接 技 术 的 未 来 研 究 方 向 进 行 了 展 望 References: [] Xiao Chuan, Wang Wei, Lin Xuein, et al. Efficient siilarity joins for near duplicate detection[c]//proceedings of the 7th International Conference on World Wide Web (WWW 08), Beijing, China, Apr -5, 008. New York, NY, USA: ACM, 008: [] Kolb L, Thor A, Rah E. Load balancing for MapReduce-based entity resolution[c]//proceedings of the 0 IEEE 8th International Conference on Data Engineering (ICDE ), Washington, DC, USA, Apr -5, 0. Washington, DC, USA: IEEE Coputer Society, 0: [3] Chaudhuri S, Ganti V, Kaushik R. A priitive operator for siilarity joins in data cleaning[c]//proceedings of the nd International Conference on Data Engineering (ICDE 06), Atlanta, GA, USA, Apr 3-8, 006. Washington, DC, USA: IEEE Coputer Society, 006: 5. [4] Sarawagi S, Kirpal A. Efficient set joins on siilarity predicates[c]//proceedings of the 004 ACM SIGMOD International Conference on Manageent of Data (SIGMOD 04), Paris, France, Jun 3-8, 004. New York, NY, USA: ACM, 004: [5] Arasu A, Ganti V, Kaushik R. Efficient exact set-siilarity joins[c]//proceedings of the 3nd International Conference on Very Large Data Bases (VLDB 06), Seoul, Korea, Sep -5, 006: [6] Li Guoliang, Deng Dong, Wang Jiannan, et al. Pass-join: a partition-based ethod for siilarity joins[j]. Proceedings of the VLDB Endowent, 0, 5(3): [7] Xiao Chuan, Wang Wei, Lin Xuein, et al. Top-k set siilarity joins[c]//proceedings of the 009 IEEE 5th International Conference on Data Engineering (ICDE 09), Shanghai, China, Mar 9-Apr, 009. Washington, DC, USA: IEEE Coputer Society, 009: [8] Zhu Shiwei, Wu Junjie, Xia Guoping. Top-k cosine siilarity interesting pairs search[c]//proceedings of the 7th International Conference on Fuzzy Systes and Knowledge Discovery (FSKD 0), Yantai, Shandong, China, Aug 0-, 00. Washington, DC, USA: IEEE Coputer Society, 00: [9] Zhu Shiwei, Wu Junjie, Xiong Hui, et al. Scaling up top-k cosine siilarity search[j]. Data & Knowledge Engineering, 0, 70(): [0] Bayardo R J, Ma Yiing, Srikant R. Scaling up all pairs siilarity search[c]//proceedings of the 6th International Conference on World Wide Web (WWW 07), Banff, Alberta, Canada, May 8-, 007. New York, NY, USA: ACM, 007: [] Li Chen, Lu Jiaheng, Lu Yiing. Efficient erging and filtering algoriths for approxiate string searches[c]//proceedings of the 008 IEEE 4th International Conference on

12 Journal of Frontiers of Coputer Science and Technology 计 算 机 科 学 与 探 索 03, 7() Data Engineering (ICDE 08), Cancún, México, Apr 7-, 008. Washington, DC, USA: IEEE Coputer Society, 008: [] Zhang Zhenjie, Hadjieleftheriou M, Ooi B C, et al. Bed-tree: an all-purpose index structure for string siilarity search based on edit distance[c]//proceedings of the 00 ACM SIGMOD International Conference on Manageent of Data (SIGMOD 0), Indianapolis, Indiana, USA, Jun 6-0, 00. New York, NY, USA: ACM, 00: [3] Yao Bin, Li Feifei, Kuar P. K nearest neighbor queries and knn-joins in large relational databases (alost) for free[c]// Proceedings of the 00 IEEE 6th International Conference on Data Engineering (ICDE 0), Long Beach, California, USA, Mar -6, 00. Washington, DC, USA: IEEE Coputer Society, 00: 4-5. [4] Qin Jianbin, Wang Wei, Lu Yifei, et al. Efficient exact edit siilarity query processing with the asyetric signature schee[c]//proceedings of the 0 ACM SIGMOD International Conference on Manageent of Data (SIGMOD ), Athens, Greece, Jun -6, 0. New York, NY, USA: ACM, 0: [5] Ki J, Lee H. Efficient exact siilarity searches using ultiple token orderings[c]//proceedings of the 0 IEEE 8th International Conference on Data Engineering (ICDE ), Washington, DC, USA, Apr -5, 0. Washington, DC, USA: IEEE Coputer Society, 0: [6] Wang Jiannan, Li Guoliang, Feng Jianhua. Can we beat the prefix filtering? An adaptive fraework for siilarity join and search[c]//proceedings of the 0 ACM SIGMOD International Conference on Manageent of Data (SIGMOD ), Scottsdale, AZ, USA, May 0-4, 0. New York, NY, USA: ACM, 0: [7] Yokoyaa T, Ishikawa Y, Suzuki Y. Processing all k-nearest neighbor queries in Hadoop[C]//LNCS 748: Proceedings of the 3th International Conference on Web-Age Inforation Manageent (WAIM ), Harbin, China, Aug 8-0, 0. Berlin, Heidelberg: Springer-Verlag, 0: [8] Zhang Chi, Li Feifei, Jestes J. Efficient parallel knn joins for large data in MapReduce[C]//Proceedings of the 5th International Conference on Extending Database Technology (EDBT ), Berlin, Gerany, Mar 7-30, 0. New York, NY, USA: ACM, 0: [9] Chaudhuri S, Ganja K, Ganti V, et al. Robust and efficient fuzzy atch for online data cleaning[c]//proceedings of the 003 ACM SIGMOD International Conference on Manageent of Data (SIGMOD 03), San Diego, California, USA, Jun 9-, 003. New York, NY, USA: ACM, 003: [0] Gravano L, Ipeirotis P G, Jagadish H V, et al. Approxiate string joins in a database (alost) for free[c]//proceedings of the 7th International Conference on Very Large Data Bases (VLDB 0), Roa, Italy, Sep -4, 00: [] Xiao Chuan, Wang Wei, Lin Xuein. Ed-Join: an efficient algorith for siilarity joins with edit distance constraints[j]. Proceedings of the VLDB Endowent, 008, (): [] Wang Jiannan, Li Guoliang, Feng Jianhua. Trie-Join: efficient Trie-based string siilarity joins with edit-distance constraints[j]. Proceedings of the VLDB Endowent, 00, 3(/): [3] Wang Jiannan, Li Guoliang, Feng Jianhua. Fast-join: an efficient ethod for fuzzy token atching based string siilarity join[c]//proceedings of the 7th International Conference on Data Engineering (ICDE ), Hannover, Gerany, Apr -6, 0. Washington, DC, USA: IEEE Coputer Society, 0: [4] Jacox E H, Saet H. Metric space siilarity joins[j]. ACM Transactions on Database Systes, 008, 33(): -38. [5] Yasin N S, Walid G A, Mohaed H A. The siilarity join database operator[c]//proceedings of the 6th International Conference on Data Engineering (ICDE 0), Long Beach, California, USA, Mar -6, 00. Washington, DC, USA: IEEE Coputer Society, 00: [6] Witten I H, Moffat A, Bell T C. Managing gigabytes: copressing and indexing docuents and iages[m]. San Francisco, CA, USA: Morgan Kaufann, 999. [7] Broder A Z, Glassan S C, Manasse M S, et al. Syntactic clustering of the web[j]. Coputer Networks and ISCN Systes, 997, 9(8/3): [8] Han Jiawei, Pei Jian, Yin Yiwen, et al. Mining frequent patterns without candidate generation: a frequent-pattern tree approach[j]. Data Mining and Knowledge Discovery, 004, 8(): [9] Bentley J L, Shaos M I. Divide-and-conquer in ultidiensional space[c]//proceedings of the 8th Annual ACM Syposiu on Theory of Coputing (STOC 76), Hershey, Pennsylvania, USA, May 3-5, 976. New York, NY, USA: ACM, 976: [30] Katoh N, Iwano K. Finding k farthest pairs and k closest/ farthest bichroatic pairs for points in the plane[c]//proceedings

13 庞 俊 等 : 相 似 性 连 接 查 询 技 术 研 究 进 展 3 of the 8th Annual Syposiu on Coputational Geoetry (SCG 9), Berlin, Gerany, Jun 0-, 99. New York, NY, USA: ACM, 99: [3] Lopez M A, Liao S. Finding k-closest-pairs efficiently for high diensional data[c]//proceedings of the th Canadian Conference on Coputational Geoetry (CCCG 00), Fredericton, Canada, Aug 6-9, 000: [3] Böh C, Braunüller B, Krebs F, et al. Epsilon grid order: an algorith for the siilarity join on assive high-diensional data[c]//proceedings of the 00 ACM SIGMOD International Conference on Manageent of Data (SIGMOD 0), Santa Barbara, CA, USA, May -3, 00. New York, NY, USA: ACM, 00: [33] Dittrich J P, Seeger B. Gess: a scalable siilarity join algorith for ining large data sets in high diensional spaces[c]// Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD 0), San Francisco, CA, USA, Aug 6-9, 00. New York, NY, USA: ACM, 00: [34] Zhao Xiang, Xiao Chuan, Lin Xuein, et al. Efficient graph siilarity joins with edit distance constraints[c]//proceedings of the 8th International Conference on Data Engineering (ICDE ), Washington, DC, USA, Apr -5, 0. Washington, DC, USA: IEEE Coputer Society, 0: [35] Wang Guoren, Wang Bin, Yang Xiaochun. Efficiently indexing large sparse graphs for siilarity search[j]. IEEE Transactions on Knowledge and Data Engineering, 0, 4(3): [36] Arun C M. MapReduce What s next[eb/ol]. [0-08-]. PANG Jun was born in 984. He is a Ph.D. candidate at Northeastern University, and the student eber of CCF. His research interests include cloud coputing and siilarity join. 庞 俊 (984 ), 男, 湖 北 咸 宁 人, 东 北 大 学 博 士 研 究 生,CCF 学 生 会 员, 主 要 研 究 领 域 为 云 计 算, 相 似 性 连 接 GU Yu was born in 98. He is an associate professor at Northeastern University, and the eber of CCF. His research interests include spatial data anageent and graph data anageent. 谷 峪 (98 ), 男, 辽 宁 鞍 山 人, 东 北 大 学 副 教 授,CCF 会 员, 主 要 研 究 领 域 为 空 间 数 据 管 理, 图 数 据 管 理 XU Jia was born in 984. She is a Ph.D. candidate at Northeastern University, and the student eber of CCF. Her research interests include RFID data anageent and siilarity join, etc. 许 嘉 (984 ), 女, 山 东 荣 成 人, 东 北 大 学 博 士 研 究 生,CCF 学 生 会 员, 主 要 研 究 领 域 为 RFID 数 据 管 理, 相 似 性 连 接 等 YU Ge was born in 96. He received his Ph.D. degree fro Kyushu University of Japan in 996. Now he is a professor and Ph.D. supervisor at Northeastern University, the senior eber of CCF and the eber of IEEE and ACM. His research interests include data strea, data ining and distributed database, etc. 于 戈 (96 ), 男, 辽 宁 大 连 人,996 年 于 日 本 九 州 大 学 获 得 博 士 学 位, 现 为 东 北 大 学 教 授 博 士 生 导 师, CCF 高 级 会 员, 美 国 ACM 和 IEEE 会 员, 主 要 研 究 领 域 为 数 据 流, 数 据 挖 掘, 分 布 式 数 据 库 等