Show simple item record

dc.contributor.authorNanongkai, Danuponen_US
dc.date.accessioned2011-09-22T17:47:16Z
dc.date.available2011-09-22T17:47:16Z
dc.date.issued2011-05-16en_US
dc.identifier.urihttp://hdl.handle.net/1853/41056
dc.description.abstractIn 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.en_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectGraph algorithmsen_US
dc.subjectDesign and analysis of algorithmsen_US
dc.subjectDistributed algorithmsen_US
dc.subjectTheoryen_US
dc.subjectDatabase algorithmen_US
dc.subjectRandom walksen_US
dc.subject.lcshDistributed operating systems (Computers)
dc.subject.lcshComputer algorithms
dc.subject.lcshAlgorithms
dc.subject.lcshRandom walks (Mathematics)
dc.titleGraph and geometric algorithms on distributed networks and databasesen_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentComputingen_US
dc.description.advisorCommittee Chair: Lipton, Richard J; Committee Member: Pandurangan, Gopal; Committee Member: Tetali, Prasad; Committee Member: Venkateswaran, H.; Committee Member: Xu, Junen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record