Generating a Venn diagram using a columnar database management system

• US 10,642,806 B2
• Filed: 05/15/2017
• Issued: 05/05/2020
• Est. Priority Date: 06/20/2013
• Status: Active Grant

• Current Assignee: Open Text Holdings, Inc. (Open Text Corporation)
• Original Assignee: Open Text Holdings, Inc. (Open Text Corporation)
• Inventors: Bayes Martin, Carles, Malo Poyatos, Jesus, Rodriguez Sierra, Marc, Sualdea Perez, Alejandro
• Primary Examiner(s): Yen, Syling
• Application Number:
  US15/595,448
• Publication Number:
  US 20170249343A1
• Time in Patent Office: 1,086 Days
• Field of Search: 707706, 707713, 707722, 707723, 707736, 707758, 707781, 707999003, 3454402, 715758, 715751
• 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 method comprising:

determining, by a computer, a plurality of intersection sets for all combinations of a plurality of input sets of data retrieved from a columnar format database, each intersection set of the plurality of intersections sets determined by the computer using a combination of input sets, the determining comprising;

loading a first combination of input sets of the plurality of input sets of data from the columnar format database,

determining a first intersection set from the first combination of input sets,

selecting a second intersection set based on a second combination of input sets, the second intersection set selected such that the input sets of the second combination include 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 from the second combination of input sets which include data that has been previously loaded with the first combination of input sets;

determining, by the computer, one or more subsets of a Venn diagram based on the plurality of intersection sets, the determining comprising computing a cardinality of each subset of the Venn diagram as a difference of a cardinality of a first intersection set and cardinality of previous computed subsets of the Venn diagram;

storing the one or more subsets of the Venn diagram on a non-transitory computer-readable medium; and

communicating a data mining result including the one or more subsets of the Venn diagram to a client device over a network for display on the client device.

2. The method according to claim 1, further comprising:

receiving a data mining request, the data mining request indicating the input sets; and

subsequent to receiving the data mining request, building a truth table representing combinations of input sets as binary values, wherein positions of bits in a binary value from the truth table correspond to input sets, wherein each bit value determines whether an input set corresponding to a position is included in a combination of the combinations.

3. The method according to claim 2, further comprising:

determining, utilizing the truth table, an order in which steps for generating the Venn diagram are executed.

4. The method according to claim 2, further comprising:

sorting entries in the truth table in an ascending order based on a number of bit positions that are marked as true or one in the combinations corresponding to the entries in the truth table.

5. The method according to claim 4, further comprising, for each non-calculated entry in the truth table for which an intersection set or a cardinality thereof has not yet been determined:

determining, in the ascending order, an intersection set based on whether an input set of data in the combination corresponding to the entry in the truth table is marked as true or one;

subsequent to determining the intersection set for the non-calculated entry in the truth table, determining the cardinality of the non-calculated entry in the truth table;

recording the cardinality thus determined as a partial result for the non-calculated entry in the truth table; and

marking the non-calculated entry in the truth table as having been calculated.

6. The method according to claim 5, further comprising, for each entry in the truth table, in descending order:

determining a final result by subtracting the partial value for the entry by a final result for each other entry in the truth table that includes a higher combination than the combination of the entry and where the higher combination includes the sets of data of the combination of the entry.

7. The method according to claim 6, further comprising:

generating the Venn diagram based on final results determined for the entries in the truth table, wherein the Venn diagram thus generated is communicated to the client device for presentation to a user.

8. A system comprising:

a processor;

a non-transitory computer-readable medium; and

stored instructions translatable by the processor for;

determining a plurality of intersection sets for all combinations of a plurality of input sets of data retrieved from a columnar format database, each intersection set of the plurality of intersections sets determined by using a combination of input sets, the determining comprising;

loading a first combination of input sets of the plurality of input sets of data from the columnar format database,

determining a first intersection set from the first combination of input sets,

selecting a second intersection set based on a second combination of input sets, the second intersection set selected such that the input sets of the second combination include 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 from the second combination of input sets which include data that has been previously loaded with the first combination of input sets;

determining one or more subsets of a Venn diagram based on the plurality of intersection sets, the determining comprising computing a cardinality of each subset of the Venn diagram as a difference of a cardinality of a first intersection set and cardinality of previous computed subsets of the Venn diagram;

storing the one or more subsets of the Venn diagram; and

communicating a data mining result including the one or more subsets of the Venn diagram to a client device over a network for display on the client device.

9. The system of claim 8, wherein the stored instructions are further translatable by the processor for:

receiving a data mining request, the data mining request indicating the input sets; and

subsequent to receiving the data mining request, building a truth table representing combinations of input sets as binary values, wherein positions of bits in a binary value from the truth table correspond to input sets, wherein each bit value determines whether an input set corresponding to a position is included in a combination of the combinations.

10. The system of claim 9, wherein the stored instructions are further translatable by the processor for:

determining, utilizing the truth table, an order in which steps for generating the Venn diagram are executed.

11. The system of claim 9, wherein the stored instructions are further translatable by the processor for:

sorting entries in the truth table in an ascending order based on a number of bit positions that are marked as true or one in the combinations corresponding to the entries in the truth table.

12. The system of claim 11, wherein the stored instructions are further translatable by the processor for, for each non-calculated entry in the truth table for which an intersection set or a cardinality thereof has not yet been determined:

determining, in the ascending order, an intersection set based on whether an input set of data in the combination corresponding to the entry in the truth table is marked as true or one;

subsequent to determining the intersection set for the non-calculated entry in the truth table, determining the cardinality of the non-calculated entry in the truth table;

recording the cardinality thus determined as a partial result for the non-calculated entry in the truth table; and

marking the non-calculated entry in the truth table as having been calculated.

13. The system of claim 12, wherein the stored instructions are further translatable by the processor for, for each entry in the truth table, in descending order:

determining a final result by subtracting the partial value for the entry by a final result for each other entry in the truth table that includes a higher combination than the combination of the entry and where the higher combination includes the sets of data of the combination of the entry.

14. The system of claim 13, wherein the stored instructions are further translatable by the processor for:

generating the Venn diagram based on final results determined for the entries in the truth table, wherein the Venn diagram thus generated is communicated to the client device for presentation to a user.

15. A computer program product comprising a non-transitory computer-readable medium storing instructions translatable by a processor for:

determining a plurality of intersection sets for all combinations of a plurality of input sets of data retrieved from a columnar format database, each intersection set of the plurality of intersections sets determined by using a combination of input sets, the determining comprising;

loading a first combination of input sets of the plurality of input sets of data from the columnar format database,

determining a first intersection set from the first combination of input sets,

selecting a second intersection set based on a second combination of input sets, the second intersection set selected such that the input sets of the second combination include 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 from the second combination of input sets which include data that has been previously loaded with the first combination of input sets;

determining one or more subsets of a Venn diagram based on the plurality of intersection sets, the determining comprising computing a cardinality of each subset of the Venn diagram as a difference of a cardinality of a first intersection set and cardinality of previous computed subsets of the Venn diagram;

storing the one or more subsets of the Venn diagram; and

communicating a data mining result including the one or more subsets of the Venn diagram to a client device over a network for display on the client device.

16. The computer program product of claim 15, wherein the instructions are further translatable by the processor for:

receiving a data mining request, the data mining request indicating the input sets; and

subsequent to receiving the data mining request, building a truth table representing combinations of input sets as binary values, wherein positions of bits in a binary value from the truth table correspond to input sets, wherein each bit value determines whether an input set corresponding to a position is included in a combination of the combinations.

17. The computer program product of claim 16, wherein the instructions are further translatable by the processor for:

sorting entries in the truth table in an ascending order based on a number of bit positions that are marked as true or one in the combinations corresponding to the entries in the truth table.

18. The computer program product of claim 17, wherein the instructions are further translatable by the processor for, for each non-calculated entry in the truth table for which an intersection set or a cardinality thereof has not yet been determined:

determining, in the ascending order, an intersection set based on whether an input set of data in the combination corresponding to the entry in the truth table is marked as true or one;

subsequent to determining the intersection set for the non-calculated entry in the truth table, determining the cardinality of the non-calculated entry in the truth table;

recording the cardinality thus determined as a partial result for the non-calculated entry in the truth table; and

marking the non-calculated entry in the truth table as having been calculated.

19. The computer program product of claim 18, wherein the instructions are further translatable by the processor for, for each entry in the truth table, in descending order:

determining a final result by subtracting the partial value for the entry by a final result for each other entry in the truth table that includes a higher combination than the combination of the entry and where the higher combination includes the sets of data of the combination of the entry.

20. The computer program product of claim 19, wherein the instructions are further translatable by the processor for:

generating the Venn diagram based on final results determined for the entries in the truth table, wherein the Venn diagram thus generated is communicated to the client device for presentation to a user.