Epsilon-closure for frequent pattern analysis
Methods, systems, and devices supporting epsilon (ε)-closure for frequent pattern (FP) analysis are described. Some database systems may analyze data sets to determine FPs. In some cases, the FP set may include a large number of semi-redundant patterns, resulting in significant memory or processing overhead. To reduce the redundancy of these patterns, the database system may implement pre-configured or dynamic threshold occurrence differences (e.g., ε values) to test against related patterns. For example, the database system may calculate the difference between the data objects covered by a sub-pattern and a super-pattern (e.g., where the super-pattern includes all the same data attributes of the sub-pattern, plus one additional attribute). This difference may be compared to a corresponding ε value, and if the difference is less than the ε value, the database system may remove one of the patterns (e.g., the sub-pattern) from the set of valid FPs to limit redundancy.
1. A method for reducing memory and processor resource overhead associated with frequent pattern (FP) analysis at a database system, comprising:
receiving, at the database system, a data set for FP analysis, the data set comprising a plurality of data objects, wherein each of the plurality of data objects comprises a set of data attributes;
performing, at the database system, an FP analysis procedure on the received data set, wherein the FP analysis procedure comprises:
determining a set of data attribute patterns for the plurality of data objects of the data set, wherein each data attribute pattern of the set of data attribute patterns comprises one or more data attributes and a number of occurrences of the data attribute pattern in the data set;
identifying a data attribute sub-pattern of a data attribute pattern from the set of data attribute patterns, the data attribute pattern comprising a first set of data attributes and the data attribute sub-pattern comprising a subset of the first set of data attributes;
calculating a difference between a number of occurrences of the identified data attribute sub-pattern and the number of occurrences of the data attribute pattern;
comparing the calculated difference to a threshold occurrence difference, the threshold occurrence difference defining a threshold value for a difference between numbers of occurrences for a sub-pattern and a pattern; and
managing memory and processing resource usage at the database system by removing the identified data attribute sub-pattern from the set of data attribute patterns, the removing based at least in part on the comparing and the calculated difference being below the identified threshold occurrence difference; and
transmitting an indication of the set of data attribute patterns resulting from the FP analysis procedure based at least in part on removing the identified data attribute sub-pattern from the set of data attribute patterns.
2. The method of claim 1 , further comprising:
selecting a different threshold occurrence difference based at least in part on a number of data attributes in the data attribute pattern or the data attribute sub-pattern.
3. The method of claim 1 , further comprising:
selecting a different threshold occurrence difference based at least in part on a category of data attributes within the data attribute pattern or based at least in part on a category of data attributes that differs between the data attribute pattern and the data attribute sub-pattern.
4. The method of claim 1 , further comprising:
configuring the threshold occurrence difference.
5. The method of claim 1 , further comprising:
constructing a condensed data structure based at least in part on the data set, wherein the FP analysis procedure is performed using the condensed data structure.
6. The method of claim 5 , wherein the condensed data structure includes a FP-tree including identified patterns and an attribute list including one or more data attributes contained in the data set and a support corresponding to each of the one or more data attributes in the attribute list.
7. The method of claim 1 , wherein each of the plurality of data objects corresponds to a user or a user device.
8. An apparatus for reducing memory and processor resource overhead associated with frequent pattern (FP) analysis at a database system, comprising:
a processor,
memory in electronic communication with the processor; and
instructions stored in the memory and executable by the processor to cause the apparatus to:
receive, at the database system, a data set for FP analysis, the data set comprising a plurality of data objects, wherein each of the plurality of data objects comprises a set of data attributes;
perform, at the database system, an FP analysis procedure on the received data set, wherein the instructions executable by the processor to cause the apparatus to perform the FP analysis procedure comprise instructions executable by the processor to cause the apparatus to:
determine a set of data attribute patterns for the plurality of data objects of the data set, wherein each data attribute pattern of the set of data attribute patterns comprises one or more data attributes and a number of occurrences of the data attribute pattern in the data set;
identify a data attribute sub-pattern of a data attribute pattern from the set of data attribute patterns, the data attribute pattern comprising a first set of data attributes and the data attribute sub-pattern comprising a subset of the first set of data attributes;
calculate a difference between a number of occurrences of the identified data attribute sub-pattern and the number of occurrences of the data attribute pattern;
compare the calculated difference to a threshold occurrence difference, the threshold occurrence difference defining a threshold value for a difference between numbers of occurrences for a sub-pattern and a pattern; and
manage memory and processing resource usage at the database system by removing the identified data attribute sub-pattern from the set of data attribute patterns, the removing based at least in part on the comparing and the calculated difference being below the identified threshold occurrence difference; and
transmit an indication of the set of data attribute patterns resulting from the FP analysis procedure based at least in part on removing the identified data attribute sub-pattern from the set of data attribute patterns.
9. The apparatus of claim 8 , wherein the instructions are further executable by the processor to cause the apparatus to:
select a different threshold occurrence difference based at least in part on a number of data attributes in the data attribute pattern or the data attribute sub-pattern.
10. The apparatus of claim 8 , wherein the instructions are further executable by the processor to cause the apparatus to:
select a different threshold occurrence difference based at least in part on a category of data attributes within the data attribute pattern or based at least in part on a category of data attributes that differs between the data attribute pattern and the data attribute sub-pattern.
11. The apparatus of claim 8 , wherein the instructions are further executable by the processor to cause the apparatus to:
configure the threshold occurrence difference.
12. The apparatus of claim 8 , wherein the instructions are further executable by the processor to cause the apparatus to:
construct a condensed data structure based on the data set, wherein the FP analysis procedure is performed using the condensed data structure.
13. The apparatus of claim 12 , wherein the condensed data structure includes a FP-tree including identified patterns and an attribute list including one or more data attributes contained in the data set and a support corresponding to each of the one or more data attributes in the attribute list.
14. The apparatus of claim 8 , wherein each of the plurality of data objects corresponds to a user or a user device.
15. A non-transitory computer-readable medium storing code for reducing memory and processor resource overhead associated with frequent pattern (FP) analysis at a database system, the code comprising instructions executable by a processor to:
receive, at the database system, a data set for FP analysis, the data set comprising a plurality of data objects, wherein each of the plurality of data objects comprises a set of data attributes;
perform, at the database system, an FP analysis procedure on the received data set, wherein the instructions to perform the FP analysis procedure are executable to:
determine a set of data attribute patterns for the plurality of data objects of the data set, wherein each data attribute pattern of the set of data attribute patterns comprises one or more data attributes and a number of occurrences of the data attribute pattern in the data set;
identify a data attribute sub-pattern of a data attribute pattern from the set of data attribute patterns, the data attribute pattern comprising a first set of data attributes and the data attribute sub-pattern comprising a subset of the first set of data attributes;
calculate a difference between a number of occurrences of the identified data attribute sub-pattern and the number of occurrences of the data attribute pattern;
compare the calculated difference to a threshold occurrence difference, the threshold occurrence difference defining a threshold value for a difference between numbers of occurrences for a sub-pattern and a pattern; and
manage memory and processing resource usage at the database system by removing the identified data attribute sub-pattern from the set of data attribute patterns, the removing based at least in part on the comparing and the calculated difference being below the identified threshold occurrence difference; and
transmit an indication of the set of data attribute patterns resulting from the FP analysis procedure based at least in part on removing the identified data attribute sub-pattern from the set of data attribute patterns.
16. The non-transitory computer-readable medium of claim 15 , wherein the instructions are further executable to:
select a different threshold occurrence difference based at least in part on a number of data attributes in the data attribute pattern or the data attribute sub-pattern.
17. The non-transitory computer-readable medium of claim 15 , wherein the instructions are further executable to:
select a different threshold occurrence difference based at least in part on a category of data attributes within the data attribute pattern or based at least in part on a category of data attributes that differs between the data attribute pattern and the data attribute sub-pattern.
18. The non-transitory computer-readable medium of claim 15 , wherein the instructions are further executable to:
configure the threshold occurrence difference.