I read:
Christopher D. Manning, Prabhakar Raghavan, Hinrich
Schutze, “Introduction to Information Retrieval”. Cambridge University
Press. 2008. Chapter 4-5.
From 4.2: Large collections where index too large for memory but index is on a single machine
use blocked sort-based indexing (BSBI)
Single-pass in-memory indexing (SPIMI) - better (from 4.3)
From 4.4: Distributed indexing
term-partitioned index
Map Reduce - (parser and inverter)
From 5.1: Must use lossless compression.
From 5.2: Methods for Dictionary Compression:
store the whole dictionary as a string to avoid wasting space
group terms into blocks and store pointer
From 5.3: Methods for Postings file compression
variable encoding to store gaps between results
variable byte codes
γ codes
Question
Is it better to update an index to handle changes to documents or recreate on a schedule?
Thursday, January 26, 2012
Week 2 - Document and Query Processing - Muddiest Point
This week my muddiest point is what are the factors for determining N in N-Gram tokenization. Is index size the primary factor?
Thursday, January 19, 2012
Week 2 - Document and Query Processing - Reading Note
I read:
Christopher D. Manning, Prabhakar Raghavan, Hinrich Schutze, “Introduction to Information Retrieval”. Cambridge University Press. 2008. Section 1.2, Chapter 2, and Chapter 3.
The example process for creating an inverted index in Section 1.2 is a basic example but I think that it will prove to be a naive implementation.
In chapter 2, there are several mentions of doing tasks by hand; such as in machine learning tokenizing, filtering stop words, and synonym lists for token normalization. It is surprising to me that these systems require such careful hand-tuning but I suppose it makes sense given the crazy rules present in language.
From 3.1, Search trees > Hashing for Dictionaries.
From 3.2, Special Indexes for General Wildcard queries:
- permuterm index: rotations of each term (simple but space inefficient)
- k-Gram index: all k character long chunks of term (more complex and requires post-filtering of results)
From 3.3.3 - 3.3.4, isolated-term: k-Gram indexes used for spelling correction use the number of shared k-grams in the two terms.
From 3.3.5, Context-sensitive: use query frequency to correct.
Question
I'm curious how these techniques relate to real-world search engines. What of this is Google using?
Christopher D. Manning, Prabhakar Raghavan, Hinrich Schutze, “Introduction to Information Retrieval”. Cambridge University Press. 2008. Section 1.2, Chapter 2, and Chapter 3.
The example process for creating an inverted index in Section 1.2 is a basic example but I think that it will prove to be a naive implementation.
In chapter 2, there are several mentions of doing tasks by hand; such as in machine learning tokenizing, filtering stop words, and synonym lists for token normalization. It is surprising to me that these systems require such careful hand-tuning but I suppose it makes sense given the crazy rules present in language.
From 3.1, Search trees > Hashing for Dictionaries.
From 3.2, Special Indexes for General Wildcard queries:
- permuterm index: rotations of each term (simple but space inefficient)
- k-Gram index: all k character long chunks of term (more complex and requires post-filtering of results)
From 3.3.3 - 3.3.4, isolated-term: k-Gram indexes used for spelling correction use the number of shared k-grams in the two terms.
From 3.3.5, Context-sensitive: use query frequency to correct.
Question
I'm curious how these techniques relate to real-world search engines. What of this is Google using?
Week 1 - Introduction and Course Overview - Muddiest Point
Thankfully, I understood the introductory lecture and do not have a muddiest point this week.
Friday, January 6, 2012
Week 1 - Introduction and Course Overview - Reading Note
Modern Information Retrieval
- R. Baeza-Yates & B. Ribeiro-Neto
Finding Out About
- R. K. Belew
I found this reading interesting because the act of "finding out about" is such a basic function but I had never given it much thought. I think that step 3 assessing the answer is the most interesting step from a human perspective because I think that there are many factors at play to judge the answer.
This article also provided a nice overview of indexing and the challenges of selecting keywords to use for building an index.
Information Retrieval: Implementing and Evaluating Search Engines
- S. Büttcher, C. L. A. Clarke & G. V. Cormack
This article introduced some practical considerations for Information Retrieval systems such as: result quality (relevance), challenges of indexing, updating documents, and system performance.I appreciated that this article was more recent than the others. I think Google has spoiled us and so we take for granted how effective web search currently is.
Question
Now that we've seen an over view of the components of a Information Retrieval system, which component has the most room for future study and improvement?
- R. Baeza-Yates & B. Ribeiro-Neto
- Information Retrieval is built on Data Retrieval
- Information Retrieval is User Focused
- Data Retrieval is System Focused
- User Tasks
- Retrieval vs Browsing
Finding Out About
- R. K. Belew
I found this reading interesting because the act of "finding out about" is such a basic function but I had never given it much thought. I think that step 3 assessing the answer is the most interesting step from a human perspective because I think that there are many factors at play to judge the answer.
This article also provided a nice overview of indexing and the challenges of selecting keywords to use for building an index.
Information Retrieval: Implementing and Evaluating Search Engines
- S. Büttcher, C. L. A. Clarke & G. V. Cormack
This article introduced some practical considerations for Information Retrieval systems such as: result quality (relevance), challenges of indexing, updating documents, and system performance.I appreciated that this article was more recent than the others. I think Google has spoiled us and so we take for granted how effective web search currently is.
Question
Now that we've seen an over view of the components of a Information Retrieval system, which component has the most room for future study and improvement?
Subscribe to:
Posts (Atom)