MONPAR - A Page Replacement Algorithm for a Spatiotemporal Database

Authors: U. Kalay, O. Kalıpsız

Abstract:

For a spatiotemporal database management system, I/O cost of queries and other operations is an important performance criterion. In order to optimize this cost, an intense research on designing robust index structures has been done in the past decade. With these major considerations, there are still other design issues that deserve addressing due to their direct impact on the I/O cost. Having said this, an efficient buffer management strategy plays a key role on reducing redundant disk access. In this paper, we proposed an efficient buffer strategy for a spatiotemporal database index structure, specifically indexing objects moving over a network of roads. The proposed strategy, namely MONPAR, is based on the data type (i.e. spatiotemporal data) and the structure of the index structure. For the purpose of an experimental evaluation, we set up a simulation environment that counts the number of disk accesses while executing a number of spatiotemporal range-queries over the index. We reiterated simulations with query sets with different distributions, such as uniform query distribution and skewed query distribution. Based on the comparison of our strategy with wellknown page-replacement techniques, like LRU-based and Prioritybased buffers, we conclude that MONPAR behaves better than its competitors for small and medium size buffers under all used query-distributions.

Keywords: Buffer Management, Spatiotemporal databases.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1084590

References:

[1] T.Y. Kahveci, T. Kahveci, A. Singh, "Buffering of Index Structures" in 2000 Proc. SPIE Conf, Boston.
[2] T. Brinkhoff, "A Robust and Self-tuning Page-Replacement Strategy for Spatial Database Systems" in 2002 Proc. Conference on Extending Database Technology (EDBT), pp. 533-552.
[3] G.M. Sacco, "Index Access with a Finite Buffer" in 1997 Proc. of the Very Large Data Bases Conf., pp. 301-309.
[4] V.T. Almeida, R.H. G├╝ting, "Indexing the trajectories of moving objects in networks" GeoInformatica vol.9, no.1, 2005, pp. 33-60.
[5] A. Guttman, "R-trees: A Dynamic Index Structure for Spatial Serching" Proc. ACM SIGMOD, Int-l Conf. Management of Data, 1984, pp. 47-57.
[6] U. Kalay, O. Kal─▒ps─▒z, "Probabilistic Point Queries Over Network-based Movements" Lecture Notes in Computer Science, Springer Verlag, 2005.
[20th Int-l Conf. ISCIS,, Istanbul, 2005]
[7] M. Hadjieleftheriou, Spatial Index Library (SaIL), Available: http://uforia. org/marioh/spatialindex/index.html.