Lecture Notes

Enhanced Data Models: Active, Temporal, Spatial, Multimedia, and Deductive

Databases

1. Introduction to Enhanced Data Models

Need for Enhanced Database Models

As database applications became more advanced and complex, users demanded:

• Greater functionality

• Better support for specialized applications

• Efficient handling of nontraditional data

Traditional relational DBMSs were insufficient for:

• Multimedia data

• Spatial information

• Historical data

• Intelligent reasoning systems

• Event-driven applications

To address these requirements, enhanced database models were developed.

2. Extensible Database Systems

Modern DBMSs support:

• Object-oriented databases

• Object-relational databases

These systems allow users to define:

• Abstract Data Types (ADTs)

• Specialized operations

• User-defined classes

Data Blades and Cartridges

Database vendors provide optional modules for specialized features.

Terminology

Vendor Term Used

Informix Data Blade

Oracle Corporation Cartridge

These modules:

• Extend DBMS functionality

• Improve performance

• Reduce development effort

3. Major Enhanced Database Models

The chapter discusses five important enhanced database systems:

1. Active Databases

2. Temporal Databases

3. Spatial Databases

4. Multimedia Databases

5. Deductive Databases

4. Active Databases

Definition

Active databases support:

• Automatic execution of rules

• Event-driven processing

The rules are called:

• Active Rules

• Triggers
Active Rules

An active rule consists of:

Event

An occurrence that activates the rule.

Examples:

• INSERT

• UPDATE

• DELETE

• Specific time reached

Condition

A logical test checked after the event occurs.

Action

Operation executed if condition is true.

This model is known as:

ECA Model

𝐸𝑣𝑒𝑛𝑡 → 𝐶𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 → 𝐴𝑐𝑡𝑖𝑜𝑛

Triggers

Triggers are:

• Automatically executed procedures

• Part of SQL standards from SQL-99 onward

Applications

• Auditing

• Constraint enforcement

• Notifications

• Automatic updates
Advantages of Active Databases

• Automation

• Reduced application coding

• Faster response to events

• Improved consistency

5. Temporal Databases

Definition

Temporal databases store:

• Historical data

• Current data

• Future/planned data

They track changes over time.

Importance

Most real-world applications are temporal.

Examples:

• Banking

• Employee records

• Reservation systems

• Medical records

Types of Temporal Data

1. Valid Time

Time during which a fact is true in reality.

2. Transaction Time

Time during which data is stored in database.

Features

Temporal databases support:

• Historical queries

• Time-based analysis

• Future schedule management

Example Queries

• Employee salary history

• Past customer addresses

• Future train schedules

SQL Support

Temporal support added in:

• SQL:2011

• IBM DB2

6. Spatial Databases

Definition

Spatial databases manage:

• Geographic

• Geometric

• Location-based data

Spatial Data Types

Examples:

• Points

• Lines
 • Polygons

• Regions

Applications

• Geographic Information Systems (GIS)

• Navigation systems

• Urban planning

• Environmental monitoring

Spatial Operations

Common operations include:

Operation Description

Intersection Overlapping regions

Containment One object inside another

Distance Spatial separation

Nearest Neighbor Closest object search

Spatial Queries

Examples:

• Find nearby hospitals

• Locate shortest route

• Identify flood-prone regions

Spatial Indexing

Used to improve query performance.

Common methods:

• R-Tree
 • Quad Tree

• Grid indexing

Spatial Data Mining

Extracts hidden patterns from spatial datasets.

Applications:

• Traffic analysis

• Weather prediction

• Crime analysis

7. Multimedia Databases

Definition

Multimedia databases store and manage:

• Images

• Audio

• Video

• Text documents

Types of Multimedia Data

Images

Examples:

• Photographs

• Medical scans

• Satellite images

Audio

Examples:

• Songs
 • Voice recordings

• Speeches

Video

Examples:

• Movies

• Surveillance footage

• Video lectures

Documents

Examples:

• Books

• Research papers

• Reports

Features of Multimedia Databases

1. Storage Management

Efficient handling of large multimedia files.

2. Content-Based Retrieval

Searching based on actual content instead of filenames.

Examples:

• Find similar images

• Search by voice pattern

3. Automatic Image Analysis

Techniques include:

• Object recognition
 • Face detection

• Pattern matching

4. Semantic Tagging

Assigning meaningful labels to multimedia content.

Example:

• “Car”

• “Tree”

• “Person”

Applications

• Medical imaging

• Digital libraries

• Video streaming

• Surveillance systems

• Social media platforms

8. Deductive Databases

Definition

Deductive databases combine:

• Database systems

• Logic programming

• Artificial intelligence

They can infer new facts using rules.

Components

Facts

Stored information.
Example:

• Employee(Ashwin, CSE)

Rules

Logical statements used to derive knowledge.

Example:

• If X is parent of Y and Y is parent of Z, then X is grandparent of Z.

Inferencing

Deductive systems generate:

• New information

• Conclusions

• Logical deductions

Logic Databases

Rules are based on:

• Mathematical logic

• Predicate calculus

Hence called:

• Logic databases

Related Systems

Expert Systems

Use:

• Domain knowledge

• Reasoning techniques

Knowledge-Based Systems
Represent knowledge using:

• Semantic networks

• Frames

• Production rules

Applications of Deductive Databases

• Medical diagnosis

• Expert advisory systems

• Fraud detection

• Intelligent query systems

• Decision support systems

9. Importance of Enhanced Data Models

Enhanced models provide support for:

Requirement Supported By

Event handling Active DB

Time management Temporal DB

Geographic data Spatial DB

Multimedia content Multimedia DB

Intelligent reasoning Deductive DB

10. Comparison of Enhanced Database Models

Database Type Main Feature Example Applications

Active DB Event-driven actions Banking alerts

Temporal DB Time-based storage Employee history

Spatial DB Geographic data GIS

Database Type Main Feature Example Applications

Multimedia DB Audio/video/image handling Streaming services

Deductive DB Logical inference Expert systems

11. Advantages of Enhanced Database Models

Improved Functionality

Supports complex applications.

Better Performance

Specialized indexing and storage.

Reduced Development Time

Reusable modules and built-in capabilities.

Intelligent Processing

Automation and reasoning support.

12. Challenges

Complexity

Implementation becomes difficult.

Large Storage Requirements

Especially for multimedia data.

Efficient Query Processing

Advanced indexing techniques required.

Standardization Issues

Different vendors implement features differently.

13. Summary

Enhanced database models extend traditional DBMS functionality to support:

• Automation

• Historical data

• Geographic information

• Multimedia processing

• Intelligent reasoning

These models are essential for modern applications such as:

• GIS systems

• AI systems

• Healthcare systems

• Multimedia platforms

• Real-time enterprise applications

Each enhanced model addresses specific requirements and continues to evolve with
advances in:

• Big Data

• Artificial Intelligence

• Cloud Computing

• Multimedia technologies
Lecture Notes

Module: Active Database Concepts and Triggers

26.1 Active Database Concepts and Triggers

1. Introduction to Active Databases

Traditional databases mainly store and retrieve data.

However, many modern applications require databases to automatically respond to
specific events.

An Active Database Management System (ADBMS) supports automatic execution of

actions when certain events occur.

These automatic actions are implemented using:

• Active Rules

• Triggers

Triggers are widely supported in modern DBMSs such as:

• Oracle

• IBM

• Microsoft

Triggers are also part of the SQL-99 standard and later SQL standards.

2. Event-Condition-Action (ECA) Model

The generalized model for active databases is called the:

Event–Condition–Action (ECA) Model

An active rule contains three components:

Component Description

Event Occurrence that triggers the rule

Condition Logical test evaluated after event

Action Operation executed if condition is true

2.1 Event

The event is what activates the rule.

Types of Events

a) Database Events

Generated by SQL operations:

• INSERT

• UPDATE

• DELETE

b) Temporal Events

Triggered at a particular time.

Example:

• Monthly salary processing

c) External Events

Generated outside the database.

Example:

• Sensor signal

• Alarm system input

2.2 Condition

After the event occurs, a condition may be checked.

• If condition = TRUE → execute action

• If condition = FALSE → no action

Condition is optional.

2.3 Action

The action may include:

• SQL statements

• Stored procedures
 • External programs

• Transactions

3. Example Database Schema

EMPLOYEE Table

Attribute Description

Name Employee Name

Ssn Social Security Number

Salary Employee Salary

Dno Department Number

Supervisor_ssn Supervisor SSN

DEPARTMENT Table

Attribute Description

Dname Department Name

Dno Department Number

Total_sal Total Department Salary

Manager_ssn Manager SSN

4. Derived Attribute Maintenance

The attribute:

Total_sal

is a derived attribute because:

𝑇𝑜𝑡𝑎𝑙_𝑠𝑎𝑙 = ∑𝑆𝑎𝑙𝑎𝑟𝑦 𝑜𝑓 𝑒𝑚𝑝𝑙𝑜𝑦𝑒𝑒𝑠 𝑖𝑛 𝑑𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡

Whenever employee data changes, Total_sal must also be updated automatically.

5. Events Affecting Total_sal

The following events can change Total_sal:

1. Insert new employee

2. Update employee salary

3. Change employee department

4. Delete employee

Triggers are used to automatically maintain consistency.

6. Oracle Trigger Syntax

General Syntax

CREATE TRIGGER trigger_name

AFTER | BEFORE event
ON table_name
FOR EACH ROW
WHEN (condition)
BEGIN
action;
END;

7. Row-Level Triggers

A row-level trigger executes once for each affected row.

Specified using:

FOR EACH ROW

8. Trigger Examples

Trigger R1 – After Insert

Purpose

Update department Total_sal after inserting employee.

CREATE TRIGGER Total_sal1
AFTER INSERT ON EMPLOYEE
FOR EACH ROW
WHEN ([Link] IS NOT NULL)

UPDATE DEPARTMENT
SET Total_sal = Total_sal + [Link]
WHERE Dno = [Link];

Explanation

Clause Meaning

AFTER INSERT Trigger activated after insert

FOR EACH ROW Executes for every inserted tuple

NEW Refers to inserted tuple

Action Add employee salary to department total

Trigger R2 – Salary Update

CREATE TRIGGER Total_sal2

AFTER UPDATE OF Salary ON EMPLOYEE
FOR EACH ROW
WHEN ([Link] IS NOT NULL)

UPDATE DEPARTMENT
SET Total_sal = Total_sal + [Link] - [Link]
WHERE Dno = [Link];

OLD vs NEW

Keyword Meaning

OLD Previous tuple value

NEW Updated tuple value

Trigger R3 – Department Change

CREATE TRIGGER Total_sal3

AFTER UPDATE OF Dno ON EMPLOYEE
FOR EACH ROW
BEGIN

UPDATE DEPARTMENT
SET Total_sal = Total_sal + [Link]
WHERE Dno = [Link];

UPDATE DEPARTMENT
SET Total_sal = Total_sal - [Link]
WHERE Dno = [Link];

END;

Trigger R4 – Employee Deletion

CREATE TRIGGER Total_sal4

AFTER DELETE ON EMPLOYEE
FOR EACH ROW
WHEN ([Link] IS NOT NULL)

UPDATE DEPARTMENT
SET Total_sal = Total_sal - [Link]
WHERE Dno = [Link];

9. BEFORE Trigger Example

Purpose

Check whether employee salary exceeds supervisor salary.

CREATE TRIGGER Inform_supervisor1

BEFORE INSERT OR UPDATE OF Salary, Supervisor_ssn
ON EMPLOYEE
FOR EACH ROW
WHEN ([Link] >
(SELECT Salary
FROM EMPLOYEE
WHERE Ssn = NEW.Supervisor_ssn))
inform_supervisor(NEW.Supervisor_ssn, [Link]);

10. Statement-Level Triggers

A statement-level trigger executes once for the entire SQL statement.

Example:

UPDATE EMPLOYEE
SET Salary = 1.1 * Salary
WHERE Dno = 5;

If 100 rows are updated:

• Row-level trigger → executes 100 times

• Statement-level trigger → executes once

11. Row-Level vs Statement-Level Triggers

Feature Row-Level Statement-Level

Execution Frequency Per row Per statement

Uses OLD/NEW Yes No

Performance Slower for bulk updates Faster

Precision High Moderate

12. Trigger Timing Options

Triggers can execute:

Type Description

BEFORE Before event execution

AFTER After event execution

INSTEAD OF Instead of event

13. Trigger Execution Models

13.1 Immediate Consideration

Condition evaluated immediately.

Options:

• Before event

• After event

• Instead of event

13.2 Deferred Consideration

Condition checked at transaction end.

Used in:

• STARBURST

13.3 Detached Consideration

Condition evaluated in separate transaction.

14. Trigger Action Execution

Actions may be:

Type Description

Immediate Executed immediately

Deferred Executed later

Detached Executed separately

15. STARBURST Active Database System

STARBURST supports:

• Statement-level triggers

• Deferred consideration
 • Transition tables

16. Transition Tables in STARBURST

Table Meaning

INSERTED Newly inserted tuples

DELETED Deleted tuples

NEW-UPDATED Updated tuples after change

OLD-UPDATED Updated tuples before change

17. Example STARBURST Trigger

CREATE RULE Total_sal1 ON EMPLOYEE

WHEN INSERTED

IF EXISTS (
SELECT * FROM INSERTED
WHERE Dno IS NOT NULL
)

THEN
UPDATE DEPARTMENT AS D
SET D.Total_sal =
D.Total_sal +
(SELECT SUM([Link])
FROM INSERTED AS I
WHERE [Link] = [Link]);

18. Conflict Set in STARBURST

All triggered rules are stored in a:

Conflict Set

Rules are processed:

• At transaction commit

• Or using PROCESS RULES command

19. Problems in Active Databases

19.1 Rule Consistency

Rules should not contradict each other.

19.2 Non-Termination Problem

Triggers may activate each other repeatedly.

Example:

• Trigger T1 updates TABLE2

• Trigger T2 inserts into TABLE1

• Infinite loop occurs

20. Applications of Active Databases

20.1 Monitoring Systems

Example:

• Industrial temperature monitoring

If temperature exceeds limit:

• Alarm triggered automatically

20.2 Integrity Constraint Enforcement

Example:

• GPA monitoring

• Course prerequisite checking

20.3 Derived Data Maintenance

Example:
 • Maintaining Total_sal

20.4 Materialized View Maintenance

Automatically update materialized views when base tables change.

20.5 Replication Maintenance

Maintain consistency among replicated databases.

21. SQL-99 Trigger Syntax

Row-Level Trigger Example

CREATE TRIGGER Total_sal1

AFTER UPDATE OF Salary

ON EMPLOYEE

REFERENCING
OLD ROW AS O
NEW ROW AS N

FOR EACH ROW

WHEN ([Link] IS NOT NULL)

UPDATE DEPARTMENT
SET Total_sal =
Total_sal + [Link] - [Link]
WHERE Dno = [Link];

22. SQL-99 REFERENCING Clause

Clause Meaning

OLD ROW AS O Old tuple alias

Clause Meaning

NEW ROW AS N New tuple alias

OLD TABLE Old transition table

NEW TABLE New transition table

23. Advantages of Active Databases

• Automatic task execution

• Reduced application code

• Better consistency

• Real-time monitoring

• Improved integrity enforcement

24. Disadvantages of Active Databases

• Difficult debugging

• Complex rule interaction

• Risk of infinite triggering

• Performance overhead

25. Key Terms

Term Meaning

Trigger Automatic rule execution

ECA Model Event-Condition-Action model

Row-Level Trigger Executes per tuple

Statement-Level Trigger Executes per statement

Transition Table Stores changed tuples

BEFORE Trigger Executes before event

Term Meaning

AFTER Trigger Executes after event

INSTEAD OF Trigger Replaces operation

26. Summary

• Active databases automatically react to events.

• Triggers are based on the ECA model.

• Triggers can be BEFORE, AFTER, or INSTEAD OF.

• Row-level and statement-level triggers are supported.

• Oracle and SQL-99 provide trigger support.

• STARBURST introduced advanced active rule concepts.

• Applications include integrity checking, monitoring, and automatic maintenance

of derived data.
Lecture Notes: Temporal Database Concepts

Introduction to Temporal Databases

A temporal database is a database that manages data involving time-related

information. It stores not only the current state of data but also historical and future
states.

Definition

Temporal databases encompass all database applications that require some aspect of
time while organizing information.

Importance of Temporal Databases

Many real-world applications require tracking historical changes over time:

• Healthcare systems → Patient medical history

• Insurance systems → Policy periods and claims history

• Reservation systems → Hotel, airline, railway bookings

• Banking systems → Transaction records

• Scientific databases → Experiment measurement times

• Company databases → Employee salary and job history

• University databases → Student grades and semester records

26.2.1 Time Representation, Calendars, and Time Dimensions

1. Time Representation in Databases

Time is treated as an ordered sequence of time points.

Chronon

The smallest unit of time used in a temporal database is called a chronon.

Examples

• Second

• Minute

• Day

• Month
If the granularity is one second, all events occurring within the same second are
considered simultaneous.

2. Calendars in Temporal Databases

A calendar provides a reference system for measuring time.

Common Calendars

• Gregorian Calendar

• Chinese Calendar

• Islamic Calendar

• Hindu Calendar

• Jewish Calendar

3. SQL Temporal Data Types

SQL supports several temporal data types.

Data Type Description Example

DATE Stores date 2026-05-20

TIME Stores time 10:30:45

TIMESTAMP Stores date and time 2026-05-20 10:30:45

INTERVAL Relative duration 10 DAYS

PERIOD Fixed duration Jan 1 to Jan 10

4. Event Information vs Duration Information

Point Events

Associated with a single time point.

Examples

• Bank deposit

• Daily stock price

 • Monthly sales

Duration Events

Associated with a time period.

Example

Employee worked from:

[2003-08-15, 2008-11-20]

5. Time Dimensions

Temporal databases mainly use two time dimensions.

A. Valid Time

The time during which a fact is true in the real world.

Example

Employee salary valid from:

01-01-2025 to 31-12-2025

Database storing this is called:

Valid Time Database

B. Transaction Time

The time when information is actually stored in the database.

Example

Salary entered into database on:

05-01-2025

Database storing this is called:

Transaction Time Database

C. Bitemporal Database

A database containing both:

• Valid Time

• Transaction Time
26.2.2 Incorporating Time in Relational Databases Using Tuple Versioning

Tuple versioning stores multiple versions of tuples instead of overwriting old data.

1. Valid Time Relations

Additional attributes:

• Vst → Valid Start Time

• Vet → Valid End Time

Example Structure

Name Salary Vst Vet

Smith 25000 2022-06-15 2023-05-31

Smith 30000 2023-06-01 Now

Key Features

Current Version

Uses special value:

 • Now

History Preservation

Old data is never deleted.

2. Types of Updates

A. Proactive Update

Update applied before becoming effective.

Example

Salary updated in database on May 15 but effective June 1.

B. Retroactive Update

Update applied after becoming effective.

C. Simultaneous Update

Update applied exactly when effective.

3. Transaction Time Relations

Additional attributes:

• Tst → Transaction Start Time

• Tet → Transaction End Time

Example

Name Salary Tst Tet

Smith 25000 2022-06-08 2023-06-04

Smith 30000 2023-06-04 uc

uc means:

Until Changed
4. Rollback Database

Transaction-time databases are also called rollback databases because previous states
can be recovered.

5. Bitemporal Relations

Contain:

• Valid Time

• Transaction Time

Additional Attributes

Attribute Meaning

Vst Valid Start Time

Vet Valid End Time

Tst Transaction Start Time

Tet Transaction End Time

Tuple Update in Bitemporal Database

When updating:

1. Old tuple closed

2. New tuple created

3. Transaction timestamp recorded

6. Append-Only Database

In bitemporal databases:

• Data is never physically removed

• Corrections are preserved

• Complete history maintained

7. Temporal Normal Form

To avoid unnecessary duplication:

• Attributes are partitioned into separate temporal relations

This reduces redundancy.

26.2.3 Incorporating Time in Object-Oriented Databases Using Attribute Versioning

Attribute Versioning

Instead of creating entire tuple versions:

• Only changed attributes are versioned.

Types of Attributes

A. Time-Varying Attributes

Change over time.

Examples

• Salary

• Department

• Supervisor

B. Non-Time-Varying Attributes

Remain constant.

Examples

• Name

• SSN

Example Structure

<Valid_start_time, Valid_end_time, Value>

Advantages of Attribute Versioning

• Reduces redundancy

• Efficient storage

• Supports asynchronous attribute changes

Bitemporal Attribute Versioning

Each version contains:

<Valid_start_time,
Valid_end_time,
Trans_start_time,
Trans_end_time,
Value>

26.2.4 Temporal Querying Constructs and TSQL2 Language

Temporal databases require temporal query operations.

1. Temporal Selection Conditions

Queries may involve:

• Attribute conditions

• Time conditions

Common Temporal Operations

Operation Meaning

INCLUDES Period fully contains another

INCLUDED_IN Period lies inside another

OVERLAPS Two periods intersect

BEFORE One period occurs before another

AFTER One period occurs after another

MEETS_BEFORE Ends exactly before another starts

MEETS_AFTER Starts exactly after another ends

Example: OVERLAPS

[𝑇. 𝑉𝑠𝑡, 𝑇. 𝑉𝑒𝑡] 𝑂𝑉𝐸𝑅𝐿𝐴𝑃𝑆 [2002-01-01, 2002-12-31]

Meaning:
Employee tuple valid at any time during 2002.

2. Coalescing

Adjacent or overlapping time periods are merged into one period.

Example

[1,5] and [6,10]

becomes

[1,10]

3. AS_OF Query

Used to query previous database states.

Example

SELECT *
FROM EMP_BT
AS OF '2024-01-01';
4. TSQL2 Language

TSQL2 extends SQL with temporal concepts.

Temporal Table Types in TSQL2

Declaration Meaning

AS VALID STATE Valid time period

AS VALID EVENT Valid time point

AS TRANSACTION Transaction time

AS VALID STATE AND TRANSACTION Bitemporal relation

Example

CREATE TABLE EMPLOYEE

AS VALID STATE DAY;

26.2.5 Time Series Data

Definition

Time series data contains values recorded at predefined time intervals.

Examples

• Daily stock prices

• Monthly sales

• Temperature readings

• Sensor data

Characteristics

• Fixed sequence of time points

• Usually event-based valid-time data

• Sequential storage
Common Time Series Queries

Query Type Example

Average Weekly average sales

Maximum Monthly highest stock price

Sum Yearly sales total

Comparison Compare current month vs previous month

Time Series Support in DBMS

Modern DBMSs support time series using:

• Oracle Time Cartridge

• Informix Time Series DataBlade

• TSQL2 event tables

Advantages of Temporal Databases

1. Maintain historical data

2. Support auditing

3. Enable rollback and recovery

4. Improve decision making

5. Support real-world applications

6. Preserve data consistency

Disadvantages of Temporal Databases

1. Increased complexity

2. Larger storage requirements

3. Complex querying

4. Higher maintenance cost

 5. Slower performance for large histories

Comparison of Temporal Databases

Feature Valid Time Transaction Time Bitemporal

Real-world history Yes No Yes

Database history No Yes Yes

Supports rollback No Yes Yes

Complexity Low Medium High

Key Terms

Term Meaning

Chronon Smallest time unit

Valid Time Real-world validity

Transaction Time Database storage time

Bitemporal Both valid and transaction time

Tuple Versioning Multiple tuple copies

Attribute Versioning Versioning individual attributes

Coalescing Merging adjacent periods

Time Series Sequential temporal data

Summary

• Temporal databases manage time-related data.

• Time can represent events or durations.

• Main temporal dimensions are valid time and transaction time.

• Tuple versioning stores multiple tuple histories.

• Attribute versioning versions individual attributes.

• TSQL2 extends SQL with temporal operations.

• Time series data is an important practical temporal application.

Lecture Notes: Spatial Database Concepts (Chapter 26.3)

26.3 Spatial Database Concepts

1. Introduction to Spatial Databases

Definition

A Spatial Database is a database system designed to store, manage, query, and

analyze data related to objects in space.

These databases support:

• Spatial data types

• Spatial relationships

• Spatial queries

• Spatial indexing

Spatial databases are widely used in:

• Geographic Information Systems (GIS)

• Navigation systems

• Weather forecasting

• Urban planning

• Remote sensing

• Transportation systems

• Bioinformatics

2. Geographic Information Systems (GIS)

GIS Definition

A Geographic Information System (GIS) is a system used to capture, store, analyze,

and visualize geographic data.

Applications of GIS

• Environmental monitoring

• Emergency response systems

• Traffic management
 • Military applications

• Disaster management

• Urban development

3. Characteristics of Spatial Data

Spatial objects contain:

1. Spatial Characteristics

Describe:

• Shape

• Size

• Position

• Geometry

2. Spatial Relationships

Describe:

• Adjacency

• Connectivity

• Overlap

• Distance

• Direction

4. Examples of Spatial Databases

Application Spatial Dimension

Maps 2D

Weather systems 3D

Satellite imaging 2D/3D

Traffic systems 2D

Terrain models 3D
5. Spatial Queries

Definition

Queries involving spatial conditions are called Spatial Queries.

Example

• Find hospitals within 5 km of a location.

• Find all rivers crossing a state.

• Find nearest police station.

6. Need for Spatial Databases

Traditional databases:

• Handle numeric and text data efficiently

• Cannot efficiently process multidimensional spatial coordinates

Problems with traditional indexing:

• B+-trees cannot efficiently index latitude-longitude data

• Spatial relationships require geometric processing

Hence specialized:

• Spatial data types

• Spatial indexes

• Spatial operators

are required.

7. Analytical Operations on Spatial Data

Common Spatial Analysis Operations

Analysis Type Operations

Measurements Distance, area, perimeter

Spatial statistics Pattern analysis

Analysis Type Operations

Flow analysis Shortest path

Location analysis Point-in-polygon

Terrain analysis Slope and elevation

Spatial search Region-based search

8. Types of Spatial Data

Spatial data exists in three forms.

8.1 Map Data

Represents geographical features.

Basic Spatial Features

a) Points

Represent single coordinate locations.

Examples:

• Buildings

• Towers

• Vehicles

b) Lines

Represent objects with length.

Examples:

• Roads

• Rivers

• Pipelines

c) Polygons

Represent objects with boundaries.

Examples:
 • Countries

• Lakes

• Cities

8.2 Attribute Data

Descriptive information associated with map objects.

Examples

For a county:

• Population

• Area

• Largest city

8.3 Image Data

Includes:

• Satellite images

• Aerial photographs

• Raster images

Used in:

• Remote sensing

• Environmental monitoring

9. Spatial Data Models

Spatial information is modeled using:

9.1 Field-Based Model

Used for continuous data.

Examples

• Temperature

• Soil quality
 • Elevation

9.2 Object-Based Model

Used for discrete objects.

Examples

• Buildings

• Roads

• Land parcels

10. Spatial Operators

Spatial operators manipulate and analyze spatial objects.

They are classified into:

10.1 Topological Operators

Used to determine spatial relationships.

Characteristics

Invariant under:

• Rotation

• Translation

• Scaling

Examples

• Inside

• Intersects

• Adjacent

• Touches

Example Query

Find all highways intersecting a city boundary.

10.2 Projective Operators

Used to analyze geometric properties.

Example

• Convex Hull

Applications:

• Shape analysis

• Concavity detection

10.3 Metric Operators

Measure geometric properties.

Examples

• Distance

• Area

• Length

• Direction

11. Dynamic Spatial Operations

Unlike static operations, dynamic operations modify objects.

Fundamental Dynamic Operations

• Create

• Destroy

• Update

Examples of Updates

• Translation

• Rotation

• Scaling

• Reflection

• Shearing
12. Types of Spatial Queries

12.1 Range Queries

Find objects inside a specified region.

Example

Find all hospitals in Bangalore city.

12.2 Nearest Neighbor Queries

Find closest object to a location.

Example

Find nearest ambulance to accident site.

k-Nearest Neighbor Query

Find 5 nearest ATMs.

12.3 Spatial Join Queries

Join objects based on spatial relationships.

Examples

• Houses within 2 km of a lake

• Towns intersecting highways

13. Spatial Data Indexing

Purpose

Spatial indexing improves query performance.

Spatial indexes organize objects into:

• Buckets

• Regions

• Rectangles
14. Spatial Indexing Techniques

14.1 Grid Files

Divide space into fixed-size cells.

Features

• Suitable for uniformly distributed data

• Implemented using multidimensional arrays

Advantages

• Simple implementation

Limitations

• Large sparse directories

• Rigid structure

14.2 R-Trees

Most important spatial indexing method.

Definition

An R-tree is a height-balanced tree for multidimensional indexing.

Objects are represented using:

Minimum Bounding Rectangle (MBR)

Smallest rectangle enclosing the object.

Properties of R-Trees

1. Leaf nodes contain:

o (MBR, Object-ID)

2. Non-leaf nodes contain:

o (MBR, Child-pointer)

3. All leaves at same level

 4. MBR edges parallel to coordinate axes

Advantages of R-Trees

• Efficient spatial searching

• Supports overlap queries

• Handles multidimensional data

14.3 Quadtrees

Recursively divide space into four equal regions.

Applications:

• Image processing

• GIS systems

15. Spatial Join Index

Definition

A precomputed index storing spatial relationships between objects.

Purpose

Speeds up spatial join queries.

Example

Find river-highway crossings.

Bipartite Graph Representation

Spatial join indexes can be represented using:

𝐺 = (𝑉1 , 𝑉2 , 𝐸)

Where:

• 𝑉1→ tuples of relation R

• 𝑉2→ tuples of relation S

 • 𝐸→ spatial relationship edges

16. Spatial Data Mining

Spatial data mining extracts hidden spatial patterns.

Main techniques:

1. Spatial Classification

2. Spatial Association

3. Spatial Clustering

16.1 Spatial Classification

Predicts spatial attributes.

Example

Predict earthquake-prone zones.

Applications:

• Crime hotspot detection

• Nest location prediction

16.2 Spatial Association

Discovers spatial relationships.

Example Rule

Countries touching Mediterranean Sea are wine exporters.

General form:

𝑃1 ∧ 𝑃2 ∧. . . ⇒ 𝑄1 ∧ 𝑄2

16.3 Spatial Clustering

Groups nearby similar objects.

Goal
 • Similar objects → same cluster

• Dissimilar objects → different clusters

17. Density-Based Clustering

Popular clustering approaches:

17.1 DBSCAN

Full form:
Density-Based Spatial Clustering of Applications with Noise

Features

• Detects arbitrary shaped clusters

• Handles noise effectively

17.2 DENCLUE

Density-based clustering using mathematical density functions.

18. Applications of Spatial Databases

18.1 Geography and GIS

• Mapping

• Navigation

• Land management

18.2 Transportation Systems

• Traffic monitoring

• Route optimization

• Fleet tracking

18.3 Environmental Monitoring

 • Climate analysis

• Pollution monitoring

• Forest management

18.4 Bioinformatics

Spatial databases assist in:

• Genome mapping

• Pattern recognition

• Biological visualization

18.5 Public Safety

• Crime analysis

• Emergency response

• Disaster management

19. Spatial Outlier Detection

Definition

A spatial object whose attributes significantly differ from neighboring objects.

Example

A new house among old houses.

Applications:

• Fraud detection

• Environmental anomaly detection

• Disease outbreak analysis

20. Advantages of Spatial Databases

• Efficient multidimensional data handling

• Supports GIS applications

 • Faster spatial querying

• Better decision making

• Advanced spatial analytics

21. Limitations of Spatial Databases

• Complex indexing

• High storage requirements

• Expensive spatial joins

• Computationally intensive operations

22. Summary

Spatial databases:

• Manage spatial and geographic information

• Support multidimensional objects

• Use spatial operators and indexes

• Enable advanced spatial queries and analysis

Important concepts:

• GIS

• Spatial data types

• R-trees

• Spatial queries

• Spatial data mining

• Spatial clustering

These databases are essential in:

• GIS

• Navigation

• Environmental systems

• Bioinformatics
• Smart city applications
Lecture Notes: Multimedia Database Concepts

26.4 Multimedia Database Concepts

Introduction

A multimedia database is a database system designed to store, manage, retrieve, and

query multimedia data such as:

• Images

• Video clips

• Audio clips

• Text/documents

These databases support content-based retrieval, where multimedia objects are

retrieved according to their contents rather than simple text descriptions.

1. Multimedia Data Types

1.1 Images

Images may include:

• Photographs

• Drawings

• Medical images

• Satellite images

Image Storage

Images are stored in:

1. Raw form

o Matrix of pixels

2. Compressed form

o Reduces storage space

Compression Standards

Common image compression formats:

• GIF

• JPEG
 • MPEG

Mathematical Transforms Used

• Discrete Fourier Transform (DFT)

• Discrete Cosine Transform (DCT)

• Wavelet Transform

1.2 Video Data

Video consists of:

• Sequence of frames

• Each frame is a still image

Video Segments

A video is divided into:

• Contiguous frame segments

• Each segment contains same objects/activities

Video Compression

• MPEG is widely used

Video Indexing

Uses:

• Frame segment trees

• Object/activity indexing

Examples:

• Detecting a soccer goal

• Identifying a famous person in a movie

1.3 Audio Data

Audio includes:

• Songs

• Speeches
 • Phone conversations

• Lectures

Audio Analysis

Used for:

• Speaker recognition

• Similarity matching

• Music retrieval

1.4 Text/Documents

Examples:

• Books

• Articles

• Magazines

Document Indexing

Documents are indexed using:

• Keywords

• Frequency of occurrence

Stopwords

Common words removed:

• the

• is

• and

• of

Dimensionality Reduction

Technique:

• Singular Value Decomposition (SVD)

Document Index Structure

• Telescoping Vector Trees (TV-trees)

2. Content-Based Retrieval (CBR)

Definition

Retrieval of multimedia data based on:

• Objects

• Activities

• Features present in the media

Examples

• Find videos containing Michael Jackson

• Retrieve images similar to a tiger image

• Locate football clips with a specific player

3. Multimedia Retrieval Approaches

3.1 Automatic Analysis

System automatically extracts features from multimedia content.

Used for:

• Images

• Video

• Audio

3.2 Manual Annotation

Human experts:

• Identify objects

• Add descriptive tags

Advantages

• Accurate semantic labeling

Disadvantages

• Time consuming
 • Expensive

4. Automatic Analysis of Images

Image analysis uses low-level visual features.

Main Features

1. Color

2. Texture

3. Shape

4.1 Color-Based Retrieval

Color Histogram

Represents:

• Distribution of colors in an image

RGB Model

Uses:

• Red

• Green

• Blue

HSV Model

More robust than RGB.

HSV Components:

• Hue

• Saturation

• Value (brightness)

4.2 Texture Analysis

Texture

Represents surface appearance:

 • Rough

• Smooth

• Silky

Texture Elements

Called:

• Texels

Texture Properties

• Contrast

• Regularity

• Coarseness

• Directionality

4.3 Shape Analysis

Shape Representation

Determines object boundaries.

Techniques

1. Segmentation

2. Edge detection

Desired Properties

Shape representation should be invariant to:

• Translation

• Rotation

• Scaling

Shape Methods

• Fourier descriptors

• Moment invariants

5. Image Similarity Techniques

5.1 Distance-Based Approach

Uses a distance function between images.

Principle

• Smaller distance → Higher similarity

Advantage

• Faster searching using indexes

5.2 Transformation Approach

Measures transformations needed to match images.

Transformations Include

• Rotation

• Translation

• Scaling

Drawback

• Computationally expensive

6. Object Recognition in Images

Definition

Process of identifying real-world objects in images/videos.

Challenges

Objects may vary in:

• Size

• Scale

• Orientation

• Illumination

Object Recognition Techniques

6.1 Segmentation
Divides image into homogeneous regions.

Example:

• Tiger separated from jungle background

6.2 Feature-Based Recognition

Finds transformation-invariant features.

7. Scale-Invariant Feature Transform (SIFT)

Developed By

David Lowe

Features of SIFT

Invariant to:

• Scaling

• Rotation

• Partial illumination changes

Working

1. Extract keypoints

2. Store feature vectors

3. Compare using Euclidean distance

Applications

• Image matching

• Scene recognition

• Object detection

8. Semantic Tagging of Images

Definition

Attaching descriptive tags to images.

Example Tags
 • tiger

• jungle

• green

• stripes

Automated Tagging

Uses:

• Image processing

• Statistical models

Ontologies and Semantic Models

Technologies

• OWL (Web Ontology Language)

Benefits

Improves:

• Semantic search

• Concept understanding

• Image retrieval quality

9. Analysis of Audio Data

Types of Audio

1. Speech

2. Music

3. Other audio signals

9.1 Speech Recognition

Purpose

Convert speech to text for indexing.

Advantages

• Easier searching

• Better accuracy

Metadata Examples

• Number of speakers

• Duration

• Recording format

9.2 Music Retrieval

Content-Based Audio Indexing

Uses sound properties such as:

• Pitch

• Rhythm

• Timbre

• Intensity

10. Multimedia Database Indexing

Purpose

Improve retrieval efficiency.

Common Indexing Methods

Multimedia Type Indexing Technique

Images Feature vectors

Videos Frame segment trees

Audio Signal features

Documents TV-trees

11. Applications of Multimedia Databases

Image Databases

• Medical imaging

• Satellite imaging

• Face recognition

Video Databases

• Surveillance systems

• Sports analytics

• Streaming platforms

Audio Databases

• Voice assistants

• Music recommendation systems

• Speech analytics

Document Databases

• Digital libraries

• Search engines

• Research archives

12. Advantages of Multimedia Databases

• Efficient multimedia storage

• Fast content retrieval

• Supports complex searches

• Enables semantic analysis

• Useful in AI and machine learning

13. Challenges of Multimedia Databases

 • Huge storage requirements

• Complex indexing

• High computational cost

• Difficult semantic understanding

• Real-time retrieval issues

14. Key Terms

Term Meaning

Pixel Smallest image element

Texel Texture element

Segmentation Dividing image into regions

SIFT Scale-Invariant Feature Transform

Content-Based Retrieval Retrieval using media content

Semantic Tagging Assigning descriptive labels

HSV Hue Saturation Value color model

MPEG Video compression standard

15. Summary

• Multimedia databases manage images, videos, audio, and text.

• Content-based retrieval is the core functionality.

• Image retrieval depends on color, texture, and shape analysis.

• Object recognition uses techniques like SIFT.

• Semantic tagging improves intelligent searching.

• Audio indexing uses speech recognition and sound features.

• Multimedia databases are widely used in AI, healthcare, surveillance, and

entertainment.
Lecture Notes: Introduction to Deductive Databases

26.5 Introduction to Deductive Databases

1. Introduction

A Deductive Database is an advanced database system that combines:

• Traditional databases

• Logic programming

• Rule-based inference mechanisms

It allows the system to derive new facts from existing data using logical rules.

Key Idea

Instead of specifying how to retrieve data, users specify what they want using a
declarative language.

The system uses an Inference Engine to:

• interpret rules,

• deduce new information,

• answer complex recursive queries.

2. Features of Deductive Databases

Main Characteristics

• Uses facts and rules

• Supports recursive queries

• Based on logic programming

• Closely related to:

o Relational Model

o Predicate Calculus

o Prolog

o Datalog
3. Facts and Rules

Facts

Facts represent stored information.

Example

SUPERVISE(franklin, john).
SUPERVISE(james, franklin).

Meaning:

• Franklin supervises John.

• James supervises Franklin.

Important Note

Attribute names are omitted.

Meaning depends on:

• Position of arguments

Example:

SUPERVISE(Supervisor, Supervisee)

Rules

Rules derive new facts.

General Form

Head :- Body.

Meaning:
“If Body is true, then Head is true.”

4. Recursive Rules

Recursive rules are the major strength of deductive databases.

Example: SUPERIOR Relation

Rule 1

SUPERIOR(X,Y) :- SUPERVISE(X,Y).

Direct supervision.
Rule 2 (Recursive)

SUPERIOR(X,Y) :- SUPERVISE(X,Z), SUPERIOR(Z,Y).

Indirect supervision.

This recursively finds:

• subordinates at all levels.

5. Queries in Deductive Databases

Variable-Based Query

SUPERIOR(james,Y)?

Returns all employees under James.

Boolean Query

SUPERIOR(james,joyce)?

Returns:

• TRUE or FALSE

6. Datalog Notation

Datalog is a simplified version of Prolog.

Atomic Formula

General form:

p(a1,a2,...,an)

Where:

• p = predicate

• a1...an = arguments

Predicate Arity

Number of arguments of predicate.

Example:

SUPERVISE(X,Y)

Arity = 2

7. Literals

Positive Literal

SUPERVISE(X,Y)

Negative Literal

NOT(SUPERVISE(X,Y))

8. Built-in Predicates

Datalog supports comparison operators:

Operator Meaning

< less than

<= less than or equal

> greater than

>= greater than or equal

= equal
Operator Meaning

/= not equal

9. Clausal Form

In logic programming:

• formulas are converted into clauses.

A clause is:

• a disjunction (OR) of literals.

10. Horn Clauses

A Horn Clause contains:

• at most one positive literal.

General Form

Q :- P1, P2, ..., Pn.

Meaning:
If all predicates P1...Pn are true,
then Q is true.

11. Integrity Constraints

Constraint form:

P1, P2, ..., Pn.

Means all predicates must hold true.

12. Interpretation of Rules

Two major interpretations:

1. Proof-Theoretic Interpretation

• Facts and rules are axioms

• New facts are derived using theorem proving

Example

Given:

SUPERVISE(james,jennifer).
SUPERVISE(jennifer,ahmad).

Then:

SUPERIOR(james,ahmad)

can be inferred.
2. Model-Theoretic Interpretation

Assigns:

• TRUE/FALSE values
to all predicate combinations.

A model is valid if:

• all rules remain true.

13. Minimal Model

A Minimal Model:

• contains only necessary true facts.

Extra unnecessary facts are removed.

14. Inference Mechanism

Inference engine performs:

• deduction,

• reasoning,

• query processing.

Two approaches:

Method Description

Top-down Used in Prolog

Bottom-up Used in Datalog

15. Top-Down Evaluation

Used in Prolog.

Characteristics

• Goal-oriented

• Uses backward chaining

 • Order of rules matters

16. Bottom-Up Evaluation

Used in Datalog.

Characteristics

• Starts from facts

• Applies rules repeatedly

• Suitable for large databases

17. Datalog Programs

Two predicate types:

1. Fact-Defined Predicates

Stored directly in database.

Example:

EMPLOYEE(john).
SALARY(john,30000).

2. Rule-Defined Predicates

Derived using rules.

Example:

SUPERVISOR(X) :-
EMPLOYEE(X),
SUPERVISE(X,Y).

18. Safety of Datalog Rules

A rule is safe if:

• it generates a finite number of facts.

Unsafe Rule Example

BIG_SALARY(Y) :- Y > 60000.

Problem:

• Infinite values for Y.

Safe Rule Example

BIG_SALARY(Y) :-
EMPLOYEE(X),
SALARY(X,Y),
Y > 60000.

Now Y is restricted to employee salaries.

19. Limited Variables

A variable is limited if:

• it appears in a regular predicate,

• or is restricted by constants/comparisons.

20. Relational Operations in Datalog

Datalog can express relational algebra operations.

Selection
SELECT_ONE(X,Y,Z) :-
REL_ONE(X,Y,Z),
Y < 5.

Projection

PROJECT_THREE(W,X) :-
REL_THREE(W,X,Y,Z).

Union

UNION_ONE_TWO(X,Y,Z) :-
REL_ONE(X,Y,Z).

UNION_ONE_TWO(X,Y,Z) :-
REL_TWO(X,Y,Z).

Intersection

INTERSECT_ONE_TWO(X,Y,Z) :-
REL_ONE(X,Y,Z),
REL_TWO(X,Y,Z).

Difference

DIFFERENCE_TWO_ONE(X,Y,Z) :-
REL_TWO(X,Y,Z),
NOT(REL_ONE(X,Y,Z)).

Cartesian Product

CART_PROD(...) :-
REL_ONE(...),
REL_THREE(...).

Natural Join
NATURAL_JOIN(...) :-
REL_ONE(...),
REL_THREE(...).

21. Recursive and Nonrecursive Queries

Nonrecursive Query

No cycles in dependency graph.

Can be evaluated directly.

Recursive Query

Contains recursive predicates.

Example:

SUPERIOR(X,Y)

22. Predicate Dependency Graph

Used to:

• analyze dependencies among predicates.

Nodes

Predicates

Edges

Dependency relationships

If graph has:

• no cycle → nonrecursive

• cycle → recursive

23. Evaluation of Nonrecursive Queries

Steps:

1. Compute base relations

2. Evaluate dependent predicates

 3. Apply relational operations

4. Generate final result

24. Query Processing in Datalog

Inference engine converts rules into:

• relational algebra expressions.

Uses:

• SELECT

• PROJECT

• JOIN

• UNION

• DIFFERENCE

Then DBMS optimization techniques are applied.

25. Advantages of Deductive Databases

• Declarative query specification

• Recursive query support

• Logical reasoning capability

 • Powerful knowledge representation

• Better semantic modeling

26. Limitations

• Complex recursive evaluation

• Safety issues

• Handling negation is difficult

• Performance overhead

27. Applications

• Expert Systems

• Artificial Intelligence

• Knowledge-Based Systems

• Semantic Web

• Recursive Query Processing

• Decision Support Systems

28. Difference Between Prolog and Datalog

Feature Prolog Datalog

Evaluation Top-down Bottom-up

Functions Supported Not supported

Recursion Supported Supported

Duplicate elimination No Yes

Query result One-at-a-time Set-at-a-time

29. Key Terms

Term Meaning

Fact Stored information

Rule Logical implication

Predicate Relation name

Literal Atomic formula

Horn Clause Clause with ≤1 positive literal

Recursive Rule Rule referring to itself

Inference Engine Deduction mechanism

Minimal Model Smallest valid interpretation

30. Summary

Deductive databases extend traditional databases with:

• logical inference,

• recursion,

• declarative programming.

Datalog provides:

• rule-based querying,

• recursive reasoning,

• logical knowledge representation.

These systems form the foundation for:

• AI databases,

• semantic systems,

• advanced query processing technologies.

Introduction to Information Retrieval and Web Search

Lecture Notes: Information Retrieval (IR) Concepts

27.1 Information Retrieval (IR) Concepts

Definition of Information Retrieval

Information Retrieval (IR) is the process of retrieving relevant documents or information

from a large collection in response to a user query or search request.

According to Gerard Salton, IR is:

“The discipline that deals with the structure, analysis, organization, storage, searching,
and retrieval of information.”

IR mainly focuses on retrieving:

• Text documents

• Web pages

• Multimedia data

• Emails and messages

• Digital library contents

27.1.1 Introduction to Information Retrieval

Structured vs Unstructured Data

Structured Data

Structured data follows a fixed schema or format.

Example

A relational table:

Lot# Address Square Footage Listed Price

101 MG Road 2400 80 Lakhs

This type of data:

• Has predefined fields

• Can be queried using SQL

• Is easy to organize and search

Unstructured Data

Unstructured data does not follow a fixed format.

Examples

• Home-buying contracts

• Web pages

• Emails

• Images

• Videos

• Audio files

• Social media posts

Characteristics:

• Natural language based

• Flexible format

• Difficult to search directly

Growth of Unstructured Information

With the rise of the:

• Internet

• Social media

• World Wide Web

the amount of unstructured information has grown exponentially.

Formats include:

• HTML

• XML

• Audio formats

• Video formats

IR systems help in:

 • Storing

• Indexing

• Searching

• Retrieving such information efficiently.

Role of IR Systems

IR systems:

• Accept free-form user queries

• Search huge repositories

• Retrieve relevant documents

Unlike databases:

• Users need not know schema details

• Queries are often keywords or natural language phrases

Example Queries

• “Artificial Intelligence”

• “Find Italian restaurants”

• “What is the currency of China?”

Extended Database Systems

Modern database systems support:

• XML data

• Multimedia data

• Spatial data

• Temporal data

These are called:

• Extended RDBMS

• Object-Relational DBMS (ORDBMS)

Characteristics of IR Systems

1. Types of Users

Expert Users

• Librarians

• Curators

• Researchers

Characteristics:

• Understand repository structure

• Form precise queries

Layperson Users

• Students

• Online shoppers

• Casual users

Characteristics:

• General information needs

• Less technical knowledge

2. Types of Data

IR systems may specialize in:

• Medical documents

• Legal records

• Enterprise files

• Web pages

• Multimedia data

Domain-Specific Search Engines

These focus on specific areas and provide better retrieval efficiency.

Examples:

• Biomedical search systems

 • Enterprise search systems

3. Types of Information Need

a) Navigational Search

Goal:
Find a specific website or page.

Example:

• “Georgia Tech official website”

b) Informational Search

Goal:
Find information about a topic.

Example:

• “Research activities in Computer Science”

c) Transactional Search

Goal:
Perform an activity or transaction.

Examples:

• Online shopping

• Hotel booking

• Social networking signup

4. Levels of Scale

Web Search Engines

Handle:

• Billions of web pages

• Massive distributed indexes

Enterprise Search
Searches:

• Emails

• Reports

• Corporate documents

Desktop Search

Searches personal computer files.

Examples:

• Spotlight

• Desktop search tools

27.1.2 Databases and IR Systems: Comparison

Databases IR Systems

Structured data Unstructured data

Fixed schema No fixed schema

SQL queries Free-form queries

Exact matching Approximate matching

Returns tuples Returns ranked documents

Schema-driven Content-driven

Exact answers Relevance-based answers

Key Differences

Database Systems

• Use relational models

• Support exact querying

• Queries return precise results

IR Systems
 • Use keyword-based searching

• Queries may be vague

• Results are ranked by relevance

27.1.3 Brief History of IR

Early Information Storage

Ancient civilizations used:

• Stone tablets

• Papyrus scrolls

• Libraries

for preserving information.

Major Developments

1950s

Hans Peter Luhn proposed:

• Word frequency analysis

• Keyword indexing

1960s

Development of:

• SMART retrieval system

• Inverted file indexing

TREC Initiative

Text Retrieval Conference (TREC)

Started by:

• National Institute of Standards and Technology

Purpose:
 • Evaluate IR methodologies

• Improve retrieval systems

Search Engines

Search engines became the most important IR application.

Components

• Crawlers

• Indexers

• Ranking algorithms

Example

Google Search Engine

27.1.4 Modes of Interaction in IR Systems

1. Retrieval Mode

Definition

Directly searching for relevant information using a query.

Example

Searching:

• “Database Management Systems”

The system retrieves matching documents.

2. Browsing Mode

Definition

Exploring related documents interactively.

Example Scenario

User searches:

• “Atlanta”

Then navigates to:

 • Georgia Tech

• Athletics

• Football schedule

This navigation process is called browsing.

Hyperlinks and Anchor Text

Hyperlinks

Connect web pages together.

Anchor Text

Clickable text associated with a hyperlink.

Web Search = Retrieval + Browsing

Modern search engines combine:

• Retrieval

• Browsing

to improve user experience.

27.1.5 Generic IR Pipeline

IR processing generally follows two approaches:

1. Statistical Approach

Documents are analyzed using:

• Words

• Phrases

• Frequency counts

• N-grams

Main Statistical Models

• Boolean Model

• Vector Space Model

 • Probabilistic Model

2. Semantic Approach

Uses:

• Meaning

• Context

• Linguistic understanding

to improve retrieval accuracy.

Stages in IR Processing System

Offline Processing

1. Document Preprocessing

Tasks include:

• Tokenization

• Stop-word removal

• Stemming

2. Document Modeling

Documents are represented mathematically.

Example:

• Vector representation

3. Indexing

Creates searchable indexes.

Most common:

• Inverted Index

Online/User Interaction Processing

4. Query Formation

User enters:

• Keywords

• Questions

• Phrases

5. Query Processing

System:

• Cleans query

• Expands query

• Matches terms

6. Searching Mechanism

Search engine searches indexes for matching documents.

7. Document Retrieval

Relevant documents are retrieved and ranked.

8. Relevance Feedback

User feedback improves future search results.

Types

• Explicit feedback

• Implicit feedback

Simplified IR Pipeline

Documents
↓
Preprocessing
↓
Document Representation
↓
Indexing
↓
Inverted Index
↓
User Query
↓
Query Processing
↓
Matching & Ranking
↓
Retrieved Documents
↓
User Feedback

Inverted Index

Definition

An inverted index maps:

• Terms → Documents containing those terms

Example

Term Documents

database D1, D3

retrieval D2, D3

search D1, D2

Advantages:

• Fast searching

• Efficient retrieval

• Scalable for web search

Important Terms

Term Meaning

Query User search request

Document Unit of searchable information

Keyword Search term

Relevance Degree of usefulness

Indexing Organizing documents for search

Ranking Ordering results by relevance

Crawling Discovering web pages

Applications of Information Retrieval

Web Search Engines

Examples:

• Google

• Yahoo

Digital Libraries

Search scholarly articles and books.

Enterprise Search

Search internal company documents.

Multimedia Retrieval

Retrieve:

• Images

• Videos

• Audio files

E-Commerce Search

Search:

• Products

• Reviews

• Services

Advantages of IR Systems

• Handles huge document collections

• Supports free-form queries

• Fast information access

• Supports ranking of results

 • Useful for unstructured data

Challenges in IR

• Handling massive web data

• Ambiguous queries

• Ranking accuracy

• Semantic understanding

• Real-time indexing

• Noise and irrelevant results

Summary

Information Retrieval (IR) is a technology used for searching and retrieving relevant
information from large collections of unstructured data. It forms the foundation of
modern search engines and digital libraries. IR systems differ from databases because
they support approximate matching and relevance ranking instead of exact matching.
Modern IR systems combine statistical and semantic techniques to provide efficient,
scalable, and user-friendly search capabilities.
Lecture Notes: Retrieval Models in Information Retrieval (IR)

27.2 Retrieval Models

Introduction

Retrieval models are mathematical and logical frameworks used in Information

Retrieval (IR) systems to:

• Represent documents

• Represent user queries

• Measure similarity between queries and documents

• Retrieve relevant information

Types of Retrieval Models

The major retrieval models are:

1. Boolean Model

2. Vector Space Model

3. Probabilistic Model

4. Semantic Model

27.2.1 Boolean Model

Definition

The Boolean model represents documents as a set of terms and uses Boolean logic
operators for searching.

Boolean Operators

AND

Retrieves documents containing all query terms.

Example:

database AND retrieval

Returns documents containing both:

• database
 • retrieval

OR

Retrieves documents containing at least one query term.

Example:

database OR retrieval

NOT

Excludes documents containing a specific term.

Example:

database NOT retrieval

Features of Boolean Model

• Simple and easy to implement

• Exact matching retrieval

• Binary relevance decision

• No ranking of documents

• Documents are either:

o Relevant

o Non-relevant

Advantages

• Fast query processing

• Suitable for structured searching

• Supports metadata searching

Example metadata:

• Author

• Date
 • Document type

Limitations

• No relevance ranking

• Ignores term frequency

• Cannot measure partial similarity

• Poor handling of vague queries

Example

Query

database AND systems

Result

Only documents containing both words are retrieved.

27.2.2 Vector Space Model (VSM)

Definition

The Vector Space Model represents documents and queries as vectors in an n-

dimensional space.

Each term represents one dimension.

Concept of Vector Representation

Suppose vocabulary contains:

database, retrieval, indexing

Then a document can be represented as:

Term Weight

database 3

retrieval 5
Term Weight

indexing 1

Features of Vector Space Model

• Supports ranking

• Uses term weights

• Measures similarity between query and document

• Supports relevance feedback

Term Weighting

Weights are usually calculated using:

• TF (Term Frequency)

• TF-IDF (Term Frequency–Inverse Document Frequency)

Term Frequency (TF)

Definition

Measures how frequently a term occurs in a document.

Formula
𝑓𝑖𝑗
𝑇𝐹𝑖𝑗 =
∑𝑓𝑖𝑗

Where:

• 𝑓𝑖𝑗 = frequency of term i in document j

Inverse Document Frequency (IDF)

Definition

Measures how important a term is across the document collection.

Formula
 𝑁
𝐼𝐷𝐹𝑖 = log⁡ ( )
𝑛𝑖

Where:

• 𝑁= total number of documents

• 𝑛𝑖 = number of documents containing term i

TF-IDF Weight

Definition

Combines TF and IDF to determine importance of a term.

Formula

𝑤𝑖𝑗 = 𝑇𝐹𝑖𝑗 × 𝐼𝐷𝐹𝑖

Cosine Similarity

Purpose

Measures similarity between document vector and query vector.

Formula
𝑑⋅𝑞
cos⁡(𝑑, 𝑞) =
∥ 𝑑 ∥∥ 𝑞 ∥

Interpretation

Cosine Value Meaning

1 Completely similar

0 Completely different

Advantages of Vector Space Model

• Supports ranking

• Partial matching possible

• Handles term importance

 • Better retrieval effectiveness

Limitations

• High dimensionality

• Computational complexity

• Assumes term independence

• Semantic meaning not considered

Rocchio Algorithm

Definition

A relevance feedback algorithm used in vector space retrieval.

It modifies the original query using:

• Relevant documents

• Non-relevant documents

Rocchio Formula
𝛽 𝛾
𝑞𝑒 = 𝛼𝑞 + ∑𝑑𝑟 − ∑𝑑
∣ 𝐷𝑟 ∣ ∣ 𝐷𝑛𝑟 ∣ 𝑛𝑟

Where:

• 𝑞= original query

• 𝐷𝑟 = relevant documents

• 𝐷𝑛𝑟 = non-relevant documents

• 𝛼, 𝛽, 𝛾= weighting parameters

Applications of Vector Space Model

• Web search engines

• Document ranking

• Digital libraries
 • Recommendation systems

27.2.3 Probabilistic Model

Definition

The probabilistic model ranks documents based on the probability that a document is
relevant to a query.

Basic Idea

A document is retrieved if:

Probability(Relevant) > Probability(Non-Relevant)

Bayes Theorem in IR

The model uses Bayes’ theorem.

Formula
𝑃(𝐷 ∣ 𝑅)𝑃(𝑅)
𝑃(𝑅 ∣ 𝐷) =
𝑃(𝐷)

Where:

• 𝑃(𝑅 ∣ 𝐷)= probability that document D is relevant

• 𝑃(𝐷 ∣ 𝑅)= probability of document given relevance

• 𝑃(𝑅)= prior relevance probability

Relevance Decision

A document is relevant if:

𝑃(𝐷 ∣ 𝑅) × 𝑃(𝑅) > 𝑃(𝐷 ∣ 𝑁𝑅) × 𝑃(𝑁𝑅)

Where:

• 𝑁𝑅= non-relevant set

Naïve Bayes Assumption

Assumes:
 • Terms occur independently

This simplifies probability calculations.

BM25 (Best Match 25)

Definition

A popular probabilistic ranking algorithm derived from the Okapi system.

Features of BM25

• Uses term frequency

• Uses document length normalization

• Produces ranked retrieval

BM25 Parameters

Parameter Meaning

𝑘1 Term frequency scaling

𝑏 Length normalization

𝑘2 Query term scaling

Advantages of Probabilistic Model

• Strong theoretical basis

• Effective ranking

• Handles uncertainty well

• Widely used in modern search engines

Limitations

• Probability estimation is difficult

• Requires assumptions
 • Complex computations

27.2.4 Semantic Model

Definition

Semantic models retrieve documents based on meaning and concepts rather than
exact keywords.

Need for Semantic Retrieval

Keyword matching may fail when:

• Synonyms are used

• Meanings differ

• User query is ambiguous

Example:

car = automobile

A semantic system understands that both are related.

Levels of Semantic Analysis

1. Morphological Analysis

Studies:

• Word roots

• Prefixes

• Suffixes

Example:

connect, connected, connection

2. Syntactic Analysis

Analyzes:

• Sentence structure
 • Grammar

• Phrase relationships

3. Semantic Analysis

Determines:

• Meaning of words

• Synonyms

• Context

• Relationships

Knowledge-Based Semantic Systems

Semantic IR systems often use:

• Artificial Intelligence

• Expert systems

• Knowledge bases

Important Semantic Knowledge Bases

Cyc

Contains:

• Commonsense knowledge

• Millions of assertions and concepts

WordNet

A large thesaurus containing:

• Synonyms

• Semantic relationships

• Word hierarchies

Widely used in:

 • NLP

• Search engines

• AI systems

Advantages of Semantic Model

• Understands meaning

• Improves retrieval accuracy

• Handles synonyms and ambiguity

• Better user satisfaction

Limitations

• Complex implementation

• Requires huge knowledge bases

• Computationally expensive

Comparison of Retrieval Models

Exact Semantic
Model Main Idea Ranking
Match Understanding

Boolean Logical matching No Yes No

Vector Similarity
Yes Partial Limited
Space measurement

Probabilistic Probability of relevance Yes Partial Limited

Meaning-based
Semantic Yes No Yes
retrieval

Applications of Retrieval Models

Boolean Model

• Library systems
 • Database filtering

Vector Space Model

• Search engines

• Document similarity systems

Probabilistic Model

• Modern IR systems

• BM25-based search engines

Semantic Model

• AI search systems

• Intelligent assistants

• NLP applications

Summary

Retrieval models form the foundation of Information Retrieval systems. The Boolean
model provides exact matching, the Vector Space model introduces ranking using
similarity measures, the Probabilistic model ranks documents using relevance
probabilities, and the Semantic model improves retrieval using conceptual
understanding and meaning-based analysis. Modern search engines often combine
multiple retrieval models to achieve efficient and accurate information retrieval.
Lecture Notes: Types of Queries in Information Retrieval (IR) Systems

27.3 Types of Queries in IR Systems

Introduction

In Information Retrieval (IR) systems, documents are indexed using:

• Keywords

• Phrases

• Metadata

• Author names

• Creation dates

• Document types

These indexed terms are stored in an:

• Inverted Index

User queries are compared against these indexed terms to retrieve relevant documents.

Purpose of Queries in IR Systems

Queries help users:

• Search documents

• Retrieve information

• Express information needs

• Filter relevant content

Modern IR systems support:

• Simple keyword queries

• Boolean expressions

• Phrase searching

• Natural language searching

Main Types of Queries

1. Keyword Queries
 2. Boolean Queries

3. Phrase Queries

4. Proximity Queries

5. Wildcard Queries

6. Natural Language Queries

27.3.1 Keyword Queries

Definition

Keyword queries are the simplest and most commonly used search queries.

Users enter:

• One or more keywords

The IR system retrieves documents containing those words.

Features of Keyword Queries

• Easy to use

• Fast searching

• Most common query type

• Supported by all retrieval models

Example

Query

database concepts

The system retrieves documents containing:

• database

• concepts

Documents containing both terms are ranked higher.

Implicit AND Operation

Most IR systems treat multiple keywords as connected using AND.

Example:

database retrieval

Equivalent to:

database AND retrieval

Stop Words

Common words are often removed before processing.

Examples of Stop Words

• a

• the

• of

• is

Advantages

• Very simple

• User-friendly

• Efficient retrieval

• Fast processing

Limitations

• Ignores word order

• Ambiguous meanings

• Limited semantic understanding

27.3.2 Boolean Queries

Definition

Boolean queries use Boolean operators to combine keywords logically.

Boolean Operators

Operator Meaning

AND Both terms must exist

OR Either term may exist

NOT Excludes term

+ Required term

- Excluded term

() Grouping of expressions

AND Operator

Retrieves documents containing all terms.

Example

database AND indexing

OR Operator

Retrieves documents containing any term.

Example

database OR retrieval

NOT Operator

Excludes documents containing specific terms.

Example

database NOT network

Parentheses in Boolean Queries

Used for nested expressions.

Example

(database OR retrieval) AND indexing

Plus (+) and Minus (-) Operators

Plus (+)

Term is mandatory.

Example:

+database retrieval

Minus (-)

Term is excluded.

Example:

database -network

Features of Boolean Queries

• Exact matching

• Logical query processing

• No ranking

• Binary relevance decision

Advantages

• Precise searching

• Flexible query construction

• Useful for expert users

Limitations

• Complex for normal users

• No ranking of results
 • Exact matching only

27.3.3 Phrase Queries

Definition

Phrase queries search for an exact sequence of words.

The phrase is usually enclosed in double quotes.

Example

"conceptual database design"

Only documents containing the exact phrase are retrieved.

Features of Phrase Queries

• Maintains word order

• More precise retrieval

• Useful for specific topics

Phrase Indexing

To support phrase searching:

• Word positions must be stored

• Relative ordering must be maintained

Advantages

• High precision

• Exact phrase matching

• Reduces irrelevant results

Limitations

• More storage overhead

 • Position tracking required

• Less flexible than keyword search

27.3.4 Proximity Queries

Definition

Proximity queries search for terms appearing close to each other within a document.

Purpose

Measures:

• Distance between words

• Relative closeness of terms

Common Proximity Operators

Operator Meaning

NEAR Terms occur near each other

ADJ Terms are adjacent

AFTER One term follows another

Example

database NEAR retrieval

Documents where:

• database

• retrieval

appear close together are retrieved.

Phrase Search as Proximity Search

Phrase search is a special case of proximity search where:

 • Terms appear in exact order

• Distance = 0

Features of Proximity Queries

• Improves contextual relevance

• Considers term positions

• More meaningful retrieval

Advantages

• Better search accuracy

• Captures contextual relationships

• Useful in large text collections

Limitations

• Computationally expensive

• Requires token position indexing

• Slower for very large datasets

27.3.5 Wildcard Queries

Definition

Wildcard queries support:

• Pattern matching

• Partial word searching

• Regular expression style searching

Wildcard Characters

Common wildcard:

*
represents:

• Any sequence of characters

Example

data*

Matches:

• data

• database

• dataset

• datapoint

Features of Wildcard Queries

• Flexible searching

• Useful when exact spelling unknown

• Supports pattern matching

Search Engine Support

Many web search engines provide:

• Limited wildcard support

because:

• Full wildcard processing is expensive

Example System

Apache Lucene supports wildcard query processing.

Advantages

• Flexible search patterns

• Handles partial terms

 • Useful for unknown word endings

Limitations

• High preprocessing cost

• Computational overhead

• Large query expansion

27.3.6 Natural Language Queries

Definition

Natural language queries are written as:

• Questions

• Sentences

• Human language expressions

Example Queries

What is the currency of China?

Find Italian restaurants in Bengaluru

Features

• User-friendly

• Conversational interaction

• Meaning-based retrieval

Natural Language Processing (NLP)

Natural language query systems use:

• Semantic parsing

• Query reformulation

• Language understanding
Applications

• Question answering systems

• Voice assistants

• AI chatbots

• Intelligent search engines

Factoid Questions

These ask for:

• Specific facts

• Definitions

• Short answers

Examples

Who invented the telephone?

Define operating system

Semantic Models in Natural Language Queries

Semantic retrieval helps:

• Understand meanings

• Identify synonyms

• Interpret context

Advantages

• Easy for users

• Human-like interaction

• Better semantic understanding

Limitations

• Difficult language processing

• Ambiguity handling required

• Computational complexity

Comparison of Query Types

Query Type Example Main Feature Ranking

Keyword Query database retrieval Simple keyword search Yes

Boolean Query database AND retrieval Logical operations No

Phrase Query "database design" Exact phrase match Yes

Proximity Query database NEAR retrieval Distance-based search Yes

Wildcard Query data* Pattern matching Yes

Natural Language Query What is DBMS? Human language search Yes

Importance of Query Types in IR

Different query types:

• Improve search flexibility

• Increase retrieval accuracy

• Support different user needs

• Enhance user experience

Applications of Query Types

Keyword Queries

• Web search

• Basic document retrieval

Boolean Queries
 • Library systems

• Research databases

Phrase Queries

• Legal document search

• Academic search

Proximity Queries

• Scientific literature retrieval

• News search

Wildcard Queries

• Dictionary search

• Pattern matching systems

Natural Language Queries

• AI assistants

• Chatbots

• Smart search engines

Summary

Information Retrieval systems support different types of queries to satisfy diverse user
information needs. Keyword queries provide simple searching, Boolean queries enable
logical filtering, phrase and proximity queries improve contextual accuracy, wildcard
queries support flexible matching, and natural language queries allow human-like
interaction. Modern IR systems combine these query types to deliver accurate, efficient,
and user-friendly information retrieval.
Lecture Notes: Text Preprocessing in Information Retrieval (IR)

27.4 Text Preprocessing

Introduction

Text preprocessing is an important step in Information Retrieval (IR) systems.

It involves:

• Cleaning

• Transforming

• Standardizing text

before indexing and searching.

Objectives of Text Preprocessing

Text preprocessing helps to:

• Reduce index size

• Improve search efficiency

• Increase retrieval accuracy

• Eliminate unnecessary words

• Standardize document representation

Major Text Preprocessing Techniques

1. Stopword Removal

2. Stemming

3. Utilizing a Thesaurus

4. Handling Digits, Hyphens, Punctuation, and Cases

5. Information Extraction

27.4.1 Stopword Removal

Definition
Stopwords are very common words that occur frequently in documents but contribute
little meaning during searching.

Examples of Stopwords

the, of, to, a, and, in, is, was, at, by

These words occur in a large percentage of documents.

Characteristics of Stopwords

• High frequency

• Low semantic importance

• Common grammatical function words

Stopword Removal Process

Before indexing:

• Stopwords are removed from documents

Before searching:

• Queries may also be preprocessed

Example

Original Sentence

The database system is used for information retrieval

After Stopword Removal

database system used information retrieval

Advantages of Stopword Removal

1. Reduces Index Size

Index size may reduce by:

• 40% or more
2. Faster Searching

Fewer indexed terms improve search speed.

3. Removes Noise

Eliminates less meaningful words.

Limitations

Sometimes stopwords are important.

Example

"To be or not to be"

If stopwords are removed:

The query loses meaning completely.

Important Note

Many search engines:

• Avoid stopword removal in user queries

• Preserve meaningful phrases

27.4.2 Stemming

Definition

Stemming reduces different forms of a word to a common root form called the stem.

Example

Word Stem

computer comput

computing comput
Word Stem

computation comput

computable comput

Purpose of Stemming

Reduces:

• Plurals

• Verb tenses

• Derivational forms

to a common representation.

Benefits of Stemming

• Reduces vocabulary size

• Improves recall

• Saves storage space

• Groups related words together

Example

Query

compute

Documents containing:

• computer

• computing

• computation

can also be retrieved.

Popular Stemming Algorithm

Martin Porter Stemmer

Porter Stemming Algorithm

• Most widely used English stemmer

• Uses rule-based suffix removal

• Efficient and lightweight

Example of Porter Stemming

Original Word Stemmed Word

running run

connected connect

studies studi

Advantages

• Improves recall

• Reduces indexing complexity

• Efficient preprocessing

Limitations

1. Overstemming

Different words may become the same stem.

Example:

university → univers
universe → univers

2. Reduced Precision

May retrieve irrelevant documents.

27.4.3 Utilizing a Thesaurus

Definition

A thesaurus is a collection of:

• Concepts

• Synonyms

• Related words

used to standardize indexing and searching.

Purpose of Thesaurus

Helps:

• Match synonyms

• Expand queries

• Improve recall

• Standardize vocabulary

Example

Word Synonym

car automobile

doctor physician

student learner

Query Expansion Example

User Query

car

System may also search:

• automobile

• vehicle
Advantages

• Improves recall

• Handles synonym matching

• Supports semantic retrieval

Challenges

Words may have:

• Multiple meanings

• Different contexts

Example:

bank

Possible meanings:

• River bank

• Financial bank

Important Thesaurus Systems

UMLS

Features

• Biomedical thesaurus

• Millions of medical concepts

• Semantic relationships

Used in:

• Medical information retrieval

WordNet

Features

• Groups words into synonym sets (synsets)

• Organizes words by meaning

 • Supports semantic relationships

Categories include:

• Nouns

• Verbs

• Adjectives

• Adverbs

Advantages of WordNet

• Controlled vocabulary

• Reduces redundancy

• Helps query formulation

• Improves semantic search

27.4.4 Other Preprocessing Steps

Handling Digits and Special Text

Examples

• Dates

• Phone numbers

• URLs

• Email addresses

Search Engine Processing

Many web search engines:

• Preserve these terms

• Use them as metadata

to improve:

• Precision

• Recall

Handling Hyphens

Example Terms

AK-47
COVID-19

Possible Strategies

1. Keep the hyphen

2. Remove the hyphen

3. Replace hyphen with space

Complexity of Hyphen Handling

Automatic handling is difficult because:

• Product names

• Version numbers
 • Technical terms

often use hyphens.

Example

Apache Lucene StandardTokenizer

Treats hyphen as:

• Word delimiter

except when numbers are involved.

Handling Punctuation Marks

Punctuation may be:

• Removed

• Preserved

• Replaced with spaces

depending on the retrieval system.

Case Conversion

Most IR systems use:

• Case-insensitive searching

All text is converted to:

• Lowercase
or

• Uppercase

Example

DATABASE = database = Database

Language-Specific Processing
Different languages require handling of:

• Accents

• Diacritics

• Language-specific grammar

27.4.5 Information Extraction (IE)

Definition

Information Extraction (IE) is the process of extracting structured information from

unstructured text.

Goals of Information Extraction

Identify:

• People

• Places

• Organizations

• Events

• Facts

• Relationships

Named Entity Recognition (NER)

A major IE task.

Recognizes named entities such as:

• Person names

• Locations

• Dates

• Institutions

Example
Sentence

Ravi works at Infosys in Bengaluru

Extracted Entities

Entity Type

Ravi Person

Infosys Organization

Bengaluru Location

Techniques Used in IE

Rule-Based Approaches

Use:

• Grammars

• Patterns

• Regular expressions

• Thesauri

Probabilistic Approaches

Use:

• Machine learning

• Statistical models

Part-of-Speech (POS) Tagging

Identifies grammatical roles such as:

• Nouns

• Verbs

• Adjectives
Applications of Information Extraction

• Search engines

• AI assistants

• Chatbots

• Text analytics

• Semantic search

• Recommendation systems

Advantages of Information Extraction

• Improves search relevance

• Supports semantic retrieval

• Enables structured analysis

• Extracts useful metadata

Limitations

• Ambiguous language

• Complex sentence structures

• Domain dependency

Summary Table

Preprocessing Technique Purpose

Stopword Removal Remove common meaningless words

Stemming Reduce words to root forms

Thesaurus Usage Handle synonyms and semantics

Case & Symbol Handling Standardize text representation

Information Extraction Extract structured information

Benefits of Text Preprocessing

• Faster indexing

• Reduced storage

• Better search quality

• Improved recall and precision

• Enhanced semantic understanding

Summary

Text preprocessing is a crucial component of Information Retrieval systems. It

transforms raw textual data into a cleaner and more standardized form suitable for
indexing and searching. Techniques such as stopword removal, stemming, thesaurus
utilization, handling punctuation and cases, and information extraction significantly
improve the efficiency and effectiveness of IR systems. Modern search engines and AI-
based retrieval systems rely heavily on these preprocessing methods to provide
accurate and meaningful search results.
Lecture Notes: Inverted Indexing in Information Retrieval (IR)

27.5 Inverted Indexing

Introduction

Searching large collections of documents by sequential scanning is very slow and

inefficient.

To improve retrieval efficiency, Information Retrieval (IR) systems use:

• Indexing techniques

• Inverted Index data structures

Need for Inverted Indexing

Sequential Search Problems

Sequentially scanning documents:

• Takes more time

• Is inefficient for large collections

• Cannot scale to web-sized datasets

Solution: Inverted Index

An inverted index allows:

• Fast keyword searching

• Efficient retrieval

• Scalable indexing

It is the core data structure used in:

• Search engines

• Digital libraries

• Enterprise search systems

Definition of Inverted Index

An inverted index is a data structure that maps:

Term → List of documents containing the term

Basic Structure of Inverted Index

Two major components:

1. Vocabulary

2. Document Information

1. Vocabulary

Definition

Vocabulary is the collection of distinct terms extracted from documents.

Vocabulary Terms May Include

• Words

• Tokens

• Phrases

• N-grams

• Names

• Dates

• Entities

• Hyperlinks

Example Vocabulary

Vocabulary Terms

database

retrieval

indexing

search
2. Document Information

For each term, the system stores:

• Document IDs

• Frequency counts

• Position offsets

• Term weights

Example Inverted Index

Term Documents

database D1, D2

retrieval D2, D3

indexing D1, D3

Positional Information

Some systems also store:

• Word positions within documents

This helps:

• Phrase searching

• Proximity searching

Example with Positions

Term Document Positions

database D1 2, 15

retrieval D2 5, 20

Term Weighting
Purpose

Weights estimate the importance of a term in a document.

Common Weighting Scheme: TF-IDF

TF-IDF Formula

𝑇𝐹-𝐼𝐷𝐹 = 𝑇𝐹 × 𝐼𝐷𝐹

Where:

• TF = Term Frequency

• IDF = Inverse Document Frequency

Importance of TF-IDF

Helps:

• Distinguish important terms

• Rank relevant documents

• Reduce influence of common words

Document Length Normalization

Long documents naturally contain more words.

Normalization ensures:

• Long documents are not unfairly favored

• Fair comparison between documents

Construction of Inverted Index

Main Steps

1. Document preprocessing

2. Collect document statistics

3. Invert document-term mapping

Step 1: Document Preprocessing

Documents are processed using:

• Tokenization

• Cleansing

• Stopword removal

• Stemming

• Thesaurus support

Example

Original Text

Information retrieval systems are efficient

After Preprocessing

information retrieval system efficient

Step 2: Collect Document Statistics

Statistics include:

• Term counts

• Document lengths

• Position information

• Frequency counts

These are stored in:

• Document lookup tables

Step 3: Invert Document-Term Stream

The document-term relationship is inverted into:

Term → Documents

Illustration
Before Inversion

Document Terms

D1 database, indexing

D2 retrieval, database

After Inversion

Term Documents

database D1, D2

indexing D1

retrieval D2

Advantages of Inverted Indexing

• Fast searching

• Efficient retrieval

• Scalable architecture

• Supports ranking

• Supports phrase and proximity queries

Searching Using an Inverted Index

Searching typically involves three steps:

1. Vocabulary Search

2. Document Information Retrieval

3. Manipulation of Retrieved Information

Step 1: Vocabulary Search

Each query term is searched in the vocabulary.

Optimization Techniques

Search can be optimized using:

• Hashing

• B+-Trees

• Lexicographic ordering

Step 2: Document Information Retrieval

The posting list for each term is retrieved.

Example

Query

database retrieval

Retrieve:

• Documents containing database

• Documents containing retrieval

Step 3: Manipulation of Retrieved Information

Further processing includes:

• Boolean operations

• Phrase matching

• Proximity searching

• Ranking

Types of Supported Queries

• Prefix queries

• Range queries

• Context queries

• Proximity queries
Inverted Index Workflow

Documents
↓
Preprocessing
↓
Tokenization
↓
Vocabulary Creation
↓
Document Statistics
↓
Term Weighting
↓
Inverted Index Construction
↓
Search & Retrieval
27.5.1 Introduction to Lucene

What is Lucene?

Apache Lucene

Lucene is:

• An open-source search engine library

• Written in Java

• Widely used for indexing and searching

Features of Lucene

• High-performance indexing

• Scalable architecture

• Efficient search API

• Support for multiple query types

Relationship Between Lucene and Solr

Apache Solr

Solr is built on top of:

• Apache Lucene

It adds:

• Web interfaces

• Enterprise search features

• Faceted search

• Document format support

Indexing in Lucene

Lucene Document

A Lucene document contains:

• Multiple fields
Similar to:

• Columns in a database table

Field Types

Field Type Description

Binary Binary data

Numeric Numbers

Text Searchable text

Token Streams

Text fields are converted into:

• Token streams

using:

• Tokenizers

• Filters

Tokenizers in Lucene

StandardTokenizer

• Unicode text segmentation

• Splits words automatically

WhitespaceTokenizer

• Splits text at spaces

Custom Tokenization

Lucene allows:

• Custom tokenizers
 • Custom filters

• Language-specific analyzers

NLP Features in Lucene

Lucene supports:

• Stemming

• Lemmatization

• Morphological analysis

• Phonetic analysis

Search in Lucene

Lucene uses:

• Inverted indexes

• Vector space model

• TF-IDF scoring

for ranking search results.

Supported Query Types in Lucene

• Wildcard queries

• Boolean queries

• Exact match queries

• Proximity queries

• Range queries

Relevance Scoring

Lucene computes:

• Relevance scores

using variants of:

 • TF-IDF

Norms in Lucene

Definition

Norms are:

• Precomputed normalization factors

stored during indexing.

Purpose of Norms

They:

• Speed up scoring

• Improve ranking efficiency

Applications of Lucene

• Search engines

• Enterprise search

• Digital libraries

• E-commerce search

• Log analysis systems

Features of Solr

Apache Solr Supports

• Faceted search

• PDF indexing

• HTML indexing

• Web APIs

• Distributed search
Advantages of Inverted Indexing

Advantage Description

Fast Retrieval Efficient searching

Scalability Handles huge datasets

Ranking Support TF-IDF scoring

Query Flexibility Supports many query types

Positional Search Supports phrase queries

Limitations

• Large storage requirements

• Complex index maintenance

• Expensive updates for dynamic collections

Comparison: Sequential Search vs Inverted Index

Feature Sequential Search Inverted Index

Speed Slow Fast

Scalability Poor Excellent

Query Processing Expensive Efficient

Suitable for Web Search No Yes

Real-World Applications

Search Engines

• Google

• Yahoo

Enterprise Search
 • Corporate document retrieval

E-Commerce

• Product search systems

Digital Libraries

• Academic article retrieval

Summary

Inverted indexing is the fundamental indexing technique used in modern Information

Retrieval systems. It maps terms to the documents containing them, enabling fast and
efficient search operations. Inverted indexes support ranking, phrase searching, and
proximity queries while significantly improving retrieval speed over sequential
searching. Technologies like Apache Lucene and Apache Solr use inverted indexing and
advanced ranking methods to power modern search engines and enterprise search
systems.
Lecture Notes: Evaluation Measures of Search Relevance in Information Retrieval
(IR)

27.6 Evaluation Measures of Search Relevance

Introduction

Evaluation measures are essential in Information Retrieval (IR) systems because they
help:

• Compare retrieval models

• Measure search effectiveness

• Improve search relevance

• Analyze ranking quality

Without evaluation techniques, it is difficult to determine whether one IR system

performs better than another.

Objectives of Evaluation Measures

Evaluation techniques measure:

1. Topical Relevance

2. User Relevance

Topical Relevance

Definition

Topical relevance measures how closely a retrieved document matches the topic of the
query.

Example

Query

Database indexing techniques

Documents discussing:

• Database indexing

• B+-Trees
 • Hash indexing

are considered topically relevant.

Challenges in Topical Relevance

Users often:

• Cannot formulate perfect queries

• Express vague information needs

• Use incomplete keywords

Thus, retrieving exactly relevant documents becomes difficult.

User Relevance

Definition

User relevance measures the usefulness or goodness of retrieved results according to

the user’s actual information need.

Factors Affecting User Relevance

• User perception

• Context

• Timeliness

• Environment

• Current task

• Personal preferences

Example

Two users searching:

Python

may expect different results:

• Programming language
 • Snake species

Ranking in Web Information Retrieval

Modern search engines:

• Do not classify documents simply as relevant or nonrelevant

• Instead provide ranked results

The most relevant documents appear at the top.

Importance of Ranking

Ranking helps users:

• Find useful information quickly

• Avoid scanning large result sets

Major Evaluation Measures

1. Recall

2. Precision

3. Average Precision

4. Recall/Precision Curve

5. F-Score

27.6.1 Recall and Precision

Binary Relevance Assumption

Documents are classified as:

• Relevant
or

• Nonrelevant
Important Terms

Term Meaning

TP True Positive

FP False Positive

FN False Negative

TN True Negative

Explanation of Terms

True Positive (TP)

Relevant documents correctly retrieved.

False Positive (FP)

Nonrelevant documents incorrectly retrieved.

False Negative (FN)

Relevant documents not retrieved.

True Negative (TN)

Nonrelevant documents correctly ignored.

Recall

Definition

Recall measures how many relevant documents were successfully retrieved.

Recall Formula
∣ 𝐻𝑖𝑡𝑠 ∣
𝑅𝑒𝑐𝑎𝑙𝑙 =
∣ 𝑅𝑒𝑙𝑒𝑣𝑎𝑛𝑡 ∣

Interpretation

High recall means:

• Most relevant documents are retrieved.

Example

Suppose:

• Relevant documents = 20

• Retrieved relevant documents = 15

Then:
15
𝑅𝑒𝑐𝑎𝑙𝑙 = = 0.75 = 75%
20

Precision

Definition

Precision measures how many retrieved documents are actually relevant.

Precision Formula
∣ 𝐻𝑖𝑡𝑠 ∣
𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 =
∣ 𝑅𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑑 ∣

Interpretation
High precision means:

• Few irrelevant documents are retrieved.

Example

Suppose:

• Retrieved documents = 25

• Relevant retrieved documents = 15

Then:
15
𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 = = 0.60 = 60%
25

Relationship Between Recall and Precision

Increasing recall:

• Often decreases precision

Increasing precision:

• Often decreases recall

Trade-Off

High Recall High Precision

More results retrieved Fewer but accurate results

May include irrelevant documents May miss relevant documents

Ranked Retrieval

Modern IR systems use ranked retrieval.

Documents are ordered according to relevance.

Ranked Retrieval Recall

At rank position i:
 ∣ 𝑆𝑖 ∣
𝑟(𝑖) =
∣ 𝐷𝑞 ∣

Where:

• 𝑆𝑖 = Relevant documents up to rank i

• 𝐷𝑞 = Total relevant documents

Ranked Retrieval Precision

At rank position i:
∣ 𝑆𝑖 ∣
𝑝(𝑖) =
𝑖

Example Table

Rank Relevant? Precision Recall

1 Yes 100% 10%

2 Yes 100% 20%

3 Yes 100% 30%

4 No 75% 30%
Observations

• Recall increases monotonically

• Precision fluctuates

27.6.2 Average Precision

Definition

Average Precision computes the average of precision values at positions where relevant
documents occur.

Formula
∑𝑝(𝑖)
𝑃𝑎𝑣𝑔 =
∣ 𝐷𝑞 ∣

Where:

• 𝑝(𝑖)= Precision at relevant document positions

• ∣ 𝐷𝑞 ∣= Number of relevant documents

Purpose

Provides:

• A single performance measure

• Easy comparison between retrieval algorithms

Example

Suppose precision values at relevant ranks are:

1.0, 1.0, 1.0, 0.57, 0.62, 0.60

Average Precision:

(1 + 1 + 1 + 0.57 + 0.62 + 0.60)/6

= 79.93%

Importance of Average Precision

Good IR systems:

• Achieve high precision at top-ranked results

27.6.3 Recall/Precision Curve

Definition

A Recall/Precision Curve graphically represents the relationship between:

• Recall

• Precision

Axes

Axis Represents

X-axis Recall

Y-axis Precision

Characteristics

The curve generally:

• Has a negative slope

• Shows inverse relationship

Interpretation

As recall increases:

• Precision often decreases

Usage

Used to:

• Compare retrieval systems

• Evaluate ranking quality

Example Behavior

High precision → Low recall

High recall → Lower precision

27.6.4 F-Score

Definition

F-score combines:

• Precision

• Recall

into a single metric.

Harmonic Mean Formula

2𝑝𝑟
𝐹=
𝑝+𝑟

Where:

• p = Precision

• r = Recall

Alternative Representation
1 1 1 1
= ( + )
𝐹 2 𝑝 𝑟

Why Harmonic Mean?

The harmonic mean:

• Penalizes low values

• Requires both precision and recall to be high

Example
Suppose:

• Precision = 80%

• Recall = 60%

Then:
2(0.8)(0.6)
𝐹= = 0.686 = 68.6%
0.8 + 0.6

Interpretation

High F-score indicates:

• Balanced precision and recall

Applications of F-Score

• Search engine evaluation

• Machine learning classification

• Recommendation systems

• Document retrieval evaluation

Comparison of Evaluation Metrics

Metric Purpose

Recall Measures completeness

Precision Measures exactness

Average Precision Measures ranking quality

Recall/Precision Curve Visual performance analysis

F-Score Combined performance measure

Importance of Evaluation Measures

Evaluation measures help:

 • Improve search algorithms

• Compare retrieval models

• Optimize ranking systems

• Enhance user satisfaction

Real-World Applications

Search Engines

• Google

• Microsoft Bing

Digital Libraries

• Academic article retrieval

E-Commerce

• Product search relevance

AI Systems

• Chatbots

• Recommendation engines

Advantages of Proper Evaluation

• Better user experience

• Improved retrieval accuracy

• Efficient ranking

• Performance benchmarking

Limitations

• User relevance is subjective

 • Difficult to capture user intent

• Precision-recall tradeoff exists

Summary

Evaluation measures are critical for assessing the effectiveness of Information Retrieval
systems. Metrics such as recall, precision, average precision, recall/precision curves,
and F-score provide quantitative ways to compare retrieval algorithms and ranking
systems. Modern search engines rely heavily on these measures to optimize relevance,
improve user satisfaction, and deliver accurate search results efficiently.
Lecture Notes: 27.7 Web Search and Analysis

1. Introduction to Web Search and Analysis

The rapid growth of the World Wide Web has created an enormous collection of digital
information. Search engines such as Google, Microsoft Bing, and Yahoo Yahoo! help
users locate relevant information by:

• Crawling Web pages

• Indexing documents

• Ranking search results

• Updating indexes continuously

Because millions of Web pages exist, sophisticated ranking and analysis methods are
required to provide relevant results.

2. Types of Search Engines

2.1 General Web Search Engines

These engines:

• Crawl the Web automatically

• Build large indexes

• Retrieve ranked search results

Examples

• Google

• Bing

• Yahoo!

Features

• Massive document collections

• Automatic indexing

• Link analysis

• Relevance ranking

2.2 Human-Powered Search Engines

These systems:

• Use manually curated directories

• Organize resources hierarchically

• Assist users in navigation

Characteristics

• Human-assisted indexing

• Categorized Web directories

• Topic-based organization

2.3 Vertical Search Engines

Vertical search engines focus on:

• A specific domain or topic

Examples

• Medical search engines

• Academic search systems

• E-commerce search systems

Advantages

• Higher precision

• Domain-specific indexing

• Specialized ranking

2.4 Metasearch Engines

Metasearch engines:

• Query multiple search engines simultaneously

• Aggregate results

Advantages

• Wider coverage

• Combined ranking results

 • Better information diversity

3. Digital Libraries

Definition

Digital libraries are collections of:

• Electronic resources

• Online catalogs

• Articles

• Books

• Multimedia documents

Examples

• IEEE Digital Library

• Google Scholar

• University library systems

Features of Digital Libraries

• Centralized access to resources

• Metadata catalogs

• Distributed repositories

• Online public access catalogs (OPACs)

4. Web Analysis (Web Mining)

Definition

Web analysis refers to:

The discovery and analysis of useful information from the Web.

It combines:

• Information Retrieval

• Data Mining
 • Machine Learning

• Natural Language Processing

• Statistics

5. Goals of Web Analysis

5.1 Finding Relevant Information

Challenges:

• Huge volume of Web pages

• Low precision

• Difficulty in measuring recall

Important Observation

Users usually care only about:

• Top few search results

5.2 Personalization of Information

Different users prefer:

• Different content

• Different presentation styles

Personalization Techniques

• Click-through monitoring

• User profiling

• Recommendation systems

• Dynamic service composition

Applications

• Personalized advertisements

• Customized search results

• Product recommendations
5.3 Finding Information of Social Value

Social networks generate valuable social information.

Examples

• Facebook

• Twitter

Social Capital

Refers to:

• Social trust

• Cooperation

• Relationships

• Community interactions

6. Categories of Web Analysis

Web analysis is classified into:

Category Description

Web Structure Analysis Studies hyperlink structure

Web Content Analysis Extracts knowledge from content

Web Usage Analysis Analyzes user access patterns

7. Web Structure Analysis

Definition

Studies:

• Hyperlinks

• Connectivity among pages

• Web graph structure

Hyperlinks
A hyperlink contains:

1. Destination page

2. Anchor text

Anchor Text

Describes the linked page.

Example:

“My favorite Web site”

Anchor texts act as:

• Implicit endorsements

Hubs and Authorities

Hub

A page linking to many authoritative pages.

Authority

A page pointed to by many hubs.

8. Link Analysis Algorithms

8.1 PageRank Algorithm

Developed by:

• Larry Page

• Sergey Brin

Basic Idea

A page is important if:

• Many important pages link to it.

Terminology
Symbol Meaning

P(A) PageRank of page A

C(X) Outgoing links from X

d Damping factor

Usually:

𝑑 = 0.85

PageRank Formula
𝑃(𝑇1 ) 𝑃(𝑇2 ) 𝑃(𝑇𝑛 )
𝑃(𝐴) = (1 − 𝑑) + 𝑑 ( + + ⋯+ )
𝐶(𝑇1 ) 𝐶(𝑇2 ) 𝐶(𝑇𝑛 )

Where:

• 𝑇1 , 𝑇2 , . . . , 𝑇𝑛 are pages linking to page A.

Characteristics

• Query-independent ranking

• Uses iterative computation

• Based on Markov model

8.2 HITS Algorithm

Developed by:

• Jon Kleinberg

Concepts

Good Hub

Points to many authorities.

Good Authority

Referenced by many hubs.

Steps in HITS

Step 1: Initialization

Set:

• Hub score = 1

• Authority score = 1

Step 2: Iterative Update

Authority score:

𝐴𝑢𝑡ℎ𝑜𝑟𝑖𝑡𝑦 = ∑𝐻𝑢𝑏 𝑆𝑐𝑜𝑟𝑒𝑠

Hub score:

𝐻𝑢𝑏 = ∑𝐴𝑢𝑡ℎ𝑜𝑟𝑖𝑡𝑦 𝑆𝑐𝑜𝑟𝑒𝑠

Step 3: Normalization

Normalize all scores.

9. Web Content Analysis

Definition

Extraction of useful information from:

• Text

• HTML pages

• XML documents

• Images

• Structured tables

10. Structured Data Extraction

Purpose

Extract meaningful structured information from Web pages.

Methods

1. Wrapper-Based Extraction

Programs extract data using:

• HTML patterns

• Structure recognition

2. Manual Extraction

Human-written extraction rules.

3. Wrapper Induction

Machine learning generates extraction rules.

4. Automatic Extraction

Automatically discovers page patterns.

11. Web Information Integration

Goal

Combine information from heterogeneous sources.

Approaches

1. Web Query Interface Integration

Access hidden information from:

• Deep Web

• Dynamic databases

2. Schema Matching

Combines multiple schemas into one global schema.

Example:

• Integrated healthcare records

12. Ontology-Based Information Integration

Ontology

Formal representation of:

• Concepts

• Relationships

• Knowledge structures

Types

Single Ontology Approach

One common ontology for all sources.

Example:

• UMLS

Multiple Ontology Approach

Each source maintains its own ontology.

Challenges:

• Conflicts

• Overlapping concepts

• Vocabulary mismatch

13. Concept Hierarchies

Purpose

Organize search results into:

• Categories

• Hierarchical groups

Benefits

• Easier navigation

• Better understanding

• Topic grouping
14. Noise Detection in Web Pages

Noise Examples

• Advertisements

• Navigation menus

• Pop-ups

Goal

Remove irrelevant sections before:

• Classification

• Clustering

• Indexing

15. Approaches to Web Content Analysis

15.1 Agent-Based Approach

Uses intelligent software agents.

Types

Intelligent Web Agents

Retrieve domain-specific information.

Information Filtering Agents

Categorize Web documents.

Personalized Agents

Customize results for users.

15.2 Database-Based Approach

Treats Web data as:

• Structured databases

• Semistructured repositories
Goals

• Better querying

• Schema discovery

• Web document warehousing

16. Object Exchange Model (OEM)

Purpose

Represents semistructured data.

Structure

• Graph-based model

• Nodes = objects

• Edges = labels

17. Web Usage Analysis

Definition

Study of user interaction patterns on Web sites.

18. Phases of Web Usage Analysis

Phase Description

Preprocessing Data cleaning and preparation

Pattern Discovery Extracting useful patterns

Pattern Analysis Interpreting results

19. Preprocessing in Web Usage Analysis

Types

Usage Preprocessing

Analyzes:
 • Clickstreams

• User sessions

• IP addresses

Content Preprocessing

Performs:

• Classification

• Clustering

Structure Preprocessing

Analyzes:

• Hyperlinks

• Navigation paths

20. Pattern Discovery Techniques

20.1 Statistical Analysis

Measures:

• Frequency

• Mean

• Median

• Viewing time

20.2 Association Rules

Discovers:

• Pages frequently visited together

Example:

Users visiting electronics pages may also visit sports pages.

20.3 Clustering

Types
User Clustering

Groups similar users.

Page Clustering

Groups similar pages.

20.4 Classification

Builds user profiles.

Example:

• Age group prediction

• Shopping behavior prediction

20.5 Sequential Patterns

Finds:

• Order of page visits

• Purchase sequences

Example:

After buying a computer, users often buy printers.

20.6 Dependency Modeling

Models dependencies among:

• User actions

• Navigation stages

• Shopping processes

21. Pattern Analysis

Techniques

• SQL querying

• OLAP operations
 • Visualization

• Graph analysis

22. Practical Applications of Web Analysis

22.1 Web Analytics

Goal

Improve:

• Website performance

• User engagement

• Marketing effectiveness

22.2 Web Spamming

Definition

Manipulating search rankings unfairly.

Examples

• Keyword stuffing

• Fake backlinks

Detection

Web mining techniques identify spam pages.

22.3 Web Security

Applications

• Intrusion detection

• Denial-of-service attack detection

• Log analysis

22.4 Web Crawlers

Definition
Programs that:

• Visit Web pages

• Download content

• Build search indexes

Applications

Legitimate Uses

• Search engine indexing

• Website validation

• Broken-link checking

Malicious Uses

• Email harvesting

• Spam generation

23. Advantages of Web Analysis

• Improves search relevance

• Enables personalization

• Supports recommendation systems

• Helps business intelligence

• Detects security threats

• Enhances digital marketing

24. Limitations of Web Analysis

• Privacy concerns

• Huge computational cost

• Dynamic Web content

• Spam and fake information

• Data integration complexity

25. Summary

• Web search engines crawl and index Web pages.

• Web analysis extracts useful knowledge from the Web.

• Major categories:

o Structure analysis

o Content analysis

o Usage analysis

• PageRank and HITS are important ranking algorithms.

• Web usage analysis helps personalization and business intelligence.

• Web analytics, security, and crawling are major practical applications.

Lecture Notes: 27.8 Trends in Information Retrieval

Introduction to Modern Trends in Information Retrieval (IR)

Information Retrieval (IR) has evolved significantly due to the rapid growth of the Web,
social media, artificial intelligence, and big data technologies. Modern IR systems focus
not only on retrieving documents but also on:

• Personalized search

• Socially aware information access

• Conversational interaction

• Intelligent question answering

• Topic discovery from large datasets

• Multi-dimensional navigation of information

The important recent trends in IR include:

1. Faceted Search

2. Social Search

3. Conversational Information Access

4. Probabilistic Topic Modeling

5. Question Answering Systems

27.8.1 Faceted Search

Definition

Faceted search is a search and navigation technique that allows users to filter
information using multiple categories called facets.

It enables users to explore information in multiple dimensions instead of following a

fixed hierarchy.

Features of Faceted Search

• Supports multi-dimensional classification

• Allows dynamic filtering

• Improves navigation experience

 • Commonly used in e-commerce websites

• Helps users narrow down search results quickly

What is a Facet?

A facet is a property or characteristic used to classify objects.

Examples of Facets

For an art collection:

Facet Example

Artist Picasso

Era Renaissance

Type Painting

Country India

Media Oil painting

Characteristics of Faceted Classification

• Facets are mutually exclusive

• Facets are exhaustive

• Objects can belong to multiple categories simultaneously

Applications

• Online shopping websites

• Digital libraries

• Travel booking systems

• Product catalogs

Examples

Popular websites using faceted search:

 • Amazon

• Expedia

Advantages

• Faster navigation

• Better user experience

• Improved search refinement

• Supports complex information spaces

27.8.2 Social Search

Definition

Social search refers to information retrieval that incorporates social interactions,

collaboration, and collective intelligence.

It uses social networks and user cooperation to improve search quality.

Key Concepts

Traditional search:

• Single user searches independently

Social search:

• Multiple users collaborate

• Uses recommendations and opinions

• Integrates social media interactions

Types of Social Search Activities

1. Collaborative Search

Multiple users jointly perform search tasks.

2. Expertise Networks

Users consult experts within social networks.

3. Collective Intelligence

Search systems utilize crowd knowledge.

4. Social Data Mining

Mining likes, comments, clicks, and shares.

Social Capital

Social capital refers to:

• Networks

• Trust

• Cooperation

• Shared knowledge

Examples:

• Online communities

• Discussion forums

• Social media platforms

Applications

• Product reviews

• Collaborative research

• Community question answering

• Social recommendations

Examples

Popular social platforms:

• Facebook

• Twitter

Advantages
 • Better decision making

• Improved recommendations

• Shared expertise

• Faster information discovery

27.8.3 Conversational Information Access

Definition

Conversational Information Access is an interactive information retrieval approach

where intelligent agents assist users during conversations.

The system understands conversations and provides relevant information dynamically.

Characteristics

• Human-like interaction

• Real-time assistance

• Intent understanding

• Context-aware retrieval

Technologies Used

1. Speaker Identification

Recognizes who is speaking.

2. Automatic Speech Recognition (ASR)

Converts speech into text.

3. Keyword Spotting

Detects important keywords.

4. Semantic Understanding

Understands meaning of conversation.

5. Discourse Analysis

Analyzes flow of conversation.

Applications

• Smart assistants

• Voice search systems

• Customer support bots

• Wearable devices

Advantages

• Natural interaction

• Faster access to information

• Goal-oriented retrieval

• Improved user engagement

27.8.4 Probabilistic Topic Modeling

Definition

Probabilistic Topic Modeling is a machine learning technique used to automatically

discover hidden topics in large document collections.

It organizes documents based on themes and topics.

Motivation

Due to huge growth of digital content:

• Organizing documents manually is difficult

• Automatic thematic organization is necessary

Basic Idea

Assumptions

1. Each document contains multiple topics

2. Each topic contains a set of words

 3. Different topics appear in different proportions

Example

A document about Barack Obama may contain topics such as:

• Politics

• Government

• Presidents

• Democrats

• American history

Topic Modeling Process

Step 1: Vocabulary Extraction

Collect important words from documents.

Step 2: Topic Discovery

Discover hidden themes automatically.

Step 3: Probability Assignment

Assign probabilities of topics to documents.

Properties

• Unsupervised learning

• No manual labeling needed

 • Works on large datasets

Latent Dirichlet Allocation (LDA)

The most popular topic modeling algorithm is:

Latent Dirichlet Allocation

LDA Assumptions

• Documents are mixtures of topics

• Topics are distributions over words

Bayesian Inference Techniques

LDA uses methods such as:

• Gibbs Sampling

• Expectation Maximization

Applications

• News categorization

• Recommendation systems

• Document summarization

• Scientific literature analysis

• Social media analysis

Advantages

• Automatic topic discovery

• Scalable to big data

• Improves document organization

27.8.5 Question Answering Systems

Definition
Question Answering (QA) systems are intelligent systems that answer natural language
questions directly.

Unlike traditional search engines, QA systems provide exact answers instead of

document lists.

Importance

QA systems are widely used in:

• Virtual assistants

• Customer support

• Educational systems

• Search engines

Examples

Popular QA assistants include:

• Apple Siri

• Microsoft Cortana

• IBM Watson

Types of Questions

1. Factoid Questions

Require short factual answers.

Examples

• Who is the President of India?

• Where was Elvis Presley born?

2. List Questions

Require multiple answers.

Example

• Name three plays written by Shakespeare.

3. Definition Questions

Ask for meanings or explanations.

Example

• What is an inert gas?

4. Opinion Questions

Seek viewpoints or sentiments.

Example

• What is public opinion about climate change?

Architecture of QA Systems

A QA system generally contains multiple stages.

1. Question Analysis

Analyzes and understands the question.

Techniques Used

a) Shallow Semantic Parsing

Identifies:

• WHO

• WHAT

• WHERE

• WHEN

• WHY

• HOW

b) Focus Detection

Finds important keywords in the question.

Example:
 • “Which book of Shakespeare…”

Focus: “book of Shakespeare”

c) Answer Type Classification

Determines expected answer category.

Examples:

• Person

• Place

• Date

• Book

d) Named Entity Recognition (NER)

Identifies entities such as:

• Person names

• Locations

• Organizations

e) Co-reference Resolution

Determines references in text.

Example:
“John said he will come.”

“He” refers to “John”.

2. Query Generation

Transforms question into multiple search queries.

Example

Question:

• “Which Shakespeare book is a tragic love story?”

Generated Queries:

• Shakespeare love story

• tragic romance Shakespeare

 • Shakespeare tragedy novel

3. Search Stage

Queries are sent to:

• Online search engines

• Offline indexes

Examples:

• Lucene

• Indri

4. Candidate Answer Generation

Potential answers are extracted from retrieved documents.

Methods:

• Surface pattern matching

• Structural matching

5. Answer Scoring

Candidate answers are ranked using confidence scores.

Higher score → Better answer

Advantages of QA Systems

• Direct answers

• Natural language interaction

• Faster information access

• Improved user satisfaction

Applications of Modern IR Trends

Trend Application

Faceted Search E-commerce

Social Search Social media recommendations

Conversational Access Voice assistants

Topic Modeling News categorization

QA Systems Chatbots and virtual assistants

Summary

Modern Information Retrieval systems are becoming:

• Intelligent

• Personalized

• Conversational

• Socially aware

• Context-sensitive

Emerging technologies such as:

• Topic modeling

• Question answering

• Social search

• Conversational agents

are transforming traditional keyword-based search into intelligent knowledge discovery

systems.