MODULE 5

PARALLEL AND DISTRIBUTED IR

5.1 INTRODUCTION
The volume of electronic text available online today is staggering. As document collections
grow larger, they become more expensive to manage with an information retrieval system. To
support the demanding requirements of modern search environments, we must turn to
alternative architectures and algorithms.
Parallel computing is the simultaneous application of multiple processors to solve a single
problem.
Processors can be combined in a variety of ways to form parallel architectures.
Flynn’s Taxonomy:
▪ SISD single instruction stream, single data stream
▪ SIMD single instruction stream, multiple data stream
▪ MISD multiple instruction stream, single data stream
▪ MIMD multiple instruction stream, multiple data stream.
The SISD class includes the traditional von Neumann computer running sequential programs,
E.g., uniprocessor personal computers.
SIMD computers consist of N processors operating on N data streams, and are often
computers with: Many relatively simple processors running the same program. A
communication network between the processors. A control unit that supervises the
synchronous operation of the processors.
The processors may use shared memory, or each processor may have its own local memory.
Sequential programs require significant modification to make effective use of a SIMD
architecture.
MISD computers use N processors operating on a single data stream in shared memory. MISD
architectures are relatively rare.
MIMD is the most general and most popular class of parallel architectures. A MIMD computer
contains N processors, N instruction streams, and N data streams. In this architecture, each
processor has its own control unit, processing unit, and local memory.
The processors can work on separate, unrelated tasks, or they can cooperate to solve a single
task. Tightly coupled: MIMD systems with a high degree of processor interaction. Loosely
coupled: systems with a low degree of processor interaction. MIMD can also characterize
distributed computing architectures.
In distributed computing, multiple computers connected by a local or wide area network
cooperate to solve a single problem.
5.2 PERFORMANCE MEASURES:
When we employ parallel computing, we usually want to know what the performance
improvement is. A few metrics are available to measure the performance of a parallel
algorithm.
One such measure is the speedup, defined as:

Running time of best available sequential algorithm

S=
Running time of parallel algorithm

▪ Ideally, when running a parallel algorithm on N processors, we would obtain perfect

speedup, or S = N
▪ In practice, perfect speedup is unattainable either because:
▪ the problem cannot be decomposed into N equal independent subtasks
▪ the parallel architecture imposes control and communication overheads, or
▪ the problem contains an inherently sequential component
▪ Amdahl’s Law

1 1
S 
f + (1 − f ) / N f
▪ where f is the fraction of the problem that must be computed sequentially
▪ Another measure of parallel performance is efficiency, given by:

S
 =
N
where S is the speedup and N is the number of processors
▪ Ideal efficiency occurs when φ = 1 and no processor is ever idle or performs
unnecessary work
▪ As with perfect speedup, ideal efficiency is unattainable in practice.
▪ Ultimately, the performance improvement of a parallel program over a sequential
program is viewed as the combination of:
▪ the reduction in real time required to complete the task.
▪ the additional monetary cost associated with the parallel hardware required
to run the parallel program.
▪ This gives the best overall picture of parallel program performance and cost
effectiveness.
5.3 PARALLEL IR
5.3.1 Introduction
We can approach the development of parallel IR algorithms from two different directions. One
possibility is to develop new retrieval strategies that directly lend themselves to parallel
implementation. For example, a text search procedure can be built on top of a neural network.
The other possibility is to adapt existing, well studied IR algorithms to parallel processing.
The modifications required to adapt an existing algorithm depend on the target parallel
platform. We investigate techniques for applying a few retrieval algorithms to the MIMD and
SIMD architectures. Parallel computing is the simultaneous application of multiple processors
to solve a single problem. The overall time required to solve the problem can be reduced to
the time required by the longest running part.

5.3.2 MIMD ARCHITECTURE IN PARALLEL IR

MIMD architectures offer a great deal of flexibility in how parallelism is defined and exploited
to solve a problem.
▪ The simplest way in which a retrieval system can exploit a MIMD computer is using
multitasking.
▪ Each of the processors in the parallel computer runs a separate, independent search
service.
▪ The submission of user queries to the search services is managed by a broker.
▪ The broker accepts search requests and distributes the requests among the available
search services.
▪ Parallel multitasking on a MIMD machine

Care must be taken to properly balance the hardware resources on the system. Search
processes running on the different processors can perform I/O and compete for disk access.
A bottleneck at the disk will be disastrous for performance and could eliminate the throughput
gains. In addition to adding more disks to the computer, the index data must be distributed
over the disks. At one extreme, replicating the entire index on each disk eliminates disk
contention at the cost of increased storage requirements and update complexity.
Alternatively, heavily accessed data can be replicated, and less frequently accessed data can
be distributed. Yet another approach is to install a disk array and let the operating system
handle partitioning the index. As in sequential systems, caching is another important
technique that improves performance.
To improve query response time, the computation required to evaluate a single query must
be:
▪ partitioned into subtasks.
▪ distributed among multiple processors.
5.3.3 INVERTED FILES IN PARALLEL IR
There are two possible methods for partitioning the data:
Document partitioning: the N documents are distributed across the P processors; each
parallel process evaluates the query on the subcollection of N/P documents assigned to it.
Term partitioning: the t indexing items are distributed across the P processors; the evaluation
process for each document is spread over multiple processors.

LOGICAL DOCUMENT PARTITIONING

Data Partitioning: The data partitioning is done logically using essentially the same basic
underlying inverted file index as in the original sequential algorithm.
The inverted file is extended to give each parallel process direct access to that portion of the
index related to the processor’s subcollection of documents.

Inverted List
Term i
Dictionary

P1

P2
item i
P3

P4

Query Evaluation: The broker initiates P parallel processes to evaluate the query. Each process
executes the same document scoring algorithm on its document subcollection. The search
processes record document scores in a single shared array of document score accumulators.
The broker produces the final ranked list of documents.
Inverted File Construction: The indexer partitions the documents among the processors. Each
indexing process generates a batch of inverted lists, sorted by indexing item. A merge step is
performed to create the final inverted file.
PHYSICAL DOCUMENT PARTITIONING
Data Partitioning: The documents are physically partitioned into separate subcollections, one
for each parallel processor. Each subcollection has its own inverted file.
Query Evaluation: The broker distributes the query to all of the parallel search processes. Each
parallel search process evaluates the query on its portion of the document collection,
producing an intermediate hit-list. The broker collects the intermediate hit-lists from all of the
parallel search processes and merges them into a final hit-list.
Inverted File Construction: Each processor creates, in parallel, its own complete index
corresponding to its document partition. A merge step is performed to accumulate the global
statistics for all of the partitions and distribute them to each of the partition dictionaries.

TERM PARTITIONING
Data Partitioning: Inverted lists are spread across the processors.
Query Evaluation: Query is decomposed into indexing items and each indexing item is sent to
the processor that holds the corresponding inverted list. The processors create hit-lists with
partial document scores and return them to the broker. The broker combines the hit-lists.
Inverted File Construction: Inverted file is created using the parallel construction technique
described for logical document partitioning.

5.3.4 SIMD ARCHITECTURE IN PARALLEL IR

Introduction: SIMD architectures lend themselves to a more restricted domain of problems than
MIMD architectures. SIMD computers are less common than MIMD computers. the best known
example of the SIMD architecture in the Thinking Machines CM-2, which has been used to
support both signature file- and inverted file-based information retrieval algorithms. The
processing elements execute local and non-local parallel instructions.
A local parallel instruction causes each processing element to perform the same operation on
data stored.
A non-local parallel instruction involves communication between the processing elements and
includes operations such as summing the components of a vector.
The CM-2 uses a separate front-end host to provide an interface to the back-end parallel
processing elements. The front-end controls the loading and unloading of data and executes
serial program instructions, such as condition and iteration statements. Parallel macro
instructions are sent from the front-end to a back-end micro controller, which controls the
simultaneous execution of the instruction on a set of back-end processing elements. The CM-
2 provides a layer of abstraction over the back-end processors, called virtual processors.
The most used application of SIMD Architectures is to support Signature Files and Inverted
Files
SIGNATURE FILES IN SIMD
First, the search system constructs a signature for the query terms.
Next, the system compares the query signature with the signature of every document in the
collection and marks documents with matching signatures.
The system scans the full text of potentially relevant documents to eliminate false drops, ranks
the matching documents, and returns the hit-list to the user.
If the probability of false drops is acceptably low, the full text scan may be eliminated.

Also, if the system is processing Boolean queries, it may need to generate more than one
signature for the query and combine the intermediate results of each signature according to
the operators used in the query. This procedure must be enhanced under the following
condition.
If the number of words in a document d exceeds the number of words W that can be inserted
into a document signature, then the document must be segmented into d/W segments and
represented by d/W signatures.
In this case, the probe_doc routine is applied to all signatures for a document and an OR
function is applied to obtain the final result for the document.
If the false drop probability warrants scanning the full text of the documents, only those
segments with matching signatures need be scanned. As soon as a qualifying segment is
found, the entire document is marked as a match for the query.
A general Boolean retrieval system can be implemented on top of [Link] with the
recursive procedure as shown in Figure.

• Here bquery_t is a recursive data type that contains two arguments and an operator.

• If the operator is NOT or WORD, then the second argument in the bquery_t is empty.

• The final return value is stored in a parallel Boolean variable, which indicates for each
document whether or not that document satisfies the Boolean query.

• Again, if the probability of false drops associated with the signature scheme is
acceptably low, the set of matching documents may be returned immediately.

• Otherwise, the system must perform further processing on the text of each matching
document to eliminate false drops.
If weights are available for the query terms, it is possible to build a ranking retrieval system
on top of the parallel signature file search process.

• Query term weights could be supplied by the end-user when the query is created, or
they could be assigned by the system

• The algorithm in Figure shows how to use [Link] to build a ranking system.

• In rank search, the wquery_t data type contains an array of query terms and an array
of weights associated with those terms.

• First, all documents that contain the current term are identified with [Link].

• Next, the score for each of those documents is updated by adding the weight
associated with the current query term

• After all query terms have been processed, the parallel variable Doc_score contains
the rank scores for all of the documents.
 • The final step in the processing of a weighted query is to rank the scored documents
by sorting and returning the top k hits.

• This can be accomplished in a number of ways. One possibility is to use the global
ranking routine provided by the CM-2, which takes a parallel variable and returns 0 for
the largest value, 1 for the next largest value

• If the number of hits returned is much less than the number of documents in the
collection (k << N), the global ranking function performs more work than necessary.

• Here the main approach is to process the collection in batches. A batch consists of as
many document signatures as will fit in main memory at one time. Each batch is read
into memory and, scored using one of the above algorithms. After all batches have
been processed, the array of document scores is ranked and the final hit-list is
generated.

An alternative to processing in batches is to use a parallel bit-sliced signature file.

Figure shows a matrix representation of the signatures for a small document collection (N =
5). In a traditional signature file, each row of the matrix, or document signature, is stored
contiguously. In a bit-sliced signature file, each column of the matrix, or bit-slice, is stored
contiguously.
A bit-slice is a vertical slice through the matrix, such that bit-slice i contains the i-th bit from
every document signature. When using a bit-sliced signature file, each virtual processor is still
responsible for scoring a single document. A bit-slice, therefore, is distributed across the virtual
processors with one bit at each processor. To search the bit-sliced signature file, we must make
a few modifications to our basic query processing procedures.
Although this technique addresses the issue of query response time on large document
collections, it defeats one of the often claimed advantages of the signature file organization,
that is indexing new documents is straightforward.
In a traditional signature file organization, new document signatures may simply be appended
to the signature file. With a bit-sliced signature file, the signature file must be inverted,
resulting in update costs similar to that of an inverted file.

INVERTED INDEX IN SIMD (Parallel Inverted File Using posting)

Inverted indexes are somewhat awkward to implement on SIMD machines. Nevertheless,
Stanfill has proposed two adaptations of inverted indexes for the CM-2.
In its simplest form, an inverted list contains a posting for each document in which a given
term appears.
• A posting is a tuple of the form ( ki, dj), where ki is a term identifier and dj is a
document identifier
• Depending on the retrieval model, postings may additionally contain weights or
positional information.
• If positional information is stored, then a posting is created for each occurrence of ki
in dj
• The first parallel inverted index for the CM-2 used the two standard structures:
a postings table and an index
 • The postings table contains the document identifiers from the postings.
• The index maps terms to their corresponding entries in the postings table
At search time these data structures are used to rank documents as follows
• First, the retrieval system loads the postings table onto the back-end
processors
• For each query term, an index lookup returns the range of postings table
entries that must be processed.
• For each row of this range, the processors that contain entries for the current
term are activated.
• Then, the associated document identifiers are used to update the scores of the
corresponding documents.
• Document scores are built up in accumulators, which are allocated in a parallel
array similar

PARTITIONED AND SKEWED POSTING

It is expensive to send posting weights to accumulators on different processors. To address
this problem, Stanfill proposed the partitioned postings file.
The partitioned postings file: This structure stores the postings and accumulator for a given
document on the same processor. This proposal eliminates the communication required in
the previous algorithm.
The Figure (a) below shows how the postings can be loaded into a table for two processors.
In this Figure, documents 0 and 1 were assigned to processor 0 and document 2 was
assigned to processor 1.

Notice that in figure ( b) the postings for the term this are skewed and no longer span consecutive
rows. To handle this situation, we apply the second trick of the partitioned postings file:

– segment the postings such that every term in segment i is lexicographically

less than or equal to every term in segment i + 1
5. 4 DISTRIBUTED IR
Introduction
A distributed computing system can be viewed as a MIMD parallel processor with relatively
slow inter-processor communication channel and the freedom to employ a heterogeneous
collection of processors in the system.
Distributed Model is very similar to the MIMD parallel processing model. The main difference
here is that subtasks run on different computers and the communication between the
subtasks is performed using network protocol such as TCP/IP.

Collection Partitioning
The procedure used to adding documents to search servers in a distributed IR system depends
a number of factors. Consider whether or not the system is centrally administered.
When the distribute system is centrally administered, more options are available.
 • The first option is simple replication of the collection across all of the search servers.
• The second option is random distribution of the documents.
• The final option is explicit semantic partitioning of the documents.

Source selection
Source selection is the process of determining which of the distributed document collections
are most likely to contain relevant documents for the current query, and therefore should
receive the query for processing.
The basic technique is to treat each collection as if it were a single large document, index the
collections, and evaluate the query against the collections to produce a ranked listing of
collections.

Query Processing
In a distributed IR system, it is important to determine which resources to allocate to process
a given query. The pool of available resources comprises components having one of the
following roles: Coordinator, cache, or query processor.
• A coordinator makes decisions on how to route the queries to different parts of the
system.
• The query processors hold index or document information.
• Cache servers can hold results for the most frequent or popular queries. They can
reduce query latency and load servers.
We classify a distributed query processing system according to four attributes:
• Number of components
• Connectivity
• Distinction of roles
• Interaction
The number of components determines the amount of resources available for processing
queries. The choices on the allocation of components change as different choices lead to
different performance values. In fact, minimizing the amount of resources per query is in
general an important goal