File Download
Supplementary

postgraduate thesis: Distributed network and spatial protocols on big data

TitleDistributed network and spatial protocols on big data
Authors
Issue Date2015
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Citation
Tang, W. [唐文斌]. (2015). Distributed network and spatial protocols on big data. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5559004
AbstractWe consider the video-on-demand (VoD) streaming problem in a Peer-to-Peer (P2P) network in a decentralized model, in which peers have no global information about the network. Assuming that only one server has all the chunks, the objective is to stream M chunks to N peers in the network such that small latency and good fluency are achieved by all peers. We design a simple and decentralized protocol in which each peer maintains a constant number of neighbors and only need to communicate with one of them chosen uniformly at random every time. Moreover, the maximum number of communications established on each peer every time is also bounded by a constant. Our theoretical analysis for the model guarantees that the latency of each peer in our protocol is at most O(〖log〗^2 N), which is an O(logN) approximation of any optimal protocol. Moreover, we provide non-trivial upper and lower bounds related to the communication details, which give key insights as to why our simple protocol achieves almost-optimal performance. We also show by experiment that even under the setting of bounded connection, bounded transmission and decentralization, our protocol ensures that almost all peers in the dynamic P2P VoD network can achieve low latency and good fluency in different kinds of network topologies. In our protocol, peers' benefits are not compromised too much when they behave unselfishly by disseminating their neighbors' downloading requests, which is very important in real world application. Experiment shows that our protocol is robust against selfish peers who block their up-streams: similar performance can be maintained under the existence of (a small fraction of) selfish peers. In the Big Trajectory Data Join problem, we develop a novel bounding technique, which enables trajectories to be pruned significantly. We further design a fast sweep line algorithm with rectangle bound for each trajectory as the heuristic information, which can be used to improve the query efficiency.
DegreeMaster of Philosophy
SubjectDistributed databases
Video-on-demand
Peer-to-peer architecture (Computer networks)
Dept/ProgramComputer Science
Persistent Identifierhttp://hdl.handle.net/10722/216253

 

DC FieldValueLanguage
dc.contributor.authorTang, Wenbin-
dc.contributor.author唐文斌-
dc.date.accessioned2015-09-08T23:11:32Z-
dc.date.available2015-09-08T23:11:32Z-
dc.date.issued2015-
dc.identifier.citationTang, W. [唐文斌]. (2015). Distributed network and spatial protocols on big data. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5559004-
dc.identifier.urihttp://hdl.handle.net/10722/216253-
dc.description.abstractWe consider the video-on-demand (VoD) streaming problem in a Peer-to-Peer (P2P) network in a decentralized model, in which peers have no global information about the network. Assuming that only one server has all the chunks, the objective is to stream M chunks to N peers in the network such that small latency and good fluency are achieved by all peers. We design a simple and decentralized protocol in which each peer maintains a constant number of neighbors and only need to communicate with one of them chosen uniformly at random every time. Moreover, the maximum number of communications established on each peer every time is also bounded by a constant. Our theoretical analysis for the model guarantees that the latency of each peer in our protocol is at most O(〖log〗^2 N), which is an O(logN) approximation of any optimal protocol. Moreover, we provide non-trivial upper and lower bounds related to the communication details, which give key insights as to why our simple protocol achieves almost-optimal performance. We also show by experiment that even under the setting of bounded connection, bounded transmission and decentralization, our protocol ensures that almost all peers in the dynamic P2P VoD network can achieve low latency and good fluency in different kinds of network topologies. In our protocol, peers' benefits are not compromised too much when they behave unselfishly by disseminating their neighbors' downloading requests, which is very important in real world application. Experiment shows that our protocol is robust against selfish peers who block their up-streams: similar performance can be maintained under the existence of (a small fraction of) selfish peers. In the Big Trajectory Data Join problem, we develop a novel bounding technique, which enables trajectories to be pruned significantly. We further design a fast sweep line algorithm with rectangle bound for each trajectory as the heuristic information, which can be used to improve the query efficiency.-
dc.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subject.lcshDistributed databases-
dc.subject.lcshVideo-on-demand-
dc.subject.lcshPeer-to-peer architecture (Computer networks)-
dc.titleDistributed network and spatial protocols on big data-
dc.typePG_Thesis-
dc.identifier.hkulb5559004-
dc.description.thesisnameMaster of Philosophy-
dc.description.thesislevelMaster-
dc.description.thesisdisciplineComputer Science-
dc.description.naturepublished_or_final_version-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats