Computing Road Signatures from Cell Sequences with Minimum Inconsistencies

Using Call Detail Records (CDR) to track mobile locations is becoming increasingly popular. CDRs provide cell sites to which a mobile connects, which in turn indicates approximate mobile locations. In this paper, we propose the concept of road signature, which is a typical sequence of cell sites that a mobile is connected to when traveling on the road (assuming that the mobile is constantly operating). A good signature provides an easy way to determine whether other mobiles travel on the road in the future. The input to our signature creation problem is a set of cell sequences. We capture the ordering of cells in a directed graph G, where a directed arc (u, v) in G corresponds to cell u appearing before cell v in some input sequence. The output signature is an ordering of all nodes in G, ideally respecting all input sequences. However, if the input contains inconsistencies, e.g. if both cell u before v and v before u appear in the input, or more generally if G contains a cycle, it would be impossible to create a consistent signature. We assume 1-position inconsistency, which means only neighboring cell sites in the signature can be out of order with respect to the input. In this case, we provide an efficient combinatorial algorithm that computes the signature. As a secondary objective, we also aim to minimize the stretch, which means, in addition to preserving the relative ordering, any neighboring cells in the input are placed as close as possible in the signature. We provide an optimal algorithm via dynamic programming. Finally, we apply our algorithms to a set of CDR traces to verify our results.