Abstract
In order to efficiently evaluate range-aggregate queries in data warehouse environments, several works on data cubes (such as the aggregate cubetree) are proposed. In the aggregate cubetree, each entry in every node stores the aggregate values of its corresponding subtree. Therefore, range-aggregate queries can be processed without visiting the child nodes whose parent nodes are fully included in the query range. However, the aggregate cubetree does not take range queries using partial dimensions and range queries without aggregation operations into account. That is, 1) a great deal of information that is irrelevant to the queries also has to be read from the disk for partially-dimensional range queries and 2) while it improves the performance of range queries with aggregate operations, it degrades the performance of the range queries without aggregate operations. In this paper, we proposed a novel index structure, called Aggregate-Tree (denoted as Ag-Tree), which gets rid of the above-mentioned weaknesses of the aggregate cubetree without any side effects. The experiments and discussions presented in this paper indicate that the new proposal is significant for range queries in data warehouse environments.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chaudhuri, S., Dayal, U.: An overview of data warehousing and OLAP technology. ACM SIGMOD Record 26(1), 65–74 (1997)
Kimball, R.: The Data Warehouse Toolkit. John Wiley, Chichester (1996)
Roussopoulos, N.: Materialized Views and Data Warehouses. ACM SIGMOD Record 27(1), 21–26 (1998)
Gray, J., Bosworth, A., Layman, A., Piramish, H.: Data Cube: A Relational Aggregation Operator Generalizing Group-By, Crosstab, and Sub-Totals. In: Proc. International Conference on Data Engineering (ICDE), pp. 152–159 (1996)
Guttman, A.: R-Trees: A Dynamic Index Structure for Spatial Searching. In: Proc. ACM SIGMOD International Conference on Management of Data, pp. 47–57 (1984)
Ho, C., Agrawal, R., Megiddo, N., Srikant, R.: Range Queries in OLAP Data Cubes. In: Proc. ACM SIGMOD International Conference on Management of Data, pp. 73–88 (1997)
Roussopoulos, N., Kotdis, Y., Roussopoulos, M.: Cubetree: Organization of and Bulk Incremental Update on the Data Cube. In: Proc. ACM SIGMOD International Conference on Management of Data, pp. 89–99 (1997)
Kotdis, Y., Roussopoulos, N.: An Alternative Storage Organization for ROLAP Aggregate Views Based on Cubetrees. In: Proc. ACM SIGMOD International Conference on Management of Data, pp. 249–258 (1998)
Gupta, H.: Selections of Views to Materialize in a Data Warehouse. In: Afrati, F.N., Kolaitis, P.G. (eds.) ICDT 1997. LNCS, vol. 1186, pp. 98–112. Springer, Heidelberg (1996)
Mumick, I.S., Quass, D., Mumick, B.S.: Maintenance of Data Cubes and Summary Tables in a Warehouse. In: Proc. ACM SIGMOD International Conference on Management of Data. Tucson, Arizona, pp. 100–111 (May 1997)
Harinarayan, V., Rajaraman, A., Ullman, J.D.: Implementing data cubes efficiently. In: Proc. ACM SIGMOD International Conference on Management of Data, pp. 205–216 (1996)
Sarawagi, S., Agrawal, R., Gupta, A.: On the computing the data cube. Research Report, IBM Almaden Research Center, Sanjose, Ca (1996)
Beckmann, N., Kriegel, H.P., Schneider, R., Seeger, B.: The R*-tree: an Efficient and Robust Access Method for Points and Pectangles. In: Proc. ACM SIGMOD International Conference on Management of Data, Atlantic City, pp. 322–331 (May 1990)
Agrawal, S., Agrawal, R., Deshpande, P., et al.: On the Computation of Multidimensional Aggregates. In: Proc.International Conference on Very Large Databases (VLDB), pp. 506–521 (August 1996)
Hong, S., Song, B., Lee, S.: Efficient Execution of Range Aggregate Queries in Data Warehouse Environments. In: Kunii, H.S., Jajodia, S., Sølvberg, A. (eds.) ER 2001. LNCS, vol. 2224, pp. 299–310. Springer, Heidelberg (2001)
Feng, Y., Makinouchi, A.: Adaptive R*-tree: An Efficient Access Method for Large Relational Datasets. IEICE Transaction on Information and Systems (submitted)
Zhang, C., Naughton, J., et al.: On Supporting Containment Queries in Relational Database Management Systems. In: Proc. SIGMOD International Conference on Management of Data, pp. 425–436 (2001)
Hjaltason, G.R., Samet, H.: Distance Browsing in Spatial Database. ACM Trans. on Database Systems 24(2), 265–318 (1999)
Lakshmanan, L.V.S., Pei, J., Zhao, Y.: Qctrees: An Efficient Summary Structure for Semantic OLAP. In: Proc. ACM SIGMOD International Conference on Management of Data (2003)
Wang, W., Lu, H., Feng, J., Yu, J.X.: Condensed cube: An Effective Approach to Reducing Data Cube Size. In: Proc.Internatial Conference on Data Engineering (ICDE) (2002)
Xin, D., Han, J., Li, X., Wah, B.W.: Star-cubing: Computing Iceberg Cubes by Top-down and Bottom-up Integration. In: Aberer, K., Koubarakis, M., Kalogeraki, V. (eds.) VLDB 2003. LNCS, vol. 2944, Springer, Heidelberg (2004)
Feng, Y., Makinouchi, A.: Batch-Incremental Nearest Neighbor Search Algorithm and Its Performance Evaluation. IEICE Transaction on Information and Systems E86-D(9), 1856–1867 (2003)
Li, X., Han, J., Gonzalez, H.: High-Dimensional OLAP: A Minimal Cubing Approach. In: Proc. International Conference on Very Large Databases (VLDB), pp. 528–539 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Feng, Y., Makinouchi, A. (2006). Ag-Tree: A Novel Structure for Range Queries in Data Warehouse Environments. In: Li Lee, M., Tan, KL., Wuwongse, V. (eds) Database Systems for Advanced Applications. DASFAA 2006. Lecture Notes in Computer Science, vol 3882. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11733836_35
Download citation
DOI: https://doi.org/10.1007/11733836_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33337-1
Online ISBN: 978-3-540-33338-8
eBook Packages: Computer ScienceComputer Science (R0)