[논문]이동 객체 궤적의 최소경계사각형 영역을 효율적으로 분할하는 알고리즘에 관한 연구

박주현; 조우현

doi:10.6109/jkiice.2013.17.1.110

이동 객체 궤적의 최소경계사각형 영역을 효율적으로 분할하는 알고리즘에 관한 연구
A Study on Efficient Split Algorithm for Minimum Bounding Box of Moving Object Trajectoty 원문보기

한국정보통신학회논문지 = Journal of the Korea Institute of Information and Communication Engineering, v.17 no.1, 2013년, pp.110 - 116

박주현 (부경대학교) , 조우현 (부경대학교)

초록
AI-Helper

최근, 무선 네트워크의 발달로 인해 이동 객체에 대한 위치 정보를 수집하여 실생활에 활용하는 다양한 위치 기반 서비스의 증가하고 있다. 그에 따라서, 이동 객체의 연속적인 위치를 효율적으로 검색하는 새로운 색인 구조가 필요하게 되었다. 본 논문에서는 이동 객체의 좌표 사이의 거리가 긴 경우 탐색 공간을 줄이기 위해 효율적으로 분할하는 방법을 제안한다. 궤적의 적절한 분할 위치를 찾아서 평균적인 질의의 크기를 고려하여 형성되는 확장된 최소 경계 사각형(EMBR)의 영역을 이용한다. 추정 분할 방법은 최소경계 사각형을 최소화하게끔 고안되었고 이를 실험하였다. 실험 결과 제안하는 추정 분할 방법이 기존의 방법에 비해서 EMBR의 면적을 더 효율적으로 줄여줌을 알 수 있었다.

Abstract ▼ AI-Helper

With the recent development of wireless network technologies, there have been increasing usage of variouse position base servies. Position based services basically collect position information of moving object for the utilization of them in real life. Accordingly, new index structures are required to efficiently retrieve the consecutive positions of moving objects. In the paper, we consider volume of Extended Minimum Bounding Rectangles(EMBR) to be determined by average size of range queries. We proposed the methode that split efficiently moving object with long distance between location, and split moving object for decrease searching space an Estimated-Split algorithm that minimizes the volume of MBRs is designed and simulated. Our experimental evaluation confirms the effectiveness and efficiency of our proposed splitting policy.

주제어

AI 본문요약
AI-Helper

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

문제 정의

그리고 궤적의 포인트와 포인트의 거리가 너무 길 경우에는 거짓 버림(False Drop)이 너무 많이 발생을 한다. 따라서 본 논문에서는 검색 시간 단축과 거짓 버림을 줄이기 위한 궤적의 효율적인 분할 방법을 제안한다.
본 논문에서는 검색 범위와 거짓 버림을 줄이기 위해 궤적 정보를 효율적으로 줄이는 알고리즘을 제안하였다. 성능 평가의 결과를 보면 제안하는 궤적분할 알고리즘은 길이가 긴 연속된 두 포인트 사이의 간격은 제시된 공식을 사용하여 분할함으로서 전체 EMBR의 면적을 줄일 수 있음을 알 수 있다.
본 논문에서는 두 번째의 이동 객체의 궤적을 검색하기 위한 방법에서 궤적 기반 데이터를 검색하기 위해 궤적 기반 질의에 초점을 맞추고 있다.
본 실험에서는 이동 객체의 궤적 포인트의 개수를 2000개로 제한하였고 공간 질의의 크기를 10×10,20×20, 30×30으로 주어서 여러 크기의 질의에 따라EMBR의 총면적이 어떻게 줄어드는지 실험을 했다.

가설 설정

[정리] Algorithm-1의 시간 복잡도는 O(nlogn)이다. 증명.

제안 방법

8GHz 프로세서와 메모리 1Gbyte, Windows 7 운영체제를 사용하는 시스템 상에서 수행했으며, 알고리즘의 구현을 위해서 C++ 언어를 사용하였다. 그리고 성능 비교 평가를 위하여 기존의 합병분할 방법과 추정 분할 알고리즘을 구현하여 실험을 하였다. 본 실험에서는 이동 객체의 궤적 포인트의 개수를 2000개로 제한하였고 공간 질의의 크기를 10×10,20×20, 30×30으로 주어서 여러 크기의 질의에 따라EMBR의 총면적이 어떻게 줄어드는지 실험을 했다.
두 번째 실험은 시간 구간의 좌표를 불규칙적으로 생성했을 때 각 알고리즘에 의해 만들어지는 EMBR의 총합을 시험하였다. 이동 객체의 좌표 (x,t)에서 시간 구간의 좌표이동 객체의 좌표 t를100~200 사이에서 불규칙적으로 생성하고 x의 좌표를 위치 변화를 각각 상하 50, 100, 150로 제한하여 이동 객체의 위치 정보를 생성하여 실험을 했다.
본 논문에서 제안하는 이동 객체 궤적에 대한 추정 분할 방법의 성능실험은 인텔 i5 2.8GHz 프로세서와 메모리 1Gbyte, Windows 7 운영체제를 사용하는 시스템 상에서 수행했으며, 알고리즘의 구현을 위해서 C++ 언어를 사용하였다. 그리고 성능 비교 평가를 위하여 기존의 합병분할 방법과 추정 분할 알고리즘을 구현하여 실험을 하였다.
본 연구에서는 3차원인 이동 객체 궤적의 위치 정보를 간단하게 나타내기 위해서 궤적을 위치 정보 x와 시간 t의 2차원 공간으로 나타낸다.
본 실험에서는 이동 객체의 궤적 포인트의 개수를 2000개로 제한하였고 공간 질의의 크기를 10×10,20×20, 30×30으로 주어서 여러 크기의 질의에 따라EMBR의 총면적이 어떻게 줄어드는지 실험을 했다. 실험에 사용된 위치 축인 t축은 상하의 위치 변화를 50,100, 150으로 주어졌고 축은 시간변화가 규칙적일 때 200으로 하고 불규칙적일 때 100~200으로 두어서 포인트의 생성을 임의 생성하여 실험에 적용했다.
두 번째 실험은 시간 구간의 좌표를 불규칙적으로 생성했을 때 각 알고리즘에 의해 만들어지는 EMBR의 총합을 시험하였다. 이동 객체의 좌표 (x,t)에서 시간 구간의 좌표이동 객체의 좌표 t를100~200 사이에서 불규칙적으로 생성하고 x의 좌표를 위치 변화를 각각 상하 50, 100, 150로 제한하여 이동 객체의 위치 정보를 생성하여 실험을 했다. 그 외의 다른 조건은 첫 번째 실험과동일한 조건을 주었다.
제안하는 방법은 제시된 공식을 이용하여 모든 궤적의 포인트와 포인트 사이의 거리가 길 경우 새롭게 궤적을 분할한다. 여기에 질의범위의 크기를 고려한 확장된 최소경계사각형(EMBR : Extended MBR)과 우선순위 큐(Priority Queue)을 이용하여 전체 EMBR의 면적이 최소가 되게 궤적을 분할하는 방법이다.
첫 번째 실험의 결과는 위치변화를 50, 100, 150으로 시간구간은 200으로 하고 포인트를 2000개 생성하여 공간 질의의 크기가 10×10, 20×20, 30×30일 경우 추정 알고리즘을 적용했을 때와 분할 알고리즘을 적용했을 때의EMBRs의 총 면적을 계산하여 비교하였다.

이론/모형

공간 질의가 주어졌을 때 이동 객체에 포함되어 있는 궤적의 데이터를 검색하기 위해 MBR을 사용한다.
이 추정 분할(Eliminated Split) 알고리즘은 기존에 제안한 개선된 분할 알고리즘[9]에 궤적의 위치 사이가 먼 경우를 강제 분할하는 추정 공식을 사용하여 만들어졌다. 이 알고리즘을 사용하면 색인 구성 후 공간 질의에 대한 거짓 버림이 줄어들고 불필요한 탐색공간을 감소시킬 수 있다.

성능/효과

3)에서 하나의 키 값을 계산하여 우선순위 큐에 삽입하는 연산 횟수는 n이다. 4)에서 EMBR집합의 합병과 새로운 우선순위 큐의 재구성을 위한 연산 횟수는 nlogn이다. 그래서 알고리즘의 총 연산 횟수는 n + n+ n + nlogn이다.
또한 거짓 버림이 줄어들게 되므로 검색의 오차를 줄일 수 있으므로 효율적인 데이터 처리를 할 수 있음을 알 수 있다. 그리고 이를 바탕으로 색인 구성을 더 효율적으로 할 수 있고 다양한 공간 질의에 대해서 효율적인 질의 처리를 할 수 있음을 알 수 있다.
EMBR의 면적이 줄어듦은 탐색을 위한 공간이 줄어들고 탐색 시간이 감소한다는 것을 의미한다. 또한 거짓 버림이 줄어들게 되므로 검색의 오차를 줄일 수 있으므로 효율적인 데이터 처리를 할 수 있음을 알 수 있다. 그리고 이를 바탕으로 색인 구성을 더 효율적으로 할 수 있고 다양한 공간 질의에 대해서 효율적인 질의 처리를 할 수 있음을 알 수 있다.
이 알고리즘을 사용하면 색인 구성 후 공간 질의에 대한 거짓 버림이 줄어들고 불필요한 탐색공간을 감소시킬 수 있다. 성능 평가 결과로 합병 분할 방법(MergeSplit)[8]과 비교해 본 결과 EMBR의 총합에 있어서 더 최적의 분할이 된다는 것을 알 수 있었다.
본 논문에서는 검색 범위와 거짓 버림을 줄이기 위해 궤적 정보를 효율적으로 줄이는 알고리즘을 제안하였다. 성능 평가의 결과를 보면 제안하는 궤적분할 알고리즘은 길이가 긴 연속된 두 포인트 사이의 간격은 제시된 공식을 사용하여 분할함으로서 전체 EMBR의 면적을 줄일 수 있음을 알 수 있다. EMBR의 면적이 줄어듦은 탐색을 위한 공간이 줄어들고 탐색 시간이 감소한다는 것을 의미한다.
위의 결과에서 보는 것 같이 합병 분할과 추정 분할 두 알고리즘의 성능 비교 결과를 보면 이동 객체에 적용되는 공간 질의의 크기가 작을수록 좌표의 위치 변화가 클수록 본 논문에서 제안하는 추정 분할 방법을 이용해서 인접한 두 좌표 사이를 분할하는 것이 EMBR 총면적에 있어 합병 분할 방법을 통해 만들어지는 EMBR 총면적보다 더 효율적으로 줄어든다는 것을 알 수 있다. EMBR의 총면적이 작다는 것은 필요 정보를 탐색한데 있어 탐색 공간이 더 줄어든다는 것이고 거짓 버림 역시 줄어든다는 것이다.
EMBR의 총면적이 작다는 것은 필요 정보를 탐색한데 있어 탐색 공간이 더 줄어든다는 것이고 거짓 버림 역시 줄어든다는 것이다. 이 결과는 본 논문에서 제안하는 추정 분할 알고리즘이 다른 방법에 비해 탐색공간을 더욱 효율적으로 줄여 주고, 평균적인 질의의 크기를 고려하여 거리가 긴 궤적을 분할하는 것이 더 이 이점이 있다는 것을 의미한다.
그림 11-13의 도표는 두 번째 실험을 통한 각 궤적 분할 방법의 성능비교 결과이다. 첫 번째 실험과 마찬가지로 제안하는 추정 분할 방법을 통해 만들어지는 EMBR총면적이 합병 분할 방법의 EMBR의 총면적보다 더 효율적으로 줄어듦을 알 수 있다.

후속연구

향후 논문 과제는 색인을 만들기 위해 단일 궤적이 아닌 다양한 형태의 시공간 궤적들에 대하여 탐색 공간을 줄이고 검색의 효율을 높일 수 있는 분할 방법에 대한 실험을 수행할 예정이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	이동 객체란 무엇인가?	이동 객체란 시간의 변화에 따라 공간적인 위치가 연속적으로 변화는 시공간 데이터이고 이러한 위치 정보 데이터를 저장하고 효율적으로 검색하기 위해서 여러 가지 색인 기법들이 연구되었다.
	추정 분할(Eliminated Split) 알고리즘을 사용하여 얻을 수 있는 효과는?	이 추정 분할(Eliminated Split) 알고리즘은 기존에 제안한 개선된 분할 알고리즘[9]에 궤적의 위치 사이가 먼 경우를 강제 분할하는 추정 공식을 사용하여 만들어졌다. 이 알고리즘을 사용하면 색인 구성 후 공간 질의에 대한 거짓버림이 줄어들고 불필요한 탐색공간을 감소시킬 수 있다. 성능 평가 결과로 합병 분할 방법(MergeSplit)[8]과 비교해 본결과 EMBR의 총합에 있어서 더 최적의 분할이 된다는 것을 알 수 있었다.
	기존의 색인 방법을 크게 3가지로 나눈다면 어떻게 나눌 수 있는가?	기존의 색인 방법을 보면 크게 3가지로 나눌 수 있는데 첫 번째로 질의의 종류에 따라 이동 객체의 이력 정보를 검색하기 위한 방법[2, 4]과 두 번째로 이동 객체의 궤적을 검색하기 위한 방법[1, 3, 5], 그리고 세 번째로 이동객체 궤적을 분석하여 미래를 예측하기 위한 방법[6, 7]으로 나눌 수 있다.

참고문헌 (9)

D. Pfoser, C. S. Jensen and Y. Tehodoridis, "Novel Approaches to the Indexing of Moving Object Trajectories", Proc of The 26thInternational Conference on Very Large Data Bases, pp. 395-406, 2000
X. Xu. J. Han and W. Lu, "RT-Tree: An Improved R-Tree Indexing Structure for Temporal Spatial Databases", Proc of The International Symposium on Spatial Data Handling, pp. 1040-1049, 1990
D. Pfoser, C. S. Jensen and Y. Tehodoridis, "Novel Approaches to the Indexing of Moving Object Trajectories" Proc of The 26th International Conference on Very Large Data Bases. pp. 395-406. 2000
Y. Theodoridis, M. Vazirgiannis and T. Sellis, "Spatio-Temporal Indexing for Large Multimedia Application", Proc of The 3rd IEEE International Conference onMultimedia Computing ans Systems, pp. 441-448, 1996
J. Nievergelt, H. Hinterberger and K. C. Sevcik, "The Grid File: An Adaptable, Symmetric Multikey File Structure", ACMTransactions on Database System, pp. 38-71, 1984.
T. Tzouramanis, M. Vassilakopoulos, "Overlapping linear quatree: a spatio-temporal acccess method", Proc of the 6th International Symplsium on Advances in Geographic Information System, pp. 1-7, 1998.
V. P. Chakka, A. C. Everspaugh and J. M. Patel, "Indexing Large Trajectory Data SetsWith SETI", Proc of The 1st Biennial Conference on Innovative Data Systems Research, 2003
S. Prabhakar, Y.Xia, D. V. Kalashnikov,W. G. Aref and S. E. Hanbrusch, "Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous on Computers", IEEE Transactions on Computers, pp. 1124-1140, 2002
전현준, 박주현, 박희숙, 조우현, "이동 객체 궤적의 색인을 위한 개선된 분할 알고리즘", 정보처리학회 논문지D, v.16D, No2, pp

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

이동 객체 궤적의 최소경계사각형 영역을 효율적으로 분할하는 알고리즘에 관한 연구
A Study on Efficient Split Algorithm for Minimum Bounding Box of Moving Object Trajectoty 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (9)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

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

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

선택된 텍스트

연합인증

이동 객체 궤적의 최소경계사각형 영역을 효율적으로 분할하는 알고리즘에 관한 연구 A Study on Efficient Split Algorithm for Minimum Bounding Box of Moving Object Trajectoty 원문보기

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

Abstract ▼ AI-Helper

주제어

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

문제 정의

가설 설정

제안 방법

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (9)

이 논문을 인용한 문헌

저자의 다른 논문 :

박주현 (4) 조우현 (11)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

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

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

선택된 텍스트

이동 객체 궤적의 최소경계사각형 영역을 효율적으로 분할하는 알고리즘에 관한 연구
A Study on Efficient Split Algorithm for Minimum Bounding Box of Moving Object Trajectoty 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper