Patent application number | Description | Published |
20100205588 | GENERAL PURPOSE DISTRIBUTED DATA PARALLEL COMPUTING USING A HIGH LEVEL LANGUAGE - General-purpose distributed data-parallel computing using a high-level language is disclosed. Data parallel portions of a sequential program that is written by a developer in a high-level language are automatically translated into a distributed execution plan. The distributed execution plan is then executed on large compute clusters. Thus, the developer is allowed to write the program using familiar programming constructs in the high level language. Moreover, developers without experience with distributed compute systems are able to take advantage of such systems. | 08-12-2010 |
20100241827 | High Level Programming Extensions For Distributed Data Parallel Processing - General-purpose distributed data-parallel computing using high-level computing languages is described. Data parallel portions of a sequential program that is written by a developer in a high-level language are automatically translated into a distributed execution plan. A set of extensions to a sequential high-level computing language are provided to support distributed parallel computations and to facilitate generation and optimization of distributed execution plans. The extensions are fully integrated with the programming language, thereby enabling developers to write sequential language programs using known constructs while providing the ability to invoke the extensions to enable better generation and optimization of the execution plan for a distributed computing environment. | 09-23-2010 |
20100241828 | General Distributed Reduction For Data Parallel Computing - General-purpose distributed data-parallel computing using high-level computing languages is described. Data parallel portions of a sequential program written in a high-level language are automatically translated into a distributed execution plan. Map and reduction computations are automatically added to the plan. Patterns in the sequential program can be automatically identified to trigger map and reduction processing. Direct invocation of map and reduction processing is also provided. One or more portions of the reduce computation are pushed to the map stage and dynamic aggregation is inserted when possible. The system automatically identifies opportunities for partial reductions and aggregation, but also provides a set of extensions in a high-level computing language for the generation and optimization of the distributed execution plan. The extensions include annotations to declare functions suitable for these optimizations. | 09-23-2010 |
20110072006 | MANAGEMENT OF DATA AND COMPUTATION IN DATA CENTERS - Data and computation may be unified (i.e., integrated) in a data center using a single query interface. Users may interact with the data center via a query interface to provide a query (i.e., a computation) to the data center. The results of the query may be referred to as derived datasets and may be managed by a cache server. In an implementation, a derived dataset is uniquely referenced by the query that computes it. Shared common computations are computed only once and may be reused by other computations. The result of a query may be computed (if not previously cached) and returned to the user. Infrequently used derived datasets may be garbage collected (e.g., deleted or otherwise removed from storage) by a garbage collector. This integration of data and computation provides efficient resource management for data center. | 03-24-2011 |
20120117551 | OPTIMIZATION OF DECLARATIVE QUERIES - Source code is generated that includes one or more iterator-based expressions such as declarative queries. The source code is translated into an intermediate language that classifies operators making up the iterator-based expressions into classes based on whether the operators are aggregating, element-wise, or sink operators. The intermediate language, including the identified classes, is processed using an automaton to replace the iterator-based expressions with one or more equivalent non-iterator-based expressions. Where an iterator-based expression is nested, the nested expression is processed using an equivalent number of nested automatons. The resulting optimized source code may be compiled and executed using fewer virtual function calls than the equivalent non-optimized source code. | 05-10-2012 |
20120246158 | CO-RANGE PARTITION FOR QUERY PLAN OPTIMIZATION AND DATA-PARALLEL PROGRAMMING MODEL - A co-range partitioning scheme that divides multiple static or dynamically generated datasets into balanced partitions using a common set of automatically computed range keys. A co-range partition manager minimizes the number of data partitioning operations for a multi-source operator (e.g., join) by applying a co-range partition on a pair of its predecessor nodes as early as possible in the execution plan graph. Thus, the amount of data being transferred is reduced. By using automatic range and co-range partition for data partitioning tasks, a programming API is enabled that abstracts explicit data partitioning from users to provide a sequential programming model for data-parallel programming in a computer cluster. | 09-27-2012 |
20120290867 | MATRIX COMPUTATION FRAMEWORK - Described herein are technologies pertaining to matrix computation. A computer-executable algorithm that is configured to execute perform a sequence of computations over a matrix tile is received and translated into a global directed acyclic graph that includes vertices that perform a sequence of matrix computations and edges that represent data dependencies amongst vertices. A vertex in the global directed acyclic graph is represented by a local directed acyclic graph that includes vertices that perform a sequence of matrix computations at the block level, thereby facilitating pipelined, data-driven matrix computation. | 11-15-2012 |
20130152057 | OPTIMIZING DATA PARTITIONING FOR DATA-PARALLEL COMPUTING - A data partitioning plan is automatically generated that—given a data-parallel program and a large input dataset, and without having to first run the program on the input dataset—substantially optimizes performance of the distributed execution system that explicitly measures and infers various properties of both data and computation to perform cost estimation and optimization. Estimation may comprise inferring the cost of a candidate data partitioning plan, and optimization may comprise generating an optimal partitioning plan based on the estimated costs of computation and input/output. | 06-13-2013 |
20140164388 | QUERY AND INDEX OVER DOCUMENTS - A document index is generated from a set of documents and is used to identify documents that match one or more queries. A tree is generated for each document with a node corresponding to each object of the document. The nodes of the generated trees are merged or combined to generate the document index, which is itself a tree. In addition, an inverted index is generated for each node of the index that identifies the tree(s) that the node originated from. When a query is received, the query is first executed against the document index tree: during the execution, proper set operations are applied to the inverted indices associated with the nodes matched by the query. The resulted set identifies the documents that may match the query. The query is then executed on the identified documents. | 06-12-2014 |
20140280047 | SCALABLE, SCHEMALESS DOCUMENT QUERY MODEL - Query models for document sets (such as XML documents or records in a relational database) typically involve a schema defining the structure of the documents. However, rigidly defined schemas often raise difficulties with document validation with even inconsequential structural variations. Additionally, queries developed against schema-constrained documents are often sensitive to structural details and variations that are not inconsequential to the query, resulting in inaccurate results and development complications, and that may break upon schema changes. Instead, query models for hierarchically structured documents that enable “twig” queries specifying only the structural details of document nodes that are relevant to the query (e.g., students in a student database having a sibling named “Lee” and a teacher named “Smith,” irrespective of unrelated structural details of the document). Such “twig” query models may enable a more natural query development, and continued accuracy of queries in the event of unrelated schema variations and changes. | 09-18-2014 |
20140324935 | MATRIX COMPUTATION FRAMEWORK - Described herein are technologies pertaining to matrix computation. A computer-executable algorithm that is configured to execute perform a sequence of computations over a matrix tile is received and translated into a global directed acyclic graph that includes vertices that perform a sequence of matrix computations and edges that represent data dependencies amongst vertices. A vertex in the global directed acyclic graph is represented by a local directed acyclic graph that includes vertices that perform a sequence of matrix computations at the block level, thereby facilitating pipelined, data-driven matrix computation. | 10-30-2014 |