slides_chap09 Modern Information Retrieval 2e 英文课件.pdf

Modern Information Retrieval Chapter 9 Indexing and Searching with Gonzalo Navarro Introduction Inverted Indexes Signature Files Suffix Trees and Suffix Arrays Sequential Searching Multi-dimensional Indexing Indexing and Searching, Modern Information Retrieval, Addison Wesley, 2010 – p. 1 Introduction Although efficiency might seem a secondary issue compared to effectiveness, it can rarely be neglected in the design of an IR system Efficiency in IR systems: to process user queries with minimal requirements of computational resources As we move to larger-scale applications, efficiency becomes more and more important For example, in Web search engines that index terabytes of data and serve hundreds or thousands of queries per second Indexing and Searching, Modern Information Retrieval, Addison Wesley, 2010 – p. 2 Introduction Index: a data structure built from the text to speed up the searches In the context of an IR system that uses an index, the efficiency of the system can be measured by: Indexing time: Time needed to build the index Indexing space: Space used during the generation of the index Index storage: Space required to store the index Query latency: Time interval between the arrival of the query and the generation of the answer Query throughput: Average number of queries processed per second Indexing and Searching, Modern Information Retrieval, Addison Wesley, 2010 – p. 3 Introduction When a text is updated, any index built on it must be updated as well Current indexing technology is not well prepared to support very freq