Soft Computing Techniques for Rank Aggregation on the World Wide Web

Rank aggregation is the problem of generating a near-“consensus” ranking for a given set of rankings. When applied to the web, this finds applications in meta-searching, search engine comparison, spam fighting and word association techniques. The rank aggregation obtained by optimizing the Spearman footrule distance is called footrule optimal aggregation (FOA), and it also satisfies the Condorcet property. We find in literature a polynomial time algorithm to compute FOA for full lists. However, when collating the results of the search engines, the lists are almost invariably always the partial ones, as different search engines usually return non-overlapping lists of documents. The FOA for partial lists, however, is NP-hard. This NP-hard nature of partial footrule optimal aggregation problem (PFOA) motivates us to apply genetic algorithm (GA) for the PFOA problem. The GA based technique may take long to compute, but we propose to decide upon the number of generations of GA based on the time limit allowed by the user. We have also considered some “positional” methods, as they are linear in complexity. A classical positional method is the Borda's method. Since, fuzzy logic has been extensively studied in literature for arriving at consensus in group decision making, the adoption of some fuzzy techniques is also being investigated here for getting an improvement over the Borda's method. We have not only adopted and compared the classical fuzzy rank ordering techniques for web applications, but also proposed three novel techniques that outshine the existing techniques.