ID Repair For Spatio-temporal Trajectories With Location-based Constraints

Currently,in many applications,moving entities are continuously tracked with the capture devices on fixed locations,which leads to a large volume of spatio-temporal trajectories.For instance,the intelligent cameras set on roads will automatically capture the vehicles passing by.In this process,one of the main tasks is to identify the ID(e.g.,the license plate)for each entity.However,sometimes the IDs of the entities may be incorrectly identified due to various reasons(e.g.,weak illumination or occlusion).As a consequence,the calculation based on these recognized results will be inaccurate or even fail.Since very often the movements of the entities are constrained by certain location-based constraints imposed by the application(e.g.,vehicles must move along the given road network),we consider how to detect and repair the erroneous IDs with these constraints.Generally,the occurrence of erroneous IDs can cause the original trajectory to be broken into trajectory fragments that violate the constraints,and that can be used to accomplish error detection.Further,considering the cause of violations,we aim to repair the errors by rewriting the erroneous IDs and merging the fragments to eliminate the invalid fragments inversely.This problem is practically challenging since it is not easy to judge which IDs are correct,and also there may be multiple candidates as the correct value for a single error.To cope with different data characteristics,we provide specific solutions for both the offline batch processing and the online stream processing.For traditional batch processing,we propose a location-based constraint named the transition graph to detect and repair the erroneous IDs.As the dataset is static and can be randomly accessed,we formulate the repair process as a global optimization problem and propose a two-phase repair paradigm,which includes candidate repair generation and compatible repair selection,to maximize the quality improvement estimated by a designed effectiveness function.Though both phases are intractable,we propose efficient algorithms to solve them by exploiting the locality and sparsity of trajectories.We further devise an index structure,as well as a pruning method to make the repair process more efficient.Experiments on both real and synthetic datasets demonstrate the effectiveness and efficiency of the proposed methods.On the other hand,we notice that such ID errors need to be repaired in a real-time stream processing form as the trajectories are often involved in some time-sensitive query processing or data analysis tasks.Due to the one-pass and sequential access characteristics on streams,it's impossible to accomplish a global optimization on the whole dataset like batch processing.We use another form of location-based constraint,the location sequence constraint,to address a specific case where the errors are singleton IDs,i.e.,as moving entities are tracked continuously,IDs that appear only once during a specific period of timecould be safely presumed tobe erroneous.We present a tracking-tree structure to index the repair options for each singleton ID,which enables selecting the best repair option for an error in real time.Also,we implement a distributed online repair system on the Apache Storm platform.Experiments on both real and synthetic datasets demonstrate the effectiveness and efficiency of our singleton detection and repair approach.In this paper,we deeply explore the ID repair problem in spatio-temporal trajectories for both batch and stream processing.In brief,the main contributions we make are as follows.(1)It's the first time that the ID repair problem for spatio-temporal trajectories with transition graphs has been defined.We also propose a two-phase repair paradigm for the problem and introduce the corresponding algorithms.(2)We propose an index structure,as well as a pruning method to improve the efficiency of the basic solution.Experiments on both real and synthetic datasets demonstrate the effectiveness and efficiency of the proposed methods.(3)We introduce the variant singleton ID repair problem on streams and present a tracking-tree structure,as well as a distributed online repair system on Apache Storm.The effectiveness and scalability for this solution are verified with the experiments on both real and synthetic datasets.