Information Retrieval & Search

Engines

Lecture 3 : Searching Algorithm

and Query Language

Dr. Mostafa Shokry

10/9/2025 Information Retrieval & Search Engines 1

 Lecture Objectives
• Define what a query language is in the context of IR.
• Understand the difference between query languages and search
models/algorithms.
• Recognize different types of query languages.
• Interpret and write sample queries in different languages.

10/9/2025 Information Retrieval & Search Engines 2

 Probabilistic IR Model
The Probabilistic IR Model tries to rank documents based on the probability
that a document is relevant to the user's query.
Each document is assigned a probability score that estimates:
“What is the chance this document is relevant to the query?”
The system ranks documents by this probability, showing the most likely
relevant documents first.
The Binary Independence Model (BIM) is one specific version of the
Probabilistic Information Retrieval (IR) Model.

10/9/2025 Information Retrieval & Search Engines 3

 Probabilistic IR Model (Cont.)
Main Formula (Binary Independence Model – BIM)
Simplified Score Formula:
For a document D and a query Q, the retrieval score is computed as:

𝐏𝐭(𝟏 − 𝐔𝐭)
𝑺𝒄𝒐𝒓𝒆 (𝑫) = ෎ 𝑳𝒐𝒈
𝐔𝐭 (𝟏 − 𝐏𝐭)
Where: 𝒕𝝐𝑸

• t: a term in the query

• Pt: probability the term appears in relevant documents
• Ut: probability the term appears in non-relevant document
10/9/2025 Information Retrieval & Search Engines 4
 Example Scenario: Cloud Computing
Query
Let’s say a student searches for:
“cloud security storage”
Document Collection:
• Doc1: "AWS cloud security and encryption services"
• Doc2: “Cloud data storage solutions"

10/9/2025 Information Retrieval & Search Engines 5

 Assumed Probabilities
Assumed Probabilities for Each Term:

Term Pt (relevant docs) Ut (non-relevant docs)

Cloud 0.95 0.80
security 0.90 0.20
storage 0.70 0.40

10/9/2025 Information Retrieval & Search Engines 6

 Calculate Individual Term Weights
• For cloud:
w_cloud = log [0.95 × (1 - 0.80) / 0.80 × (1 - 0.95)]
= log [0.95 × 0.20 / 0.80 × 0.05]
= log [0.19 / 0.04]
= log [4.75] ≈ 0.677
• For security:
w_security = log [0.90 × (1 - 0.20) / 0.20 × (1 - 0.90)]
= log [0.90 × 0.80 / 0.20 × 0.10]
= log [0.72 / 0.02]
= log [36] ≈ 1.556
10/9/2025 Information Retrieval & Search Engines 7
 Calculate Individual Term Weights
(Cont.)
• For storage:
w_storage = log [0.70 × (1 - 0.40) / 0.40 × (1 - 0.70)]
= log [0.70 × 0.60 / 0.40 × 0.30]
= log [0.42 / 0.12]
= log [3.5] ≈ 0.544

10/9/2025 Information Retrieval & Search Engines 8

 Document Scoring
• Doc1: Contains cloud and security
Score = w_cloud + w_security
= 0.677 + 1.556
= 2.233
• Doc2: Contains cloud and storage
Score = w_cloud + w_storage
= 0.677 + 0.544
= 1.221

10/9/2025 Information Retrieval & Search Engines 9

 Probabilistic IR Model (Cont.)
Advantages
• Handles uncertainty better than Boolean models.
• Learns and improves with user feedback.
• Works well for ranking results by relevance.
Disadvantages
• More complex math and probability involved.
• Needs data about relevant vs. non-relevant documents (often hard to get).

10/9/2025 Information Retrieval & Search Engines 10

 Probabilistic IR Model vs (VSM)
Feature Vector Space Model (VSM) Probabilistic IR Model (BIM)
Measures similarity between Estimates probability that a document
Core Idea
document and query vectors is relevant
Documents and queries are Documents are sets of terms, used to
Representation
vectors in a space compute probability
Uses cosine similarity between Uses probabilistic scoring (e.g., BIM
Scoring
vectors formula)
Relevance Based on term frequency and Based on likelihood of relevance
Assumption angle (similarity) (relevant vs. non-relevant sets)

10/9/2025 Information Retrieval & Search Engines 11

 What is a Query Language?
A query language is the syntax and structure used by users or systems to
formulate queries that retrieve information from a document collection.
Why It Matters:
• It's the interface between the user and the IR system.
• Determines how precise, expressive, and structured a query can be.
• Helps in retrieving relevant documents effectively.

10/9/2025 Information Retrieval & Search Engines 12

 Search Models vs. Query Languages

Aspect Query Language Search Model (Algorithm)

Role User input syntax Mathematical framework

Purpose Express search intent Score and rank documents
User-visible? Yes No (hidden from user)
Examples Boolean, Lucene. Boolean Model, VSM, Probablistic

10/9/2025 Information Retrieval & Search Engines 13

 Types of Query Languages
• Boolean Query Language.
• Lucene Query Language.

10/9/2025 Information Retrieval & Search Engines 14

 Boolean Query Language
• The Boolean Query Language allows users to formulate queries using
Boolean logic (based on set theory).
• Documents are either retrieved or not retrieved—no ranking is done.
• It is the foundation of classical IR systems, such as library catalogs, early
search engines, and some digital archives.

10/9/2025 Information Retrieval & Search Engines 15

 Boolean Query Language (Cont.)

Operator Meaning Example

AND both terms must appear cybersecurity AND firewall
OR at least one term must appear phishing OR malware
NOT exclude documents with a term ransomware NOT trojan
() Parentheses: group expressions (AI OR ML) AND NOT "chatbot"

10/9/2025 Information Retrieval & Search Engines 16

 Boolean Query Language (Cont.)
Syntax Rules:
Case-insensitive (typically)

Use quotes for phrases: "machine learning"

Use parentheses to group logic

No support for fuzzy matching, proximity, ranking, etc.

10/9/2025 Information Retrieval & Search Engines 17

 Boolean Query Language (Cont.)

Query Result
"information retrieval" Docs with the exact phrase
retrieval AND "data mining" Docs with both terms
"deep learning" OR "neural net" Docs with either phrase
Docs with phrase but exclude firewall-
"network security" NOT firewall
related docs

10/9/2025 Information Retrieval & Search Engines 18

 Boolean Query Language (Cont.)
Example:
("data science" OR AI) AND (cybersecurity OR privacy) AND NOT marketing

Returns documents discussing data science or AI, and cybersecurity or

privacy, but not related to marketing.

10/9/2025 Information Retrieval & Search Engines 19

 Boolean Query Language (Cont.)
• Characteristics of Boolean Model:
Feature Description
Exact match Returns documents that match the condition exactly
No partial ranking All retrieved documents are considered equally relevant
Binary decision Document either matches or not
User control Full control over query structure
Query complexity Complex queries can be hard for users to write

10/9/2025 Information Retrieval & Search Engines 20

 Boolean Query Language (Cont.)
Practice Exercises: Evaluate Boolean Query
Doc ID Content
D1 "Cybersecurity and network defense strategies"
D2 "AI techniques for phishing detection"
D3 "Firewall configurations and rules"
D4 "AI and cybersecurity: a combined approach"

10/9/2025 Information Retrieval & Search Engines 21

 Boolean Query Language (Cont.)
Query 1:
cybersecurity AND NOT firewall

Expected: D1, D4

10/9/2025 Information Retrieval & Search Engines 22

 Boolean Query Language (Cont.)
Query 2:
AI AND (cybersecurity OR phishing)

Expected: D2, D4

10/9/2025 Information Retrieval & Search Engines 23

 Boolean Query Language (Cont.)
Rewrite the following in Boolean form:
“Find documents that mention either deep learning or machine learning
but not chatbot.”

("deep learning" OR "machine learning") AND NOT "chatbot"

10/9/2025 Information Retrieval & Search Engines 24