Graph and geometric algorithms on distributed networks and databases
MetadataShow full item record
In this thesis, we study the power and limit of algorithms on various models, aiming at applications in distributed networks and databases. In distributed networks, graph algorithms are fundamental to many applications. We focus on computing random walks which are an important primitive employed in a wide range of applications but has always been computed naively. We show that a faster solution exists and subsequently develop faster algorithms by exploiting random walk properties leading to two immediate applications. We also show that this algorithm is optimal. Our technique in proving a lower bound show the first non-trivial connection between communication complexity and lower bounds of distributed graph algorithms. We show that this technique has a wide range of applications by proving new lower bounds of many problems. Some of these lower bounds show that the existing algorithms are tight. In database searching, we think of the database as a large set of multi-dimensional points stored in a disk and want to help the users to quickly find the most desired point. In this thesis, we develop an algorithm that is significantly faster than previous algorithms both theoretically and experimentally. The insight is to solve the problem on the streaming model which helps emphasize the benefits of sequential access over random disk access. We also introduced the randomization technique to the area. The results were complemented with a lower bound. We also initiat a new direction as an attempt to get a better query. We are the first to quantify the output quality using "user satisfaction" which is made possible by borrowing the idea of modeling users by utility functions from game theory and justify our approach through a geometric analysis.
Showing items related by title, author, creator and subject.
Lee, Eun Jae; Hodges, Larry F. (Georgia Institute of Technology, 1993)This paper describes a hybrid method which uses structural properties of raster lines, such as runs, to improve the efficiency of multi-point line generation. A quadruple-step algorithm is developed which requires fewer ...
Das Sarma, Atish (Georgia Institute of Technology, 2010-07-01)
Lertpratchya, Daniel; Blough, Douglas M. (Georgia Institute of Technology, 2011)It is known that using a spatial TDMA (STDMA) access scheme can increase the capacity of a wireless network over CSMA/CD access scheme. Modern wireless devices are capable of transmitting at different data rates depending ...