MONPAR - A Page Replacement Algorithm for a Spatiotemporal Database
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:64203", author = "U. Kalay and O. Kalıpsız", title = "MONPAR - A Page Replacement Algorithm for a Spatiotemporal Database", 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.", volume = "2", number = "11", pages = "3979-5", }