Distributed network and spatial protocols on big data

Abstract

We 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.