최근 무선 컴퓨팅 기술의 발달과 이동객체의 위치를 실시간으로 추적할 수 있는 GPS 기술의 발달로 인하여 물류 및 수송 관리, 디지털 전장, 항공 교통 통제, 위치 기반 서비스 등과 같은 응용 서비스들이 개발되고 있다. 이러한 다양한 응용 서비스들을 지원하는 모바일 ...

최근 무선 컴퓨팅 기술의 발달과 이동객체의 위치를 실시간으로 추적할 수 있는 GPS 기술의 발달로 인하여 물류 및 수송 관리, 디지털 전장, 항공 교통 통제, 위치 기반 서비스 등과 같은 응용 서비스들이 개발되고 있다. 이러한 다양한 응용 서비스들을 지원하는 모바일 데이터 관리 시스템은 시간의 흐름에 따른 이동객체의 빈번한 위치 변화를 신속하게 관리할 수 있어야 한다.
선택율 추정은 질의 최적화를 위한 기법중의 하나이다. 이동객체의 질의에 대한 기존 선택율 추정 기법은 시간에 따른 이동객체의 위치 변화를 요약 정보에 반영하지 못하며, 또한 기존 공간 요약 정보를 확장하여 이용함으로써 선택율 추정시 많은 에러를 발생시키고 있다. 기존 기법들이 이동객체의 위치 정보 변화를 요약 정보에 반영하기 위해서는 요약 정보를 자주 재생성해야 하며, 그러므로 전체 데이터베이스를 자주 스캔해야 하는 문제점을 갖고 있다. 따라서 이 논문에서는 이동객체 질의 선택율 추정 기법을 개발하기 위하여 쿼드 트리 기반의 이동객체 히스토그램 기법을 제안하였다.
이 논문에서 제안한 쿼드 트리 기반의 이동객체 히스토그램을 이용한 질의 선택율 추정에 대한 연구 내용은 다음과 같다.

첫째, 데이터베이스 시스템에서 이동객체의 위치 정보를 다루기 위한 위치 정보 모델을 제시하였다. 이를 위해 2차원 공간에서 이동하는 이동객체를 정의하고, 이동객체가 갖는 시간 및 공간 속성에 대하여 기술하였다. 또한 이동객체 정보를 관리하기 위한 이동객체 데이터베이스를 정의하였다. 또한 이동객체의 질의 유형에 대한 분석을 기반으로 이동객체에 대한 질의 선택율 추정 기법에 대하여 명확히 정의하였으며, 아울러 이동객체의 현재 질의 및 미래 예측 질의를 위한 선택율 추정 공식들을 제시하였다.

둘째, 이동객체의 최신 위치 정보를 요약 정보에 반영하기 위한 이동객체 질의 선택율 추정 기법을 제안하였다. 제안된 기법은 이동객체의 동적인 위치 변화를 요약 정보에 반영하기 위하여, 쿼드 트리를 기반으로 이동객체 히스토그램을 생성토록 하였다. 제안된 기법은 쿼드 트리의 공간 분할시 객체의 속도 정보를 반영하도록 함으로써 히스토그램의 각 버켓에 속하는 객체의 속도 편차를 줄이도록 하였으며, 해쉬 테이블을 이용하여 쿼드 트리의 노드에 해당하는 버켓을 생성함으로써 요약 정보를 이용하기 위해 전체 색인을 모두 스캔해야 하는 부담을 줄일 수 있었다. 또한 색인의 단말 노드에 버켓을 할당할 경우 발생하는 공간 오버헤드를 줄이기 위해 색인의 높이에 따라 버켓을 할당함으로써 버켓의 수를 조정할 수 있도록 하였다.

셋째, 제안된 기법을 이용한 선택율 추정시 소요되는 질의 와 버켓간의 기여도 계산 시간을 줄이기 위해 차원 변환을 이용한 버켓 필터링을 통해 불필요한 버켓들에 대한 질의와의 연산을 수행하지 않도록 하였다. 또한 제안된 기법을 이용한 현재 및 미래 예측 질의 선택율 추정을 위한 알고리즘을 제시하였다.

넷째, 제안된 기법을 구현하고, 기존의 대표적인 요약 기법과의 비교 평가를 통하여 제안된 기법의 성능을 평가하였다. 실험 결과를 토대로 이 논문에서 제안하는 요약 기법이 기존의 요약 기법에 비하여 시간에 따라 변화하는 이동객체의 위치 정보를 잘 반영할 수 있음을 확인하였다.

이 논문에서 제안된 이동객체의 현재 및 미래 위치 정보에 대한 질의 선택율 기법은 기존 연구에서 제시된 방법들 보다 이동객체의 위치 정보를 잘 반영할 수 있으며, 그러므로 정확도 측면에서 상당히 우수한 성능을 가짐을 보였다.
이 논문에서 제안된 기법은 모바일 환경에서 연속적으로 이동하면서 위치 정보를 변경시키는 이동객체의 위치 정보 관리 및 질의 처리를 수행하기 위한 기법이다. 따라서 제안 기법은 차량 추적 시스템, 위치 기반 서비스, 응급 구조 서비스, 그리고 텔레매틱스 서비스 등과 같은 연속적으로 위치를 변경하는 이동객체의 정보를 실시간으로 관리하고 검색하는 응용분야에 활용 가능할 것이다.

Recently, along with the development of wireless computing and GPS technologies, which can support a real-time tracking of moving objects, many applications using the moving object data have been developed. These types of applications include vehicle ...

Recently, along with the development of wireless computing and GPS technologies, which can support a real-time tracking of moving objects, many applications using the moving object data have been developed. These types of applications include vehicle tracking, digital battlefields, airplane traffic management systems, as well as location-based services. Mobile data management systems efficiently supporting such kinds of application services should be able to manage the moving objects that continuously change their positions over time.

Selectivity estimation is one of the query optimization techniques. It is difficult for previous selectivity estimation techniques to apply the real-time position data of moving objects to a synopsis. Therefore, they result in much error when estimating selectivity for queries, because they are based on the extended spatial synopsis which does not consider the property of the moving objects. In order to reduce the estimation error, the existing techniques should often rebuild the synopsis. Consequently problem occurs, that is, the whole database should be read frequently.

In this dissertation, we propose a moving object histogram method based on quad tree to develop a selectivity estimation technique for moving object queries. We then analyze the performance of the proposed method through the implementation and evaluation of the proposed method. The contents of this dissertation are as follows.

First, we describe a location information model and the definition of moving objects in two dimensional space. And we define a moving object database that manages location information of moving object.

Second, we propose a new selectivity estimation method for moving object queries. The proposed method can reflect the location change of moving objects in the synopsis. In order to construct such a synopsis we use quad tree and hash table. Our method can reduce the variance of velocity within a bucket due to the consideration of moving objects’ velocities in the step of spatial partitioning while constructing quad tree. Our method also can reduce the overhead which the whole index should be scanned to use the index based synopsis, since the synopsis of our method maintains as hash table in memory. To reduce the spatial overhead occurring when buckets are assigned to a target node in the index, we adjust the number of buckets according to the height level of the index.

Third, in order to reduce the estimation time, we minimize the number of buckets for which is necessary for selectivity estimation through the bucket filtering based on dimensional transformation. We also suggest a selectivity estimation algorithm for current and future queries.

Finally, we analyze the performance of the proposed method comparing with the existing methods via various performance studies. We will show that the proposed method can reflect the location change of moving objects over time in the synopsis better than the existing methods through the experimental results.

In summary, a new selectivity estimation method for current and future queries on moving objects is introduced in this dissertation. The proposed method has better performance than the existing methods since the location change of moving objects over time in the synopsis is reflected. Our method can manage and process queries on moving objects. Hence, it is able to be used in various location management systems such as vehicle location tracking systems, location based services, telematics services, emergency rescue service, etc in which the location information of moving objects changes over time.

최근 무선 컴퓨팅 기술의 발달과 이동객체의 위치를 실시간으로 추적할 수 있는 GPS 기술의 발달로 인하여 물류 및 수송 관리, 디지털 전장, 항공 교통 통제, 위치 기반 서비스 등과 같은 응용 서비스들이 개발되고 있다. 이러한 다양한 응용 서비스들을 지원하는 모바일 ...

최근 무선 컴퓨팅 기술의 발달과 이동객체의 위치를 실시간으로 추적할 수 있는 GPS 기술의 발달로 인하여 물류 및 수송 관리, 디지털 전장, 항공 교통 통제, 위치 기반 서비스 등과 같은 응용 서비스들이 개발되고 있다. 이러한 다양한 응용 서비스들을 지원하는 모바일 데이터 관리 시스템은 시간의 흐름에 따른 이동객체의 빈번한 위치 변화를 신속하게 관리할 수 있어야 한다.

선택율 추정은 질의 최적화를 위한 기법중의 하나이다. 이동객체의 질의에 대한 기존 선택율 추정 기법은 시간에 따른 이동객체의 위치 변화를 요약 정보에 반영하지 못하며, 또한 기존 공간 요약 정보를 확장하여 이용함으로써 선택율 추정시 많은 에러를 발생시키고 있다. 기존 기법들이 이동객체의 위치 정보 변화를 요약 정보에 반영하기 위해서는 요약 정보를 자주 재생성해야 하며, 그러므로 전체 데이터베이스를 자주 스캔해야 하는 문제점을 갖고 있다. 따라서 이 논문에서는 이동객체 질의 선택율 추정 기법을 개발하기 위하여 쿼드 트리 기반의 이동객체 히스토그램 기법을 제안하였다.

이 논문에서 제안한 쿼드 트리 기반의 이동객체 히스토그램을 이용한 질의 선택율 추정에 대한 연구 내용은 다음과 같다.

첫째, 데이터베이스 시스템에서 이동객체의 위치 정보를 다루기 위한 위치 정보 모델을 제시하였다. 이를 위해 2차원 공간에서 이동하는 이동객체를 정의하고, 이동객체가 갖는 시간 및 공간 속성에 대하여 기술하였다. 또한 이동객체 정보를 관리하기 위한 이동객체 데이터베이스를 정의하였다. 또한 이동객체의 질의 유형에 대한 분석을 기반으로 이동객체에 대한 질의 선택율 추정 기법에 대하여 명확히 정의하였으며, 아울러 이동객체의 현재 질의 및 미래 예측 질의를 위한 선택율 추정 공식들을 제시하였다.

둘째, 이동객체의 최신 위치 정보를 요약 정보에 반영하기 위한 이동객체 질의 선택율 추정 기법을 제안하였다. 제안된 기법은 이동객체의 동적인 위치 변화를 요약 정보에 반영하기 위하여, 쿼드 트리를 기반으로 이동객체 히스토그램을 생성토록 하였다. 제안된 기법은 쿼드 트리의 공간 분할시 객체의 속도 정보를 반영하도록 함으로써 히스토그램의 각 버켓에 속하는 객체의 속도 편차를 줄이도록 하였으며, 해쉬 테이블을 이용하여 쿼드 트리의 노드에 해당하는 버켓을 생성함으로써 요약 정보를 이용하기 위해 전체 색인을 모두 스캔해야 하는 부담을 줄일 수 있었다. 또한 색인의 단말 노드에 버켓을 할당할 경우 발생하는 공간 오버헤드를 줄이기 위해 색인의 높이에 따라 버켓을 할당함으로써 버켓의 수를 조정할 수 있도록 하였다.

셋째, 제안된 기법을 이용한 선택율 추정시 소요되는 질의 와 버켓간의 기여도 계산 시간을 줄이기 위해 차원 변환을 이용한 버켓 필터링을 통해 불필요한 버켓들에 대한 질의와의 연산을 수행하지 않도록 하였다. 또한 제안된 기법을 이용한 현재 및 미래 예측 질의 선택율 추정을 위한 알고리즘을 제시하였다.

넷째, 제안된 기법을 구현하고, 기존의 대표적인 요약 기법과의 비교 평가를 통하여 제안된 기법의 성능을 평가하였다. 실험 결과를 토대로 이 논문에서 제안하는 요약 기법이 기존의 요약 기법에 비하여 시간에 따라 변화하는 이동객체의 위치 정보를 잘 반영할 수 있음을 확인하였다.

이 논문에서 제안된 이동객체의 현재 및 미래 위치 정보에 대한 질의 선택율 기법은 기존 연구에서 제시된 방법들 보다 이동객체의 위치 정보를 잘 반영할 수 있으며, 그러므로 정확도 측면에서 상당히 우수한 성능을 가짐을 보였다.

이 논문에서 제안된 기법은 모바일 환경에서 연속적으로 이동하면서 위치 정보를 변경시키는 이동객체의 위치 정보 관리 및 질의 처리를 수행하기 위한 기법이다. 따라서 제안 기법은 차량 추적 시스템, 위치 기반 서비스, 응급 구조 서비스, 그리고 텔레매틱스 서비스 등과 같은 연속적으로 위치를 변경하는 이동객체의 정보를 실시간으로 관리하고 검색하는 응용분야에 활용 가능할 것이다.

이 논문에서 제안된 이동객체의 현재 및 미래 위치 정보에 대한 질의 선택율 기법은 기존 연구에서 제시된 방법들 보다 이동객체의 위치 정보 변화를 잘 반영할 수 있으며, 그러므로 정확도 측면에서 우수한 성능을 가진다.

이 논문에서 제안된 기법은 모바일 환경에 ...

이 논문에서 제안된 이동객체의 현재 및 미래 위치 정보에 대한 질의 선택율 기법은 기존 연구에서 제시된 방법들 보다 이동객체의 위치 정보 변화를 잘 반영할 수 있으며, 그러므로 정확도 측면에서 우수한 성능을 가진다.

이 논문에서 제안된 기법은 모바일 환경에서 연속적으로 이동하면서 위치 정보를 변경시키는 이동객체의 위치 정보 관리 및 질의 처리를 수행하기 위한 기법이다. 따라서 제안 기법은 차량 추적 시스템, 위치 기반 서비스, 응급 구조 서비스, 그리고 텔레매틱스 서비스 등과 같은 연속적으로 위치를 변경하는 이동객체의 정보를 실시간으로 관리하고 검색하는 응용분야에 활용 가능하다.