Systems, devices, and/or methods for managing data

• US 8,166,047 B1
• Filed: 08/06/2008
• Issued: 04/24/2012
• Est. Priority Date: 08/06/2008
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Cohen, Edith, Kaplan, Haim
• Primary Examiner(s): MORRISON, JAY A
• Application Number:
  US12/186,873
• Time in Patent Office: 1,357 Days
• Field of Search: 707/748, 707/999.2, 706/48
• US Class Current: 707/748
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Certain exemplary embodiments can provide a method, which can comprise automatically storing and computing a sketch of a dataset that supports an automatically determined estimator of properties of a dataset. The dataset can be related to any population. For example, the dataset can comprise data flows through a network node (e.g., a router), sales data, and/or marketing data, etc. The estimator can be based upon a sketch of the dataset.

Claims

1. A method, comprising:

sampling a first dataset and a second dataset;

obtaining an all-distance bottom-k sketch of the first dataset and the second dataset;

deriving a k-min sketch from the all-distance bottom-k sketch by utilizing a processor;

obtaining estimators of the all-distance bottom-k sketch from corresponding estimators of the k-min sketch, wherein the estimators of the all-distance bottom-k sketch have exponentially distributed ranks;

computing a rank for a new item received for the first dataset and the second dataset by utilizing the processor, wherein the new item has a distance value;

updating the all-distance bottom-k sketch if the new item has a minimum rank among all items in the all-distance bottom-k sketch having a distance value smaller than the distance value of the new item;

storing the new item and all items in the all-distance bottom-k sketch in order of increasing distances in order of increasing ranks; and

rendering an estimator indicative of a size of a planned dataset to be stored on a memory device, wherein the planned dataset is a union of the first dataset and the second dataset.

2. The method of claim 1, further comprising

testing the all-distance bottom-k sketch to determine whether the all-distance bottom-k sketch will be updated in response to receiving items for the first and second datasets.

3. The method of claim 1, further comprising

causing the all-distance bottom-k sketch to be updated in response to receiving items for the first and second datasets.

4. The method of claim 1, further comprising

updating the all-distance bottom-k sketch in response to receiving items for the first and second datasets;

and

analyzing a number of update operations performed on the all-distance bottom-k sketch.

5. The method of claim 1, further comprising

updating the all-distance bottom-k sketch in response to a determination that a rank value of an item received for the first and second datasets is less than a rank of a k^th smallest current ranked item at a node that has a distance that is at most that of the item received.

6. The method of claim 1, further comprising

calculating a weight of the first and second datasets, wherein the estimator is based upon the weight.

7. The method of claim 1, further comprising

calculating an estimator indicative of selectivity of a sub-population for an input selection predicate of the subpopulation.

8. The method of claim 1, further comprising

estimating a Jaccard similarity of two subsets based on an application of estimators to a bottom-k sketch of a union of the two subsets, wherein the estimator of the properties is based upon the Jaccard similarity.

9. The method of claim 1, wherein

the all-distance bottom-k sketch is maintained based upon new flow records outputted by a statistics collecting module associated with the first and second datasets.

10. The method of claim 1, wherein

items in the all-distance bottom-k set are stored in order of increasing distances from a predetermined location.

11. A system, comprising:

a processor configured to;

sample a first dataset and a second dataset;

obtain an all-distance bottom-k sketch of the first dataset and the second dataset;

derive a k-min sketch from the all-distance bottom-k sketch by utilizing a processor;

obtain estimators of the all-distance bottom-k sketch from corresponding estimators of the k-min sketch, wherein the estimators of the all-distance bottom-k sketch have exponentially distributed ranks;

compute a rank for a new item received for the first dataset and the second dataset by utilizing the processor, wherein the new item has a distance value;

update the all-distance bottom-k sketch if the new item has a minimum rank among all items in the all-distance bottom-k sketch having a distance value smaller than the distance value of the new item;

store the new item and all items in the all-distance bottom-k sketch in order of increasing distances in order of increasing ranks; and

render an estimator indicative of a size of a planned dataset to be stored on a memory device, wherein the planned dataset is a union of the first dataset and the second dataset.

12. The system of claim 11, wherein the processor is configured to calculate an estimator indicative of selectivity of a sub-population for an input selection predicate of the subpopulation.

13. The system of claim 11, wherein the processor is configured to test the all-distance bottom-k sketch to determine whether the all-distance bottom-k sketch is to be updated in response to receiving items for the first and second datasets.

14. The system of claim 11, wherein the processor is configured to store items in the all-distance bottom-k sketch in one of an order of increasing distances from a predetermined location and in an arbitrary order.

15. The system of claim 11, wherein the processor is configured to update the all-distance bottom-k sketch in response to a determination that a rank value of an item received for the first and second datasets is less than a rank of a k^th smallest current ranked item.

16. The system of claim 11, wherein the processor is configured to compute a weight and a distance value for each item in the first and second datasets.

17. The system of claim 11, wherein the exponentially distributed ranks correspond to a sampling method using weighted sampling without replacement.

18. A non-transitory computer-readable medium comprising instructions, which, when loaded and executed by an electronic processor, causes the electronic processor to perform activities comprising:

sampling a first dataset and a second dataset;

obtaining an all-distance bottom-k sketch of the first dataset and the second dataset;

deriving a k-min sketch from the all-distance bottom-k sketch by utilizing a processor;

obtaining estimators of the all-distance bottom-k sketch from corresponding estimators of the k-min sketch, wherein the estimators of the all-distance bottom-k sketch have exponentially distributed ranks;

computing a rank for a new item received for the first dataset and the second dataset by utilizing the processor, wherein the new item has a distance value;

updating the all-distance bottom-k sketch if the new item has a minimum rank among all items in the all-distance bottom-k sketch having a distance value smaller than the distance value of the new item;

storing the new item and all items in the all-distance bottom-k sketch in order of increasing distances in order of increasing ranks; and

rendering an estimator indicative of a size of a planned dataset to be stored on a memory device, wherein the planned dataset is a union of the first dataset and the second dataset.

19. The computer-readable medium of claim 18, further comprising testing the all-distance bottom-k sketch to determine whether the all-distance bottom-k sketch will be updated in response to receiving items for the first and second datasets.

20. The computer-readable medium of claim 18, further comprising maintaining the all-distance bottom-k sketch based upon new flow records outputted by a statistics collecting module associated with the first and second datasets.