[논문]이동 객체의 궤적 처리를 위한 색인 구조 및 궤적 데이터 생성 알고리즘

채철주; 김용기

doi:10.15207/jkcs.2019.10.4.033

초록
AI-Helper

최근 다양한 LBS(location-based service) 서비스를 지원하기 위해 실제 공간 네트워크를 고려한 연구가 활발하게 진행 중이다. 이를 위해, 도로 네트워크에서 데이터 처리를 위한 실험 데이터가 다수 존재한다. 그러나 이러한 이동 객체의 궤적을 처리하기 위한 데이터는 이용하기에 적합하지 않다. 따라서 본 논문에서는 도로 네트워크 환경에서 궤적 데이터를 처리할 수 있는 색인 구조와 궤적 데이터 생성 알고리즘을 제안한다. 또한, 제안하는 구조와 알고리즘의 우수성을 입증하기 위해, 샌프란시스코 맵으로부터 만들어진 데이터를 이용하여 제안하는 알고리즘을 통해 에지 기반의 궤적 데이터를 생성됨을 보인다.

Abstract ▼ AI-Helper

Recently, to support location-based services, there have been many researches which consider the spatial network. For this, there are many experimental data for data processing on the road network. However, the data to process the trajectory of moving objects are not suitable. Therefore, we propose ...

Recently, to support location-based services, there have been many researches which consider the spatial network. For this, there are many experimental data for data processing on the road network. However, the data to process the trajectory of moving objects are not suitable. Therefore, we propose index structure to process the trajectory data on the road network and the trajectory data generation algorithm. In addition, to prove efficiency of our index structure and algorithm, we show that edge-based trajectory data are generated through the proposed algorithm using the map data of San Francisco Bay.

주제어

표/그림 (8)

그림 Fig. 1. Example of location based service on road network
표 Table 1. Mobile phone ownership over time
그림 Fig. 2. Classification of research dealing with moving objects
그림 Fig. 3. Road network and moving objects (or Points of Interest)
그림 Fig. 4. Network Index Structure and Relationship between Edge and Trajectory
그림 Fig. 7. Data generation by moving object generator
그림 Fig. 5. Insertion algorithm of moving objects
그림 Fig. 6. Edge based trajectory generation algorithm

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

그러나, 이러한 데이터 중 이동 객체의 궤적을 처리하기 위한 데이터는 존재하지 않는다. 따라서 본 연구는 도로 네트워크 환경에서의 궤적 데이터를 처리하기 위한 색인 구조를 제안하고, 이를 이용하여 궤적 데이터 생성 기법에 대해 제안한다.
도로 네트워크상에서의 데이터 처리를 위한 이동객체에 대한 실데이터가 다수 존재함에도 불구하고, 궤적 데이터를 처리하기 위한 데이터는 존재하지 않는다. 따라서 본 연구는 도로 네트워크 환경에서의 궤적 데이터를 처리하기 위한 색인 구조를 제안하고, 이를 이용하여 좌표 기반의 이동 객체 데이터를 에지 기반의 이동 객체 궤적 데이터로 생성하는 알고리즘을 제안하였다. 아울러, Brinkhoff가 제안한 샌프란시스코 맵에서의 이동객체 데이터와 제안 알고리즘을 통해 에지 기반의 궤적 데이터가 생성됨을 보였다.
향후 연구로는 도로 네트워크 상황을 고려하여 이동객체의 네트워크 연결을 수행하는 연구가 진행되어야 한다. 또한, 이러한 궤적 데이터의 응용 연구를 수행하여 제안하는 알고리즘을 통해 생성된 궤적 데이터의 유용성을 검증하는 것이다.

가설 설정

제안하는 저장 구조는 좌표로 구성된 네트워크의 정보를 색인할 수 있으며, 각 궤적은 에지 RTree의 단말노드에 위치하여 에지의 정보가 궤적 데이터를 가리킨다. 다음 Fig.

제안 방법

본 연구에서는 기존 이동객체 생성 프레임워크[15]를 이용하여 데이터 추출 후 해당 데이터를 에지 기반의 궤적 데이터로 생성함으로써, 제안하는 생성 알고리즘을 이용하여 에지기반의 궤적 데이터를 생성할 수 있음을 보였다. 본 연구에서 사용된 기존 이동객체 생성 프레임워크는 네트워크 기반 이동 객체의 가장 중요한 특성으로 객체의 속도와 경로에 대한 다른 움직이는 객체의 영향, 객체의 시작과 목적지의 적절한 결정 등 9가지를 제시하고, 이 특성을 반영한 이동객체를 생성한다. 아울러 네트워크 상에서 엄격하게 움직임을 전제로 하여 이동 객체의 위치를 표현하여 실제 네트워크 데이터에 매핑하여 표현한 데이터 셋을 생성하였다.
본 연구에서 사용된 기존 이동객체 생성 프레임워크는 네트워크 기반 이동 객체의 가장 중요한 특성으로 객체의 속도와 경로에 대한 다른 움직이는 객체의 영향, 객체의 시작과 목적지의 적절한 결정 등 9가지를 제시하고, 이 특성을 반영한 이동객체를 생성한다. 아울러 네트워크 상에서 엄격하게 움직임을 전제로 하여 이동 객체의 위치를 표현하여 실제 네트워크 데이터에 매핑하여 표현한 데이터 셋을 생성하였다. 제안 방법에 대한 실험은 Windows 환경에서 C++을 이용하였다.
6과 같다. 에지로 구성된 궤적 데이터를 생성하기 위하여 우선적으로 이동 객체의 포인트들을 에지로 매핑을 수행한다. 다음으로, 매핑된 에지들을 연결한다.
둘째, 경로 내 kNN 질의는 주어진 경로를 적게 벗어나면서 원하는 관심정보를 찾는 것이다. 이를 위해 경로 내 이동 비용과 경로를 벗어나 관심정보에 도달 및 되돌아오는 비용을 계산하여 모든 경로의 비용이 적은 경로를 찾는 기법을 제공한다. 이러한 경로를 이용하여 처리하는 질의의 경우는 네트워크를 탐색하는 비용이 많기 때문에 효율적인 인덱스 저장 구조가 필요하다.
연속 kNN 질의는 주어진 경로상의 모든 지점으로부터 가까운 k개의 관심 정보를 찾는 것이다. 이를 위해 공간 네트워크상에서 보로노이 다이어그램(voronoi network diagram)을 이용하여 미리 찾고자 하는 관심 정보의 네트워크 거리를 미리 계산하여 빠르게 질의처리를 수행할 수 있는 기법을 제공한다. 둘째, 경로 내 kNN 질의는 주어진 경로를 적게 벗어나면서 원하는 관심정보를 찾는 것이다.

성능/효과

아울러, Brinkhoff가 제안한 샌프란시스코 맵에서의 이동객체 데이터와 제안 알고리즘을 통해 에지 기반의 궤적 데이터가 생성됨을 보였다. 본 연구에서 제시한 에지 기반의 이동 객체 궤적 데이터는 현재 시점의 위치에서 다음 시점의 위치를 네트워크 연결을 통해 경로를 설정하여 이동 객체가 표현됨으로써, 다양한 경로기반의 질의, 궤적기반의 질의 등을 수행할 수 있다. 단, 현재의 알고리즘 상에서는 현재 위치로 다음 위치로 네트워크 연결을 수행할 시 거리 기반의 네트워크 연결을 시도하였다.
본 연구에서는 기존 이동객체 생성 프레임워크[15]를 이용하여 데이터 추출 후 해당 데이터를 에지 기반의 궤적 데이터로 생성함으로써, 제안하는 생성 알고리즘을 이용하여 에지기반의 궤적 데이터를 생성할 수 있음을 보였다.
따라서 본 연구는 도로 네트워크 환경에서의 궤적 데이터를 처리하기 위한 색인 구조를 제안하고, 이를 이용하여 좌표 기반의 이동 객체 데이터를 에지 기반의 이동 객체 궤적 데이터로 생성하는 알고리즘을 제안하였다. 아울러, Brinkhoff가 제안한 샌프란시스코 맵에서의 이동객체 데이터와 제안 알고리즘을 통해 에지 기반의 궤적 데이터가 생성됨을 보였다. 본 연구에서 제시한 에지 기반의 이동 객체 궤적 데이터는 현재 시점의 위치에서 다음 시점의 위치를 네트워크 연결을 통해 경로를 설정하여 이동 객체가 표현됨으로써, 다양한 경로기반의 질의, 궤적기반의 질의 등을 수행할 수 있다.

후속연구

따라서 다양한 도로 네트워크 상황을 고려할 필요가 있다. 향후 연구로는 도로 네트워크 상황을 고려하여 이동객체의 네트워크 연결을 수행하는 연구가 진행되어야 한다. 또한, 이러한 궤적 데이터의 응용 연구를 수행하여 제안하는 알고리즘을 통해 생성된 궤적 데이터의 유용성을 검증하는 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	range 질의처리 알고리즘을 효율적으로 처리하기 위해 제공하는 것은 무엇인가?	kNN 질의처리 알고리즘은 현재 질의 지점으로부터 가장 가까운 k개의 관심 정보를 찾는 알고리즘으로써 grid 기반의 탐색 방법, graph 기반의 탐색 방법 등을 이용하여 적은 비용을 가 진 관심정보를 빠르게 찾아내는 알고리즘이다. Range 질의처리 알고리즘은 질의 지점으로부터 주어진 범위 내에 있는 관심정보를 빠르게 찾아내는 알고리즘을 말하며, 이를 효율적으로 처리하기 위해 Grid 구조, Tree 구조, Network 구조 등의 색인 작업을 통해 탐색하는 방법을 제공한다. 아울러, 동적인 이동객체의 특성을 반영한 경로를 기반으로 한 질의처리 알고리즘이 있다.
	grid 기반의 탐색 방법, graph 기반의 탐색 방법 등을 이용하여 적은 비용을 가 진 관심정보를 빠르게 찾아내는 알고리즘은 무엇인가?	이 중 정적인 관심정보(Point of Interest)를 찾기 위한 kNN(k nearest neighbor) 및 range 질의처리 알고리즘이 있다[3,4]. kNN 질의처리 알고리즘은 현재 질의 지점으로부터 가장 가까운 k개의 관심 정보를 찾는 알고리즘으로써 grid 기반의 탐색 방법, graph 기반의 탐색 방법 등을 이용하여 적은 비용을 가 진 관심정보를 빠르게 찾아내는 알고리즘이다. Range 질의처리 알고리즘은 질의 지점으로부터 주어진 범위 내에 있는 관심정보를 빠르게 찾아내는 알고리즘을 말하며, 이를 효율적으로 처리하기 위해 Grid 구조, Tree 구조, Network 구조 등의 색인 작업을 통해 탐색하는 방법을 제공한다.
	Range 질의처리 알고리즘은 무엇인가?	kNN 질의처리 알고리즘은 현재 질의 지점으로부터 가장 가까운 k개의 관심 정보를 찾는 알고리즘으로써 grid 기반의 탐색 방법, graph 기반의 탐색 방법 등을 이용하여 적은 비용을 가 진 관심정보를 빠르게 찾아내는 알고리즘이다. Range 질의처리 알고리즘은 질의 지점으로부터 주어진 범위 내에 있는 관심정보를 빠르게 찾아내는 알고리즘을 말하며, 이를 효율적으로 처리하기 위해 Grid 구조, Tree 구조, Network 구조 등의 색인 작업을 통해 탐색하는 방법을 제공한다. 아울러, 동적인 이동객체의 특성을 반영한 경로를 기반으로 한 질의처리 알고리즘이 있다.

참고문헌 (15)

S. Shekhar, S. Chawla, S. Ravada, A. Fetterer, X. Liu & C. T. Lu. (1999). Spatial databases-accomplishments and research needs. IEEE transactions on knowledge and data engineering, 11(1), 45-55.

상세보기
L. Speicvcys, C. S. Jensen & A. Kligys. (2003). Computational data modeling for network-constrained moving objects. In Proceedings of the 11th ACM international symposium on Advances in geographic information systems 118-125.
D. Papadias, J. Zhang, N. Mamoulis & Y. Tao. (2003). Query processing in spatial network databases. In Proceedings of the 29th international conference on Very large data bases, 29, 802-813.
Roussopoulos, N., Kelley, S., & Vincent, F. (1995). Nearest neighbor queries. In ACM sigmod record, 24(2), 71-79.
Korea Information Society Development Institute. (2019). Korea Media Panel Survey Contents. KISDI STAT. 19(2). 1-8.
A. P. Sistla, O. Wolfson, S. Chamberlain & S. Dao. (1997). Modeling and querying moving objects. In icde. (97), 422-432.
C. S. Jensen, T. B. Pedersen, L. Speicys & I. Timko. (2003). Data modeling for mobile services in the real world. In International Symposium on Spatial and Temporal Databases. 1-9.
M. R. Kolahdouzan & C. Shahab. (2004). Continuous K-Nearest Neighbor Queries in Spatial Network Databases. In STDBM, 33-40.
K. Mouratidis, M. L. Yiu, D. Papadias & N. Mamoulis. (2006). Continuous nearest neighbor monitoring in road networks. In Proceedings of the 32nd international conference on Very large data bases, 43-54.
J. S. Yoo & S. Shekhar. (2005). In-route nearest neighbor queries. GeoInformatica, 9(2), 117-137.

상세보기
R. A. Finkel & J. L. Bentley. (1974). Quad trees a data structure for retrieval on composite keys. Acta informatica, 4(1), 1-9.

상세보기
J. L. Bentley. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 509-517.

상세보기
A. Guttman. (1984). R-trees: a dynamic index structure for spatial searching. 14(2), 47-57.
Z. Song & N. Roussopoulos. (2003, January). SEB-tree: An approach to index continuously moving objects. In International Conference on Mobile Data Management (pp. 340-344). Springer, Berlin, Heidelberg.
T. Brinkhoff. (2002). A framework for generating network-based moving objects. GeoInformatica, 6(2), 153-180.

상세보기

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

이동 객체의 궤적 처리를 위한 색인 구조 및 궤적 데이터 생성 알고리즘
Index Structure and Trajectory Data Generation Algorithm to Process the Trajectory of Moving Object 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

표/그림 (8)

표/그림 (8)

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

성능/효과

후속연구

질의응답

참고문헌 (15)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

이동 객체의 궤적 처리를 위한 색인 구조 및 궤적 데이터 생성 알고리즘 Index Structure and Trajectory Data Generation Algorithm to Process the Trajectory of Moving Object 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

표/그림 (8) 모든 표/그림 보기

표/그림 (8) 슬라이드로 보기

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

성능/효과

후속연구

질의응답

참고문헌 (15)

이 논문을 인용한 문헌

저자의 다른 논문 :

채철주 (9)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

이동 객체의 궤적 처리를 위한 색인 구조 및 궤적 데이터 생성 알고리즘
Index Structure and Trajectory Data Generation Algorithm to Process the Trajectory of Moving Object 원문보기

초록
AI-Helper

표/그림 (8)

표/그림 (8)

AI 본문요약
AI-Helper