Lucent Technologies Inc.

International Business Machines Corporation

At+t Corp.

Brown University

Jeffrey S Vitter

Yossi Matias

Elizabeth A Shriver

Bruce K Hillyer

Rakesh D Barve

Phillip B Gibbons

P Krishnan

Kenneth M Curewitz

Eugene E Lindstrom

Phillio B Gibbons

Neal E Young

A method for scheduling access of data blocks located in a computer system having a plurality of disk drives, each disk drive has a disk cache with a specified fence parameter value coupled to a host computer via a common bus. The method according to one embodiment, comprises the steps of: (a) sequentially accessing each of the disk drives for a predetermined number of iterations to retrieve a predetermined number of data blocks; (b) for a specified number of the iterations, transferring data located in the disk cache to be transferred to the common bus and requesting data corresponding to the following iteration to be transferred to the disk cache; and (c) repeating steps (a) and (b) until the predetermined iterations are completed.

System and method for modeling and optimizing I/O throughput of multiple disks on a bus

A method for estimating and read durations, in response to requests to read data blocks stored in the disk drives in a computer system having a plurality of disk drives. Each disk drive has a disk cache with a non-zero fence parameter value coupled to a host computer via a common bus. The method according to one embodiment, comprises the steps of: (a) measuring an overhead period corresponding to the time during which a request to read is transmitted to a disk drive via the bus; (b) measuring an expected minimum positioning time corresponding to the shortest time required for a disk drive to locate said data block; (c) measuring mechanism-to-cache read time corresponding to the time required for a disk drive to transfer a data portion B,to a disk cache; (d) measuring the time required to transfer data blocks stored in each of said disk caches to the host; and (e) adding the times measured at steps (a) through (d).

A method of implementing approximate data structures is disclosed. The method recognizes that an approximate data structure can be implemented using a mapping of elements in the data strucure and using an exact data strucure on the mapped elements.

Method for implementing approximate data structures using operations on

Online prediction techniques based on data compression principles are employed to make predictions in restricted memory environments. Predictors have data structures in the form of trees that are paged and maintained in a cache on a least recently used replacement basis. A fast sequence of events strategy increments the counts for events at the current node of the predictor.

Online background predictors and prefetchers for locality management

A method for executing an external distribution sort in which the data to be rearranged includes keyed stored records that can be accessed on associative secondary storage. The method steps include random sampling of a certain number of keys and internally sorting the sampled keys; forming equal sized partitions of records in a single pass, each partition of which can fit within internal CPU memory and constitute a range of key values; and associatively retrieving all of the records whose keys lie within a range and internally sorting said records.

Growing community of inventors

Durham, NC, United States of America

Jeffrey S Vitter