On Comparing the Similarity and Dissimilarity Between Two Distinct Vehicular Trajectories
| Autor: | Lihui Dai, Peng Zou, Binhai Zhu, Letu Qingge, Qing Yang |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
General Computer Science
Computer science vehicular trajectories local search General Engineering Set cover problem 0102 computer and information sciences 02 engineering and technology Similarity and dissimilarity Flow network 01 natural sciences Constraint (information theory) Similarity (network science) 010201 computation theory & mathematics Metric (mathematics) NP-hardness 0202 electrical engineering electronic engineering information engineering Adjacency list 020201 artificial intelligence & image processing General Materials Science Point (geometry) lcsh:Electrical engineering. Electronics. Nuclear engineering lcsh:TK1-9971 Algorithm Local search (constraint satisfaction) |
| Zdroj: | IEEE Access, Vol 9, Pp 34415-34422 (2021) |
| ISSN: | 2169-3536 |
| DOI: | 10.1109/access.2021.3061501 |
| Popis: | In this paper, we study the problem of comparing the similarity and dissimilarity between two distinct vehicular trajectories by proposing an adjacency-based metric. This approach has a broad application in building truthfulness by comparing the similarity between two vehicles and evaluating the dissimilarity between two distinct paths in hazardous materials transportation. Given two sequences $A$ and $B$ of Point of Interests (POIs) visited by two vehicles in a road/transportation network, the problem is to delete some nodes from $A$ and $B$ to obtain $A'$ and $B'$ such that the number of adjacencies in $A'$ and $B'$ is maximized. In the sequences $A'$ and $B'$ duplicated nodes are allowed, e.g., to represent road edges. We prove that this problem is NP-hard when noisy POIs are deleted and all the remaining POIs must be involved in some adjacency. On the other hand, when the adjacency involvement constraint is dropped, a variation of the problem is as hard as Exact Set Cover hence cannot be approximated within a constant factor unless P=NP. At last, we design a practical approach based on local search and show that the algorithm is very effective on simulation data. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|