International Business Machines Corporation

Iowa State University Research Foundation, Inc.

David Paul Woodruff

Kenneth Lee Clarkson

Srikanta Tirthapura

Jelani Osei Nelson

Haim Avron

Grigory Yaroslavtsev

Vikas Sindhwani

Qin Zhang

Christos Boutsidis

Huy Le Nguyen

Moritz Hardt

A lower-dimensional representation (e.g., approximation) of a dataset is determined. The lower-dimensional representation can be used, for example, to perform semantic document analysis. Given a matrix of input data points, where each entry of the matrix indicates a number of times a particular term in a set of terms appears in a particular document in a set of documents, a lower-dimensional compressed matrix is obtained from the matrix by sampling rows of the matrix based on a target rank parameter, a desired accuracy tolerance, leverage scores calculated for the rows, and/or distances from rows of the matrix to a span of the initial set of sampled rows. The compressed matrix is used to determine a similarity metric indicative of a degree of similarity between documents. The documents can then be classified into a same document cluster or different clusters based on whether the similarity metric satisfied a threshold value.

Lower-dimensional subspace approximation of a dataset

Embodiments relate to methodologies and program product is provided for conducting regression analysis. In one embodiment the method includes obtaining data related to a statistical process including a plurality of points in a plurality of dimensions and organizing the plurality of points and the plurality of dimensions in a matrix. The method also includes calculating a vector of a particular measurement such that the measurement equal the number of the plurality of points and calculating a least absolute deviation by determining the number of non-zero entries provided in the matrix.

Robust regression analysis techniques using exponential random variables

A system for retrieving stored data includes memory and a processor. The memory stores a first matrix, A, having dimensions n&#xd7;d, a first sparse matrix, R, and a second sparse matrix, S. The processor receives an input value, k, corresponding to a selected rank to generate a second matrix, AR, by multiplying the first matrix, A, by the first sparse matrix, R. The second matrix, AT, has dimensions n&#xd7;t. The processor generates a third matrix, SA, by multiplying the second sparse matrix, S, by the first matrix, A. The third matrix, SA, has dimensions t'&#xd7;n, and the processor generates a fourth matrix, (SAR), by calculating a Moore-Penrose pseudo-inverse of a matrix, (SAR), and approximating the first matrix, A by generating a fifth matrix, &#xc3;, the fifth matrix defined as AR&#xd7;(SAR)&#xd7;SA.

Information retrieval using sparse matrix sketching

A system, method and computer program product for quickly and approximately solving structured regression problems. In one aspect, the system, method and computer program product are applied to problems that arise naturally in various statistical modeling settings&#x2014;when the design matrix is a Vandermonde matrix or a sequence of such matrices. Using the Vandermonde matrix structure further accelerates the solution of the regression problem, achieving running times that are faster than 'input sparsity'. The modeling framework speedup benefits of randomized regression for solving structured regression problems.

Sketching structured matrices in nonlinear regression problems

One embodiments is a computer-implemented method for finding a CUR decomposition. The method includes constructing, by a computer processor, a matrix C based on a matrix A. A matrix R is constructed based on the matrix A and the matrix C. A matrix U is constructed based on the matrices A, C, and R. The matrices C, U, and R provide a CUR decomposition of the matrix A. The construction of the matrices C, U, and R provide at least one of an input-sparsity-time CUR and a deterministic CUR.

Finding a CUR decomposition

Embodiments of the invention relate to sketching for M-estimators for performing regression. One embodiment includes providing one or more sets of input data. A matrix A and a vector b are generated using the input data. A processor device is used for processing the matrix A and the vector b based on a randomized sketching matrix S. A vector x that minimizes a normalized measure function is determined based on the matrix A and the vector b. A relationship between the input data is determined based on the vector x.

Regression using M-estimators and polynomial kernel support vector machines and principal component regression

Embodiments relate to data processing. A method includes analyzing a plurality of data items in a relational database, where different portions of the data items are stored in a plurality of servers. The method also includes determining a maximum size of a subset of the data items stored in each of at least two servers among the plurality of servers, calculating a logarithm function based on the maximum size of the subset of the data items in each of the two servers, and calculating a highest number of sequences of communications between the two servers such that when the logarithmic function is iteratively applied, a value of the logarithmic function remains smaller than one. A protocol is then generated between the two servers for performing an intersection operation using the highest number of sequences calculated.

Communication and message-efficient protocol for computing the intersection between different sets of data

Embodiments relate to identifying a sketching matrix used by a linear sketch. Aspects include receiving an initial output of the linear sketch, generating a query vector and inputting the query vector into the linear sketch. Aspects further include receiving an revised output of the linear sketch based on inputting the query vector and iteratively repeating the steps of generating the query vector, inputting the query vector into the linear sketch, and receiving an revised output of the linear sketch based on inputting the query vector until the sketching matrix used by the linear sketch can be identified.

Identifying a sketching matrix used by a linear sketch

A mechanism is provided for computing the frequency packets in network devices. Respective packets are associated with entities in a vector, where each of the entities is mapped to corresponding ones of the respective packets, and the entities correspond to computers. Upon a network device receiving the respective packets, a count is individually increased for the respective packets in the vector respectively mapped to the entities, and computing a matrix vector product of a matrix A and the vector. The matrix A is a product of at least a first matrix and a second matrix. The first matrix includes rows and columns where each of the rows has a single random location with a one value and remaining locations with zero values. The matrix vector product is transmitted to a centralized computer for aggregating with other matrix vector products.

Fast distributed database frequency summarization

A method for estimating aggregates over a stream of axis-aligned rectangles, includes: decomposing the stream along one-dimensional intervals, wherein vertices for the rectangle are located in a predetermined grid; assigning each grid row to buckets, wherein the one-dimensional intervals are placed into buckets according to the corresponding rows in which the one-dimensional intervals are positioned; and estimating a sum of a number of grid points touched by at least one of the rectangles in each row of the grid to approximate a volume of the axis-aligned rectangles by: using pairwise-independent hash functions in a multi-dimensional algorithm to determine buckets that include a first interval corresponding to a given rectangle, wherein the interval has hash function results that meet a predetermined threshold; and inserting a second interval for the rectangle corresponding to the first interval into a one-dimensional algorithm for the corresponding bucket meeting the predetermined threshold.

Summarizing a stream of multidimensional, axis-aligned rectangles

A two-party approximation protocol is transformed into a private approximation protocol. A first input x&#x3b5;{0, 1, . . . , M}and a second input y&#x3b5;{0, 1, . . . , M}of a two party approximation protocol approximating a function of a form &#x192;(x, y)=&#x3a3;g (x, y) is received. Variable B is set as a public upper bound on &#x192;(x, y). Variable l is set l=O*(1). The following is performed until or B&#x3c;1, where t is an arbitrary number: (1) a private importance sampling protocol with the first input x, the second input y, and a third input 1, is executed independently for j&#x3b5;[l], where k is a security parameter, an output of the private importance sampling protocol is shares of I&#x3b5;[n]&#x222a;{&#x22a5;}; (2) l coin tosses z, . . . , zare independently generated where z=1 iff I&#x2260;&#x22a5;; and (3) B is divided by 2 if or B&#x3c;1 is not satisfied. When or B&#x3c;1 a private (&#x3b5;, &#x3b4;)-approximation protocol &#x3a8; for &#x192;(x, y)=&#x3a3;g(x, y) is outputted where &#x3b5; is an arbitrary number, and &#x3b4;=exp(&#x2212;k).

Two-party private estimation of dataset similarity

Described herein are approaches for computing correlated aggregates. An aspect provides for receiving a stream of data elements at a device, each data element having at least one numerical attribute; maintaining in memory plurality of tree structures comprising a plurality of separate nodes for summarizing numerical attributes of the data elements with respect to a predicate value of a correlated aggregation query, said maintaining comprising: creating the plurality of tree structures in which each node implements one of: a probabilistic counter and a sketch, wherein said probabilistic counter and said sketch each act to estimate aggregated data element numerical attributes to form a summary of said numerical attributes; and responsive to a correlated aggregation query specifying said predicate value, using said plurality of tree structures as a summary of said data element numerical attributes to compute a response to said correlated aggregate query.

Growing community of inventors

Mountain View, CA, United States of America

David Paul Woodruff