[-] Show simple item record

dc.contributor.advisorRao, Praveen R., advisoren
dc.contributor.authorSlavov, Vasil Georgiev
dc.date.issued2012-10-03
dc.date.submitted2012 Summeren
dc.descriptionTitle from PDF of title page, viewed on October 3, 2012en
dc.descriptionThesis advisor: Praveen R. Raoen
dc.descriptionVitaen
dc.descriptionIncludes bibliographic references (p. 58-69)en
dc.descriptionThesis (M.S.)--School of Computing and Engineering. University of Missouri--Kansas City, 2012en
dc.description.abstractAfter more than a decade of active research and development, the peer-to-peer (P2P) computing model continues to be successful. We have witnessed the deployment of commercial P2P applications in large, Internet-scale environments. With the rise and growth of P2P, indexing and querying data stored in large-scale sharing systems has become increasingly di cult. Computing statistics over data stored in Internet-scale P2P systems is an important component of query optimization. Decentralized gossip-based protocols are very popular in networking, and in particular, in sensor networks. The simplicity and scalability of gossip protocols render them perfect for quickly computing accurate estimates of aggregates (sums, averages, etc.) in Internet-scale systems where node and link failures are the norm. In this thesis, we present the problem of cardinality estimation of XPath queries over XML data stored in a distributed, Internet-scale environment. We focus our work on three objectives: implementing gossip in an Internet-scale environment, conducting a comprehensive performance evaluation in a wide-area network, and analyzing the experimental results. We implement two gossip-based algorithms (VanillaXGossip and XGossip) which, given an XPath query, estimate the number of XML documents in the network that contain a match for the query. XGossip employs a new, divide-and-conquer strategy for load-balancing and reducing the bandwidth consumption. We conduct a comprehensive performance evaluation of both gossip algorithms on Amazon Elastic Compute Cloud (Amazon EC2) web service using a heterogeneous collection of XML documents. The goal of the performance evaluation is to nd if the results we obtain are consistent with the theoretical analysis of VanillaXGossip and XGossip.en_US
dc.description.tableofcontentsIntroduction -- Background and motivations -- The design of VanillaXGossip and XGossip -- Implementation of VanillaXGossip and XGossip -- Evaluation -- Conclusion and future work -- Appendix A. Algorithms -- Appendix B. XPath grammaren
dc.format.extentxi, 70 pagesen
dc.identifier.urihttp://hdl.handle.net/10355/15636
dc.publisherUniversity of Missouri--Kansas Cityen
dc.subject.lcshPeer-to-peer architecture (Computer networks)en
dc.subject.lcshQuerying (Computer science)en
dc.subject.otherThesis -- University of Missouri--Kansas City -- Computer scienceen
dc.titleA study of gossip algorithms for internet-scale cardinality estimation of distributed XML dataen_US
dc.typeThesisen_US
thesis.degree.disciplineComputer Scienceen
thesis.degree.grantorUniversity of Missouri--Kansas Cityen
thesis.degree.levelMastersen
thesis.degree.nameM.S.en


Files in this item

[PDF]

This item appears in the following Collection(s)

[-] Show simple item record