Web Engineering & Development Lecture 5: Search Engines

A special symbol used in permuterm indexing to mark the beginning and end of a word, allowing rotations of the term for wildcard searches.

A technique used to search for terms that match a wildcard query, where the wildcard character () is rotated to the end of the string to create a unique lookup key in the permuterm index. For example, the wildcard query "unirse" would be rotated to "rse$uni*" for indexing.

A type of index that stores all possible k-grams (sequences of k characters) occurring in a set of terms. This allows for efficient searching of terms containing specific k-grams.

A special technique for processing wildcard queries using k-gram indexes. It involves breaking down the query into individual k-grams and then retrieving terms that match all the specified k-grams. Example: The query "mon*" could be broken into "$m", "mo", and "on".

A method of filtering the results of a wildcard query by checking the retrieved terms against the original query. This helps to eliminate false positives and ensure that the final results accurately match the intended query.

A type of query where the user uses the wildcard character * to represent any character or sequence of characters. For example, the query "autom*" would match terms like "automatic", "automation", and "automated".

A special character that is used to represent any character or sequence of characters in a wildcard query. For instance, the query "aeiou" would seek documents containing any term that includes all the five vowels in sequence.

A technique for handling wildcard queries. It works by rotating a term so that the wildcard character is always at the end. For example, the term "hello" would be indexed as: "hello$", "ello$h", "llo$he", "lo$hel", "o$hell" where $ represents the end of the term. This allows efficient lookups for different wildcard placements in a query.

A special symbol that is used to indicate the end of a term in the permuterm index.

A sequence of k consecutive characters within a term. Used in the k-gram index to store and retrieve terms effectively.

The process of measuring the similarity or distance between two strings by counting how many edit operations are needed to transform one string into another. Edit operations include insertions, deletions, and substitutions. For example, the edit distance between "cat" and "cot" is 1 (one substitution).

A technique for handling misspellings in search queries. It works by using the k-gram index to find potential matches that have a high overlap with the query's k-grams. This allows efficient searches for misspelled terms and provides suggestions for corrections.

A technique to find the words in a lexicon that are closest to a given character sequence, based on edit distance.

An algorithm for computing the edit distance between two strings. It involves dynamic programming to find the minimum number of operations.

The term-document inverted index is used for finding documents based on a query consisting of the terms in the query. The k-gram index is used for finding terms based on a query consisting of k-grams.

Misspellings in a query can be handled by suggesting several alternative queries with the correct spelling. The process of finding relevant documents based on the correct spellings.

Alternative techniques used for finding words in a lexicon that are closest to a given character sequence, such as k-gram overlap.

The number of times a term appears in a document.

A measure of how important a term is based on how often it appears in a document relative to its rarity in the entire corpus.

The number of documents in a collection containing a specific term.

A measure of how distinctive or rare a term is across a collection of documents.

A weighting scheme used to assign scores to documents based on the frequency of terms in the document and the inverse document frequency of those terms.

A logarithmic function that weights rarer terms more heavily.

A score that reflects the relevance of a document to a query. It is calculated by multiplying term frequency and inverse document frequency.

A method of finding words that match a query by comparing sets of overlapping characters (k-grams).

A commonly used measure of overlap between two sets of elements, calculated as the size of their intersection divided by the size of their union.

A system that ranks search results based on their relevance to a query, returning the most relevant documents first.

The process of assigning a score to each document based on its relevance to a query, used for ranking search results.

The process of adapting a standard postings merge algorithm to use the Jaccard coefficient (or another measure) to identify relevant words based on k-gram overlap.

A specific example where the query 'lorm' is compared to terms containing the bigram 'lo' using the Jaccard coefficient to find the best matches.

A measure of how relevant the retrieved documents are to the search query. Calculated as the ratio of relevant documents retrieved to the total number of documents retrieved.

A measure of how many relevant documents are retrieved from the total number of relevant documents in the database.

The process of evaluating the effectiveness of a search engine's ability to retrieve relevant documents for a given query.

The product of the term frequency (tf) and inverse document frequency (idf) for a particular term in a document. It reflects the importance of a term to a specific document within a collection.

A method for ranking documents based on the similarity between the query and the document. It calculates a score that reflects the overall importance of the terms in the query that appear in the document.

A measure used for evaluating the effectiveness of a search engine, based on the ability to retrieve relevant documents. It encompasses both precision and recall.