Distributed set-expression cardinality estimation

• US 20060149744A1
• Filed: 12/30/2004
• Published: 07/06/2006
• Est. Priority Date: 12/30/2004
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Ganguly, Sumit, Rastogi, Rajeev, Garofalakis, Minos N., Das, Abhinandan Sujit
• Granted Patent: US 7,873,689 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/564 Enhancement of application control based on intercepted application data
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70

Abstract

A method and system for answering set-expression cardinality queries while lowering data communication costs by utilizing a coordinator site to provide global knowledge of the distribution of certain frequently occurring stream elements to significantly reduce the transmission of element state information to the central site and, optionally, capturing the semantics of the input set expression in a Boolean logic formula and using models of the formula to determine whether an element state change at a remote site can affect the set expression result.

Claims

1. In a system adapted to receive update streams from a plurality of update stream sites, a method comprising:

establishing, for each of said update stream sites, a respective site charge budget; and

communicating said site charge budgets toward said update stream sites;

each site charge budget being adapted to control an initiation of update stream transmission by restricting transmission of said update stream until a sum of element charges at the respective update stream site exceeds the site charge budget, said element charges being attributed to stream element updates.

2. The method of claim 1, wherein a total error budget comprises the sum of the site charge budgets allocated to each of said update sites, said total error budget being allocated among said update sites in proportion to stream update rates at the sites.

3. The method of claim 1, wherein a total error budget comprises the sum of the site charge budgets allocated to each of said update sites, said total error budget being allocated among said update sites in a manner satisfying the following invariant:

Σ

_jε

_j=ε and

for all j, ε

_j≧

0.

4. The method of claim 1, wherein said update stream elements comprise insertion elements and deletion elements, each of said insertion elements and deletion elements being associated with element charges.

5. The method of claim 4, wherein the element charges are determined by at least one of set expression semantics and global information of element counts.

6. The method of claim 4, wherein insertion element charges and said deletion element charge are determined in a manner satisfying the following invariants:

For each e∈

E−

Ê

, Σ

_jφ

_j⁺(e)≧

1; and

For each e∈

Ê

−

E, Σ

_jφ

_j⁻

(e)≧

1.

7. The method of claim 6, wherein insertion element charges and deletion element charges are determined according to a Boolean logic formula.

8. The method of claim 7, wherein the Boolean logic formula is described as follows:

Ψ

_j⁺=({circumflex over (F)}_EF_E)(Ĝ

_jG_jH); and

Ψ

_j⁻

=({circumflex over (F)}_EF_E)(Ĝ

_jG_jH).

9. The method of claim 8, wherein the Boolean logic formula is used to determine element charges φ

_j⁺(e) and φ

_j⁻

(e) as follows;

10. The method of claim 6, wherein insertion element charges and deletion element charges are determined according to a tree based heuristic that propagates charges in a bottom up manner starting from leaf nodes of a set expression tree, wherein the a charge at a root node is used to determine the element update charge at a given site.

11. The method of claim 10, wherein:

charge triples of the form (a,b,x) are propagated up the expression tree;

leaf nodes are initialized according to the following table;

Stream StateCharge Triples(e ∈

Ŝ

_{i, j} e ∈

F_i) e ∈

S_{i, j}(1, 1, ∞

)e ∈

Ŝ

_{i, j} e ∈

F_i e ∉

S_{i, j}(1, 1, ∞

) (1, 0, i)e ∈

Ŝ

_{i, j} e ∉

F_i e ∉

S_{i, j}(1, 1, ∞

) (1, 0, i)e ∉

Ŝ

_{i, j} e ∈

F_i e ∉

S_{i, j}(1, 1, ∞

) (1, 0, i)e ∉

Ŝ

_{i, j} e ∉

F_i e ∈

S_{i, j}(1, 1, ∞

) (0, 1, i)e ∉

Ŝ

_{i, j} e ∉

F_i e ∉

S_{i, j}(1, 1, ∞

) (1, 0, i)(0, 1, i) (0, 0, ∞

)

; and

the set C={(a,b,x)} of charge triples for each internal node V is computed as follows;

combining pairs of triples (a₁,b₁,x₁) and (a₂,b₂,x₂) from V'"'"'s two children nodes;

calculating a=a₁ op a₂,b=b₁ op b₂, and setting x to one of x₁ or x₂, whichever has the smaller charge index pair <

φ

(S_x,i),x_i>

, where op is the Boolean operation corresponding to the set operation for V.

12. The method of claim 1, wherein:

each of said plurality of update stream sites maintains a summary of its respective update stream, said summary formed using a delete resistant scheme for maintaining distinct sample.

13. The method of claim 12, wherein said summary structure comprises a JD sketch synopsis data structure.

14. A distributed framework for providing a set expression estimation, comprising:

allocating error budgets to each of a plurality of remote sites according to a first set of invariants, each of said remote sites providing a respective update stream to a coordinator site, said update streams including at least one of insert elements and delete elements; and

allocating update stream insert element and delete element charges according to a second set of invariants;

wherein

each of said remote sites accumulating element charges in response to the occurrence of respective update and delete elements;

each of said remote sites transmitting a respective update stream to said coordinator site when an accumulation of element charges exceeds a respective error budget.

15. The distributed framework of claim 14, wherein:

said coordinator site using update streams transmitted by said remote sites to estimate a set expression and its cardinality.

16. The distributed framework of claim 14, wherein said first set of invariants comprises:

Σ

_jε

_j=ε and

for all j, ε

_j≧

0.

17. The distributed framework of claim 14, wherein said second set of invariants comprises:

For each e∈

E−

Ê

, Σ

_jφ

_j⁺(e)≧

1; and

For each e∈

Ê

−

E, Σ

_jφ

_j⁻

(e)≧

1.

18. The distributed framework of claim 14, further comprising:

adapting at least one of said site error budgets, said insert element charges and said delete element charges in response to coordinator site global information.

19. The distributed framework of claim 18, wherein said global information comprises lower bounds on a number of distinct sites at which a stream element is present.

20. The distributed framework of claim 19, wherein:

said site error budget θ

_i(e) is reduced by a factor of 2 if C_i(e) becomes less than θ

_i(e), and doubled if C_i(e) exceeds 4×

θ

_i(e).

21. The distributed framework of claim 19, further comprising:

propagating global knowledge of element counts according to a scheme that satisfies the invariant C_i(e)≧

θ

_i(e).

22. A distributed framework for processing set-expression cardinality queries, wherein:

each update stream site being allocated an error budget adapted to determine when the update stream site communicates stream state information to a central site;

each update stream site associates a charge with every stream element that is inserted or deleted since stream state was previously transmitted to a central site;

each update stream site transmits current stream state information when the sum of its respective element charges exceeds its respective error budget.