Assignment 2 : Simple Search Engine using Hadoop MapReduce

Course: Big Data - IU S25
Author: Firas Jolha
Deadline: April 15, 23:59

Repository template

• https://github.com/firas-jolha/big-data-assignment2-2025

Moodle submission link

• https://moodle.innopolis.university/mod/assign/view.php?id=127260

Dataset

• A large corpus of plain text documents (e.g., news articles, Wikipedia pages, Stack Overflow posts).
  • https://www.kaggle.com/datasets/jjinho/wikipedia-20230701?select=a.parquet
  • You can bring similar plain text documents if you have
    • The naming format of the text documents should be <doc_id>_<doc_title>.txt.

Agenda

Prerequisites

• Docker and docker compose
• RAM: at least 10 GB.

Description

In this assignment, you need to implement a simple search engine with Hadoop MapReduce, Cassandra and Spark RDD. It should support the indexing, ranking and retrieval of plain text documents. The engine should retrieve documents relevant to a query given as an input text. The goal is to practice on using MapReduce, Cassandra and Spark for building such naive search engine and the complexity of the search is not the main performance gaug

You can introduce additional optimizations, but you have to feature them in the report and describe how they improve your software. Remember that your optimizations should not compromise the baseline search quality.

Search engine

The goal is to implement a simple search engine based on a naive text indexer and a document retriever. These components are often found in search engines. Conceptually, search engines were the first who tackled the problem of Big Data with the constraint of low latency response. Imagine a typical search engine that has millions of documents in its index. Every second it receives hundreds to thousands of queries and requires to produce a list of the most relevant documents at sub-millisecond speed. In addition, it also needs to index new documents regularly. The problem of finding relevant information is one of the key problems in the field of Information Retrieval, which can be subdivided into two related tasks:

• Document indexing
• Query answering (Document retrieval)

While the second task is more related to real-time low latency processing, the indexing step can be done offline as batch processing. Hadoop MapReduce here will be used to do batch processing. It will create the index of a text corpus and store it in (distributed) Cassandra database (cluster). For the sake of this assignment, you are going to do a naive implementation of both tasks using MapReduce paradigm and Spark RDDs. Cassandra cluster here contains one node but you can scale it out if you have more resources. The diagram for such a search engine is shown on the figure below.

The most common task in Information Retrieval (IR) is textual information retrieval. Whenever a user submits a query, the ranking engine should compute the set of the most relevant documents in its collection. To complete this task, the developer should determine how the documents and queries are represented, and define the measure of relevance of a query for a particular document.

TF/IDF

One of the most simple IR models is the TF/IDF model. It states that we need to count the occurrence of the search term in a given document.

Let’s take a small corpus composed of three documents as shown below.

d1 = cats and dogs are pets.
d2 = cats and dogs are pet animals though I prefer dogs. Dogs obey our commands, can be trained easily and play with us all the time.
d3 = Horses are also pets.

Let’s assume that the user’s query is “dogs” where the TF values are:

tf("dogs", d1) = 1
tf("dogs", d2) = 3
tf("dogs", d3) = 0

We compute IDF for the entire corpus and not just a single document. It measures the importance of a term (“dogs” in our case) across the entire corpus. It’s the logarithm of the total number of documents in the corpus divided by the number of documents containing the term. So, the IDF score for our example is log(3/2) as “dogs” occur in 2 of the 3 documents.

Calculating TF-IDF simply boils down to multiplying the two values TF and IDF. So, the results show that document (d2) will be retrieved.

idf("dogs") = log(total docs N/number of docs containing the word "dogs") = log(3/2) = 0.176

Now we can calculate the tf-idf for each query term per document as follows.

tf-idf("dogs", d1) = 1 * 0.176 = 0.176
tf-idf("dogs", d2) = 3 * 0.176 = 0.528
tf-idf("dogs", d3) = 0 * 0.176 = 0

There is a small problem however with our TF-IDF calculation. We haven’t considered the length of our document. It matters how long a sentence is and we cannot ignore that. For example, though “dogs” occurs 3 times in the second document (d2), there are 25 words in it. But the first document(d1) only has 5 words. So let’s normalize our TF-IDF by simply dividing it with the document length.

tf-idf("dogs", d1) = (1 * 0.176) / 5 = 0.0352
tf-idf("dogs", d2) = (3 * 0.176) / 25 = 0.0212
tf-idf("dogs", d3) = (0 * 0.176) / 4 = 0

Suddenly, our retrieval result now returns document (d1) instead of document (d2) as tf-idf("dogs", d1) > tf-idf("dogs", d2). We can make it more sophisticated by including something called saturation.

Saturation is to penalize words that occur more in documents or words should get lesser weightage or value as they occur more and more in a document. Let’s consider the second document, “Cats and dogs are pet animals though I prefer dogs. Dogs obey our commands, can be trained easily, and play with us all the time”. What if the document keeps repeating the term, “dogs” over and over again? As the term frequency increases, we will give lesser and lesser weightage to terms as shown in the plot from the paper on BM25.

Best Match 25 (BM25)

If we incorporate saturation and document length into TF-IDF, we will arrive at the BM algorithms. More specifically, we are interested in the most popular BM25 which incorporates saturation function and document length using this scary-looking formula:

Where

• $q$: the user’s query
• $t$: a term $t$ in the user’s query
• $N$: number of documents in the corpus
• $df(t)$: the document frequency or number of documents containing the term $t$.
• $k_1, b$: model’s hyperparameters (e.g. $k_1=1, b = 0.75$)
• $tf(t, d)$: the term $t$ frequency in the document $d$.
• $dl(d)$: the length of the document $d$.
• $dl_{avg}$: average document length.

To calculate BM25, we will have to include the average length of the document which is fairly easy for our toy corpus, which is $(5 + 25 + 4) / 3 = 11.33$. $k_1$ and $b$ are the hyperparameters chosen by us. But typically k_1 is 1 or 2 and b is 0.75. Let $k_1$=1 and $b=0.75$ then $dl_{avg} = (5+25+4)/3=11.3$. We plug in the formula for BM25 and we get the following values.

BM25("dogs", d1) = 0.7818
BM25("dogs", d2) = 0.3093
BM25("dogs", d3) = 0

That’s it! We have just calculated the BM25 for the term “dogs” on our toy corpus of three sentences. Now in this assignment, you need to implement the BM25 model.

Data collection and preparation

<doc_id>    <doc_title>    <doc_text>

# ./app/prepare_data.py
from pathvalidate import sanitize_filename
from tqdm import tqdm
from pyspark.sql import SparkSession


spark = SparkSession.builder \
    .appName('data preparation') \
    .master("local") \
    .config("spark.sql.parquet.enableVectorizedReader", "true") \
    .getOrCreate()


df = spark.read.parquet("/a.parquet")
n = 1000
df = df.select(['id', 'title', 'text']).sample(fraction=100 * n / df.count(), seed=0).limit(n)


def create_doc(row):
    filename = "data/" + sanitize_filename(str(row['id']) + "_" + row['title']).replace(" ", "_") + ".txt"
    with open(filename, "w") as f:
        f.write(row['text'])


df.foreach(create_doc)


# df.write.csv("/index/data", sep = "\t")

[50 points] Indexer tasks

These tasks are related to building a text indexer.

[50 points] Ranker tasks

These tasks are related to building a Ranker.

[Extra 15 points] Vector search

Report structure

Instructions

In this assignment, you need to submit all required files for running your search engine to your repository. In Moodle, you need to submit the link to the repository. You must follow the repository template shared with you. You can add more files or remove some files but check below to see which files your repository should minimally have. You also need to submit the report report.pdf. In summary, you need to submit at least the following files in the repository:

• ./app/mapreduce/mapper1.py
  • mapper script for mapreduce pipeline
• ./app/mapreduce/reducer1.py
  • reducer script for mapreduce pipeline

  You should have at least one MapReduce pipeline but you may have more than one pipeline then submit all mapreduce script files in the folder ./app/mapreduce.

• ./app/index.sh
  • creating vocabulary and index and storing them in Cassandra.
• ./app/app.sh
  • Starting the services
  • Running the indexer
  • Running the ranker for some queries
• report.pdf
  • Your report
• requirements.txt
  • Python dependencies
  • This does not determine which package manager you use but the requirements should be kept in this file
• search.sh
  • For running the search engine on a specific query
• start-services.sh
  • For starting the services of Hadoop

Plagiarism policy

References

• https://www.ai-bites.net/tf-idf-and-bm25-for-rag-a-complete-guide/
• https://en.wikipedia.org/wiki/Okapi_BM25