CS298 Proposal

Algorithm to obtain a total order from partial orders for social networks

Chandrika Satyavolu (satyavolu.chandrika@gmail.com)

Advisor: Dr. Chris Pollett

Committee Members:Dr. Robert Chun, Dr. David Taylor

Abstract:

Social Networking can be used to harness human intelligence to solve problems which might be hard to program a computer to do. An example of this is a recaptcha. Captcha is a method that ensures security and prevents spam. The user is asked to complete a simple test (e.g: read and enter the scanned and distorted text displayed) that determines if the user is human. Recaptcha is a similar technique that uses human intelligence to digitize books and enable search through scanned text. The goal of this project is to develop an algorithm that gives the most accurate total order. This order is generated from pre-recorded relative partial orders computed by humans. A variance of this algorithm can be built into test websites for applications like: (1) In Grading, to construct a total order from partial orders created by the students themselves or the assistants. (2) To rank movies, a total order can be developed from the partial rankings given by viewers. (3) In auction and shopping portals, when searching for an item, the results displayed would be a total order obtained from the partial orders that are humanly created using ratings given to the sellers. These websites would also be tested with partial orders that are randomly generated to match the humanly created partial orders. Also, they would be tested against actual human inputs for partial orders. Finally, they would be tested with faulty partial orders to observe the fault tolerance capability of the algorithms. The main technology used to develop the web application would be PHP and MySQL database.

CS297 Results

• Learned sorting networks and different sorting algorithms which lead to develop this algorithm.
• Researched about various planning algorithms.
• Conducted experiments to test the accuracy of the total order obtained when the number of partial orders and partial order set size were fixed on certain numbers. The experiments helped to draw conclusions for the appropriate number of partial orders and the partial order set size to give the correct total order.
• Extended the experiments to make the algorithm fault tolerant in case of errors introduced into the partial orders. The experiments helped to get the appropriate number of partial orders and the partial order set size that would give the correct total order inspite of faulty partial orders.

Proposed Schedule

Key Deliverables:

• Software
  • Build a website: 100 best movies that would generate and display the total order of the best 100 movies from partial orders that are humanly ordered and stored in a MySQL database. The users of the website can add new movies of different categories to the database. The users can also generate partial rankings within specific categories. The total order of best 100 movies would be calculated from the humanly computed partial orders stored and obtained using MySQL which will be the backend.
  • Develop test websites with variants of this algorithm to observe the results of the total order generated for a set of randomly generated partial orders.
  • Test these websites against the humanly created partial orders.
  • Extend the implementation so that it works inspite of introduced faults. The partial orders manually generated could have errors. The application would use the appropriate numbers(from the experiments conducted as a part of CS297) for the number of partial orders and partial order set sizes to give back the correct total order.
• Report
  • Write the final CS298 report.

Innovations and Challenges

• There would be a tradeoff between the number of partial orders to be created and the partial order set size to give the correct total order. The most appropriate numbers should ensure minimum database use and also the algorithm must return the correct total order.
• The numbers for partial orders and their set size chosen above must also accomodate faults introduced into partial orders.
• The framework of the website and its different features would be challenging.

References:

[1] Introduction to Algorithms. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Prentice-Hall, 2nd edition, 2002.

[2] Intelligent Planning - A Decomposition and Abstraction Based Approach. Qiang Yang, Springer-Verlag, 1997.

[3] Artifical Intelligence: A Modern Approach. S. Russell and P. Norvig, Prentice-Hall, 2nd edition, 2002.