Sampling methods for summarizing unordered vehicle-to-vehicle data streams

In the vehicle-to-vehicle (V2V) communication environment, vehicles interchange traffic data with each other. Because of the unbounded size of traffic data streams, sampling is used for summarization of traffic data, instead of storing the original data directly, for estimating traffic characteristics such as speed in the next step. All existing sampling methods assume that data arrivals are in the increasing timestamp order. However, this assumption may not be true in the V2V environment due to multiple data sources, transmission delays and different ways of dissemination. This disordered issue is explored in two ways in this paper. First, the traditional sampling methods for ordered streams are extended to be compatible with the disorder, especially the Unordered Extension of Exponentially Biased Reservoir Sampling (UEEBRS). Second, we propose a novel method, called the polynomially biased reservoir sampling (PBRS), to summarize unordered traffic data streams. Two measurements, the relative bias of speed and the cover rate of information obtained from the constructed summarizations, are used to assess performance of the extended methods and the novel way of comparing them with the classical methods. Preliminary simulation results show the proposed methods (UEEBRS and PBRS) reduce the relative bias of speed by about 10% with respect to the best reported result, while their cover rates of information are comparable at least to the others and are sufficiently high to support real-world applications. © 2011 Elsevier Ltd.