Browse Prior Art Database

A Unified Analysis of Batched Searching of Sequential and Tree Structured Files

IP.com Disclosure Number: IPCOM000128314D
Original Publication Date: 1986-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 9 page(s) / 27K

Publishing Venue

Software Patent Institute

Related People

S. D. Lang: AUTHOR [+5]

Abstract

A direct and unified approach is used to analyze the efficiency of batched searching of sequential and tree structured files. The analysis is applicable to arbitrary search distributions, and closed-form expressions are obtained for the expected batched searching cost and savings. Furthermore, four types of uniform (random) search distribution are considered as simple cases; the results refine and extend earlier work in this area.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 18% of the total text.

Page 1 of 9

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Unified Analysis of Batched Searching of Sequential and Tree Structured Files

by

S. D. Lang, J. R. Driscoll, and J. H. Jou

CS-TR-86 A Unified Analysis of Batched Searching of Sequential and Tree Structured Files

S. D. Lang J. R. Driscoll

Department of Computer Science University of Central Florida, Orlando, FL 32816

J. H. Jou

Department of Computer Science University of Texas at Dallas, Richardson, T_X 75080

ABSTRACT

A direct and unified approach is used to analyze the efficiency of batched searching of sequential and tree structured files. The analysis is applicable to arbitrary search distributions, and closed-form expressions are obtained for the expected batched searching cost and savings. Furthermore, four types of uniform (random) search distribution are considered as simple cases; the results refine and extend earlier work in this area.

1. Introduction

The benefit of batched processing is well known for its potential improve-ment. of processor demand and. user response time even for online real-time sys-tems, Shneiderman. and Goodman [1] assessed. the benefit of batched searching of sequential and tree structured files. When the searches are independently and uniformly distributed, they obtained the expected savings of batched searching in a closed-form expression for sequential files, and in a recurrence formula for complete j-ary tree structured files. In a more general context, Batory [2] obtained both lower and upper bound estimates of the expected sav- ings of batched searching using a formula due to Cardenas [~3]. Recently, Palvia [4] analyzed the expected cost and savings of batched searching assuming a CD

different uniform (random) distribution, and obtained closed-form expressions for searching of sequential files and approximate expressions for searching of tree structured files. Also, Piwowarski [5] rounded out the work in [1] and obtained a closed-form expression for the expected savings of batched searching of complete j-ary tree structured files. All these results indicate that batching searches may yield significant savings in disk access, therefore batching is recommended whenever it is permissible given the nature of user requirements.

Although the efficiency of batched searcY.dng has been analyzed for sequen-tial and tree structured files, a common drawback of the existing work is that each analysis is limited to one

University of Central Florida Page 1 Dec 31, 1986

Page 2 of 9

A Unified Analysis of Batched Searching of Sequential and Tree Structured Files

specific search distribution. In addition, the only analyzed tree structured files are completely filled j-ary trees. No precise analysis has been given to more realistic tree structured files such as the B-tree [6] and its variants [7]. even though related work appears in [8, 9].

In this paper we study the efficiency of batched searching from a more gen-eral perspective. A direct and unif...