Discover Your Island University

Graduate Projects


Project ID: 370
Author: Sharath Ranga
Project Title: Probabilistic Top-k Query Processing Using Central Limit Theorem
Semester: 3 2011
Committe Chair: Dr. Long-zhuang Li
Committee Member 1: Dr. Mario Garcia
Committee Member 2: Dr. John Fernandez
Project Description: Top-k query processing is a widespread field of research. Its application can be used in many fields like wireless sensor networks, mobile ad-hoc networks, peer-to-peer networks and many more. The basic problem in top-k query processing is that, a single algorithm cannot be used as a solution to the problem of top-k query processing because there are many types of top-k query processing. The algorithm has to be based on the situation, the classification and the type of database and query model. The research method used in this project provides a solution to the problem of generating the probable top-k query results. The algorithm also provides the probability that the results are more likely in the top-k result set. The most prominent algorithms in the field of top-k query processing techniques are FA (Fagin Algorithm), TA (Threshold Algorithm). The algorithm used in this project is built upon the Threshold Algorithm making it applicable for a wider range of top-k query processing problems with better efficiency. In this project the algorithm is implemented on sorted data. The confidence for the results is also assigned. The confidence is calculated by using the cumulative frequency distribution functions and Central Limit Theorem. Histograms implemented in the Threshold Algorithm for the data approximation are replaced with the graphs based on Central Limit Theorem to approximate the probability of the results from the data aggregated. Implementation of the Threshold Algorithm with the concepts of Central Limit Theorem result in fast and efficient top-k query processing.
Project URL:   370.pdf