Generating a Venn Diagram Using a Columnar Database Management System

• US 20140379703A1
• Filed: 06/19/2014
• Published: 12/25/2014
• Est. Priority Date: 06/20/2013
• Status: Active Grant

• Current Assignee: Open Text Holdings, Inc. (Open Text Corporation)
• Original Assignee: Actuate Corporation (Open Text Corporation)
• Inventors: Martn, Carles Bays, Poyatos, Jess Malo, Sierra, Marc Rodrguez, Prez, Alejandro Sualdea
• Granted Patent: US 9,679,000 B2
• Time in Patent Office: Days
• US Class Current: 707/723
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results

Abstract

Venn diagrams are computed for a given plurality of input sets. The process of computing the Venn diagrams is executed on columnar database systems for efficient execution. The computation of various subsets of the Venn diagrams is performed by determining subsets of various combinations of the input sets and computing set differences of the intersection sets. The process orders the execution of various steps of computing the subsets for the Venn diagram in an order that reduces the number of times an input set is loaded. Information describing various subsets of a Venn diagram is used to render the Venn diagram for display, for example, on a client device.

Claims

1. A computer-implemented method for generating information describing Venn diagrams, the method comprising:

receiving a request to determine one or more subsets of a Venn diagram, the request identifying a plurality of input sets of data to be used as input for the Venn diagram, wherein the input sets are stored in a columnar format;

determining, by a computer, a plurality of intersection sets based on the input sets, an intersection set determined using a combination of input sets, the determining comprising;

loading a first combination of input sets for determining a first intersection set,

selecting a second intersection set based on a second combination of input sets, the second intersection set selected responsive to the input sets of the second combination including the input sets of the first combination,

loading input sets of the second combination that are not included in the first combination, and

determining the second intersection set;

determining, by the computer, the one or more subsets of the Venn diagram based on the plurality of intersection sets; and

storing the subsets of the Venn diagram.

2. The computer-implemented method of claim 1, wherein determining a plurality of intersection sets comprises:

building a truth table representing combinations of input sets as binary values, wherein positions of bits in a binary value correspond to input sets and the value of a bit determines whether the input set corresponding to the position of the bit is included in the combination represented by the binary value.

3. The computer-implemented method of claim 2, the method further comprising:

ranking the combinations of input sets based on number of ones in each binary value and using the ranking to select the second intersection set responsive to loading the input sets of the first combination.

4. The computer-implemented method of claim 1, the method further comprising:

ranking the combinations of input sets based on the number of input sets in each combination and using the ranking to select the second intersection set responsive to loading the input sets of the first combination.

5. The computer-implemented method of claim 1, wherein determining the one or more subsets of the Venn diagram based on the plurality of intersection sets further comprises:

determining a subset of the Venn diagram as a set difference of a first intersection set and one or more subsets of the Venn diagram that were previously computed.

6. The computer-implemented method of claim 1, wherein determining cardinality of the one or more subsets of the Venn diagram based on the plurality of intersection sets further comprises:

determining a cardinality of a subset of the Venn diagram as a difference of a cardinality of a first intersection set and cardinality of subsets of the Venn diagram that were previously computed.

7. The computer-implemented method of claim 1, wherein determining the one or more subsets of the Venn diagram based on the plurality of intersection sets comprises:

ranking the combinations of sets based on the number of input sets in each combination; and

processing the combinations of sets in decreasing order of the number of input sets of each combination to determine subsets of the Venn diagram as set difference of intersection sets and previously computed subsets of Venn diagram.

8. The computer-implemented method of claim 1, wherein the inputs sets are stored such that elements of a column are stored adjacent to each other on a secondary storage device.

9. A non-transitory computer readable storage medium storing instructions for:

receiving a request to determine one or more subsets of a Venn diagram, the request identifying a plurality of input sets of data to be used as input for the Venn diagram, wherein the input sets are stored in a columnar format;

determining, by a computer, a plurality of intersection sets based on the input sets, an intersection set determined using a combination of input sets, the determining comprising;

loading a first combination of input sets for determining a first intersection set,

selecting a second intersection set based on a second combination of input sets, the second intersection set selected responsive to the input sets of the second combination including the input sets of the first combination,

loading input sets of the second combination that are not included in the first combination, and

determining the second intersection set;

determining, by the computer, the one or more subsets of the Venn diagram based on the plurality of intersection sets; and

storing the subsets of the Venn diagram.

10. The non-transitory computer readable storage medium of claim 9, wherein determining a plurality of intersection sets comprises:

building a truth table representing combinations of input sets as binary values, wherein positions of bits in a binary value correspond to input sets and the value of a bit determines whether the input set corresponding to the position of the bit is included in the combination represented by the binary value.

11. The non-transitory computer readable storage medium of claim 10, further comprising instructions for:

ranking the combinations of input sets based on number of ones in each binary value and using the ranking to select the second intersection set responsive to loading the input sets of the first combination.

12. The non-transitory computer readable storage medium of claim 9, further comprising instructions for:

ranking the combinations of input sets based on the number of input sets in each combination and using the ranking to select the second intersection set responsive to loading the input sets of the first combination.

13. The non-transitory computer readable storage medium of claim 9, wherein determining the one or more subsets of the Venn diagram based on the plurality of intersection sets further comprises:

determining a subset of the Venn diagram as a set difference of a first intersection set and one or more subsets of the Venn diagram that were previously computed.

14. The non-transitory computer readable storage medium of claim 9, wherein determining cardinality of the one or more subsets of the Venn diagram based on the plurality of intersection sets further comprises:

determining a cardinality of a subset of the Venn diagram as a difference of a cardinality of a first intersection set and cardinality of subsets of the Venn diagram that were previously computed.

15. The non-transitory computer readable storage medium of claim 9, wherein determining the one or more subsets of the Venn diagram based on the plurality of intersection sets comprises:

ranking the combinations of sets based on the number of input sets in each combination; and

processing the combinations of sets in decreasing order of the number of input sets of each combination to determine subsets of the Venn diagram as set difference of intersection sets and previously computed subsets of Venn diagram.

16. A computer-implemented system comprising:

a computer processor; and

a non-transitory computer-readable storage medium storing instructions for;

receiving a request to determine one or more subsets of a Venn diagram, the request identifying a plurality of input sets of data to be used as input for the Venn diagram, wherein the input sets are stored in a columnar format;

determining, by a computer, a plurality of intersection sets based on the input sets, an intersection set determined using a combination of input sets, the determining comprising;

loading a first combination of input sets for determining a first intersection set,

selecting a second intersection set based on a second combination of input sets, the second intersection set selected responsive to the input sets of the second combination including the input sets of the first combination,

loading input sets of the second combination that are not included in the first combination, and

determining the second intersection set;

determining, by the computer, the one or more subsets of the Venn diagram based on the plurality of intersection sets; and

storing the subsets of the Venn diagram.

17. The computer-implemented system of claim 16, wherein determining a plurality of intersection sets comprises:

building a truth table representing combinations of input sets as binary values, wherein positions of bits in a binary value correspond to input sets and the value of a bit determines whether the input set corresponding to the position of the bit is included in the combination represented by the binary value.

18. The computer-implemented system of claim 16, further comprising instructions for:

ranking the combinations of input sets based on the number of input sets in each combination and using the ranking to select the second intersection set responsive to loading the input sets of the first combination.

19. The computer-implemented system of claim 16, wherein determining the one or more subsets of the Venn diagram based on the plurality of intersection sets further comprises:

determining a subset of the Venn diagram as a set difference of a first intersection set and one or more subsets of the Venn diagram that were previously computed.

20. The computer-implemented system of claim 16, wherein determining the one or more subsets of the Venn diagram based on the plurality of intersection sets comprises:

ranking the combinations of sets based on the number of input sets in each combination; and

processing the combinations of sets in decreasing order of the number of input sets of each combination to determine subsets of the Venn diagram as set difference of intersection sets and previously computed subsets of Venn diagram.