Abstract
This paper is about how to efficiently evaluate partially-dimensional range queries, which are often used in many actual applications. If the existing multidimensional indices are employed to evaluate partially-dimensional range queries, then a great deal of information that is irrelevant to the queries also has to be read from disk. A modification of R*-tree is described in this paper to ameliorate such a situation. Discussions and experiments indicate that the proposed modification can clearly improve the performance of partially-dimensional range queries, especially for large datasets.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Markl, V., Zirkel, M., Bayer, R.: Processing Operations with Restrictions in Relational Database Management Systems without External Sorting. In: Proc. ICDE Intl. Conf., pp. 562–571 (1999)
Markl, V., Ramsak, F., Bayer, R.: Improving OLAP Performance by Multidimensional Hierarchical Clustering. In: Proc. IDEAS Intl. Symposium, pp. 165–177 (1999)
Beckmann, N., et al.: The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. In: Proc. ACM SIGMOD Intl. Conf., pp. 322–331 (1990)
Berchtold, S., Keim, D., Kriegel, H.P.: The X-tree: An Index Structure for High-dimensional data. In: Proc. The 22nd VLDB Intl., pp. 28–39 (1996)
Sakurai, Y., Yoshikawa, M., Uemura, S., Kojima, H.: The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation. In: Proc. The 26th VLDB Intl. Conf., pp. 516–526 (2000)
Gaede, V., Gunther, O.: Multidimensional Access Methods. ACM Computing Surveys 30(2), 170–231 (1998)
Cui, Y.: High-Dimensional Indexing, vol. 2341 (Monograph), pp. 9–35. Springer, Heidelberg (2002)
Informix Spatial DataBlade Module. IBM (2004), http://ww306.ibm.com/software/data/Informix/blades/spatial/rtree.html
Hjaltason, G.R.l., Samet, H.: Distance Browsing in Spatial Database. ACM Transactions on Database Systems 24(2), 265–318 (1999)
Hong, S., Song, B., Lee, S.-H.: 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)
Zhang, C., et al.: On Supporting Containment Queries in Relational Database Management Systems. In: Proc. SIGMOD Intl. Conf., pp. 425–436 (2001)
Berchtold, S., Böhm, C., Keim, D.A., Kriegel, H.-P., Xu, X.: Optimal Multidimensional Query Processing Using Tree Striping. In: Kambayashi, Y., Mohania, M., Tjoa, A.M. (eds.) DaWaK 2000. LNCS, vol. 1874, pp. 244–257. Springer, Heidelberg (2000)
Shao, M., et al.: Clotho: Decoupling Memory Page Layout from Storage Organization. In: Proc. VLDB Intl. Conf., pp. 696–707 (2004)
Bhattacharjee, B., et al.: Efficient Query Processing for Multi-Dimensionally Clustered Tables in DB2. In: Proc. VLDB Intl. Conf. (2003)
Feng, Y., Makinouchi, A.: Ag-Tree: A Novel Structure for Range Queries in Data Warehouse Environments. In: Li Lee, M., Tan, K.-L., Wuwongse, V. (eds.) DASFAA 2006. LNCS, vol. 3882, pp. 498–512. Springer, Heidelberg (2006)
Grust, T.: Accelerating XPath Location Steps. In: Proc. ACM SIGMOD International Conference, pp. 109–120 (2002)
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). Efficient Evaluation of Partially-Dimensional Range Queries Using Adaptive R*-tree. In: Bressan, S., Küng, J., Wagner, R. (eds) Database and Expert Systems Applications. DEXA 2006. Lecture Notes in Computer Science, vol 4080. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11827405_67
Download citation
DOI: https://doi.org/10.1007/11827405_67
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37871-6
Online ISBN: 978-3-540-37872-3
eBook Packages: Computer ScienceComputer Science (R0)