Information Retrieval (AD-603 (C)) - Unit 3 Short Notes

How unit 3 is examined

This unit covers web search and its structure, crawling architectures, near-duplicate detection, index compression and XML retrieval; no past questions are recorded, so all five topics are equally likely.

Web search overview and web structure, paid placement, SEO

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Web search is retrieval of relevant pages from the huge, hyperlinked, uncontrolled web, ranked using both page content and link structure.</mark>

Key points.

1. The web is a directed graph in which pages are nodes and hyperlinks are edges, so link structure can signal importance.
2. Paid placement means advertisers bid to have their listings shown against chosen queries and pay per click.
3. Search engine optimization (SEO) is improving a page's content, titles and inbound links so that it ranks higher in organic results.
4. Black-hat SEO such as keyword stuffing or link farms is penalised as spam.

Web search architectures: crawling, meta-crawlers, focused crawling

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>A crawler is a program that follows hyperlinks from seed URLs to download pages for the indexer.</mark>

Key points.

1. The pipeline is crawler, then indexer, then query processor with ranking, and the crawler keeps a URL frontier of pages still to fetch.
2. A polite crawler obeys robots.txt and limits its request rate per host.
3. A meta-crawler has no index of its own; it sends the query to several search engines and merges their results.
4. A focused crawler follows only links likely to lead to pages on a chosen topic, saving bandwidth and storage.

Web indexes and near-duplicate detection

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Near-duplicate detection finds pages that are almost identical, using shingling, so that only one copy is indexed.</mark>

Key points.

1. A $k$-shingle is a contiguous run of $k$ words, and each document becomes its set of shingles.
2. Similarity is the Jaccard coefficient $J(A,B)=\frac{|A\cap B|}{|A\cup B|}$, and pages above a threshold are near-duplicates.
3. Hashing each shingle and keeping a small min-hash sketch avoids comparing full sets.
4. Removing duplicates shrinks the index and stops repeated results.

Index compression

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Index compression stores the postings lists in fewer bits so the index takes less disk and memory and is read faster.</mark>

Key points.

1. Postings are stored as gaps between sorted document IDs, since small gaps need fewer bits than large IDs.
2. Variable-byte coding uses 7 data bits per byte and a continuation bit.
3. Gamma coding writes the length of the offset in unary, then the offset, which is the binary number without its leading 1.
4. Example: gap 13 is 1101, so the offset is 101, the length 3 is written 1110, and the code is 1110101.

XML retrieval

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>XML retrieval is structured retrieval in which the units returned are document elements, not whole documents.</mark>

Key points.

1. An XML document is an ordered tree of nested elements, so a query can target a specific element.
2. Queries may combine content and structure, for example in the form of XPath-like paths.
3. The system must choose the right retrieval unit, because a whole document is too coarse and a tiny leaf element too small.
4. Results are ranked by element and nested results are avoided to reduce redundancy.

Last-minute revision

• Web is a directed graph: pages are nodes, hyperlinks are edges.
• Paid placement is pay-per-click bidding; SEO improves organic ranking.
• Crawler starts from seed URLs and uses a URL frontier and robots.txt.
• A meta-crawler queries several engines and merges their results.
• A focused crawler follows only topic-relevant links.
• Shingle is a $k$-word window; similarity is $J=\frac{|A\cap B|}{|A\cup B|}$.
• Compression stores docID gaps, not raw IDs.
• Gamma code of 13 is 1110101.
• XML retrieval returns elements from a tree.

Memory hooks

• Meta-crawler means borrowed index; focused crawler means topic-only.
• Shingle then Jaccard: sets of words, overlap over union.
• Gaps are small, so bits are few.
• SEO is organic, paid placement is bought.

Coverage checklist

• Web search overview, web structure the user paid placement search engine optimization: no past questions.
• Web Search Architectures - crawling - meta-crawlers, Focused Crawling: no past questions.
• web indexes - Near duplicate detection: no past questions.
• Index Compression: no past questions.
• XML retrieval: no past questions.