On the Allocation of Documents in Multiprocessor Information Retrieval Systems

Ophir Frieder, Hava T. SiegelmannSIGIR 1991 · DOI

TL;DR

This paper tackles the challenge of efficiently distributing documents across multiple processors in information retrieval systems to minimize search times. They introduce the Multiprocessor Document Allocation Problem (MDAP) and propose a Genetic Algorithm (GA) to find near-optimal document placements, demonstrating its effectiveness compared to pseudo-optimal solutions.

What Problem Does This Paper Address?

Modern information retrieval systems deal with massive datasets, requiring significant computational power for users to find relevant documents quickly. To meet these demands, researchers have turned to multiprocessor systems. However, in distributed memory architectures (where each processor has its own memory), the way documents are organized and placed across these processors critically impacts overall search performance. Poor placement can lead to excessive communication between processors, negating the benefits of parallelism. This paper addresses this challenge by formalizing the "Multiprocessor Document Allocation Problem" (MDAP) and developing a heuristic algorithm to solve it. MDAP aims to distribute documents evenly across processors while minimizing the "diameter" of clusters of related documents, which directly relates to communication costs.

Methods

The authors first formally define the Multiprocessor Document Allocation Problem (MDAP) and prove it is NP-Complete, meaning finding a guaranteed optimal solution is computationally infeasible for large problems. To overcome this, they propose a Genetic Algorithm (GA).

The GA operates on a population of potential document allocations, represented as permutations. It iteratively refines these allocations through several phases:

  • Initialization: Creates an initial population of random document permutations.
  • Reproduction: Selects "fitter" allocations (those with lower cluster diameters) to survive and reproduce, using a biased roulette wheel mechanism.
  • Crossover: Combines parts of two parent allocations to create new offspring allocations, mimicking biological reproduction.
  • Mutation: Introduces random changes to allocations to prevent the algorithm from getting stuck in local optima.

The "fitness" of an allocation is determined by a cost function that measures the sum of cluster diameters, aiming to minimize this sum.

Datasets

The paper describes experiments conducted using a simulated 64-document database. The document distribution into clusters was varied, including:

  • An even distribution where each cluster had an equal number of documents.
  • A non-uniform distribution (specifically a (64, 8, 25, 50) distribution) where 25% of the clusters contained 50% of the documents.

No specific real-world datasets were used for evaluation; instead, a simulated environment was employed.

Key Insights and Ideas

  • MDAP is NP-Complete: This fundamental finding justifies the need for heuristic algorithms like GAs, as optimal solutions are computationally intractable.
  • GA Effectiveness: The proposed GA demonstrates a strong ability to find good document allocations, significantly outperforming a "pseudo-optimal" baseline derived from random sampling.
  • Mutation's Double-Edged Sword: While mutation is crucial for escaping local optima and generally improves results, excessively high mutation rates can degrade performance by disrupting good solutions. This suggests a need for careful tuning of mutation parameters relative to population size.
  • Architecture Matters: The communication topology of the multiprocessor architecture significantly influences the improvement gained from the GA. Architectures with higher communication diameters see more substantial benefits from optimized document allocation.

Key Results

The paper presents simulation results for various architectures (hypercube, mesh) and document distributions.

  • The GA consistently produced better document allocations than a pseudo-optimal solution derived from 100,000 random permutations, especially when mutations were enabled.
  • In most cases, the GA achieved lower "cost" (sum of cluster diameters) than the pseudo-optimal solution.
  • The improvement in allocation quality was more pronounced for architectures with higher communication diameters.
  • Varying population size showed that larger populations generally led to better results, up to a point, especially when mutations were not used.
  • The presence of mutation generally led to better final allocations, preventing convergence to suboptimal solutions.

Limitations and Future Work

  • Small Database Size: The experiments were conducted on a small 64-document database. Future work will involve models with larger document databases and non-uniform access frequencies.
  • Parameter Tuning: The precise ratio between mutation rate and population size requires further study to optimize performance.
  • Real-World Evaluation: The current evaluation is based on simulations. Future work includes developing and evaluating a hypercube-based multiprocessor information retrieval system to compare the GA's performance against standard allocation schemes in a real-world setting.
  • Larger Population Sizes: The population sizes used were small due to the small database size; larger populations will be explored in future studies.

Summary updated

BibTeX
@inproceedings{frieder1991allocation,
  author = {Ophir Frieder and Hava T. Siegelmann},
  title = {{On the Allocation of Documents in Multiprocessor Information Retrieval Systems}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {1991},
  doi = {10.1145/122860.122884},
}
Figure