Real-time adaptive binning

• US 8,909,644 B2
• Filed: 05/24/2012
• Issued: 12/09/2014
• Est. Priority Date: 05/26/2011
• Status: Active Grant

• Current Assignee: NICE Systems Technologies UK Limited (Nice Ltd)
• Original Assignee: NICE Systems Technologies UK Limited (Nice Ltd)
• Inventors: Newnham, Leonard Michael, McFall, Jason Derek
• Primary Examiner(s): Corrielus, Jean M
• Application Number:
  US13/479,911
• Publication Number:
  US 20120303598A1
• Time in Patent Office: 929 Days
• Field of Search: 707/737, 707/736, 707/693, 707/741, 707/764
• US Class Current: 707/737
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/972 Access to data in other repository systems, e.g. legacy data or dynamic Web page generation
• CPC Class Codes: G06F 18/23213 with fixed number of clusters, e.g. K-means clustering
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

In one embodiment, a set of boundaries may be obtained, where the set of boundaries includes boundaries for each of one or more bins. The boundaries for each of the one or more bins may include a lower boundary and an upper boundary, wherein the set of boundaries of the one or more bins together defines a contiguous range of data values capable of being stored in the one or more bins. A data value may be obtained. The data value may be added to one of the one or more bins according to the boundaries of the one or more bins. It may be determined whether to modify the set of boundaries. The set of boundaries may be adjusted according to a result of the determining step.

Claims

1. A method, comprising:

obtaining a set of boundaries, the set of boundaries including boundaries for each of one or more bins, the boundaries for each of the one or more bins including a lower boundary and an upper boundary, wherein the set of boundaries of the one or more bins together define a contiguous range of data values capable of being stored in the one or more bins;

in an incremental process;

obtaining a single data value;

adding the single data value to one of the one or more bins according to the boundaries of the one or more bins;

after adding the single data value, determining by a processor whether to modify the set of boundaries; and

modifying the set of boundaries incrementally after adding the single data value according to a result of the determining step such that the set of boundaries of the one or more bins together continue to define a contiguous range of data values capable of being stored in the one or more bins.

2. The method as recited in claim 1, further comprising:

generating or updating a model based, at least in part, upon a set of data values in at least one of the one or more bins.

3. The method as recited in claim 2, further comprising:

applying the model to generate a customer decision for one or more customers; and

applying the customer decision to the one or more customers.

4. The method as recited in claim 2, further comprising:

applying the model to identify content to serve to one or more customers; and

providing the content to the one or more customers.

5. The method as recited in claim 1, further comprising:

generating a set of indexes based, at least in part, upon a set of data values in at least one of the one or more bins.

6. The method as recited in claim 1, wherein obtaining the set of boundaries, obtaining the single data value, adding the single data value, determining whether to modify the set of boundaries, and modifying the set of boundaries are performed for each one of a plurality of data values, the plurality of data values corresponding to a particular variable, wherein the one or more bins are associated with the particular variable.

7. The method as recited in claim 6, wherein the particular variable is ordinal, continuous, discrete, binary, or nominal.

8. The method as recited in claim 6, wherein adding the data value to one of the bins is performed according to an order determined based, at least in part, upon a type of the particular variable.

9. The method as recited in claim 6, wherein the particular variable is associated with a user feature.

10. The method as recited in claim 1, wherein determining whether to modify the set of boundaries is performed in response to adding the data value to one of the one or more bins.

11. The method as recited in claim 1, wherein the boundaries of each one of the one or more bins define a different corresponding subset of the contiguous range of data values, the subset of the contiguous range of data values being capable of being stored in the corresponding one of the one or more bins.

12. The method as recited in claim 1, further comprising:

ascertaining a number of data values in each of the one or more bins;

wherein determining whether to modify the set of boundaries is performed, at least in part, upon an optimal number of data values in each of the one or more bins and the ascertained number of data values in each of the one or more bins.

13. The method as recited in claim 1, wherein modifying the set of boundaries according to a result of the determining step comprises:

adding a boundary to the boundaries of the one or more bins such that a bin is added to the one or more bins.

14. The method as recited in claim 1, wherein modifying the set of boundaries according to a result of the determining step comprises:

eliminating at least one of the boundaries of at least one of the one or more bins such that at least one of the one or more bins is eliminated.

15. The method as recited in claim 1, wherein determining by a processor whether to modify the set of boundaries comprises determining by the processor whether to perform a boundary adjustment of at least one of the boundaries for at least one of the one or more bins;

and wherein modifying the set of boundaries according to a result of the determining step comprises;

adjusting at least one of the boundaries of at least one of the one or more bins according to the result of the determining step.

16. The method as recited in claim 1, further comprising:

maintaining a set of counts including a count for each unique data value in the plurality of data values, the count indicating a number of times the unique data value occurs in the plurality of data values.

17. The method as recited in claim 1, wherein the data single value is single numerical value.

18. An apparatus, comprising:

a processor; and

a memory, at least one of the processor or the memory being adapted for;

obtaining boundaries for each of one or more bins, the boundaries for each of the one or more bins including a lower boundary and an upper boundary, wherein the boundaries of the one or more bins together define a contiguous range of data values capable of being stored in the one or more bins;

in an incremental process;

obtaining a single data value;

adding the single data value to one of the one or more bins according to the boundaries of the one or more bins;

after adding the single data value, determining whether to perform a boundary adjustment of at least one of the boundaries for at least one of the one or more bins; and

adjusting at least one of the boundaries of at least one of the one or more bins incrementally after adding the single data value according to a result of the determining step such that the boundaries of the one or more bins together continue to define a contiguous range of data values capable of being stored in the one or more bins.

19. The apparatus as recited in claim 18, at least one of the processor or the memory being adapted for performing steps, further comprising:

generating or updating a model based, at least in part, upon a set of data values in at least one of the one or more bins.

20. The apparatus as recited in claim 19, at least one of the processor or the memory being adapted for performing steps, further comprising:

applying the model to generate a customer decision for one or more customers; and

applying the customer decision to the one or more customers.

21. The apparatus as recited in claim 18, wherein obtaining the boundaries, obtaining the single data value, adding the single data value, determining whether to perform the boundary adjustment, and adjusting at least one of the boundaries are performed for each one of a plurality of data values, the plurality of data values corresponding to a particular variable, wherein the one or more bins are associated with the particular variable.

22. The apparatus as recited in claim 18, wherein the boundaries of each one of the one or more bins define a different corresponding subset of the contiguous range of data values, the subset of the contiguous range of data values being capable of being stored in the corresponding one of the one or more bins.

23. The apparatus as recited in claim 18, further comprising:

compressing at least a portion of the data values in at least one of the one or more bins.

24. The apparatus as recited in claim 18, at least one of the processor or the memory being adapted for performing steps, further comprising:

ascertaining a number of data values in each of the one or more bins;

wherein determining whether to adjust at least one of the boundaries of at least one of the one or more bins is performed, at least in part, upon an optimal number of data values in each of the one or more bins and the ascertained number of data values in each of the one or more bins.

25. The apparatus as recited in claim 18, wherein determining whether to perform the boundary adjustment for at least one of the one or more bins comprises calculating a mean-squared error (MSE) between a vector of ideal number of data values per bin and a vector of current number of data values per bin;

and

wherein adjusting at least one of the boundaries of at least one of the one or more bins according to the result of the determining step is performed such that the MSE between the vector of ideal number data values per bin and the vector of current number of data values per bin is minimized.

26. The apparatus as recited in claim 18, wherein determining comprises performing a hill climbing algorithm.

27. The apparatus as recited in claim 18, wherein adjusting at least one of the boundaries of at least one of the one or more bins according to the result of the determining step is performed such that the contiguous range of data values capable of being stored in the one or more bins is increased or decreased.

28. The method as recited in claim 18, wherein determining whether to perform the boundary adjustment for at least one of the one or more bins is performed in response to adding the data single value to one of the one or more bins.

29. The apparatus as recited in claim 18, wherein adjusting at least one of the boundaries of at least one of the one or more bins according to the result of the determining step comprises:

adjusting at least one of the boundaries of at least one of the one or more bins to approximate an optimum number of data values for each of the one or more bins according to a desired distribution.

30. The apparatus as recited in claim 18, wherein determining whether to perform the boundary adjustment comprises:

determining whether to adjust at least one of the boundaries in order to maintain or achieve an approximately optimal distribution of data values in the one or more bins.

31. The apparatus as recited in claim 18, wherein adding the single data value, determining whether to perform the boundary adjustment, and adjusting at least one of the boundaries are performed during an adaptive binning process.

32. The apparatus as recited in claim 18, wherein adjusting at least one of the boundaries of at least one of the one or more bins according to a result of the determining step comprises

adjusting two boundaries of the set of boundaries, wherein the two boundaries separate two adjoining bins in the one or more bins.

33. The apparatus as recited in claim 32, wherein the two boundaries comprise an upper boundary of a first one of the two adjoining bins and a lower boundary of a second one of the two adjoining bins.

34. A non-transitory computer-readable medium storing thereon computer-readable instructions, comprising:

instructions for obtaining boundaries for each of one or more bins, the boundaries for each of the one or more bins including a lower boundary and an upper boundary, wherein the boundaries of the one or more bins together define a contiguous range of data values capable of being stored in the one or more bins;

instructions for an incremental process, the instructions for the incremental process comprise;

instructions for obtaining a single data value;

instructions for adding the single data value to one of the one or more bins according to the boundaries of the one or more bins;

instructions for determining whether to perform a boundary adjustment of at least one of the boundaries for at least one of the one or more bins, after adding the single data value; and

instructions for adjusting at least one of the boundaries of at least one of the one or more bins incrementally after adding the single data value according to a result of the determining step such that the boundaries of the one or more bins together continue to define a contiguous range of data values capable of being stored in the one or more bins.

35. The non-transitory computer-readable medium as recited in claim 34, further comprising:

instructions for generating or updating a model based, at least in part, upon a set of data values in at least one of the one or more bins.

36. The non-transitory computer-readable medium as recited in claim 35, further comprising:

instructions for applying the model to generate a customer decision for one or more customers; and

instructions for applying the customer decision to the one or more customers.

37. The non-transitory computer-readable medium as recited in claim 34, wherein obtaining the boundaries, obtaining the data value, adding the data value, determining whether to perform the boundary adjustment, and adjusting at least one of the boundaries are performed for each one of a plurality of data values, the plurality of data values corresponding to a particular variable, wherein the one or more bins are associated with the particular variable.

38. The non-transitory computer-readable medium as recited in claim 37, further comprising instructions for maintaining a set of counts including a count for each unique data value in the plurality of data values, the count indicating a number of times the unique data value occurs in the plurality of data values.

39. The non-transitory computer-readable medium as recited in claim 38, wherein adding the one of the plurality of data values comprises

determining whether a count for the one of the plurality of data values exists in the set of counts;

and

incrementing or generating the count for the one of the plurality of data values according to a result of determining whether the count for the one of the plurality of data values exists in the set of counts.

40. The non-transitory computer-readable medium as recited in claim 39, further comprising:

instructions for depreciating the count for each other unique data value in the plurality of data values.

41. The non-transitory computer-readable medium as recited in claim 38, further comprising:

instructions for depreciating each count in the set of counts.

42. The non-transitory computer-readable medium as recited in claim 37, wherein each one of the plurality of data values has a time associated therewith, wherein the time indicates when the corresponding one of the plurality of values was obtained or received, the non-transitory computer-readable medium further comprising:

instructions for deleting one or more of the plurality of data values from the one or more bins based, at least in part, upon the time associated therewith.

43. The non-transitory computer-readable medium as recited in claim 37, further comprising:

instructions for depreciating the plurality of data values.

44. The non-transitory computer-readable medium as recited in claim 37, further comprising:

instructions for compressing at least a subset of data values in one of the one or more bins, the subset of data values being a subset of the plurality of data values.

45. The non-transitory computer-readable medium as recited in claim 44, wherein compressing comprises:

merging the subset of data values within the one of the one or more bins to a single merged data value.

46. The non-transitory computer-readable medium as recited in claim 45, further comprising:

maintaining a set of counts including a count for each unique data value in the plurality of data values, the count indicating a number of times the unique data value occurs in the plurality of data values;

wherein merging the subset of data values includes merging the count for each of the subset of the data values to a single count corresponding to the single merged data value.

47. The non-transitory computer-readable medium as recited in claim 34, wherein the one or more data values are added such that the data values are ordered according to an intrinsic or extrinsic order.

48. An apparatus, comprising:

means for obtaining a set of boundaries, the set of boundaries including boundaries for each of one or more bins, the boundaries for each of the one or more bins including a lower boundary and an upper boundary, wherein the set of boundaries of the one or more bins together define a contiguous range of data values capable of being stored in the one or more bins;

means for performing an incremental process, the means for performing the incremental process comprises;

means for obtaining a single data value;

means for adding the single data value to one of the one or more bins according to the boundaries of the one or more bins;

means for determining whether to modify the set of boundaries, after adding the single data value; and

means for modifying the set of boundaries incrementally after adding the single data value according to a result of the determining step such that the set of boundaries together continue to define a contiguous range of data values capable of being stored in the one or more bins.