Abstract
For a spatial database management system, it is an important goal to minimize the I/O-cost of queries and other operations. Several page-replacement strategies have been proposed and compared for standard database systems. In the context of spatial database systems, however, the impact of buffng techniques has not been considered in detail, yet. In this paper, different page-replacement algorithms are compared for performing spatial queries. This study includes wellknown techniques like LRU and LRU-K as well as new algorithms observing spatial optimization criteria. Experiments show that spatial pagereplacement algorithms outperform LRU buffers for many distributions, but not for all investigated query sets. Therefore, a combination of spatial page-replacement strategies with LRU strategies is proposed and experimentally investigated. An algorithm is presented, which is self-tuning and adapts itself to different or changing query distributions. This adaptable spatial buffer outperforms LRU in respect to the I/O-cost by performance gains of up to 25%.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Beckmann, N., Kriegel, H.-P., Schneider, R., Seeger, B.: The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. In: Proceedings ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, 1990, 322–331.
Brinkho., T., Horn, H., Kriegel, H.-P., Schneider, R.: A Storage and Access Architecture for Efficient Query Processing in Spatial Database Systems. In: Proceedings 3rd International Symposium on Large Spatial Databases, Singapore, 1993. Lecture Notes in Computer Science, Vol. 692, Springer, 357–376.
Chen, C.M., Roussopoulos, N.: Adaptive Database Buffer Allocation Using Query Feedback. In: Proceedings 19th International Conference on Very Large Data Bases, Dublin, Ireland, 1993, 342–353.
Chou, H.T., DeWitt, D.J.: An Evaluation of Buffer Management Strategies for Relational Database Systems. In: Proceedings 11th International Conference on Very Large Data Bases, 1985, Stockholm, Sweden, 127–141.
Guttman, A.: R-trees: A Dynamic Index Structure for Spatial Searching. In: Proceedings ACM SIGMOD International Conference on Management of Data, Boston, 1984, 47–57.
Härder, T., Rahm, E.: Datenbanksysteme: Konzepte und Techniken der Implementierung. Springer, 1999.
IBM: Hard Disk Drives. http://www.storage.ibm.com/hardsoft/diskdrdl.htm
Leutenegger, S.T., Lopez, M.A.: The Effect of Buffering on the Performance of R-Trees. In: Proceedings of the 14th International Conf. on Data Engineering, Orlando, 1998, 164–171.
Ng, R.T., Faloutsos, C., Sellis, T.K.: Flexible Buffer Allocation Based on Marginal Gains. In: Proceedings ACM SIGMOD International Conference on Management of Data, Denver, CO, 1991, 387–396
O’Neil, E.J., O’Neil, P.E., Weikum, G.: The LRU-K Page Replacement Algorithm for Data Disk Buffering. In: Proceedings ACM SIGMOD International Conference on Management of Data, Washington, DC, 1993, 297–306.
Orenstein, J.A., Manola, F.A.: PROBE Spatial Data Modelling and Query Processing in an Image Database Application. IEEE Transactions on Software Engineering, Vol.14, No.5, 1988, 611–629.
Samet, H.: Applications of Spatial Data Structures. Addison-Wesley, 1990.
Stonebraker, M., Frew, J., Gardels, K., Meredith, J.: The SEQUOIA 2000 Storage Benchmark. In: Proceedings ACM SIGMOD International Conference on Management of Data, Washington, DC, 1993, 2–11.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brinkhoff, T. (2002). A Robust and Self-tuning Page-Replacement Strategy for Spatial Database Systems. In: Jensen, C.S., et al. Advances in Database Technology — EDBT 2002. EDBT 2002. Lecture Notes in Computer Science, vol 2287. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45876-X_34
Download citation
DOI: https://doi.org/10.1007/3-540-45876-X_34
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43324-8
Online ISBN: 978-3-540-45876-0
eBook Packages: Springer Book Archive