Performance and stability analysis of multilevel data structures with deferred reorganization

QSpace/Manakin Repository

Performance and stability analysis of multilevel data structures with deferred reorganization

Show simple item record


dc.contributor.author Chen, Ing-Ray
dc.contributor.author Banawan, Sayed A.
dc.date.accessioned 2009-12-30T08:17:02Z
dc.date.available 2009-12-30T08:17:02Z
dc.date.issued 2002-08-06
dc.identifier.citation Volume: 25 , Issue: 5 en_US
dc.identifier.uri http://dx.doi.org/10.1109/32.815327
dc.identifier.uri http://hdl.handle.net/10576/10585
dc.description.abstract We develop a methodology for analyzing the performance and stability of a server that maintains a multilevel data structure to service a set of access operations for (key, value) records. A subset of the operations executed by the server (e.g., insert and delete) require the multilevel data structure be reorganized so that the sewer can execute all subsequent requests efficiently. We study how often the server should carry out data reorganization (i.e., maintenance) to maximize its performance. If the server is frequently idle then there is no need to impose the reorganization overhead on the operation requests. The reorganization overhead may be completely eliminated by utilizing server-idling periods. If the server is frequently busy, then the reorganization overhead can be minimized by performing a complete reorganization only after the server has served a sufficient number of insert/delete operations so that the amortized cost per operation is small. Therefore, the issue of how often one should perform data reorganization to minimize the average service time depends not only on the multilevel data structure maintained by the server but also on the type and intensity of the system workload. The proposed methodology is exemplified with a two-level sorted file with deferred maintenance. The performance and stability results are compared with those of a single-level binary tree data structure with on-the-fly maintenance. It is shown that deferred maintenance of the two-level sorted file outperforms on-the-fly maintenance of the single-level binary tree in both open and closed systems. Furthermore, deferred maintenance can sustain higher workload intensities without risking system stability en_US
dc.language.iso en en_US
dc.subject multilevel data structures en_US
dc.title Performance and stability analysis of multilevel data structures with deferred reorganization en_US
dc.type Article en_US

Files in this item

Files Size Format View Description
Multilevel.pdf 191.6Kb PDF View/Open Performance and stability analysis of multilevel data structures with deferred reorganization

This item appears in the following Collection(s)

Show simple item record

Search QSpace


Advanced Search

Browse

My Account