Journal of Computer Applications ›› 2013, Vol. 33 ›› Issue (07): 2031-2036.DOI: 10.11772/j.issn.1001-9081.2013.07.2031

• Network and distributed techno • Previous Articles     Next Articles

New inverted index storage scheme for Chinese search engine

MA Jian1,ZHANG Taihong1,2,CHEN Yanhong1   

  1. 1. College of Computer and Information Engineering, Xinjiang Agricultural University, Urumqi Xinjiang 830052, China
    2. College of Information and Electrical Engineering, China Agricultural University, Beijing 100083, China
  • Received:2013-01-25 Revised:2013-03-06 Online:2013-07-06 Published:2013-07-01
  • Contact: ZHANG Taihong

中文搜索引擎分块倒排索引存储模式

马健1,张太红1,2,陈燕红1   

  1. 1. 新疆农业大学 计算机与信息工程学院,乌鲁木齐 830052
    2. 中国农业大学 信息与电气工程学院,北京 100083
  • 通讯作者: 张太红
  • 作者简介:马健(1984-),男,新疆乌鲁木齐人,硕士,主要研究方向:搜索引擎、数据库;张太红(1965-),男,甘肃静宁人,教授,主要研究方向:数据库;陈燕红(1979-),女,新疆乌鲁木齐人,讲师,硕士,主要研究方向:数据库。
  • 基金资助:

    新疆维吾尔自治区科技攻关项目(200931103)

Abstract: After analyzing inverted index structure and access mode of an open source search engine-ASPSeek, this paper gave an abstract definition of "inverted index". In order to solve the difficulties of inverted index updating and the efficiency issues caused by directly accessing inverted index through file caching of operating system in ASPSeek, considering the characteristics of 1.25 million Chinese agricultural Web pages, this article proposed a new blocking inverted index storage scheme with a buffer mechanism which was based on CLOCK replacement algorithm. The experimental results show that the new scheme is more efficient than ASPSeek whether the buffer system is disabled or enabled. When the buffer system got enabled and 160 thousand Chinese terms or 50 thousand high-frequency Chinese terms were used as a test set, the retrieval time of new scheme tended to be a constant after one million accesses. Even when using entire 827309 terms as a test set, the retrieval time of new scheme began to converge after two million accesses.

Key words: inverted index, search engine, full-text retrieval, blocking structure, retrieval efficiency

摘要: 针对开源搜索引擎ASPSeek中的倒排索引的内部结构和访问模式,抽象出了倒排索引的形式化定义。为解决ASPSeek倒排索引更新困难和直接采用操作系统文件缓冲访问机制带来的效率问题,以125万张中文农业网页为样本,结合其特点,提出了一种块大小可变的分块倒排索引存储模式和基于CLOCK替代策略的专用缓冲管理机制。实验结果表明在禁用和启用缓冲的情况下,分块访问模式检索效率都优于ASPSeek。在启用缓冲并使用16万中文词条或5万高频中文词条作为测试集合的条件下,分块存储模式在访问倒排索引100万次后的检索时间趋于常量,即使以全部的827309个词条作为测试集合的条件下,分块存储模式在访问倒排索引200万次后的检索时间趋于收敛。

关键词: 倒排索引, 搜索引擎, 全文检索, 分块结构, 检索效率

CLC Number: