Item 10203/222428

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 586
  • Download : 0
이동 객체에 대한 기반 기술이 발전함에 따라 그들의 위치를 추적, 분석, 저장하여 위치 기반 서비스(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)을 가짐을 확인하였다.
Advisors
황규영researcherWhang, Kyu-Youngresearcher
Description
한국과학기술원 :전산학부,
Publisher
한국과학기술원
Issue Date
2016
Identifier
325007
Language
kor
Description

학위논문(박사) - 한국과학기술원 : 전산학부, 2016.8 ,[v, 80 p. :]

Keywords

다중 세그먼트 근사법; 부궤적 검색; 인덱싱 기반 검색; 모든 부궤적 쌍 검색; Mult-Segment Approximation; Subtrajectory Matching; Indexible Matching; All Subtrajectory Pair Matching

URI
http://hdl.handle.net/10203/222428
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=663212&flag=dissertation
Appears in Collection
CS-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0