범위 모자이크 질의의 효율적인 수행 = Efficient Execution of Range Mosaic Queries

국문 초록 (Abstract)

질의 영역에 대한 단일 값의 통계 정보를 반환하는 범위 집계 질의와는 달리, 범위 모자이크 질의는 질의 영역 내의 데이타 분포를 모자이크 형태로 반환한다. 즉, 범위 모자이크 질의는 질의 영역을 다차원 격자로 나눈 후, 나뉜 각 영역에 대해 집계값을 구해서 결과로 반환하는 질의이다. 이 논문에서는 범위 모자이크 질의와, 범위 모자이크 질의를 SQL문으로 표현하기 위한 mosaic-by 연산자를 제안한다. 그리고 이 논문에서는 집계 R-트리를 이용한 범위 모자이크 질의의 효율적인 수행 알고리즘을 소개한다. 알고리즘은 모든 모자이크 셀의 집계값을 한 번의 트리 순회만으로 계산하며, 집계 R-트리의 집계값을 이용하여 질의 영역 내의 모든 노드를 접근하지 않고도 작은 수의 노드 접근만으로 질의를 수행할 수 있다. 실험 결과를 통해 제안된 알고리즘이 생성된 데이타와 실제 데이타 모두에 대해 좋은 성능을 보이는 것을 알 수 있다.

다국어 초록 (Multilingual Abstract)

A range mosaic query returns distribution of data within the query region as a pattern of mosaic, whereas a range aggregate query returns a single aggregate value of data within the query region. The range mosaic query divides a query region by a multi-dimensional grid, and calculates aggregate values of grid cells. In this paper, we propose a new type of query, range mosaic query and a new operator, mosaic-by, with which the range mosaic queries can be represented. In addition, we suggest efficient algorithms for processing range mosaic queries using an aggregate R-tree. The algorithm that we present computes aggregate results of every mosaic grid cell by one time traversal of the aggregate R-tree, and efficiently executes the queries with only a small number of node accesses by using the aggregate values of the aggregate R-tree. Our experimental study shows that the range mosaic query algorithm is reliable in terms of performance for several synthetic datasets and a real-world dataset.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. 범위 모자이크 질의
• 4. 실험 및 분석
• 5. 결론
• 참고문헌
• 저자소개

참고문헌 (Reference)

• 1 "http://www.tpc.org/tpch/" 2004.
• 2 "http://www.census.gov/geo/www/tiger/" 2002.
• 3 "The pyramid-technique Towards breaking the curse of dimensionality" ACM Press 142153-, 1998.6
• 4 "Range queries in OLAP data cubes" pp.73- 88. ACM Press 1997.5
• 5 "Progressive approximate aggregate queries with a multi- resolution tree structure" pp.401-412. ACM Press 2001.5
• 6 "Processing range top-k queries in a sparse data cube" CSREA Press 2004.
• 7 "Efficient execution of range aggregate queries in data warehouse environments" Springer 299-310, 2001
• 8 "Efficient OLAP operations in spatial data warehouses" 443-459, 2001.7
• 9 "Data Cube A Relational Aggregation Operator Generalizing, Group-By, Crosstab, and Sub-Totals" 1996.
• 10 "An Overview of Data Warehousing and OLAP Technology" no.1 : 65-74, 1997.
• 11 "An Introduction to Spatial Database Systems" 3 no.4 : 357-399, 1994.
• 12 "Adaptive method for range top-k queries in OLAP data cubes" Springer 2002
• 13 "A dynamic index structure for spatial searching Proceedings ACM SIGMOD International Conference on Management of Data" pp.47-57. ACM Press 19841984.