ITEC 4020 - L7: Indexing and Search

Search Types

The different kinds of searches users perform, including question answering, navigation, task accomplishment, and housekeeping.

Question Answering Search

A search focused on finding specific factual information, such as “best lens Sanibel.”

Navigation Search

A search used to locate a known web page or resource, such as “garden photography.”

Task Accomplishment Search

A search performed to complete an action, such as “photo sharing.”

Housekeeping Search

A search done to find site-related information like “privacy policy” or “contact us.”

SQL Search Limitation

SQL searches rely on exact matches and lack ranking or relevance-based results.

LIKE Operator Problem

The SQL LIKE operator performs linear scans (O(N)) and becomes inefficient with large datasets.

Full Text Search

A search technique that allows ranked, flexible, and high-performance retrieval from large text collections.

Benefits of Full Text Search

Provides fast results, relevance ranking, and reduces cases with no returned results.

Index in Databases

A data structure that improves retrieval speed by storing keywords and their locations.

Trade-off of Indexing

Indexes speed up reads but slow down writes and updates due to maintenance overhead.

Information Retrieval (IR) Index

An index designed for text and document retrieval, different from traditional DBMS indexes.

Inverted Index

A structure that maps words to the list of documents containing them, enabling fast searches.

Steps to Build an Inverted Index

Parse documents, extract tokens, sort tokens, merge duplicates, and store term frequencies.

Dictionary or Lexicon

In IR, a list of unique terms with the number of documents containing each term.

Postings File

A file that contains document IDs and positions for each term in the dictionary.

Term Frequency (TF)

The number of times a term appears within a document, used for ranking relevance.

Inverse Document Frequency (IDF)

A measure of how unique or rare a term is across all documents, calculated as log(N/nj).

TF-IDF Weighting

A ranking method that increases importance for terms that appear often in a document but rarely overall.

Stop Words

Common words like “and” or “the” that are ignored in search indexing to improve efficiency.

Stemming

Reduces words to their base form (e.g., “running” becomes “run”) to standardize search terms.

Relevance Ranking

The process of ordering search results based on how closely they match the query terms.

MySQL FULLTEXT Index

A feature that allows text-based indexing and searching for TEXT or VARCHAR columns.

Creating FULLTEXT Index

The SQL command CREATE TABLE or ALTER TABLE is used with FULLTEXT(title, body).

MATCH...AGAINST Syntax

The MySQL command for performing full text searches and retrieving ranked results.

Natural Language Mode

A MySQL search mode that interprets queries as normal phrases without special operators.

Boolean Mode

A MySQL search mode that supports operators like + (must include) and - (must exclude).

Query Expansion Mode

A MySQL search mode that expands queries by adding related terms automatically.

Relevance Score

A numerical value returned by MySQL to indicate how closely a record matches a search query.

SQL vs Full Text Search

SQL is exact-match based, while full-text search provides ranked, flexible, and faster querying.

Web Crawler

An automated program that browses the internet to collect and index web pages for search engines.

Web Crawling Process

Starts with known URLs, follows links recursively, respects robots.txt, and stores page data.

robots.txt

File on a website that defines which pages web crawlers are allowed or disallowed to access.

Duplicate Detection

Uses hashing to detect and ignore identical pages during crawling.

Recrawling

Revisiting web pages periodically to ensure index freshness and accuracy.

Search Engine Challenges

Issues like broken links, duplicate pages, and misleading or spam content.

Link Analysis

Technique where pages gain ranking based on how many other reputable pages link to them.

PageRank

Google’s algorithm that ranks pages based on incoming links weighted by their own importance.

PageRank Formula

PR(A) = (1-d) + d(PR(A1)/C(A1) + … + PR(An)/C(An)), where d is the damping factor (~0.85).

PageRank Damping Factor

A value (typically 0.85) representing the probability a user continues following links.

Hit List

In Google’s indexing, a list of tuples

Barrels

Inverted files grouped by topic or word ID range, used in Google’s index for efficient searching.

Lexicon

A mapping of words to word IDs and their positions in the index structure.

Google Ranking Combination

Google combines PageRank (link importance) with IR relevance (TF-IDF) for results.

SQL Search Complexity

Linear time O(N) — inefficient for large datasets.

Full Text Search Complexity

Constant time O(1) — efficient with indexes.

Difference Between IR and DBMS Indexing

IR focuses on keyword relevance; DBMS indexes focus on primary key access.

Crawling Freshness

The measure of how up-to-date a search index is compared to the live web.

Ranking Factors

Combination of TF-IDF scores, PageRank, and metadata relevance in modern search engines.

Full Text Search Example Query

SELECT * FROM articles WHERE MATCH(title, body) AGAINST('database' IN NATURAL LANGUAGE MODE);

Boolean Mode Example

SELECT * FROM articles WHERE MATCH(title, body) AGAINST('+database -MySQL' IN BOOLEAN MODE);

Query Expansion Example

SELECT * FROM articles WHERE MATCH(title, body) AGAINST('database' WITH QUERY EXPANSION);

Relevance Ranking Advantage

Ensures that more meaningful results appear higher in search output.

Information Retrieval Goal

Retrieve the most relevant documents efficiently based on the user’s search intent.