Lucent Technologies Inc.

Ncr Corporation

Avaya Technology LLC

Phillip B Gibbons

Yossi Matias

Viswanath Poosala

Swarup Acharya

Andrew Witkowski

Guy E Blelloch

Abraham Silberschatz

Eran Gabber

Elizabeth A Shriver

Bruce K Hillyer

Sridhar Ramaswamy

David Morris Kristol

Alain Jules Mayer

Sumit Ganguly

Jeffrey S Vitter

Rakesh D Barve

Todd C Mowry

Girija J Narlikar

Shimin Chen

Micah A Adler

For use with a database that accommodates distinct value queries having predicates, a distinct sampling system and a method of distinct sampling. In one embodiment, the distinct sampling system includes a scanning subsystem that is configured to scan each row in the database for a distinct target attribute, employ a hash function to map the distinct target attribute to an attribute priority level, maintain random samples of each row based on a sample priority level and a sample size, and produce a distinct sample therefrom. The distinct sampling system further includes a distinct query estimator that is configured to receive the distinct value queries, cause the distinct value queries to be executed on the distinct sample to retrieve a result, and adjust the result to produce a distinct estimate therefrom.

Distinct sampling system and a method of distinct sampling for optimizing distinct value query estimates

A method for generating an approximate answer to a query in a database environment in which the database has a plurality of base relations. A query relating to a database is received, and an approximate answer to the query is generated such that the approximate answer is based on at least one join synopsis formed from the database. The method further includes steps of forming a sample-tuple set for at least one selected base relation of a plurality of base relations of a database such that each sample-tuple set contains at least one sample tuple from a corresponding base relation, and forming a join synopsis set for each selected base relation such that each join synopsis set contains a join synopsis for each sample tuple in a sample-tuple set. A join synopsis of a sample tuple is based on a join of the sample tuple and at least one descendent relation of the sample tuple. All join synopsis sets form a statistical summary of the database and are stored.

Join synopsis-based approximate query answering

The present invention provides a prefetch system for use with a cache memory associated with a database employing indices. In one embodiment, the prefetch system includes a search subsystem configured to prefetch cache lines containing an index of a node of a tree structure associated with the database. Additionally, the prefetch system also includes a scan subsystem configured to prefetch cache lines based on an index prefetch distance between first and second leaf nodes of the tree structure.

System and method for improving index performance through prefetching

A system for, and method of, generating an alias source address for an electronic mail (&ldquo;e-mail&rdquo;) message having a real source address and a destination address and a computer network, such as the Internet, including the system or the method. In one embodiment, the system includes an alias source address generator that employs the destination address to generate the alias source address. The system further includes an alias source address substitutor that substitutes the alias source address for the real source address. This removes the real source address from the e-mail message and thereby renders the sender, located at the real source address, anonymous. Further-described are systems and methods for forwarding reply e-mail and filtering reply e-mail based on alias source address.

System and method for providing anonymous remailing and filtering of electronic mail

An approximate querying method comprising grouping tuples within a database according to grouping attributes, determining how many tuples are needed to represent each group, selecting the tuples from a corresponding group to create a database sample, and querying the database sample. The database sample yields statistically unbiased answers when queried. The sample may be created and maintained without a priori knowledge of the data distribution within the database or the queries to be performed.

Approximate querying method for databases with multiple grouping attributes

There is provided methods and systems for testing linearizable, linearizable priority, and non-linearizable queues. According to one embodiment of the invention, there is provided a method for verifying correct function of a linearizable queue with respect to a program executed by a plurality of processors in a computer processing system. A distinct-values trace is given that includes operations on the queue and an identifier associated with each of the operations. Each operation is associated with two timestamps respectively corresponding to a start time and an end time of the operation. The method includes the step of matching the operations to generate corresponding operation pairs, based on the identifiers. The function of the queue is identified as correct, when, for any operation pair comprising an enqueue operation e and a corresponding dequeue operation e&prime;, there does not exist another operation pair comprising an enqueue operation d and a corresponding dequeue operation d&prime; such that an end time of the enqueue operation e precedes a start time of the enqueue operation d and an end of the dequeue operation d&prime; precedes a start of the dequeue operation e&prime;.

Methods and systems for testing parallel queues

Method and system for generating a statistical summary of a database using a join synopsis

A parallel processing method involves the steps of determining a sequential ordering of tasks for processing, assigning priorities to available tasks on the basis of the earliest and then later in the sequential ordering, selecting a number of tasks greater than a total number of available parallel processing elements from all available tasks having the highest priorities, partitioning the selected tasks into a number of groups equal to the available number of parallel processing elements, and executing the tasks in the groups in the parallel processing elements. The determining step establishes an ordering with a specific predetermined sequential schedule that is independent of the parallel execution, and the assigning step assigns priorities for parallel execution on the basis of the sequential schedule that is independent of the parallel execution.

Methods and apparatus for scheduling parallel processors

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

Techniques for maintaining a random sample of a relation in a database in the presence of updates to the relation. The random sample of the relation is referred to as a 'backing sample,' and it is maintained in the presence of insert, modify and delete operations involving the relation. When a new tuple is inserted into the relation, a sample of the given tuple is added to the backing sample if the size of the backing sample is below an upper bound. Otherwise, a randomly-selected tuple of the backing sample is replaced with the new tuple if a sample of the new tuple must be inserted into the backing sample to maintain randomness or another characteristic. When a tuple in the relation is the subject of a modify operation, the backing sample is left unchanged if the modify operation does not affect an attribute of interest to an application which uses the backing sample. Otherwise, a value field in a sample of the tuple in the backing sample is updated. When a tuple is deleted from the relation, any sample of that tuple in the backing sample is removed. A new backing sample may be computed if this removal causes the size of the backing sample to fall below a prespecified lower bound. The backing sample can be of a size which is negligible in comparison to the relation, and need only be modified very infrequently. As a result, its overhead in terms of computation time and storage space is minimal.

Maintaining a random sample of a relation in a database in the presence

A system and method for scheduling and controlling delivery of advertising in a communications network and a communications network and remote computer program employing the system or the method. The system includes: (1) a time allocation controller that allocates time available in a particular advertising region in a display device of a remote computer between at least two advertisements as a function of one of a desired user frequency, a desired time frequency, or a desired geometry, for each of the at least two advertisements and (2) data communication controller, coupled to the time allocation controller, that delivers the at least two advertisements to said remote computer for display in the advertising region according to the allocating of the time.

System and method for scheduling and controlling delivery of advertising

Techniques for maintaining an approximate histogram of a relation in a database, in the presence of updates to the relation. The histogram includes a number of subsets, or 'buckets,' each representing at least one possible value of an attribute of the relation. Each of the subsets has a count associated therewith indicative of the frequency of occurrence of the corresponding value of the attribute. After an update to the relation, the counts associated with the subsets are compared to a threshold. If the count associated with a given subset exceeds the threshold, the given subset is separated at its median into two separate subsets. After the separation operation, the two subsets with the lowest counts are combined such that a constant number of subsets are maintained in the histogram, if the total combined count of the subsets does not exceed the threshold. If no two subsets have a total combined count which does not exceed the threshold, the histogram is recomputed from a random sample of the relation. The invention substantially reduces the number of times the histogram must be recomputed from the random sample, and is particularly well-suited for use with approximate equi-depth and compressed histograms.

Incremental maintenance of an approximate histogram in a database system

Parallel processing is performed by determining sequential ordering of tasks for processing, assigning priorities to the tasks available on the basis of the sequential ordering, selecting a number of tasks greater than a total number of available parallel processing elements from all available tasks having the highest priorities, partitioning the selected tasks into a number of groups equal to the available number of parallel processing elements, and executing the tasks in the parallel processing elements.

Methods and means for scheduling parallel processors

A method of estimating the query size of two databases T and R is disclosed. The method uses a threshold value to categorize the databases as dense or sparse. A dense-dense procedure is then applied to the two databases to produce a dense-dense estimate (A.sub.d). A sparse-any procedure that suppresses the dense data items coming from database T is performed which produces a first sparse-any estimate (A.sub.s1). A second sparse-any estimate (A.sub.s2) is then produced by suppressing the dense data items from database R. Ultimately a query size estimate is produced by combining the dense-dense estimate, the first sparse-any estimate and the second sparse-any estimate.

Method for skew resistant join size estimation

A method maintains information associated with items in a database of limited memory which information is used to generate representations of the information such as high-biased histograms. In a first embodiment of the inventive method, information associated with all items with sales above a threshold, together with approximate counts of the items, is maintained. Appropriate choice of a threshold limits the amount of information required to be maintained so as to generate accurate representations of the information with high probability. In a second embodiment of the inventive method, information used to generate a high-biased histogram is maintained within a fixed allotment of memory by dynamic adjusting a threshold which threshold is used to determine a probability with which information is retained in the database.

Growing community of inventors

North Plainfield, NJ, United States of America

Phillip B Gibbons