Lucent Technologies Inc.

Universita′ Di Pisa

Shanmugavelayut Muthukrishnan

Swarup Acharya

Torsten Suel

Ganapathy Subramanian Sundaram

Viswanath Poosala

Paolo Ferragina

Sachin More

Elizabeth A Shriver

Sanjeev Khanna

Suleyman Cenk Sahinalp

Giovanni Manzini

Michael S Paterson

Fabrizion Luccio

Soumen Chakarbarti

Michael A Bender

A method of structuring and compressing labeled trees of arbitrary degree and shape for optimal succinctness, the method including a transform for compressing and indexing tree shaped data, using path sorting and grouping to linearize labeled tree shaped data into two coordinated arrays, one capturing the structure of the tree and the other capturing the labels of the tree. Additional navigational operations and basic searching may be performed on the transformed data.

Method of structuring and compressing labeled trees of arbitrary degree and shape

In accordance with one embodiment of the invention, a central server system computes a feasible stretch value for use in scheduling the servicing of job requests by a plurality of communication channels. A stretch value provides an indication of the delay experienced by each job request to complete, when the central server processes many jobs concurrently. A processing time is calculated for each job request based on the size of the job request and the bandwidth of the channel. Thereafter, a stretch value is proposed. The server system computes a deadline for each job to be the arrival time of the job request plus the product of the processing time and the proposed stretch value. Thereafter, each job request is scheduled, based on an 'earliest deadline first' arrangement. According to the EDF methodology, the central server schedules for service, via k local channel servers, the job requests, such that the k job requests which have the earliest deadlines are serviced first by the k local channel servers and the remaining job requests are subsequently serviced as the local channel servers become available. The proposed stretch value is deemed feasible if each pending job request can be completed prior to its deadline. If the proposed stretch value is deemed not feasible, it is adjusted iteratively until a feasible stretch value is found. The feasible stretch value is then utilized to schedule the job requests to be serviced by the channels.

Adaptive scheduling of data delivery in a central server

A method and apparatus for scheduling jobs having a staging time and a processing time are described. In one method, the jobs are divided into subsets based on a predetermined criteria such as depending on whether the staging time is longer than the processing time. In this method, the jobs in each subset are ordered independently. The jobs are then scheduled by alternating between the ordered subsets. In a second method, the jobs are again divided into subsets based on a predetermined criteria such as depending on whether the staging time is longer than the processing time. The jobs in each subset are ordered independently. The jobs in one subset are then simply appended to the other subset. In a third method, the jobs are ordered according to a predetermined criterion into a list and are executed by alternating between both ends of the list. The invention is also applicable to scheduling jobs having a destaging time. In this case, the staging time is set equal to the staging time plus the processing time and the processing time is set equal to the processing time plus the destaging time. The jobs are then scheduled according to the second method discussed above.

Method to increase the efficiency of job sequencing from sequential storage

In accordance with one embodiment of the invention, a broadcast server system computes a feasible stretch value for use in scheduling job requests. A stretch value provides an indication of the delay experienced by each job request to complete, when the broadcast server processes many jobs concurrently. A processing time is calculated for each job request based on, the size of the job request and the bandwidth of the server downlink. Thereafter, a stretch value is proposed. The server system computes a deadline for each job to be the arrival time of the job request plus the product of the processing time and the proposed stretch value. Thereafter, each job request is scheduled, based on an &ldquo;earliest deadline first&rdquo; arrangement, wherein the job request that has the earliest deadline is scheduled first, the job request having the next earliest deadline is scheduled second, etc. The proposed stretch value is deemed feasible if each pending job request can be completed prior to its deadline. If the proposed stretch value is deemed not feasible, it is adjusted iteratively until a feasible stretch value is found. The feasible stretch value is then utilized to schedule the job requests to be broadcast by the system. When the broadcast of a job request is completed, all job requests for the same data item, which arrived prior to the start of the broadcast, are eliminated from the pending job requests.

System and method for scheduling on-demand broadcasts for heterogeneous workloads

In accordance with one embodiment, a method for scheduling the servicing of job requests in a point-to-point communication system having a central server providing job requests to a plurality of local channel servers. In a first step, the method receives a new job request at a central server. A performance of each local channel server is measured, and the job request is dispatched to one of the local channel servers for servicing thereby dependent upon the performance of each of the local channel servers. In one embodiment, the job request is dispatched to the local channel servers having the lowest current average flow time. In another embodiment, the job request is dispatched to the local channel server having the lowest current maximum stretch value, wherein a stretch value is a ratio equal to an amount of time required to service a job request while also serving other uncompleted job requests, divided by an amount of time required to service said job request if no other job requests were required to be serviced.

System and method for scheduling data delivery using flow and stretch algorithms

A method and system for efficiently resolving the multi-method dispatching problem provided. The dispatching problem is reduced to geometric problems on multi-dimensional grids and new data structures are provided for the resulting geometric problems. In particular, methods having the same name are mapped to a set of rectangles based on a pair of numbers associated with each argument. The pair of numbers is an interval identifying the position of the argument in a class hierarchy tree. The interval is found by computing an Euler Tour of the class hierarchy tree. For a given method invocation in an object-oriented program, the method invocation is mapped to a point based on one of the numbers in the interval associated with each argument in the invocation. The problem of finding the most specific method for the method invocation is thus transformed into the so-called point enclosure problem in geometry, in which the smallest rectangle is found which encloses a given point. To help find efficient solutions to the point enclosure problem, the set of rectangles is broken into a number of subsets having certain geometric properties and stored in efficient data structures. Queries are performed on the various data structures to find the smallest or minimal rectangle, if any, in the various subsets. The result is either the identification of the minimal rectangle overall, or of an ambiguity requiring resolution by the programmer.

Method and system for supporting multi-method dispatching in object-oriented programming

A system and method for increasing the speed of flow of a quantity of data or of a plurality of data types through a communication system. The communication system comprises a plurality of switches including a source and a sink, each of the switches connected to a neighboring switch by a communication link having a capacity, each of the links having a pair of queue buffers, and one queue buffer of each pair of queue buffers is located at each switch connected by a link. For a single data type, a flow is computed for each link as a function of a last previous amount of flow across the same link. In the multi-data type case, a weighted queue difference is computed as a function of a last previous amount of flow between the same pair of queues and an amount of flow f of said data type i is routed across each said link such that &Sgr; f (&Dgr;&prime; (e)&minus;f ) is maximized. In other embodiments of the invention, the system and method resolves the contention between different data types for the capacity of a communication link with and without a normalization factor, and adjusts flow so as not to exceed the capacity of a communication link or the amount of a data available to be routed by the sending queue buffer.

System and method for increasing the speed of distributed single and multi-commodity flow using second order methods

A method and apparatus for determining an approximated solution to the partitioning of a two or greater dimensional array in an amount of time on the order of O(1). Given a desired maximum weight or a maximum number of partitions, an array of data is partitioned by determining a temporary division of the array of blocks such that each block has a weight of at least two times the desired maximum weight. Within each block, rectangles are determined which contain array elements greater than or equal to an arbitrary value corresponding to a guess at a maximum weight. From among these rectangles, a largest set of independent rectangles is determined, and partitions are defined based on the sides of the largest set of independent rectangles determined for each block. Select ones of the partitions may be deleted until a total number of defined partitions is equal to or less than a desired maximum number of partitions.

Apparatus and method for efficiently partitioning a weighted array

Grid layouts of switching and sorting networks

In accordance with one embodiment of the invention, a server system computes a feasible stretch value for use in scheduling job requests. A stretch value provides an indication of the delay experienced by each job to complete, when the server processes many jobs concurrently. For a set of job requests, a processing time is calculated for each job request based on, for example, the characteristics of the job and the server system. Thereafter, an estimated stretch value for the set is selected. The server system computes a deadline for each job to be the arrival time of the job request plus the product of the processing time and the estimated stretch value. Thereafter, each job request is scheduled, based on an 'earliest deadline first' arrangement, wherein the job request that has the earliest deadline is scheduled first, the job request having the next earliest deadline is scheduled second, etc. The selected stretch value is deemed feasible if each pending job in the set can be completed prior to its deadline. If the selected stretch value is deemed not feasible, it is adjusted iteratively until an appropriate feasible stretch value is found. The appropriate stretch value is then utilized to schedule the job requests to be serviced or processed by the system. According to one embodiment, the feasible stretch value is adjusted until an optimal feasible stretch value is found, which equals the smallest feasible stretch value which permits all pending jobs to be completed prior to their deadline.

System and method for scheduling web servers with a quality-of-service

A novel and unique method, apparatus and programmed storage medium for approximating large data distributions of a database in order to allow a user to accurately analyze the entire data distribution using a limited amount of memory space in a reasonable amount of time. The approximation is based on partitioning the data domain into a number of regions, approximating each region using any well-known technique, and composing the errors of approximation to optimize suitable criteria for approximating the entire data distribution.

Computer method, apparatus and programmed medium for approximating large

A computer method, apparatus and programmed medium for optimizing the number of buckets, and thus minimizing the necessary amount of memory space, needed to construct a histogram of a data distribution contained within a computer database with a cumulative error bounded by a specified threshold. The method according to the present invention allows a user to determine the near-minimal memory space necessary to store an approximation of a database with a maximum error measure at most three times that specified by the user to allow the user to maximize computer resources.

Growing community of inventors

New York, NY, United States of America

Shanmugavelayut Muthukrishnan