Search

An increasing number of vehicles are now equipped with GPS devices to facilitate fleet management and send their GPS locations continuously, generating a huge volume of trajectory data. Sending and storing such vehicle trajectory data cause sustainable communication and storage overheads. Trajectory data compression becomes a promising way to alleviate overhead issues. However, previous solutions are commonly carried out at the side of the data center after data having been received, thus saving the storage cost only. Here, we bring the idea of mobile edge computing and transfer the computation-intensive data compression task to the mobile devices of drivers. As a result, the trajectory data is reduced at the side of data generators before being sent out; thus, it can lower data communication and storage costs simultaneously. We propose DAVT, an error-bounded trajectory data representation, and a compression framework. Specifically, the trajectory data is reformatted into three parts (i.e., Distance, Acceleration & Velocity, and Time), and three compressors are wisely devised to compress each part. For D and AV parts, a similar Huffman tree-forest structure is exploited to encode data elements effectively, but with quite different rationales. For the T part, the large absolute timestamps are transformed to small time intervals firstly, and different encoding techniques are adopted based on the data quality. We evaluate our proposed system using a large-scale taxi trajectory dataset collected from the city of Beijing, China. Our results show that our compressors outperform other baselines. [ABSTRACT FROM AUTHOR]

Abstract: In the partial alphabetic tree problem we are given a multiset of non-negative weights , partitioned into blocks . We want to find a binary tree T where the elements of W reside in its leaves such that if we traverse the leaves from left to right then all leaves of precede all leaves of for every . Furthermore among all such trees, T has to minimize , where is the depth of in T. The partial alphabetic tree problem generalizes the problem of finding a Huffman tree over W (there is only one block) and the problem of finding a minimum cost alphabetic tree over W (each block consists of a single item). This problem arises when we need an optimal binary code for a set of items with known frequencies, such that we have a lexicographic restriction for some of the codewords. Our main result is a pseudo-polynomial time algorithm that finds the optimal tree. Our algorithm runs in time where , , and ( is the golden ratio). In particular the running time is polynomial in case the weights are bounded by a polynomial of n. To bound the running time of our algorithm we prove an upper bound of on the depth of the optimal tree. Our algorithm relies on a solution to what we call the layered Huffman forest problem which is of independent interest. In the layered Huffman forest problem we are given an unordered multiset of weights , and a multiset of integers . We look for a forest F with k trees, , where the weights in W correspond to the leaves of F, that minimizes where is the depth of in its tree plus if . Our algorithm for this problem runs in time. [Copyright &y& Elsevier]