1、北 京 大 学 博 士 研 究 生 学 位 论 文题 目 ： 搜 索 引 擎 检 索 系 统 的 效 率 优 化与 效 果 评 估 研 究姓 名 ： 彭 波学 号 ： 10108808院 系 ： 计 算 机 科 学 技 术 系专 业 ： 计 算 机 系 统 结 构研 究 方 向 ： 计 算 机 网 络 与 分 布 式 系 统导 师 ： 李 晓 明 教 授2004 年 5 月On Efficiency Optimization and Effectiveness Evaluation of Search Engine Retrieval SystemDissertation Submitted
2、toPeking Universityin partial fulfillment of the requirementFor the degree ofDoctor of Natural ScienceByPeng Bo( Computer Science and Technology )Dissertation Supervisor: Professor Xiaoming LIMay, 2004版 权 声 明任 何 收 存 和 保 管 本 论 文 各 种 版 本 的 单 位 和 个 人 ， 未 经 本 论 文作 者 同 意 ， 不 得 将 本 论 文 转 借 他 人 ， 亦 不 得 随 意
3、 复 制 、 抄 录 、 拍照 或 以 任 何 方 式 传 播 。 否 则 ， 引 起 有 碍 作 者 著 作 权 之 问 题 ， 将 可能 承 担 法 律 责 任 。 i 摘 要本 文 研 究 工 作 是 国 家 重 点 基 础 研 究 发 展 规 划 项 目 “网 络 环 境 下 海 量 信息 组 织 与 处 理 的 理 论 与 方 法 研 究 ”的 一 部 分 ； 针 对 Web 搜 索 引 擎 应 用 背 景 ，以 构 建 大 规 模 、 高 性 能 搜 索 引 擎 的 检 索 系 统 为 目 标 ， 系 统 地 研 究 了 检 索 系 统的 效 率 问 题 和 效 果 评 估 问 题
4、 ， 提 出 了 若 干 关 键 技 术 ， 在 大 量 实 验 和 真 实 数 据分 析 的 基 础 上 ， 得 到 了 如 下 研 究 成 果 和 结 论 ：1） 提 出 了 一 种 混 合 索 引 技 术 。 该 技 术 针 对 中 文 信 息 检 索 索 引 词 选 择 的问 题 ， 通 过 结 合 中 文 自 动 分 词 与 未 登 录 词 识 别 技 术 ， 把 基 本 分 词 结 果 与 在 识别 生 成 的 扩 展 词 典 上 的 分 词 结 果 都 选 择 作 为 索 引 词 。 通 过 在 实 际 系 统 的 应 用实 践 ， 表 明 该 技 术 能 有 效 提 高 短 语
5、 检 索 效 率 。2） 提 出 了 一 种 倒 排 文 件 分 块 组 织 方 法 ， 它 兼 顾 了 文 档 编 号 序 列 和 文 档权 值 序 列 在 检 索 系 统 性 能 中 的 不 同 作 用 ， 为 综 合 优 化 系 统 性 能 提 供 了 一 个 可操 作 的 框 架 。 和 已 有 相 关 工 作 相 比 ， 这 一 研 究 基 于 搜 索 引 擎 应 用 背 景 ， 通 过搜 索 引 擎 系 统 的 实 际 数 据 ， 建 立 了 一 个 检 索 性 能 模 型 ， 在 此 模 型 基 础 上 研究 分 块 组 织 策 略 对 性 能 的 影 响 和 分 块 参 数 的
6、 优 选 。 研 究 结 果 表 明 ， 这 一 分 块组 织 策 略 可 以 有 效 提 高 检 索 效 率 。3） 倒 排 文 件 缓 存 是 检 索 系 统 效 率 优 化 的 重 要 技 术 。 结 合 到 大 规 模 检 索过 程 中 磁 盘 I/O 以 及 操 作 系 统 页 面 调 度 的 特 点 ， 本 文 研 究 了 倒 排 文 件 缓 存 优化 设 计 中 的 性 能 指 标 选 择 、 替 换 算 法 、 页 面 大 小 和 倒 排 文 件 组 织 方 式 对 缓 存性 能 影 响 等 问 题 。 研 究 结 果 为 倒 排 文 件 缓 存 优 化 设 计 提 供 了 指
7、 导 。4） 针 对 搜 索 引 擎 检 索 系 统 效 果 评 估 中 的 若 干 问 题 ， 设 计 并 实 现 了 一 个搜 索 引 擎 检 索 系 统 检 索 效 果 评 估 的 实 验 环 境 。 基 于 搜 索 引 擎 的 用 户 查 询 日 志 ，按 查 询 类 别 构 建 了 用 户 查 询 集 合 。 对 不 同 搜 索 引 擎 搜 集 系 统 搜 集 网 页 集 合 的差 异 、 评 测 员 结 果 之 间 的 差 异 对 评 估 实 验 的 稳 定 性 、 连 续 性 的 相 关 度 评 分 分值 以 及 对 应 的 评 估 指 标 、 查 询 集 合 大 小 对 评 估
8、 实 验 的 稳 定 性 等 问 题 进 行 了 研究 ， 结 果 对 于 进 行 有 效 的 检 索 评 估 实 验 有 重 要 指 导 意 义 。5） 基 于 对 搜 索 引 擎 用 户 点 击 日 志 数 据 的 分 析 ， 提 出 了 一 种 自 动 构 建 评估 实 验 相 关 结 果 集 合 与 进 行 自 动 评 估 实 验 的 方 法 。 实 验 显 示 这 一 自 动 方 法 得 ii 到 的 结 果 和 人 工 评 估 实 验 结 果 保 持 一 致 ， 并 且 对 不 同 查 询 集 合 保 持 稳 定 。 这一 方 法 为 解 决 大 规 模 数 据 集 上 检 索 系
9、 统 评 估 的 可 扩 展 性 问 题 提 供 了 一 条 有 效的 途 径 。关 键 词 ： 万 维 网 ， 搜 索 引 擎 ， 信 息 检 索 ， 检 索 效 率 ， 性 能 ， 评 估 iii AbstractSearch engine is now an infrastructure of the information society. In this dissertation, we studied the performance of large-scale retrieval system of search engine; especially focused on eff
10、iciency optimization and effectiveness evaluation. The main contributions include:1. A mixture index term selection method is proposed. By integrating the techniques of Chinese automatic word segmentation and unknown word detection, we select both the results of word segmentation on the basic dictio
11、nary and the results on the extended dictionary consisting of detected words as index terms. This method can improve the efficiency of phrase query and is successfully applied in the Tianwang search engine system.2. A block organization of inverted file is proposed. It integrates the effects of the
12、document identifier data and document weight data to improve the efficiency of retrieving process. A performance model of retrieval system was build based on the real data of Tianwang search engine, and then the block organization was studied by simulations on this model. The results show that this
13、method improves the efficiency of retrieving process.3. Inverted file cache is an important technique for system performance optimization. We studied some important problems in the optimal design of inverted file cache, which include the performance metrics selection, replacement algorithms comparis
14、ons, the effects of page size and physical organization of inverted file, etc. The results give a good guide for implementation of cache system.4. Aiming at the problems in effectiveness evaluation of the retrieval system in search engine, we designed and implemented an evaluation experiment platfor
15、m. We constructed a query set with query types and studied many problems of the evaluation on Web search, which include the effects of the continuous relevance scores and the evaluation stableness on the iv difference of relevance assessors, measures and query set size. The results are important for
16、 guiding effective evaluation experiments.5. An automatic evaluation method is proposed based on analyzing the click log of search engine. The results of experiments based on this automatic evaluation method are consistent with the results of the one on the manual judgment, and keep stable to different query sets. This automatic evaluation method is a promising answer for the scalability problem of the evaluation on large-scale Web search system.Keywords: Worldwide Web, Search Engine, Information Retrieval, Retrieval Efficiency, Performance, Evaluation
