Stanford InfoLab Publication Server

OODB Loading Revisited: The Partitioned-List Approach

Wiener, J. and Naughton, J. (1995) OODB Loading Revisited: The Partitioned-List Approach. Technical Report. Stanford InfoLab. (Publication Note: 21th International Conference on Very Large Data Bases (VLDB 1995), September 11-15, 1995, Zurich, Switzerland)




Object-oriented and object-relational databases (OODB) need to be able to load the vast quantities of data that OODB users bring to them. Loading OODB data is significantly more complicated than loading relational data due to the presence of relationships, or references, in the data; the presence of these relationships means that naive loading algorithms are slow to the point of being unusable. In our previous work, we presented the late-invsort algorithm, which performed significantly better than naive algorithms on all the data sets we tested. Unfortunately , further experimentation with the late-invsort algorithm revealed that for large data sets (ones in which a critical data structure of the load algorithm does not fit in the performance of late-invsort rapidly degrades to where it, too, is unusable. In this paper we propose a new algorithm, the partitioned-list algorithm, whose performance almost matches that of late-invsort for smaller data sets but does not degrade for large data sets. W e present a performance study of an implementation within the Shore persistent object repository showing that the partitioned-list algorithm is at least an order of magnitude better than previous algorithms on large data sets. In addition, because loading gigabytes and terabytes of data can take hours, we describe how to checkpoint the partitioned-list algorithm and resume a long-running load after a system crash or other interruption

Item Type:Techreport (Technical Report)
Subjects:Computer Science > Data Integration and Mediation
Related URLs:Project Homepage
ID Code:111
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:14 Jan 2009 14:13

Download statistics

Repository Staff Only: item control page