With the development of base technologies for moving objects, many studies concerning tracing, analyzing, and storing object locations in the database and applying them to location-based services (LBS) have been actively conducted. Many previous studies represent a trajectory as a sequence of points, which we call point approximation. However, the similarity measures such as LCSS, EDR, and ERP using point approximation may return inconsistent similarity values depending on the moving speed, sampling rate, and sampling phase, and thus, incur inaccurate search result. To cope with this problem, recent studies represent a trajectory as a sequence of line segments connecting two contiguous points and use `all continuous points' on the segment. We call this representation segment approximation. In this paper, we present a sub-trajectory matching algorithm using multi-segment approximation. We also present an indexing mechanism for fast processing of the search. Using multi-segment approximation for efficient sub-trajectory matching has remained a major challenge due to the difficulty in defining a measure of the multi-segment similarity between trajectories. In this paper we define a new similarity measure between two multi-segment trajectories as the Hausdorff distance. The Hausdorff distance effectively handles the multi-segment nature of trajectories by decomposing the distance between trajectories into those between individual segments. We can employ various distances between segments reflecting the characteristics of specific applications. Sub-trajectory matching is a problem a lot more general than whole trajectory matching since the query should match the data trajectory at an arbitrary position. Again, we solve this problem by decomposing the trajectory into individual segments. We reconstruct the trajectory or sub-trajectory matched from the individual matching segments by an innovative “stitching” algorithm based on simple and fast matrix operations. We employ indexing to facilitate fast search. To the extent of our knowledge, employing indexing for sub-trajectory matching is new. Again, we solve this problem by decomposing the trajectories into segments, indexing those segments, and stitching them to reconstruct the (sub) trajectories. Extensive experiments using real and synthetic datasets show excellence of our similarity measure in terms of F-measure compared with that of the state-of-art EDwP, which can handle only whole trajectory matching. The results also show that our algorithm significantly improves the performance by up to 5180 times over the EDwP-based one without an index and by up to 16.7 times over the EDwp with an index. We also show that the performance of our algorithm is linearly scalable in the size of the database, which is an essential characteristic to handle massive scale databases.
In this paper, we also define the problem of searching for all pairs of query sub-trajectories and data sub-trajectories, and present an algorithm to solve the problem, which we call all sub-trajectory pair matching. All sub-trajectory pair matching is more general than sub-trajectory matching since an arbitrary query sub-trajectory should match the data trajectory at an arbitrary length. To the extent of our knowledge, the all sub-trajectory pair matching problem is new. We solve this problem by extending the sub-trajectory matching algorithm presented in this paper. In common with sub-trajectory matching, we decompose trajectories into individual segments and reconstruct the trajectory or sub-trajectory from the individual matching segments by an extended stitching algorithm. The extension of the stitching algorithm matches an arbitrary query sub-trajectory with an arbitrary data sub-trajectory. Extensive experiments using real and synthetic datasets shows a performance superiority of our algorithm compared with a naive one, which repeatedly uses the sub-trajectory matching algorithm presented in this paper. We compared with the naive algorithm since no other algorithm for all sub-trajectory pair matching has been proposed in the literature. The results show that our algorithm for all sub-trajectory pair matching improves the performance by up to 650 times over the naive one. As in the preceding case, we also show the performance of our algorithm is also linearly scalable in the size of the database.
이동 객체에 대한 기반 기술이 발전함에 따라 그들의 위치를 추적, 분석, 저장하여 위치 기반 서비스(location-based services, LBS)에 응용하기 위한 많은 연구가 활발히 진행되고 있다. 기존의 많은 연구에서는 궤적(trajectory)을 좌표 점들의 연속(sequence)으로 표현하였고, 본 논문에서는 이를 점 근사법(point approximation)이라 부른다. 하지만 점 근사법에 기반한 LCSS, EDR, ERP 등의 유사도 척도들은 이동 객체의 이동 속도, 샘플링 주기(sampling rate), 샘플링 위상 차이(phase variation) 등에 따라 일관되지 않은 궤적 유사도 값을 반환하며, 그로 인해 유사 궤적 검색의 정확도를 떨어뜨린다. 이러한 문제를 해결하고자 최근의 연구에서는 궤적을 두 인접한(contiguous) 점들을 연결한 라인 세그먼트들(line segments)의 연속으로 표현하고, 그 세그먼트 상의 `연속된(continuous) 모든 점들'을 이용한다. 본 논문에서는 이를 세그먼트 근사법(segment approximation)이라고 부른다. 본 논문은 다중 세그먼트 근사법(multi-segment approximation)에 기반한 부궤적 검색(sub-trajectory matching) 알고리즘을 제안한다. 또한 효율적인 검색을 위한 인덱싱 방법도 제안한다. 기존에 다중 세그먼트 근사법을 이용한 효율적인 부궤적 검색 해법이 존재하지 않는 것은 두 궤적 간의 다중 세그먼트 유사도를 정의하기 어렵기 때문이다. 본 논문에서는 두 다중 세그먼트 궤적 간의 유사도 척도를 하우스도르프 거리(Hausdorff distance)로 정의한다. 하우스도르프 거리는 두 궤적 간의 거리를 그들을 구성하는 개별적인 세그먼트 간의 거리로 분해(decompose)함으로써 다중 세그먼트 특성을 효율적으로 다룬다. 세그먼트 간의 거리는 특정 응용에 적절한 다양한 거리를 이용할 수 있다. 부궤적 검색은 질의 궤적이 데이터 궤적 내의 임의의 위치의 부궤적과 매칭되므로 전체 궤적 검색(whole trajectory matching)보다 더 일반적인 문제이다. 본 논문에서는 부궤적 검색 알고리즘도 궤적을 개별적인 세그먼트로 분해함으로써 해결한다. 각 질의 세그먼트에 매칭되는 데이터 세그먼트들을 단순하고 빠른 비트 행렬 연산으로 구성된 혁신적인 `스티칭(stitching)' 알고리즘을 통하여 유사 궤적 또는 부궤적으로 재구성한다. 매칭되는 데이터 세그먼트의 빠른 검색을 위하여 인덱싱을 이용하며, 부궤적 검색을 위하여 인덱싱을 이용하는 것은 새로운 해결방법이다. 실제 및 합성 데이터셋을 이용한 다양한 실험 결과, 제안된 유사도 척도는 기존에 가장 정확도가 높은 EDwP 척도에 비하여 F-척도(F-measure) 면에서 우수함을 알 수 있었다. 실험 결과를 통하여 제안된 알고리즘은 전체 궤적 검색만을 수행하는 EDwP 기반의 알고리즘에 비하여 인덱스가 없는 경우 최대 5180배, 인덱스를 이용한 경우 최대 16.7배 성능이 향상되었다. 또한 제안된 알고리즘의 성능이 데이터베이스 크기에 따라 선형성(scalability)을 가짐을 확인하였으며, 이는 대용량 데이터베이스를 처리할 때에 필수적인 특성이다.
본 논문은 또한 모든 부궤적 쌍 검색(all sub-trajectory pair matching) 알고리즘을 제안한다. 이 알고리즘은 질의 궤적과 데이터 궤적 내에 서로 유사한 모든 부궤적 쌍을 반환한다. 모든 부궤적 쌍 검색은 질의 궤적 전체를 포함하여 모든 가능한 질의 부궤적에 대하여 매칭되는 데이터 부궤적을 검색하므로, 부궤적 검색보다 더 일반적인 문제이며, 기존에 동일한 문제를 다룬 연구는 존재하지 않는다. 본 논문에서는 앞에서 제안한 부궤적 검색 알고리즘을 확장하여 모든 부궤적 쌍 검색 문제를 해결한다. 부궤적 검색 알고리즘과 동일하게 모든 궤적을 개별적인 세그먼트로 분해하고, 각 질의 세그먼트와 유사한 데이터 세그먼트들을 확장된 스티칭 알고리즘을 통하여 유사 부궤적 쌍으로 재구성한다. 실제 및 합성 데이터셋을 이용한 다양한 실험 결과, 제안된 알고리즘은 모든 가능한 부궤적 간의 거리를 계산하는 단순(naive) 알고리즘에 비하여 성능이 최대 650배까지 크게 향상되었다. 실험을 통하여 모든 부궤적 쌍 검색 알고리즘은 부궤적 검색 알고리즘과 동일하게 데이터베이스 크기에 따라 성능이 선형성(scalability)을 가짐을 확인하였다.
