Patent US6169989B1 successfully refreshed from Google Patents.
US6169989B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for parallel profile matching in a large scale webcasting system
Assignee: International Business Machines Corp
•
Filing: 1998-05-21
•
Granted: 2001-01-02
•
Expires: 2018-05-21
Abstract
Abstract A method and apparatus for efficiently matching a large collection of user profiles against a large volume of data in a webcasting system. The invention generally includes in one embodiment four steps to parallelize the profiles. First, an initial profile set is partitioned into several subsets also referred to as sub-partitions using various heuristic methods. Second, each sub-partition is mapped onto one or more independent processing units. Each processing unit is not required to have equal processing performance. However, for best performance results, subset data should be mapped in one embodiment where the subset with a highest cost is mapped to a fastest processor, and the next highest cost subset mapped to the next fastest processor. Where appropriate, the invention evaluates the relative subset processing speed of each processor and adjusts future subset mapping based upon these evaluations. For each information item I that needs to be matched with a profile predicate, a third and a fourth step are executed. The third step broadcasts I to all processing units, and a fourth step performs a sequential profile match on I.
Inventors
- 👤 Matthias Eichstaedt
- 👤 Qi Lu
- 👤 Shang-Hua Teng
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 19:11
CPC Classifications
G; G06; G06Q; G06Q30/00; G06Q30/02; G06Q30/0283; G06F; G06F16/00; G06F16/90; G06F16/95; G06F16/953; G06F16/9535; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99941; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
65 words
A method for parallel matching a user profile with desired data, the method comprising: partitioning a profile database into sub-partitions having data subsets, the subsets comprising predicates, the predicates used to assert selected properties to information items; mapping each sub-partition onto one or more processors yielding greatest processing efficiency; communicating an information item to each processor; and matching the information item with a corresponding predicate.
Claim 2
Independent Claim
65 words
A method for parallel matching a user profile with desired data, the method comprising: partitioning a profile database into sub-partitions having data subsets, the subsets comprising predicates, the predicates used to assert selected properties to information items; mapping each sub-partition onto one or more processors yielding greatest processing efficiency; communicating an information item to each processor; and matching the information item with a corresponding predicate.
Claim 3
Dependent Claim
31 words
The method recited in claim 1 , wherein the profile database is partitioned based upon a cost of each sub-partition, the cost related to system overhead required to process the sub-partition.
Claim 4
Dependent Claim
15 words
The method recited in claim 2 , wherein a sub-partition is mapped to one processor.
Claim 5
Dependent Claim
22 words
The method recited in claim 3 , wherein a processor to which a sub-partition is mapped is based upon a sub-partition's cost.
Claim 6
Dependent Claim
46 words
The method recited in claim 4 , wherein a highest cost sub-partition is mapped to a processor with a fastest processing capability compared to other processors available in the system for processing sub-partitions, and all next-highest cost sub-partitions are mapped correspondingly to all next-fastest available processors.
Claim 7
Dependent Claim
47 words
The method recited in claim 5 , mapping further comprising: if the sub-partition's data subsets have a predetermined overlap, then using a means for greedy mapping partitioning the profile database; and if the data subsets have unacceptable overlap, using another partitioning means for partitioning the profile database.
Claim 8
Dependent Claim
21 words
The method recited in claim 6 , using another partitioning means comprising using a means for β-Mapping partitioning the profile database.
Claim 9
Dependent Claim
20 words
The method recited in claim 6 , using another partitioning means comprising using a means for clustering partitioning the database.
Claim 10
Dependent Claim
22 words
The method recited in claim 6 , using another partitioning means comprising using a means for incremental clustering partitioning of the database.
Claim 11
Dependent Claim
32 words
The method recited in claim 6 , further comprising: building a profile index, wherein the profile index includes a collection of user profiles including predicates; and identifying predicates shared by user profiles.
Claim 12
Dependent Claim
69 words
The method recited in claim 10 , wherein evaluating the predicates further comprises: dynamically monitoring the evaluation of each predicate; assigning an evaluation cost to each predicate based upon the monitoring, wherein the cost of a cheap predicate requires less evaluation time and the cost of an expensive predicate requires more evaluation time; and adjusting the mapping of the predicates to a processor based upon dynamically determined processing cost.
Claim 13
Dependent Claim
47 words
The method recited in claim 11 , wherein evaluating a predicate against a data item by: accessing an index for the data items, the data items having contents and the index comprising a list of the contents; and evaluating a predicate against the list of the contents.
Claim 14
Dependent Claim
82 words
A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for matching a user profile with desired data, said method comprising: partitioning a profile database into sub-partitions having data subsets, the subsets comprising predicates, the predicates used to assert selected properties to information items; mapping each sub-partition onto one or more processors yielding greatest processing efficiency; communicating an information item to each processor; and matching the information item with a corresponding predicate.
Claim 15
Dependent Claim
82 words
A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for matching a user profile with desired data, said method comprising: partitioning a profile database into sub-partitions having data subsets, the subsets comprising predicates, the predicates used to assert selected properties to information items; mapping each sub-partition onto one or more processors yielding greatest processing efficiency; communicating an information item to each processor; and matching the information item with a corresponding predicate.
Claim 16
Dependent Claim
34 words
The signal-bearing medium recited in claim 13 , wherein the method includes partitioning the profile database based upon a cost of each sub-partition, the cost related to system overhead required to process the sub-partition.
Claim 17
Dependent Claim
23 words
The signal-bearing medium embodying a program for the method recited in claim 14 , wherein a sub-partition is mapped to a one processor.
Claim 18
Dependent Claim
26 words
The signal-bearing medium recited in claim 15 , the method further comprising wherein a processor to which a sub-partition is mapped is upon a sub-partition's cost.
Claim 19
Dependent Claim
52 words
The signal-bearing medium recited in claim 16 , the method step further comprising wherein a highest cost sub-partition is mapped to a processor with a fastest processing capability compared to other processors available in the system for processing sub-partitions, and all next-highest cost sub-partitions are mapped correspondingly to a next-fastest available processor.
Claim 20
Dependent Claim
49 words
The signal-bearing medium recited in claim 17 , the method step further comprising: if the sub-partitions data subsets have acceptable overlap, then using a greedy clustering means for partitioning the profile database; and if the data subsets have unacceptable overlap, using another partitioning means for partitioning the profile database.
Claim 21
Dependent Claim
35 words
The signal-bearing medium recited in claim 18 , the method further comprising: building a profile index, wherein the profile index includes a collection of user profiles including predicates; and identifying predicates shared by user profiles.
Claim 22
Dependent Claim
68 words
The signal-bearing medium recited in claim 19 , the method further comprising: dynamically monitoring the evaluation of each predicate; assigning an evaluation cost to each predicate based upon the monitoring, wherein the cost of a cheap predicate requires less evaluation time and the cost of an expensive predicate requires more evaluation time; and adjusting the mapping of the predicates to a processor based upon dynamically determined processing cost.
Claim 23
Dependent Claim
43 words
The signal-bearing medium recited in claim 20 , the method further comprising: accessing an index for the data items, the data items having contents and the index comprising a list of the contents; and evaluating a predicate against the list of the contents.
Claim 24
Independent Claim
94 words
An apparatus to match a user profile with desired data, the apparatus comprising: a webcasting system, the system including: a profile handler; a profile matcher; a profile database; an data item fetcher; a processor, wherein the processor is capable of executing instructions to: partitioning a profile database into sub-partitions having data subsets, the subsets comprising predicates, the predicates used to assert selected properties to information items; mapping each sub-partition onto one or more processors yielding greatest processing efficiency; communicating an information item to each processor; and matching the information item with a corresponding predicate.
Claim 25
Independent Claim
94 words
An apparatus to match a user profile with desired data, the apparatus comprising: a webcasting system, the system including: a profile handler; a profile matcher; a profile database; an data item fetcher; a processor, wherein the processor is capable of executing instructions to: partitioning a profile database into sub-partitions having data subsets, the subsets comprising predicates, the predicates used to assert selected properties to information items; mapping each sub-partition onto one or more processors yielding greatest processing efficiency; communicating an information item to each processor; and matching the information item with a corresponding predicate.
Claim 26
Dependent Claim
39 words
The apparatus recited in claim 22 , wherein the processor is further capable of executing instructions to partition the profile database based upon a cost of each sub-partition, the cost related to system overhead required to process the sub-partition.
Claim 27
Dependent Claim
23 words
The apparatus recited in claim 23 , wherein the processor is further capable of executing instructions to map a sub-partition to one processor.
Claim 28
Dependent Claim
28 words
The apparatus recited in claim 24 , wherein the processor is further capable of executing instructions to map a sub-partition to a processor based upon the sub-partition's cost.
Claim 29
Dependent Claim
46 words
The apparatus recited in claim 25 , wherein a highest cost sub-partition is mapped to a processor with a fastest processing capability compared to other processors available in the system for processing sub-partitions, and all next-highest cost sub-partitions are mapped correspondingly to a next-fastest available processor.
Claim 30
Dependent Claim
53 words
The apparatus recited in claim 26 , wherein the processor is further capable of executing instructions to: if the sub-partitions data subsets have acceptable overlap, then using a greedy clustering means for partitioning the profile database; and if the data subsets have unacceptable overlap, using another partitioning means for partitioning the profile database.
Claim 31
Dependent Claim
53 words
The apparatus recited in claim 27 , wherein the processor is further capable of executing instructions for: if the sub-partitions data subsets have acceptable overlap, then using a greedy clustering means for partitioning the profile database, and if the data subsets have unacceptable overlap, using another partitioning means for partitioning the profile database.
Claim 32
Dependent Claim
40 words
The apparatus recited in claim 28 , wherein the processor is further capable of executing instructions for: building a profile index, wherein the profile index includes a collection of user profiles including predicates; and identifying predicates shared by user profiles.
Claim 33
Dependent Claim
73 words
The apparatus recited in claim 29 , wherein the processor is further capable of executing instructions for: dynamically monitoring the evaluation of each predicate; assigning an evaluation cost to each predicate based upon the monitoring, wherein the cost of a cheap predicate requires less evaluation time and the cost of an expensive predicate requires more evaluation time; and adjusting the mapping of the predicates to a processor based upon dynamically determined processing cost.
Claim 34
Dependent Claim
48 words
The apparatus recited in claim 30 , wherein the processor is further capable of executing instructions for: accessing an index for the data items, the data items having contents and the index comprising a list of the contents; and evaluating a predicate against the list of the contents.
Claim 35
Independent Claim
112 words
A method for matching a user profile with selected data, the method comprising: partitioning a profile database into sub-partitions having data subsets, the subsets comprising predicates, the predicates used to assert selected properties to information items; mapping each sub-partition onto one or more processors yielding greatest processing efficiency; communicating an information item to each processor; and matching the information item with a corresponding predicate; wherein the profile database is partitioned based upon a cost of each sub-partition, the cost related to system overhead required to process the sub-partition; wherein a sub-partition is mapped to a one processor; and wherein a processor to which a sub-partition is mapped is upon a sub-partition's cost.
Claim 36
Independent Claim
112 words
A method for matching a user profile with selected data, the method comprising: partitioning a profile database into sub-partitions having data subsets, the subsets comprising predicates, the predicates used to assert selected properties to information items; mapping each sub-partition onto one or more processors yielding greatest processing efficiency; communicating an information item to each processor; and matching the information item with a corresponding predicate; wherein the profile database is partitioned based upon a cost of each sub-partition, the cost related to system overhead required to process the sub-partition; wherein a sub-partition is mapped to a one processor; and wherein a processor to which a sub-partition is mapped is upon a sub-partition's cost.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-01-02 | 2004-07-03 | 2005-01-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-01-02 | 2008-07-03 | 2009-01-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-01-02 | 2012-07-03 | 2013-01-02 | $7700.00 | Window Closed / Lapsed |