Module 3.

Query Languages
Outline
■ Keyword-Based Querying
■ Pattern Matching
■ Structural Queries
■ Query Protocols
Keyword-Based Querying
■ A query is formulation of a user information need.
■ In its simplest form, a query is composed of keywords and
the documents containing such keywords are searched for.
■ Keyword-based queries are popular because they are
intuitive, easy to express, and allow for fast ranking.

1. Single-Word Queries
2. Context Queries
3. Boolean Queries
4. Natural Language Queries
[Link]-Word Queries
■ A query is formulated by a word.
■ A document is formulated by long sequences of words.
■ A word is a sequence of letters surrounded by separators
■ A definition of letter and separator is flexible. e.g hyphen - can
be defined as a letter or a separator e.g on-line

■ The result of word queries is the set of documents containing

word of the query.
■ Further, the resulting documents are ranked according to a
degree of similarity to the query.
■ To support ranking, two common statistics on word occurrences
inside texts are commonly used: 'term frequency' and 'inverse
document frequency' (TF-IDF)
2. Context Queries
■ Definition
- Search words in a given context that is near other words.
- We may want to form phrases of words or find words which are proximal in the text.
-Words which appear near each other may signal a higher likelihood of relevance than
if they appear apart.
-Cotextual queries help to capture meaning and context of words within the
documents, making search results more precise.
Types
⮚ Phrase (some flexibility on how the words are separated)
>a sequence of single-word queries
>e.g. enhance retrieval, red apple
⮚ Proximity ( a relaxed version of phrase query)

>a sequence of single words or phrases, and a maximum allowed distance

between them are specified.
>e.g,within distance (enhance, retrieval, 4) will match ‘…enhance the
power of retrieval…’
⮚ This is useful when you are looking for concepts that might be expressed by
multiple different phrases. e.g Curriculum Theories
Boolean Queries
▪ Definition
▪ A syntax composed of atoms that retrieve documents, and of
Boolean operators which work on their operands
▪ e.g, translation AND syntax OR syntactic

■ Fuzzy Boolean(Partial Matching)

⮚ Retrieve documents appearing in some operands (The AND
may require it to appear in more operands than the OR)
=
Natural Language
■ Generalization of “fuzzy Boolean”
■ A query is an enumeration of words and context queries
■ All the documents matching a portion of the user query
are retrieved.
■ Higher ranking is assigned to those documents matching
more parts of the query.
■ The negation can be handled by letting the user express
that some words are not desired.
■ A threshold may be selected so that the documents with
very low weights are not retrieved.
■ Under this scheme we have completely eliminated any
reference to Boolean operations and entered into the field
of natural language queries.
Pattern Matching
■ A pattern is a set of syntactic features that must
occur in a text segment.
/OCR
‘pro(blem|tein)(s|є)(0|1|2)*’->’problem2’ and ‘proteins’
8. Extended Patterns:
■ Extended patterns are a user friendly way to represent complex search queries.
■ EPs are subsets of REs which are expressed with simpler syntax.
■ Retrieval systems can internally convert external patterns into REs or search them
with specific algorithm.
■ Each system supports its own set of EPs and hence no formal definition exists for
EPs.
Structural Queries
■ Mixing contents and structure in queries
- contents: words, phrases, or patterns
- structural constraints: containment, proximity, or other
restrictions on structural elements present in the
document.

■ The Boolean queries can be built on top of the

structural queries, so that they combine the sets of
documents delivered by those queries.

■ Three main structures

- Fixed structure (Filled form)
- Hypertext structure (web pages)
- Hierarchical structure (books, articles,legal documents)
1. Fixed Structure
■ The documents had a fixed set of fields, much like a filled form.
■ Each field had some text inside.
■ Some fields were not present in all documents.
■ Only rarely could the fields appear in any order or repeat across a document.
■ A document could not have text not classified under any field.
■ Fields were not allowed to nest or overlap.
■ The retrieval activity allowed on them was restricted to specifying that a given
basic pattern was to be found only in a given field.
■ Most current commercial systems use this model.
■ This model is reasonable when the text collection has a fixed structure.
■ EX: a mail has a sender, a receiver, a date, a subject and a body field.
User can search for the mails sent to a given person with “football” in the Subject field.

■ Drawback:The model is inadequate to represent the hierarchical structure present

in an HTML document,
 2. Hypertext
■ Hypertexts probably represent the maximum freedom with respect to structuring power.
■ A hypertext is a directed graph where the nodes hold some text and the links represent
connections between nodes or between positions inside the nodes .

■ Initially, the retrieval from a hypertext began as a merely navigational activity. That
is, the user had to manually traverse the hypertext nodes following links to search what
he wanted.

■ It was not possible to query the hypertext based on its structure. Even in the Web
one can search by the text contents of the nodes, but not by their structural connectivity.

■ An interesting proposal to combine browsing and searching on the Web is WebGlimpse.

■ It allows classical navigation plus the ability to search by content in the neighborhood of
the current node.
 Hypertext : WebGlimpse

WebGlimpse: combine browsing and searching on the Web

■ Querying hypertexts based on both their content and structure requires specialized tools
and techniques that can handle the complexity of hypertext documents.

■ Hypertexts, such as web pages, are interconnected through links and contain a mixture
of text, images, multimedia, and other elements.

■ The following tools and techniques are commonly used for this purpose:

1. XPath

● Purpose: XPath is a query language for selecting nodes from an XML document, which
can also be applied to HTML documents.
● Functionality: It allows users to query hypertexts based on their structure by
navigating through the document's hierarchy, selecting elements, attributes, and text.
● Example: Extracting all links (<a> tags) from a webpage or selecting all paragraphs
within a specific section.

2. CSS Selectors

● Purpose: CSS selectors are used to select elements in HTML documents based on their
attributes, classes, IDs, or relationships to other elements.
● Functionality: Similar to XPath, but more focused on the styling attributes of HTML
elements, making it useful for querying content based on structural relationships.
● Example: Selecting all headings (<h1>, <h2>, etc.) within a specific <div>.

3. Regular Expressions (Regex)

● Purpose: Regex is a powerful tool for searching and manipulating strings based on
patterns.
● Functionality: It can be used to query content within hypertexts by identifying patterns
4. SQL/XML or XQuery

● Purpose: SQL/XML and XQuery are query languages designed for querying XML data.
● Functionality: XQuery can be used to query both the content and structure of XML-based hypertexts.
SQL/XML integrates SQL queries with XML content, allowing for complex querying of structured
documents.
● Example: Retrieving specific elements from an XML document based on hierarchical relationships
and content.

5. Web Scraping Libraries (e.g., BeautifulSoup, Scrapy)

● Purpose: These libraries are designed to extract data from web pages by parsing HTML or XML
content.
● Functionality: They combine content and structural querying by allowing users to traverse the
document tree, extract elements, and analyze the content within those elements.
● Example: Extracting all articles from a news website and analyzing their structure to identify the most
common layout patterns.
3) Hierarchical Structure
Hierarchical Structure
Samples of Hierarchical Model
■ PAT Expressions
■ Overlapped Lists
■ Lists of References
■ Proximal Nodes
■ Tree Matching

link : Samples of Hierarchical Models

Query Protocols
■ These are query languages that are used automatically by software applications to
query text databases.
■ Some of them are proposed as standards for querying CD-ROMs or as intermediate
languages to query library systems. Because they are not intended for human
use, we refer to them as protocols rather than languages.
■ Some of the query protocols are:
⮚ Z39.50
⮚ WAIS (Wide Area Information Service)
⮚ CCL (Common Command Language)
⮚ CD-RDx (Compact Disk Read only Data exchange)
⮚ SFQL (Structured Full-text Query Language)
Z39.50
■ It is a protocol approved as a standard in 1995 by ANSI and NISO.

■ This protocol is intended to query bibliographical information using a standard

interface between the client and the host database manager which is independent
of the client user interface and of the query database language at the host.

■ The database is assumed to be a text collection with some fixed fields (although it
is more flexible than usual).

■ The Z39.50 protocol is used broadly and is part, for instance, of WAIS.

■ The protocol does not only specify the query language and its semantics, but also
the way in which client and server establish a session, communicate and exchange
information, etc.

■ Although originally conceived only to operate on bibliographical information (using

the Machine Readable Cataloging Record (MARC) format), it has been extended to
query other types of information as well.
WAIS(Wide Area Information Service)
■ WAIS is a suite of protocols that was popular at the beginning of the 1990s before the boom
of the Web. The goal of WAIS was to be a network publishing protocol and to be able to
query databases through the Internet.
 Other Query protocols….
■ In the CD-ROM publishing arena, there are several proposals for query protocols. The
main goal of these protocols is to provide 'disk interchangeability.' This means more
flexibility in data communication between primary information providers and end users.
It also enables significant cost savings since it allows access to diverse information
without the need to buy, install, and train users for different data retrieval applications.
We briefly cover three of these proposals:
a. CCL (Common Command Language) is a NISO proposal (Z39.58 or ISO 8777)
based on Z39.50. It defines 19 commands that can be used interactively. It is
more popular in Europe, although very few products use it. It is based on the
classical Boolean model.
b. CD-RDx (Compact Disk Read only Data exchange) uses a client-server
architecture and has been implemented in most platforms. The client
is generic while the server is designed and provided by the CD-ROM
publisher
who includes it with the database in the CD-ROM. It allows fixed-length fields,
images, and audio, and is supported by such US national agencies as the CIA,
NASA, and GSA.
Other Query protocols….
c. SFQL (Structured Full-text Query Language)
■ It is based on SQL and also has a client-server architecture.
■ SFQL has been adopted as a standard by the aerospace community (the Air Transport
Association/Aircraft Industry Association).
■ Documents are rows in a relational table and can be tagged using SGML.
■ The language defines the format of the answer, which has a header and a variable length
message area.
■ The language does not define any specific formatting or markup. For example, a query in
SFQL is:
Select abstract from [Link] where title contains
"text search"
■ The language supports Boolean and logical operators, thesaurus, proximity
operations, and some special characters such as wild cards and repetition. For
example:
where paper contains "retrieval" or like "info %"
and date > 1/1/98
■ Compared with CCL or CD-RDx, SFQL is more general and flexible, al-though it is
based on a relational model, which is not always the best choice for a document
database.
Module 3.2

Query Operations
Query Modification
■ Approaches for Improving initial query formulation
through query expansion and term reweighting.
⮚ Relevance feedback
• approaches based on feedback information from users.

⮚ Local analysis
• approaches based on information derived from the set of
documents initially retrieved (called the local set of documents).
• The system analyzes these documents to identify additional
important terms.

⮚ Global analysis
• approaches based on global information derived from the entire
document collection, not only initial retrieved documents.
• It builds statistical or semantic relationships between terms across
the whole corpus.
 Relevance Feedback (RF)
■ The main idea consists of
⮚ selecting important terms, or expressions, attached to
the documents that have been identified as relevant by
the user, and
⮚ enhancing the importance of these terms in a new
query formulation.

■ The expected effect is that the new query will be moved

towards the relevant documents and away from the non-
relevant ones.

■ Two basic techniques of query modification using RF

⮚ Query expansion
• addition of new terms from relevant documents
⮚ Term reweighting
• modification of term weights based on the user relevance
judgement
 Relevance Feedback (RF)

■ Two basic techniques of query modification using RF

⮚ Query expansion
• addition of new terms from relevant documents

⮚ Term reweighting
• modification of term weights based on the user relevance
judgement
Advantages of Relevance Feedback over other query
reformulation strategies

1. Shields the user from query reformulation details

● The user doesn’t need to manually change the query.

● They only need to mark documents as relevant or not relevant.
● The system handles all the mathematical work of reweighting and
expanding terms.
- Advantage: Makes the search process user-friendly and less
technical.

2. Breaks the searching task into small, easy steps

● Instead of expecting the user to craft a perfect query at the beginning,

RF allows incremental improvement.
● The user starts with an initial query → system retrieves results → user
gives feedback → query improves → better results.
- Advantage: Helps the user gradually reach the most relevant set of
documents.
Advantages of Relevance Feedback over other query
reformulation strategies

3. Provides a controlled process of emphasizing/de-emphasizing

terms

● RF automatically increases weights of useful (relevant) terms

(appearing in relevant docs).

● It reduces the impact of irrelevant terms (appearing in non-relevant

docs).

● The result is a refined and focused query that captures the user’s
real intent.
-Advantage: Improves both precision (fewer irrelevant docs) and
recall (more relevant docs found).
Query Expansion and Term Reweighting for
the Vector-space Model
■ The application of relevance feedback to the vector
model considers that —
1. relevant documents resemble each other.
2. non-relevant documents have term-weight vectors
which are dissimilar from the ones for the relevant
documents.

■ The basic idea is to reformulate the query such that it

gets closer to the term-weight vector space of the
relevant documents.
Query Expansion and Term Reweighting

● In the Vector Space Model (VSM), Query Expansion and

Term Reweighting are techniques used to enhance the
effectiveness of information retrieval by -
○ refining the user's query and
○ adjusting the importance of terms within that query.
 Technique 1 : Query Expansion

■ Query Expansion involves modifying the original user query to

include additional terms that are semantically related or highly
relevant to the original terms.

■ The goal is to capture more relevant documents that might not

be retrieved with the original query terms alone.

■ The expanded query improves recall by retrieving documents that contain

any of the expanded terms, thus covering a broader range of relevant
documents.
Query Expansion Methods
● Synonym Expansion: Adding synonyms of the query terms.
○ For example,Query: "job"
○ Expanded: "job OR employment OR occupation OR profession OR
career"
● Stemming or Lemmatization: Expanding the query to include different
forms of a word.
○ For example, "run" might be expanded to include "running," "ran,"
etc.
● Thesaurus-based Expansion: Using a thesaurus to find related words.
○ For example, "data mining" might be expanded to include "knowledge
discovery."
● Relevance Feedback: Based on user feedback, expanding the query with terms
found in relevant documents.
○ If a user marks documents containing "text mining" as relevant, the query might
be expanded to include "text mining."

● Co-occurrence or Statistical Methods: Identifying terms that frequently co-occur

with the original query terms in the document corpus.
○ For example, if "artificial intelligence" frequently co-occurs with "machine
learning," the query might be expanded to include "machine learning."
Technique 2: Term Reweighting
■ Term Reweighting in the Vector Space Model adjusts the
importance (weight) of each term in the query vector to better
reflect its significance in retrieving relevant documents.

■ The weights are typically based on the term's frequency in the

document(TF) and its inverse document frequency (IDF).
Reweighting Process
1. Initial Weight Assignment: Initially, each term in the query is
assigned a weight based on TF-IDF.
2. Relevance Feedback: If relevance feedback is available (e.g.,
the user marks certain documents as relevant), the system can
reweight terms based on their occurrence in relevant versus non-
relevant documents.
3. Rocchio Algorithm (Example): The Rocchio algorithm can be
used to adjust the query vector by emphasizing terms in relevant
documents and de-emphasizing those in non-relevant ones:

● This reweighting adjusts the query vector to improve the retrieval

of relevant documents.
■ Rocchio Algorithm Formula
Example 1
Original Query: data mining
weight (data) = 0.3
weight (mining) = 0.7
Relevance Feedback:
■ D1 [0.4,0.8] and D2 [0.5,0.6] are marked as Relevant by user and
■ D3 [0.2,0.1] non-relevant.
Find modified query vector using vector space model.

Rocchio formula.( α=1,β=0.75,γ=0.25 )

Example
Step 6: Interpret the Reweighted Query

■ The reweighted query vector indicates that the term "mining"

has gained more importance relative to "data" based on the
feedback.

■ When this new query vector is used to search the document

collection, it will prioritize documents that emphasize "mining"
more strongly, thus likely improving the relevance of the
retrieved documents.
Summary
■ Original Query: A simple vector based on initial term weights.
■ Relevance Feedback: Incorporates user feedback on document
relevance.
■ Rocchio Algorithm: Adjusts the original query vector by adding
information from relevant documents and subtracting influence from non-
relevant ones.
■ Reweighted Query: A new query vector with updated term weights,
which better reflects the user's true intent and improves the accuracy of
search results.
Advantages of relevance feedback techniques

■ The main advantages of the relevance feedback techniques are

simplicity and good results.

⮚ The simplicity is due to the fact that the modified term

weights are computed directly from the set of retrieved
documents.

⮚ The good results are observed experimentally and are due

to the fact that the modified query vector does reflect a
portion of the intended query semantics.
Disadvantages of relevance feedback techniques

■ The main disadvantage is that no clear rule (optimality

criterion) is adopted:

⮚ Without an optimality criterion, there's no systematic way

to evaluate whether the query modifications are actually
improving the relevance of search results.

⮚ The modifications might be based on heuristic or ad-hoc

adjustments rather than a principled approach.

⮚ This can lead to suboptimal query changes that do not

significantly enhance the retrieval performance.
Example 2
Use Rocchio reweighting with α=1, β=0.8, γ=0.2

● Query Q: “data warehouse”

● Relevant DR​: “ETL and OLAP in data warehouse”

● Non-relevant DNR​: “warehouse logistics and inventory”

Use binary term frequencies over the vocabulary

{data,warehouse,ETL,OLAP,logistics,inventory}
 Solution
Vocabulary: {data, warehouse, ETL, OLAP, logistics, inventory}

● Query Q: “data warehouse” [0.6931, 0]

● Relevant DR​: “ETL and OLAP in data warehouse” [0.6931, 0, 0.6931, 0.6931, 0, 0]
● Non-relevant DNR​: “warehouse logistics and inventory” [0, 0, 0, 0, 0.6931,
0.6931]

Answer:
Q′={data:(1+0.8)=1.8,warehouse:(1+0.8−0.2)=1.6,ETL=0.8,OLAP=0.8,logistics=−0.2,inventory=−0.2}

Q′= [1.8, 1.6, 0.8, 0.8, −0.2 , −0.2]

Example 3
■ A query Q={AI:1, ML:1} is submitted to a system.
■ The user marks one document as relevant DR={AI:2, ML:3, Deep:1}
and one document as non-relevant DNR={AI:1, Spam:2}
■ Using Rocchio’s formula with α=1,β=0.75,γ=0.25 compute the new
query vector Q′
Solution
Step 1: Write given data

● Original query: Q={AI:1, ML:1}

● Relevant document centroid: DR={AI:2, ML:3, Deep:1}
● Non-relevant document centroid: DNR={AI:1, Spam:2}
● α=1,β=0.75,γ=0.25

Step 2: Apply weights

● αQ = 1⋅{AI:1, ML:1} = {AI:1, ML:1}

● βDR = 0.75⋅{AI:2, ML:3, Deep:1} = {AI:1.5, ML:2.25, Deep:0.75}

● γDNR = 0.25⋅{AI:1, Spam:2} = {AI:0.25, Spam:0.5}

Solution(Cntd..)
Step 3: Combine

● Q′ = {AI:1,ML:1} + {AI:1.5,ML:2.25,Deep:0.75} − {AI:0.25,Spam:0.5}

Step 4: Final Query Vector

● Q′ = {AI:(1+1.5−0.25) =2.25, ML:(1+2.25)=3.25, Deep:0.75, Spam:−0.5}

The new query vector is:

Q′ = {AI: 2.25, ML: 3.25, Deep: 0.75, Spam: -0.5}

Thus, ML and AI gain higher weight, “Deep” is added, and “Spam” is penalized. This improves retrieval toward
documents more relevant to the user.
Term Re-Weighting for the Probabilistic Model
■ Term reweighting in probabilistic models is the process of
adjusting the weights (or importance) of query terms based on
their estimated relevance to improve the effectiveness of the
information retrieval system.

■ The goal is to enhance the ranking of documents by giving more

weight to terms that are more indicative of relevance and less
weight to terms that are less informative.

■ In probabilistic models like the Binary Independence Model

(BIM), term reweighting is often influenced by relevance feedback
from users, which allows the model to better estimate the
probabilities associated with terms in relevant and non-relevant
documents.
Basic Concept of Term Reweighting in Probabilistic Model

■ The idea behind term reweighting in a probabilistic model is to

adjust the weight of each term in a query based on the likelihood
that the term appears in relevant documents versus non-relevant
ones.
■ This adjustment is typically guided by the following probabilities:

● Relevance Feedback and Rocchio-like Adjustments in

Probabilistic Models
○ To reweight the terms after initial retrieval, relevance feedback
is used.
○ The user provides feedback on which documents are relevant or
non-relevant. This feedback is then used to update the term
probabilities and reweight the query terms accordingly.
Term Reweighting Process
1. Initial Query Weight Calculation:
■ Initially, each query term is assigned a weight based on the
likelihood ratio:

■ This weight indicates how much evidence the presence of term t

provides for the relevance of a document.

2. Collecting Relevance Feedback:

● After the initial retrieval, the user marks certain documents as

relevant or non-relevant.
● This feedback allows the system to re-estimate the
probabilities P(t ∣ R=1) and P(t ∣ R=0)more accurately.
Term Reweighting Process
3. Updating Term Weights:
● Using the feedback, update the term weights:

■ If a term frequently appears in the relevant documents but not

in non-relevant ones, its weight will increase, indicating that it is
a strong indicator of relevance.

■ Conversely, if a term appears more in non-relevant documents,

its weight will decrease.
Term Reweighting Process
4. Re-ranking the Documents:
● The reweighted query is used to re-rank the documents, ideally
pushing more relevant documents higher in the ranking.
Example
Scenario:
Suppose you have a collection of documents, and a user is searching for information on "machine
learning" The system needs to rank documents based on their relevance to this query. Initially, the
system will use the BIM to assign weights to terms in the query and then apply relevance feedback to
reweight the terms.

Step 1: Initial Setup

Document Collection:

Let's consider a small set of documents:

● Document 1 (D1): "Machine learning and AI"

● Document 2 (D2): "Deep learning in medical applications"
● Document 3 (D3): "Introduction to machine learning"
● Document 4 (D4): "Applications of machine learning"
● Document 5 (D5): "AI and deep learning techniques"

User Query: "machine learning."

Step 2: Initial Term Weighting Using BIM and initial document scoring

The Binary Independence Model assumes that terms are independent and assigns
weights to terms in the query based on their presence or absence in the documents.

Terms in Query: Term 1: "machine" and Term 2: "learning" ● D1: "Machine learning and AI"
● D2: "Deep learning in medical
applications"
● D3: "Introduction to machine learning"
● D4: "Applications of machine
Probability Calculation:
learning"
● D5: "AI and deep learning techniques"

Let’s assume we don’t initially know which documents are relevant, so we estimate
these probabilities from the document collection.

Term Frequencies:

● "machine" appears in D1, D3, and D4. (3 out of 5 documents)

● "learning" appears in D1, D2, D3, D4, and D5. (5 out of 5 documents)

Now, let’s assume the initial probabilities:

Initial Document Scoring
Step 3: Relevance Feedback and Term Reweighting

Suppose the user reviews the results and marks D1, D3 and D4 as
relevant and D2,D5 as non-relevant. ● D1: "Machine learning and AI"
● D2: "Deep learning in medical
Updating Probabilities: applications"
● D3: "Introduction to machine learning"
Based on the feedback: ● D4: "Applications of machine
learning"
● D5: "AI and deep learning techniques"
● Relevant Documents (D1, D3,D4):
○ "machine": Appears in 3 out of 3 relevant documents.
○ "learning": Appears in 3 out of 3 relevant documents.
● Non-Relevant Document (D2,D5):
○ “machine”: Appears in 0 out of 2 non-relevant document.
○ "learning": Appears in 2 out of 2 non-relevant document.

Calculate Updated probabilities

Updated Probabilities:

Reweighting Terms using updated probabilistic

Step 4: New document scores with Reweighted query
Step 5: Final Ranking

After reweighting, the final ranking would prioritize documents

containing "machine" since "learning" alone has been identified as
less discriminative based on relevance feedback.

D1, D3, D4: Score = 4.605 (most relevant)

D2, D5: Score = 0 (least relevant)

 Evaluation of Relevance feedback strategies
■ Evaluating the retrieval performance of a modified query vector by considering
only the residual collection is a more realistic approach because it focuses on the
part of the document collection that has not been retrieved by the original query.
■ This subset of documents is the target of the modified query after relevance
feedback is applied.

■ Why Use the Residual Collection?

1. Focus on Improvement:The goal of relevance feedback is to refine the
query so that previously missed relevant documents are retrieved. By
focusing on the residual collection, the evaluation can directly measure the
improvement made by the modified query.
2. Avoiding Overestimation: If you evaluate the modified query against the
entire collection, including documents already retrieved by the original query,
the performance metrics might be skewed. The modified query might always
appear more effective simply because it retrieves documents that were
already known to be relevant, rather than finding new relevant documents.
3. Realistic User Experience:In practical IR systems, users are interested in
retrieving additional relevant documents that were missed by the initial
query. The residual collection represents the remaining unexplored portion of
the collection, making the evaluation more aligned with a real-world search
scenario.
How to Implement this Evaluation?

1. Initial Retrieval:
● Perform an initial retrieval using the original query. This will yield a set of
documents that are deemed relevant (or irrelevant) based on the original query
vector.
2. Residual Collection Construction:
● Construct the residual collection by removing the initially retrieved documents from
the entire document collection.
3. Apply Modified Query:
● Apply the modified query vector (after relevance feedback) to the residual
collection. This will test the effectiveness of the modifications in finding additional
relevant documents that were not retrieved initially.
4. Performance Metrics:
● Calculate precision, recall, and other relevant metrics based on the documents
retrieved from the residual collection. This will provide a clearer picture of how well
the modified query performs in identifying new relevant documents.
5. Comparative Analysis:
● Compare the performance of the modified query on the residual collection to its
performance on the full collection. This helps in understanding whether the
modifications are genuinely beneficial in improving retrieval performance beyond
Benefits of this evaluation approach

1. Efficiency: Evaluating on the residual collection reduces the number of documents

to be processed, making the evaluation more efficient.

1. Accuracy: It avoids the potential inflation of performance metrics, offering a more

accurate assessment of the relevance feedback strategies effectiveness.

1. Practical Relevance: It better mimics a real-world scenario where the goal is to

uncover new relevant information, rather than simply re-confirming what was
already known.

By focusing on the residual collection, the evaluation of the modified query vector
becomes more meaningful, realistic, and aligned with the goals of relevance feedback in
Information Retrieval systems.
Multimedia IR Models
Link
 Module 3.3
Multimedia IR Models
Multimedia Information Retrieval (IR) models are designed to search, retrieve, and manage
information from various types of multimedia data, including text, images, audio, video, and
more.

Challenges of Multimedia Data in Databases

1. Variety of Data Types and Formats

● Heterogeneity: Multimedia data includes a range of types, such as text, images, audio,
video, and graphics. Each type has different characteristics and requires different methods
for storage, indexing, retrieval, and processing.
● Format Diversity: Within each multimedia type, there are multiple formats (e.g., JPEG,
PNG for images; MP3, WAV for audio; MP4, AVI for video). Databases must support a
wide array of formats, which increases complexity in terms of both storage and retrieval
mechanisms.

2. High Storage Requirements

● Large Data Size: Multimedia files are typically large. For example, high-definition
videos and images require significant storage space. The database must handle large
volumes of data efficiently, both in terms of storage space and access speed.
● Efficient Storage Management: Databases need to manage storage efficiently to handle
multimedia data, which may involve compression techniques, specialized file systems, or
distributed storage solutions to manage large datasets effectively.

3. Unstructured and Semi-Structured Data

● Lack of Structure: Unlike structured data (e.g., numbers, dates), multimedia data lacks a
predefined structure, making it difficult to index and retrieve using traditional relational
database methods.
● Metadata Dependency: To retrieve multimedia content efficiently, databases often rely
on metadata (descriptive data about the multimedia content). However, generating and
managing accurate and comprehensive metadata can be challenging, especially at scale.

4. Complexity in Indexing and Retrieval

● Indexing Difficulties: Traditional indexing techniques are not effective for multimedia
data. For example, textual content can be indexed using inverted indexes, but multimedia
 data often requires complex feature-based indexing (e.g., visual features for images,
acoustic features for audio).
● Content-Based Retrieval: Multimedia retrieval often relies on content-based methods,
which involve extracting and matching features from the multimedia objects (e.g., color
histograms in images, spectral features in audio). Developing efficient algorithms for
content-based retrieval is challenging, particularly in high-dimensional spaces.

5. Processing and Analysis Requirements

● High Computational Cost: Processing multimedia data, such as decoding video or

analyzing image content, requires substantial computational resources. Databases must
optimize for both storage and computation to ensure responsive retrieval.
● Need for Advanced Algorithms: Advanced algorithms (e.g., machine learning, deep
learning) are often required to analyze multimedia content for indexing and retrieval,
adding further complexity to database management.

6. Dynamic and Temporal Aspects

● Temporal Dependencies: For video and audio data, temporal relationships (e.g.,
sequence of frames or audio segments) are crucial for understanding and retrieval.
Databases need to support time-based indexing and querying.
● Dynamic Content: Multimedia content can change over time (e.g., live video streams),
requiring databases to handle dynamic updates and provide real-time querying
capabilities.

7. Quality and Fidelity Concerns

● Lossy Compression and Quality Trade-offs: To manage storage and bandwidth,

multimedia data is often stored in compressed formats, which can be lossy. Databases
must balance the need for compression with the preservation of data quality.
● Data Integrity and Fidelity: Ensuring the integrity and fidelity of multimedia data over
time and across different storage and retrieval operations is challenging, especially when
dealing with lossy formats and multiple conversions.

8. Security and Privacy Issues

● Protection of Sensitive Content: Multimedia databases may contain sensitive content

(e.g., personal videos or images) requiring robust security measures to protect against
unauthorized access and distribution.
● Privacy Concerns: In addition to security, privacy concerns arise, particularly when
multimedia data includes identifiable personal information. Databases need to support
privacy-preserving mechanisms such as access controls and data anonymization.
9. Scalability and Performance

● Scalability Challenges: Multimedia databases must scale to handle large volumes of data
and concurrent queries, especially in applications like social media, video streaming, and
surveillance.
● Performance Optimization: Optimizing performance for multimedia queries is
challenging due to the large size of the data and the need for complex, often
computationally intensive retrieval operations.

10. Integration with Traditional Data

● Hybrid Data Models: Multimedia databases often need to integrate multimedia data
with traditional structured data (e.g., user profiles, transaction records). This requires
hybrid data models and query mechanisms that can efficiently handle both types of data.

11. Semantic Gap

● Difference Between Data Representation and Human Interpretation: The semantic

gap refers to the difference between low-level multimedia features (e.g., pixel values in
images) and high-level human interpretations (e.g., recognizing a face or an emotion).
Bridging this gap is a significant challenge in multimedia IR, requiring advanced
algorithms and contextual understanding.

Overall, managing multimedia data in databases involves addressing a combination of technical,

computational, and contextual challenges to support efficient storage, retrieval, and analysis.
Different approaches and models used in multimedia IR

1. Content-Based Multimedia Retrieval (CBMR)

● Content-Based Image Retrieval (CBIR): This approach retrieves images based on their
visual content, such as color, texture, and shape. Techniques often involve feature
extraction and matching these features to those in the database.
● Content-Based Audio Retrieval (CBAR): Similar to CBIR but applied to audio. This
can involve analyzing spectral features, rhythms, or specific sound patterns.
● Content-Based Video Retrieval (CBVR): Video retrieval involves extracting features
from both the visual and auditory components, as well as motion patterns.

2. Multimodal Fusion Models

● These models combine information from different media types, such as text, audio, and
images, to improve retrieval accuracy. Techniques can include early fusion (combining
raw data from different modalities) and late fusion (combining the results from different
models).
● Deep Learning-Based Multimodal Models: Deep neural networks, especially
convolutional neural networks (CNNs) and recurrent neural networks (RNNs), are often
used to process different types of data. Models like Multimodal Transformer architectures
extend traditional Transformer models to handle multiple types of inputs concurrently.

3. Machine Learning and Deep Learning Models

● Convolutional Neural Networks (CNNs): Widely used for image retrieval due to their
effectiveness in extracting spatial hierarchies of features.
● Recurrent Neural Networks (RNNs) and Long Short-Term Memory (LSTM)
Networks: Useful for processing sequential data such as audio and video, where
temporal dependencies are crucial.
● Transformers and Vision Transformers (ViTs): Increasingly popular in image and
video retrieval tasks due to their ability to capture long-range dependencies and
contextual information more effectively than traditional CNNs.

4. Hybrid Models

● These models combine different IR techniques and integrate both content-based and
metadata-based retrieval. For instance, combining CBIR with text-based metadata
searches can provide more accurate retrieval results.
● Graph-Based Models: Used for representing and retrieving multimedia data by
modeling relationships between different entities and media types. This can involve graph
convolutional networks (GCNs) or other graph-based learning methods.
5. Cross-Modal Retrieval Models

● Joint Embedding Spaces: These models aim to map different types of media (e.g.,
images and text) into a common embedding space where semantically similar content is
close together. Popular techniques include using dual-branch neural networks that align
embeddings from different modalities.
● Contrastive Learning Models: These models learn by contrasting similar and dissimilar
pairs, which can be useful in aligning embeddings of different modalities in the same
latent space.

6. Attention Mechanisms and Transformers

● Attention Models: These models can focus on specific parts of input data, such as
regions in an image or words in a sentence, to improve retrieval effectiveness.
● Transformers: Originally designed for natural language processing, transformers have
been adapted for various multimedia retrieval tasks, leveraging their ability to handle
sequential data and capture complex dependencies.

7. Reinforcement Learning and Active Learning Approaches

● These approaches are used to iteratively refine search results and improve retrieval
accuracy by interacting with users or learning from feedback.

8. Semantic and Knowledge-Based Models

● Ontology-Based Retrieval: Uses structured knowledge representations like ontologies to

enhance retrieval by understanding the semantic relationships between different media
elements.
● Knowledge Graphs: Utilized to integrate and infer relationships between multimedia
content based on structured knowledge.

9. Federated and Distributed IR Models

● Federated Learning Models: Allow for multimedia retrieval across decentralized data
sources, which is especially useful for privacy-sensitive applications where data cannot
be centralized.

10. Evaluation Metrics and Benchmarks

● Performance of multimedia IR models is typically evaluated using metrics such as

precision, recall, mean average precision (mAP), and normalized discounted cumulative
 gain (nDCG). Benchmarks like TRECVID for video retrieval and MIR-Flickr for image
retrieval are commonly used to assess model performance.

Key Challenges in Multimedia IR:

● Heterogeneity of Data: Managing different types of data (text, audio, images, video)
with varying structures and semantics.
● High Dimensionality: Multimedia data often involves high-dimensional feature spaces,
requiring effective dimensionality reduction techniques.
● Semantic Gap: The difference between low-level features and high-level human
understanding, making it difficult to accurately capture content semantics.
● Real-Time Processing: The need for efficient retrieval methods that can process and
respond in real-time, especially for large-scale data.

Overall, multimedia IR models are continually evolving to incorporate advances in machine

learning, deep learning, and artificial intelligence to improve their effectiveness in handling
diverse and complex data types.

Applications of Multimedia IR Models

Multimedia IR models have a wide range of applications, including:

● Visual Search Engines: Platforms like Google Images and Pinterest use sophisticated
multimedia IR models to enable users to search for images based on visual similarity.
● Video Recommendation Systems: Platforms like YouTube and Netflix use multimedia
IR models to recommend videos to users based on their viewing history and content
features.
● Content Moderation and Filtering: Social media platforms use multimedia IR models
to detect and filter inappropriate content, such as violence, nudity, or hate speech.
● Healthcare and Medical Imaging: Multimedia IR models are used to retrieve medical
images and assist in diagnostic tasks by comparing patient data with existing cases.
● Intelligent Surveillance Systems: These systems use multimedia IR models to detect
and track objects or people of interest across multiple video feeds, often in real-time.
Data Modeling in Multimedia IR Models

In multimedia Information Retrieval (IR) models, data modeling techniques are crucial for
efficiently organizing, indexing, and retrieving diverse types of data such as text, images, audio,
and video. Here are some common techniques used:

1. Feature Extraction and Representation:

○ Text: Techniques like Bag-of-Words (BoW), Term Frequency-Inverse Document
Frequency (TF-IDF), and word embeddings (e.g., Word2Vec, GloVe) are used to
convert text into numerical representations.
○ Images: Features can be extracted using Convolutional Neural Networks (CNNs)
or descriptors like SIFT (Scale-Invariant Feature Transform) and HOG
(Histogram of Oriented Gradients).
○ Audio: Techniques such as Mel-Frequency Cepstral Coefficients (MFCCs) and
spectrograms are used to capture audio features.
○ Video: Features are typically extracted from frames using CNNs or
spatiotemporal models like 3D CNNs or Long Short-Term Memory (LSTM)
networks.
2. Multimodal Integration:
○ Late Fusion: Combining features from different modalities (e.g., text and images)
at the decision level, such as by aggregating scores from separate models.
○ Early Fusion: Integrating features from different modalities at the feature level
before model training.
○ Cross-modal Learning: Techniques like Canonical Correlation Analysis (CCA)
or deep learning approaches (e.g., multi-modal transformers) that learn shared
representations across different modalities.
3. Indexing and Retrieval:
○ Vector Space Model: Representing multimedia data as vectors in a
high-dimensional space and using similarity measures (e.g., cosine similarity) for
retrieval.
○ Inverted Index: Commonly used for text retrieval, but can be adapted for other
modalities by indexing features or descriptors.
○ Hashing Techniques: Locality Sensitive Hashing (LSH) or deep hashing methods
for efficient similarity search in high-dimensional spaces.
4. Learning-to-Rank:
○ Supervised Learning-to-Rank: Training models to rank multimedia data based
on labeled relevance judgments, often using techniques like RankNet,
LambdaMART, or gradient boosting.
○ Learning-to-Rank for Multimodal Data: Combining features from different
modalities and learning ranking functions that optimize retrieval performance.
 5. Cross-Modal Retrieval:
○ Techniques that enable searching for one type of data (e.g., finding images based
on text queries) by learning joint representations or mappings between modalities.
6. Deep Learning Approaches:
○ Multimodal Neural Networks: Models like multi-stream CNNs or transformers
that handle and integrate multiple types of data simultaneously.
○ Self-Supervised Learning: Leveraging large amounts of unlabelled data to learn
useful representations for various modalities.

These techniques help in improving the efficiency and accuracy of multimedia information
retrieval systems by effectively handling the complexities of different data types and their
interactions.

Multimedia data support in commercial DBMS

Commercial Database Management Systems (DBMS) offer varying levels of support for
multimedia data, depending on their features and design. Here’s a general overview of how
multimedia data is supported in commercial DBMS:

1. Storage Capabilities

● Binary Large Objects (BLOBs): Most commercial DBMSs support BLOBs, which
allow for the storage of large binary files such as images, audio, and video. Examples
include Microsoft SQL Server’s VARBINARY(MAX), Oracle’s BLOB, and
PostgreSQL’s BYTEA.
● File System Integration: Some systems integrate with file systems to store large
multimedia files outside the database, using the DBMS to store metadata and file paths.

2. Indexing and Search

● Full-Text Search: For textual metadata associated with multimedia content, many
DBMSs offer full-text search capabilities. For example, SQL Server has Full-Text Search
and PostgreSQL has built-in support for full-text indexing.
● Spatial Indexes: For spatial data such as geotagged images or videos, some DBMSs
offer spatial indexing features. Examples include Oracle Spatial and PostgreSQL with
PostGIS.
● Custom Indexes: In cases where specialized indexing is required, such as for image or
audio features, custom indexing solutions can be implemented.

3. Multimedia Processing
 ● In-Database Processing: Some DBMSs provide features for processing multimedia data
directly within the database. For example, Oracle supports Media Data Management,
which allows for managing and processing large volumes of media files.
● Integration with External Tools: Many DBMSs support integration with external
multimedia processing tools or libraries. This can be done via APIs or custom extensions.

4. Querying and Retrieval

● Basic Retrieval: DBMSs handle basic querying and retrieval of multimedia data, such as
fetching images or videos by ID or metadata.
● Advanced Querying: For more advanced queries, such as content-based retrieval or
similarity search, additional tools or extensions might be required. Some DBMSs support
plugins or custom functions to handle these tasks.

5. Data Integrity and Security

● Access Control: Commercial DBMSs provide mechanisms for controlling access to

multimedia data, ensuring that only authorized users can view or modify content.
● Backup and Recovery: They offer robust backup and recovery solutions to protect
multimedia data from loss or corruption.

6. Examples of Commercial DBMSs

● Oracle Database: Offers support for multimedia data through its Oracle Multimedia
(formerly Oracle InterMedia) option, which provides tools for storing and managing
multimedia content.
● Microsoft SQL Server: Provides BLOB storage with support for managing large binary
data and integrates with SQL Server Integration Services (SSIS) for multimedia
processing tasks.
● PostgreSQL: Supports binary data with BYTEA and Large Object types and offers
extensions like PostGIS for spatial data.
● IBM Db2: Offers BLOB and CLOB storage types and can integrate with external tools
for advanced multimedia processing.

For many commercial DBMSs, handling large-scale multimedia data often requires a
combination of the database’s built-in features and additional tools or custom solutions.

The MULTOS Data Model

The MULTOS data model is a framework designed for managing and retrieving multimedia data
within database systems. It addresses the specific challenges associated with multimedia data,
such as large file sizes, complex structures, and the need for efficient querying and indexing.
Here’s an overview of the MULTOS data model:

1. Conceptual Framework

● Multimedia Objects: The MULTOS model treats multimedia content as distinct objects
within the database. These objects can include images, audio, video, and other forms of
multimedia.
● Attributes and Metadata: Each multimedia object is associated with various attributes and
metadata. Metadata might include information like file type, resolution, duration, and
descriptive tags.

2. Data Representation

● Object Model: MULTOS uses an object-oriented approach to represent multimedia data.

Each multimedia object is an instance of a class that defines its attributes and
relationships.
● Hierarchical Structures: Multimedia objects can be organized in hierarchical structures,
reflecting their internal organization. For example, a video might be divided into scenes,
and scenes into individual frames.

3. Indexing and Retrieval

● Feature-Based Indexing: MULTOS supports indexing based on features extracted from

multimedia content. For images, this might include color histograms or texture features;
for audio, it could include frequency patterns or speech recognition results.
● Semantic Indexing: In addition to low-level features, MULTOS can also incorporate
semantic information to improve retrieval accuracy. This includes tagging and annotation
of content to reflect its meaning or context.

4. Query Processing

● Query Models: MULTOS supports various query models tailored for multimedia data.
This includes content-based retrieval, where queries are based on the actual content of the
multimedia objects rather than just metadata.
● Similarity Search: The model includes mechanisms for similarity search, allowing users
to find multimedia objects that are similar to a given query object. This is particularly
useful for applications like image search or audio matching.
5. Integration and Scalability

● Scalability: The MULTOS model is designed to handle large volumes of multimedia data
efficiently. It incorporates techniques for distributed storage and processing to scale with
the size of the data.
● Integration: MULTOS can be integrated with various multimedia processing tools and
systems to enhance its capabilities. This might include external libraries for image
processing, audio analysis, or video encoding.

6. Applications

● Digital Libraries: MULTOS is often used in digital libraries and archives to manage and
retrieve multimedia content.
● Media Management Systems: It is also applied in media management systems where
efficient storage, retrieval, and processing of large multimedia datasets are critical.

The MULTOS data model provides a structured and efficient approach to managing multimedia
data, addressing the unique challenges posed by such data and facilitating advanced retrieval and
processing techniques.