Method and apparatus for filtering streaming data

• US 8,447,718 B2
• Filed: 08/26/2010
• Issued: 05/21/2013
• Est. Priority Date: 11/09/2007
• Status: Active Grant

• Current Assignee: Masimo Corporation
• Original Assignee: Vantrix Corporation
• Inventors: Norton, Richard Elliott, Poirier-Beauchemin, Louis-Rene, Hroux, Robert, Lavalliere, Mario Joseph Leo Claude
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): SITIRICHE, LUIS A
• Application Number:
  US12/869,635
• Publication Number:
  US 20100332618A1
• Time in Patent Office: 999 Days
• Field of Search: None
• US Class Current: 706/47
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A method of content filtering of data containers of multiple content types is based on generating a set of encoded filters and a set of encoded rules for each content type. Each encoded filter is expressed as a respective operator, from among user-defined operators, and two operands including a content descriptor and a descriptor criterion. A filter has a binary state and a rule may be based on a single filter or a number of selected filters. An apparatus implementing the method has a user interface for receiving user-defined configuration data, a configuration module for generating a set of encoded filters and a set of encoded rules for each content type, a network interface for receiving data containers from a network and transmitting filtered data containers to the network, and a filtering module for applying the rules to received data containers.

Claims

1. A device for data-stream filtering, comprising:

a user interface for receiving;

a set of content types;

a set of content descriptors;

a set of descriptors'"'"' criteria;

a set of operators;

a set of filter definitions; and

a set of rule definitions;

a configuration module storing processor-readable instructions which cause a first processor to;

generate encoded filters based on said filter definitions, each encoded filter having a binary state determined by an operator, a content descriptor, and a descriptor criterion;

generate encoded rules based on said rule definitions, each encoded rule having a binary outcome determined according to a binary state of each of at least one filter; and

arrange said encoded rules in hierarchical rule strata where rules within a rule stratum are independent of each other and rules of a rule stratum beyond a root stratum depend on rules of preceding rule strata;

a rule-memory device for storing said encoded rules, said encoded filters, and descriptor definitions;

a network interface for receiving data streams from a network; and

a filtering module for applying said encoded rules to said data streams.

2. The device of claim 1 further comprising an action-memory device for storing a set of actions each action implemented as processor-readable instructions which cause a processor to perform a corresponding editing function of a data container of a data stream.

3. The device of claim 2 further comprising a description-memory device for storing a set of action-descriptions, each action-description containing a natural-language description of a corresponding action within said set of actions.

4. The device of claim 2 further comprising an instructions memory storing processor-readable instructions which cause a second processor to:

extract data containers from said data streams;

parse each data container into components;

determine a content type for each component;

evaluate specific encoded filters and specific encoded rules pertinent to said content type; and

perform actions according to values of said specific encoded rules.

5. The device of claim 4 further comprising processor-readable instructions stored in said instructions memory which cause said second processor to

read a description of each action performed on said each data container from said description-memory device;

and

insert said description of said each action in said each data container.

6. The device of claim 1 further comprising instructions stored in a memory device of said configuration module which cause said first processor to arrange said encoded rules in

at least one rule tree wherein each rule in each rule tree has a binary outcome and is followed by one of two actions and wherein at least one rule has at least one successor rule.

7. A device for content filtering of data containers, comprising:

a first data-memory device storing;

a set of content types;

a set of content descriptors;

a set of descriptors'"'"' criteria; and

a set of operators;

a first instructions-memory device having stored thereon a first set of processor readable instructions which cause a first processor to;

prompt a user to define a set of filters, each filter specifying a content type, a content descriptor, a descriptor criterion, and an operator;

encode said each filter to produce a set of encoded filters;

prompt said user to define a set of rules;

encode said rules to produce a set of encoded rules; and

prompt said user to select an order of exercising said encoded rules for each content type to produce a set of content-specific ordered rules;

and

a second instructions-memory device having stored thereon a second set of processor readable instructions which cause a second processor to;

parse each data container into components;

determine a content type of each component; and

apply a respective set of ordered rules to said each component.

8. The device of claim 7 further comprising a memory device storing processor-readable instructions which cause said first processor to arrange said set of content-specific ordered rules in at least one rule tree, each rule tree of said at least one rule tree having:

a respective number μ

of rules, μ

>

1, labeled as R₀ to R<sub>μ

-1</sub>; and

a number 2×

μ

of actions, labeled as A₁ to A_2μ

,

wherein rule R_j, 0≦

j<

μ

, resolves to one of two states, 0 and 1, and results in one of two actions A_2j+1 and A_2j+2.

9. The device of claim 8 wherein at least one rule R_j, 0≦

j<

(μ

−

1)/2, proceeds to one of two rules R_2j+1 and R_2j+2.

10. The device of claim 9 wherein said second set of processor-readable instructions cause said second processor to:

evaluate a rule R_j, 0≦

j<

μ

;

apply action A_2j+1 in response to an indication that R_j, resolves to 0; and

apply action A_2j+2 in response to an indication that R_j, resolves to 1.

11. The device of claim 7 further comprising processor readable instructions, stored in said first instructions-memory device, which cause said first processor to:

prompt said user to specify, for each rule, two actions and two succeeding rules from among said set of rules, wherein at least one rule has null succeeding rules;

and

sort said set of rules into a number of strata, wherein rules within a stratum are independent of each other and rules of a stratum beyond the first stratum depend on rules of any of preceding strata.

12. The device of claim 7 further comprising a memory device storing processor-readable instructions which cause said first processor to:

display said set of content descriptors, said set of criteria, and said operators to facilitate defining said set of filters;

display said set of encoded filters to facilitate defining said set of rules; and

display said set of encoded rules to facilitate selecting said order of exercising said encoded rules.

13. The device of claim 7 wherein a rule in said set of rules is defined according to one of:

a single filter; and

a Boolean function of at least two filters.

14. A method of content filtering of data containers, the method comprising employing at least one processor and at least one memory device storing processor-executable instructions for:

receiving from a user definitions of content types, content descriptors, descriptors'"'"' criteria, filters, and rules;

generating for each said content type, based on said definitions;

a set of encoded filters, each encoded filter having a binary state and expressed as a respective operator, from among user-specified operators, and two operands including a content descriptor and a descriptor criterion;

and

a set of rules, every rule of which expressed as a user-specified function of binary states of selected filters;

receiving from a network a data container having components of different content types;

determining for each component a respective content type; and

assigning to said each component a respective set of rules pertinent to said respective content type.

15. The method of claim 14 further comprising:

receiving a set of actions, each action presented as a set of processor executable instructions; and

receiving identifications of actions, within said set of actions, performed by individual rules of said set of rules.

16. The method of claim 15 further comprising:

receiving a set of action-descriptions each action description corresponding to an action within said set of actions and containing a natural-language description of a respective action; and

storing said set of action-descriptions in a description-memory device.

17. The method of claim 16 further comprising:

determining a value of a selected rule from among said respective set of rules;

performing an action corresponding to a value of said selected rule;

reading a description of said action from said description-memory device; and

inserting said description in said data container.

18. The method of claim 14 further comprising:

acquiring user-defined priority of said content type;

sorting said components according to priority order of respective content types to produce sorted components; and

sequentially filtering said sorted components employing for each component of a specific content type a selected set of rules corresponding to said specific content type.

19. The method of claim 14 further comprising:

concurrently filtering said components, employing for said each component said respective set of rules, to produce filtered components; and

combining said filtered components into a single data stream.

20. The method of claim 14 further comprising pre-computing and storing said user-specified function for all binary states of said selected filters.