International Business Machines Corporation

Rainer Gemulla

Peter Haas

Wolfgang Lehner

John Sismanis

Kevin Scott Beyer

Berthold Reinwald

Systems and methods directed toward processing optimization problems using loss functions, wherein a loss function is decomposed into at least one stratum loss function, a loss is decreased for each stratum loss function to a predefined stratum loss threshold individually using gradient descent, and the overall loss is decreased to a predefined threshold for the loss function by appropriately ordering the processing of the strata and spending appropriate processing time in each stratum. Other embodiments and aspects are also described herein.

Systems and methods for large-scale randomized optimization for problems with decomposable loss functions

One embodiment of the present invention provides a method for incrementally maintaining a Bernoulli sample S with sampling rate q over a multiset R in the presence of update, delete, and insert transactions. The method includes processing items inserted into R using Bernoulli sampling and augmenting S with tracking counters during this processing. Items deleted from R are processed by using the tracking counters and by removing newly deleted items from S using a calculated probability while maintaining a degree of uniformity in S.

System and method for maintaining and utilizing Bernoulli samples over evolving multisets

The task of estimating the number of distinct values (DVs) in a large dataset arises in a wide variety of settings in computer science and elsewhere. The present invention provides synopses for DV estimation in the setting of a partitioned dataset, as well as corresponding DV estimators that exploit these synopses. Whenever an output compound data partition is created via a multiset operation on a pair of (possibly compound) input partitions, the synopsis for the output partition can be obtained by combining the synopses of the input partitions. If the input partitions are compound partitions, it is not necessary to access the synopses for all the base partitions that were used to construct the input partitions. Superior (in certain cases near-optimal) accuracy in DV estimates is maintained, especially when the synopsis size is small. The synopses can be created in parallel, and can also handle deletions of individual partition elements.

Method for estimating the number of distinct values in a partitioned dataset

A method of incrementally maintaining a stable, bounded, uniform random sample S from a dataset R, in the presence of arbitrary insertions and deletions to the dataset R, and without accesses to the dataset R, comprises a random pairing method in which deletions are uncompensated until compensated by a subsequent insertion (randomly paired to the deletion) by including the insertion's item into S if and only if the uncompensated deletion's item was removed from S (i.e., was in S so that it could be removed). A method for resizing a sample to a new uniform sample of increased size while maintaining a bound on the sample size and balancing cost between dataset accesses and transactions to the dataset is also disclosed. A method for maintaining uniform, bounded samples for a dataset in the presence of growth in size of the dataset is additionally disclosed.

Growing community of inventors

Dresden, Germany

Rainer Gemulla