  Retrieving similar trajectories from a large trajectory dataset is important
for a variety of applications, like transportation planning and mobility
analysis. Unlike previous works based on fine-grained GPS trajectories, this
paper investigates the feasibility of identifying similar trajectories from
cellular data observed by mobile infrastructure, which provide more
comprehensive coverage. To handle the large localization errors and low sample
rates of cellular data, we develop a holistic system, cellSim, which seamlessly
integrates map matching and similar trajectory search. A set of map matching
techniques are proposed to transform cell tower sequences into moving
trajectories on a road map by considering the unique features of cellular data,
like the dynamic density of cell towers and bidirectional roads. To further
improve the accuracy of similarity search, map matching outputs M trajectory
candidates of different confidence, and a new similarity measure scheme is
developed to process the map matching results. Meanwhile, M is dynamically
adapted to maintain a low false positive rate of the similarity search, and two
pruning schemes are proposed to minimize the computation overhead. Extensive
experiments on a large-scale dataset and real-world trajectories of 1701 km
reveal that cellSim provides high accuracy (precision 62.4% and recall of
89.8%).
