이동객체를 위한 현재 질의 선택율 추정 기법 = A Selectivity Estimation Technique for Current Query of Moving Objects

국문 초록 (Abstract)

선택율 추정은 질의 최적화를 위한 기법중의 하나이다. 이동객체에 대한 기존 선택율 추정 기법은 시간에 따른 이동객체의 위치 변화를 요약 정보에 반영하지 못하며, 또한 기존 공간 요약 정보를 확장하여 이용함으로써 선택율 추정시 많은 에러를 발생시키고 있다. 기존 기법들이 이동객체의 위치 정보 변화를 요약 정보에 반영하기 위해서는 요약 정보를 자주 재생성해야 하며, 그러므로 전체 데이터베이스를 자주 스캔해야 하는 문제점을 갖고 있다. 따라서 이 논문에서는 이동객체의 현재 질의에 대한 선택율 추정 기법을 개발하기 위하여 쿼드 트리 기반의 히스토그램 기법을 제안하였다. 또한 제안된 기법의 구현과 평가를 통해 제안된 기법의 성능을 분석하였다. 이 논문에서 제안된 기법은 차량 추적 시스템, 위치 기반 서비스, 응급 구조 서비스, 그리고 텔레매틱스 서비스 등과 같은 연속적으로 위치를 변경하는 이동객체의 정보를 실시간으로 관리하고 검색하는 응용분야에 활용 가능할 것이다.

다국어 초록 (Multilingual Abstract)

Selectivity estimation is one of the query optimization techniques. It is difficult for the previous selectivity estimation techniques for moving objects to apply the position change of moving objects to 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 paper, we proposed a moving object histogram method based on quad tree to develop a selectivity estimation technique for moving object queries. We then analyzed the performance of the proposed method through the implementation and evaluation of the proposed method. Our method can 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.

목차 (Table of Contents)

• 요약
• Abstract
• Ⅰ. 서론
• Ⅱ. 관련연구
• Ⅲ. 쿼트 트리 기반 히스토그램 기법
• Ⅳ. 실험 및 평가
• Ⅴ. 결론
• 참고문헌
• 저자소개

참고문헌 (Reference)

1 "웹 기반 공간데이터 공통 컴포넌트 설계 기법" 9 (9): 31-36, 2004년3월

2 "공간질의 최적화를 위한 선택률 추정 방법" 25 (25): 980-995, 1998년7월

3 "공간 데이터 변환 시스템의 설계 및 구현" 8 (8): 41-46, 2003년12월

4 "“The Design and Analysis of Spatial Data Structures" ” Addison Wesley Publishing Company INC 1994

5 "“Dynamic Maintenance of Data Distribution for Selectivity Estimation" 29-51, 1994

6 "Wavelet-based Cost Estimation for Spatial Queries" 175-196, Jul.2001

7 "Spatio-temporal Histogram" 19-36, 2005.aug

8 "Spatial Selectivity Estimation using Compressed Histogram Information" 489-494, Mar.2005

9 "Selectivity Estimation in Spatial Databases" 13-24, Jun.1999

10 "Selectivity Estimation for Spatio-Temporal Queries to Moving Objects" 440-451, Jun.2002

11 "Selectivity Estimation for Predictive Spatio-Temporal Queries" 417-428, Mar.2003

12 "Query Optimization" 28 (28): 121-123, Mar.1996

13 "Performance Evaluation of Spatio-Temporal Selectivity Estimation Techniques" 202-211, 2003.Jul

14 "On the Generation of Spatiotemporal Datasets" 147-164, Jul.1999

15 "Improved Histograms for Selectivity Estimation of Range Predicates" 294-305, Jun.1996

16 "Histogram -Based Solutions to Diverse Database Estimation Problems" 18 (18): 10-18, Sep.1995

17 "Clustering Moving Objects for Spatio-Temporal Selectivity Estimation" 123-130, 2004.Jan

18 "Analyzing Range Queries on Spatial Data" 525-534, Feb.2000