Distributed companion trajectory search algorithm

The work is focused on development of the distributed algorithm for search of companion-trajectories. We call two trajectories as companion-trajectories if they both contain section of required duration on which at any time moment distance between two objects is no larger than specified threshold. It's assumed that search is performed on database that is so big that it cannot be stored and processed on a single work station. Such tasks are usually called big-data tasks. We define trajectory quantization procedure, introduce cell index data structure, define similar trajectories. Then we build effective algorithm for search of similar trajectories. Based on this algorithm we develop effective local and distributed algorithms for search of companion trajectories. Asymptotic complexity of these algorithms is estimated.