Tableau Software, Inc.

Daniel Ting

Richard Lee Cole

Liqi Xu

Justin Talbot

A method for generating schemas to compress storage of denormalized data includes receiving user selection of an initial data table and constructing a snowflake schema to decompose the initial data table into a plurality of tables. Tables in the plurality of tables that are related to one another are connected by foreign keys. The snowflake schema is constructed according to a cost model that balances the cost of storing the plurality of tables and the cost of storing the foreign keys. The method also includes transforming data in the initial data table into the plurality of tables according to the snowflake schema.

Database normalization using statistical analysis

A method selects a federation engine to process a query. The system receives a query that specifies retrieval of data from multiple data sources at distinct physical locations. The system generates multiple federated query plans. Each federated query plan specifies execution of the query using a respective data source as the federation engine. For each federated query plan, the system forms a feature vector including two or more of: (1) a remote cost estimate for executing query operators on data sources distinct from the respective data source; (2) a local cost estimate for executing query operators on the respective data source; and (3) a data transfer cost estimate for transferring partial results from external data sources to the respective data source. The system predicts runtime for each federated query plan, selects a preferred federated query plan using the predicted runtimes, and the preferred federated query plan specifies the federation engine.

Federated query optimization

A method builds a regression model for predicting processing times for federated queries using a variety of data sources. The method includes obtaining federated queries (e.g., from benchmarks), and generates a plurality of federated query plans for each federated query. Each federated query plan corresponds to executing a respective federated query using a respective data source as the federation engine. The method includes forming feature vectors for each federated query plan based on cost estimations for executing the respective federated query plan and cost estimations for data transfer. The method further includes training a regression model, using the feature vectors for the plurality of federated query plans, to predict runtimes for executing federated queries using the variety of data sources as a federation engine. Some implementations use the trained regression model to determine a suitable federation engine for a given federated query.

A method samples a stream of data items. Each data item has an associated timestamp. The method assigns a priority value to each data item. Each data item is represented as a point on a two-dimensional graph whose axes are time and priority. A sliding window covers a predetermined length of time tand uses a backward probability decay curve to specify what priority values are included in the sliding window. This defines, for a current time t, a current data sample consisting of data items whose timestamps t fall within the time span t&#x2212;t&#x2264;t&#x2264;tand have priority values below the decay curve. The data sample is stored in a buffer. The process iteratively moves the sliding window forward by a time increment, creating a provisional data sample. When the size of the provisional data sample is too large or too small, the process scales the decay curve.

Sampling in sliding windows with tight optimality and time decayed design

Data items are aggregated in a quantile sketch according to a compactor hierarchy. A first number of data items are stored in a first buffer corresponding to a first (i.e., lowest) compaction level of the compactor hierarchy, and a top level number of data items are stored in a top buffer corresponding to a top compaction level of the compactor hierarchy. For a first subset of the first number of data items, each data item is already stored in the top buffer, and a weight of the respective data item stored in the top buffer is increased by 1. For a second subset of the first number of data items, each data item does not match any data item stored in the top buffer, and a second number of data items are selected from the second subset and stored in a second buffer of a second compaction level.

Quantile data sketches based on frequent data items

A method estimates counts of distinct items. A system allocates a matrix B in memory and receives a data stream including many data items. Each item includes a set of query fields and a set of identifier fields. For each item, the system computes a row for the data item by hashing data values of the identifier fields. The system also computes a column for the data item by hashing a combination of data values of the query fields and the row. The system computes a bin value for the item by hashing data values of the identifier fields. The system updates the matrix B by computing B[r,c]=max(v, B[r,c]). Subsequently, the system receives a query key value. For each row in the matrix B, the system computes a column, and estimates the number of data items from the data stream matching the query key.

Computing approximate distinct counts for large datasets

This application is directed to modifying display of data visualizations. A computer system visualizes on its display a set of data in a first data space. A focus point is identified in the first data space and used as a starting point for constructing a set of geodesics, each of which is configured to connect the focus point to a respective data point in the first data space. A plurality of primary eigenvectors are determined in the first data space and they are used to create a second data space having fewer dimensions than the first data space. For each data point, the computer system determines a plurality of projection values associated with the primary eigenvectors. The set of data is re-visualized in the second data space created using the projection values of each data point.

Using visual distortion to emphasize targeted regions of data visualizations according to geodesic curves

A process creates a data sketch for a data set with many rows. A user selects data fields from the data source. The process allocates storage for N bins, where each bin has storage space for a key value and an associated counter value (which is initialized to zero). The process sequentially accesses the rows from the data source (e.g., as a stream). For each row, the process computes a respective key value using data values for the selected data fields. When the respective key value matches a key value for a respective bin, the process increments the counter value for the respective bin. Otherwise, the process identifies a respective bin with a smallest counter value c. The process increments the counter value of the respective bin, and with probability 1/(1+c), replaces the key value of the respective bin with the respective key value.

Growing community of inventors

Seattle, WA, United States of America

Daniel Ting