Je. Cook et al., A HIGHLY EFFECTIVE PARTITION SELECTION POLICY FOR OBJECT DATABASE GARBAGE COLLECTION, IEEE transactions on knowledge and data engineering, 10(1), 1998, pp. 153-172
Citations number
33
Categorie Soggetti
Computer Science Artificial Intelligence","Computer Science Information Systems","Engineering, Eletrical & Electronic","Computer Science Artificial Intelligence","Computer Science Information Systems
We investigate methods to improve the performance of algorithms for au
tomatic storage reclamation of object databases. These algorithms are
based on a technique called partitioned garbage collection, in which a
subset of the entire database is collected independently of the rest.
We evaluate how different application, database system, and garbage c
ollection implementation parameters affect the performance of garbage
collection in object database systems. We focus specifically on invest
igating the policy that is used to select which partition in the datab
ase should be collected. Three of the policies that we investigate are
based on the intuition that the values of overwritten pointers provid
e good hints about where to find garbage. A fourth policy investigated
chooses the partition with the greatest presence in the I/O buffer. U
sing simulations based on a synthetic database, we show that one of ou
r policies requires less I/O to collect more garbage than any existing
implementable policy. Furthermore, that policy performs close to a lo
cally optimal policy over a wide range of simulation parameters, inclu
ding database size, collection rate. and database connectivity. We als
o show what impact these simulation parameters have on application per
formance and investigate the expected costs and benefits of garbage co
llection in such systems.