Representation of an interactive document as a graph of entities

• US 9,304,672 B2
• Filed: 12/17/2010
• Issued: 04/05/2016
• Est. Priority Date: 12/17/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Mital, Vijay, Katzenberger, Gary Shon, Rubin, Darryl Ellis, Reddish, Andrew D., Beckman, Brian C., Colle, Olivier
• Primary Examiner(s): Baderman, Scott
• Assistant Examiner(s): JUNG, SEUNG WOON
• Application Number:
  US12/972,249
• Publication Number:
  US 20120159333A1
• Time in Patent Office: 1,936 Days
• Field of Search: 715/215, 715/234, 715/247, 715/255
• US Class Current: 1/1
• CPC Class Codes: G06F 3/04847 Interaction techniques to control parameter settings, e.g. interaction with sliders or dials
• CPC Class Codes: G06F 9/451 Execution arrangements for user interfaces

Abstract

Techniques for representing and publishing an interactive document useful for analyzing data. The document may be represented as a directed acyclic graph of entities interconnected by edges. The entities may be of multiple types. Yet, a broad range of interactive documents may be represented by a limited number of types of entities and the capabilities to interconnect entities of different types and to share a data schema across entities of different types. A tool may enable a user to author such documents. The tool may also facilitate publishing of the document. For publishing, the document may be converted to an executable form. Prior to such a conversion, the graph may be modified for more efficient processing. The graph may also be partitioned such that portions of the graph, when distributed across tiers of a computing system, such as a cloud-based platform, execute on computing devices that provide efficient operation.

Claims

1. At least one computer storage device, as an article of manufacture or a machine, storing computer-executable instructions that, when executed, perform a method of operating a document authoring tool that authors an interactive document, the method comprising:

receiving a plurality of user inputs defining the interactive document, the plurality of user inputs identifying;

a plurality of entities, at least a portion of the plurality of entities comprising a transformation indicating a relationship between input data and output data of the entity; and

a plurality of edges, each of the edges indicating a data flow between two of the plurality of entities;

verifying, by the document authoring tool, that the plurality of edges interconnecting the plurality of entities form a graph of acyclic nature, and based on the verifying;

prompting, by the document authoring tool to specify one or more additional entities for inclusion in the graph;

including the one or more additional entities and one or more additional edges in the graph based on the specifying of the one or more additional entities;

determining whether the plurality of entities and the one or more additional entities include an entity that receives user interaction;

decomposing the entity into at least two entities based on the determination, wherein a first of the at least two entities has only an input and no outputs and a second of the at least two entities has only an output and no inputs; and

modifying the graph based on at least one criteria related to operation of the interactive document, wherein the document authoring tool verifies that the graph resulting after each modification maintains the acyclic nature of the graph.

2. The computer-readable storage medium of claim 1, wherein:

the method further comprising;

representing the at least one entity in the graph by the at least two entities to maintain the acyclic nature of the graph.

3. The computer-readable storage medium of claim 2, further comprising:

reordering entities in the graph, wherein the reordering comprises reordering an entity having a transform that implements a filter to precede an entity having a transform that implements a computation.

4. The computer-readable storage medium of claim 1, wherein:

modifying the graph based on at least one criteria comprises removing an entity in the graph such that removing the entity reduces amount of processing without changing overall output of the graph.

5. The computer-readable storage medium of claim 1, wherein:

modifying the graph based on at least one criteria comprises merging at least two entities in the graph.

6. The computer-readable storage medium of claim 1, wherein:

modifying the graph based on at least one criteria comprises;

identifying an entity having a transform that receives as input static values; and

replacing the entity with an entity representing pre-computed static values.

7. A computer-implemented method of operating a document authoring tool, the method comprising each of the following as implemented on a processor:

receiving a plurality of user inputs defining the interactive document, the plurality of user inputs identifying;

a plurality of entities, at least a portion of the plurality of entities comprising a transformation indicating a relationship between input data and output data of the entity; and

a plurality of edges, each of the edges indicating a data flow between two of the plurality of entities;

verifying, by the document authoring tool, that the plurality of edges interconnecting the plurality of entities form a graph of acyclic nature, and based on the verifying;

prompting, by the document authoring tool, to specify one or more additional entities for inclusion in the graph;

including the one or more additional entities and one or more additional edges in the graph based on the specifying of the one or more additional entities;

determining whether the plurality of entities and the one or more additional entities include an entity that receives a user interaction;

decomposing the entity into at least two entities based on the determination, wherein one of the two entities has only an input and no outputs and another of the two entities has only an output and no inputs; and

modifying the graph based on at least one criteria related to operation of the interactive document, wherein the document authoring tool verifies that the graph resulting after each modification maintains the acyclic nature of the graph.

8. The computer-implemented method of claim 7, further comprising and based on the verifying:

representing the at least one entity in the graph by the two separate entities to maintain the acyclic nature of the graph.

9. The computer-implemented method of claim 7, further comprising reordering entities in the graph comprising reordering an entity having a transform that implements a filter to precede an entity having a transform that implements a computation.

10. The computer-implemented method of claim 7, wherein modifying the graph based on at least one criteria comprises removing an entity in the graph such that removing the entity reduces amount of processing without changing overall output of the graph.

11. The computer-implemented method of claim 7, wherein modifying the graph based on at least one criteria comprises merging at least two entities in the graph.

12. The computer-implemented method of claim 7, wherein modifying the graph based on at least one criteria comprises:

identifying an entity having a transform that receives as input static values; and

replacing the entity with an entity representing pre-computed static values.

13. A system for processing an interactive document represented by a graph comprising a plurality of entities, the system comprising a processor and a memory, and further comprising:

an authoring tool adapted to receive user input, the user input defining an interactive document by defining a graph comprising;

a plurality of entities, the plurality of entities being of a plurality of types, and at least a portion of the plurality of entities comprising a transformation indicating a relationship between input data and output data of a corresponding entity; and

a plurality of edges, each of the plurality of edges indicating a data flow between two of the plurality of entities;

wherein the authoring tool;

verifies that the graph resulting after each modification maintains the acyclic nature of the graph;

prompts a user to specify additional entities for inclusion in the graph;

includes one or more additional entities and one or more additional edges in the graph based on a user response specifying one or more additional entities;

determines whether the plurality of entities includes an entity that receives user interaction;

decomposes the entity into at least two entities, wherein a first entity of the two entities has only an input and no outputs and a second entity of the two entities has only an output and no inputs; and

modifies the graph based on at least one criteria related to an operation of the interactive document.