InfoMall数据检索服务的设计以及全文检索系统的初步实现

Presentation on theme: "InfoMall数据检索服务的设计以及全文检索系统的初步实现"— Presentation transcript:

1 InfoMall数据检索服务的设计以及全文检索系统的初步实现
杨志丰 1、Infomall的问题 2、解决模型 3、服务原语 4、服务系统组成 5、全文索引系统结构 6、索引构建流程 7、压缩算法 8、实验结果 9、本文贡献 10、谢谢

2 InfoMall万维网信息博物馆 中国万维网历史信息的存储和展示系统
维护2001年以来从中国万维网上搜集的近12亿篇网页（约20TeraByte） 以每月1000万的速度增长

3 现有服务及问题 目前提供三种服务 局限 根据URL检索历史网页 提供人工整理的历史事件专题回放 免费提供网页和日志数据
整理历史事件专题需要大量的人工工作 只能获得某个时间段搜集的全部网页，且免费数据的获取需要很多人工维护工作

4 InfoMall数据检索服务 目的 InfoMall数据检索服务 整合现有服务
通过统一的数据访问接口，提供更加丰富，更加自动和便利的数据服务 InfoMall数据检索服务 提供以InfoMall历史网页文档为核心数据，以内容、空间、时间为查询纬度的，面向高层应用的客户服务器体系结构的数据检索服务。

5 “三维”的数据模型

6 检索服务原语 Augmented BNF 语法定义（部分摘录如下） 例子
<query> = “select” <data-type> “from” <data-repository> “where” 1*<conditions> [“max” <maximum-item-number>] <conditions> = <content-condition> / <time-condition> / <location-condition> 例子 select Web-pages from where content contains 民主 time between to location at GEO: location at URL: *.gov.cn” <time>的表示采用国际标准ISO8601[7]中定义的时间日期的表示格式。这种格式兼顾了可读性和机器处理的方便性。例如，2000年1月30日8点30分59秒可以表示为” :30:59”。 <URL>为RFC1738[10]规定的统一资源定位符。 地区编码<region-code>采用中国国家标准GB [11]规定的中国地区编码。这样可以借助标准化数据带来的好处为客户提供统一灵活的服务。例如，150000代表内蒙古自治区，152700代表内蒙古自治区伊克昭盟，152701代表内蒙古自治区伊克昭盟东胜市。

7 系统组成

8 全文检索系统 lines

9 索引构建流程 （1）从文档源取得文档 （2）对文档进行分词得到<DocID, Term, Positions>三元组
（3）查看词典，把新出现的索引词合并到词典中，得到<DocID, TermID, Positions> （4）当<DocID, TermID, Positions>三元组的数量恰好填满内存时，对整个三元组集合执行快速排序 （5）使用“游程编码”处理递增排序的三元组，然后编码压缩，输出到临时顺串文件（run file） （6）对所有顺串文件执行多路归并，结果输出为最终索引文件 （7）将最终得到的词典存入文件

10 索引压缩 目的 方法 减少索引数据空间 提高索引构建的速度
第一步，游程编码，也就是把递增整数序列变换为差分序列（原来相邻整数之间的增量序列） 第二步，采用某种编码方法对整数进行编码

11 编码方法 统计方法 字典方法 哈夫曼编码（Huffman coding） 算术编码（arithmetic coding）
特定分布的ad-hoc编码 Unary Code (Pr[x]=2-x ) Delta Code Golomb Code 字典方法 Ziv-Lempel编码

12 实验结果

13 本文贡献 设计了一个服务：如何利用宝贵的历史网页数据提供公共信息服务以充分发挥信息作为研究工作基础设施的作用
设计和实现了全文索引系统：重点讨论了利用压缩技术减少全文索引的倒排文件索引的大小，为海量历史网页数据的检索服务提供现实可行的基础设施保障

14 谢谢！