Patent US2717604A successfully refreshed from Google Patents.
Patent US6006223A successfully refreshed from Google Patents.
US6006223A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Mapping words, phrases using sequential-pattern to find user specific trends in a text database
Assignee: GlobalFoundries Inc
•
Filing: 1997-08-12
•
Granted: 1999-12-21
•
Expires: 2017-08-12
Abstract
Abstract A method and apparatus for mining text databases, employing sequential pattern phrase identification and shape queries, to discover trends. The method passes over a desired database using a dynamically generated shape query. Documents within the database are selected based on specific classifications and user defined partitions. Once a partition is specified, transaction IDs are assigned to the words in the text documents depending on their placement within each document. The transaction IDs encode both the position of each word within the document as well as representing sentence, paragraph, and section breaks, and are represented in one embodiment as long integers with the sentence boundaries. A maximum and minimum gap between words in the phrases and the minimum support all phrases must meet for the selected time period may be specified. A generalized sequential pattern method is used to generate those phrases in each partition that meet the minimum support threshold. The shape query engine takes the set of phrases for the partition of interest and selects those that match a given shape query. A query may take the form of requesting a trend such as "recent upwards trend", "recent spikes in usage", "downward trends", and "resurgence of usage". Once the phrases matching the shape query are found, they are presented to the user.
Inventors
- 👤 Rakesh Agrawal
- 👤 Ramakrishnan Srikant
- 👤 Brian Scott Lent
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 13:32
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/31; G06F16/313; G06F2216/00; G06F2216/03; Y; Y10; Y10S; Y10S707/00; Y10S707/964; Y10S707/966; Y10S707/967; Y10S707/968; Y10S707/99931; Y10S707/99933; Y10S707/99935; Y10S707/99936; Y10S707/99941; Y10S707/99943; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
209 words
A computer executed method for discovering trends in a database, comprising: mapping words in a plurality of words to a data-sequence of data contained in a data field and identifiable by a position identifier, the data-sequence having transactions where a transaction includes a set of items, a word mapped to a single-item transaction in a data-sequence; mapping phrases to a sequential-pattern of data contained in the data field and identifiable by a position identifier, the sequential-pattern of data having sets of items, a phrase mapped to a sequential-pattern having one item in each set of items; generating a time stamp for each word of a plurality of words mapped in a data field, the time stamp specifying a data field location; partitioning the database into discrete portions using the time stamp for each word; determining a support value for a phrase, the support value representing a number of data-sequences in a selected data partition containing the phrase; and outputting trends based upon the support values of the phrases, by: determining frequent phrases using the mapping of each phrase, a phrase being frequent if the presence of the phrase in the selected partition of the database exceeds a minimum required support value; and outputting trends using only the frequent phrases.
Claim 2
Dependent Claim
209 words
A computer executed method for discovering trends in a database, comprising: mapping words in a plurality of words to a data-sequence of data contained in a data field and identifiable by a position identifier, the data-sequence having transactions where a transaction includes a set of items, a word mapped to a single-item transaction in a data-sequence; mapping phrases to a sequential-pattern of data contained in the data field and identifiable by a position identifier, the sequential-pattern of data having sets of items, a phrase mapped to a sequential-pattern having one item in each set of items; generating a time stamp for each word of a plurality of words mapped in a data field, the time stamp specifying a data field location; partitioning the database into discrete portions using the time stamp for each word; determining a support value for a phrase, the support value representing a number of data-sequences in a selected data partition containing the phrase; and outputting trends based upon the support values of the phrases, by: determining frequent phrases using the mapping of each phrase, a phrase being frequent if the presence of the phrase in the selected partition of the database exceeds a minimum required support value; and outputting trends using only the frequent phrases.
Claim 3
Dependent Claim
29 words
The method recited in claim 1 where outputting trends further comprises pruning the frequent phrases based upon user-defined constraints to reduce the number of phrases used to identify trends.
Claim 4
Dependent Claim
18 words
The method recited in claim 1 including cleansing the database to remove undesired data from each data field.
Claim 5
Dependent Claim
13 words
The method recited in claim 1 including caching histories of the support values.
Claim 6
Dependent Claim
227 words
A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for discovering trends in a database, said method comprising: mapping words in a plurality of words to a data-sequence of data contained in a data field and identifiable by a position identifier, the data-sequence having transactions where a transaction includes a set of items, a word mapped to a single-item transaction in a data-sequence; mapping phrases to a sequential-pattern of data contained in the data field and identifiable by a position identifier, the sequential-pattern of data having sets of items, a phrase mapped to a sequential-pattern having one item in each set of items; generating a time stamp for each word of a plurality of words mapped in a data field, the time stamp specifying a data field location; partitioning the database into discrete portions using the time stamp for each word; determining a support value for a phrase, the support value representing a number of data-sequences in a selected data partition contain the phrase; and outputting trends based upon the support values of the phrases, by: determining frequent phrases using the mapping of each phrase, a phrase being frequent if the presence of the phrase in the selected partition of the database exceeds a minimum required support value; and outputting trends using only the frequent phrases.
Claim 7
Dependent Claim
227 words
A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for discovering trends in a database, said method comprising: mapping words in a plurality of words to a data-sequence of data contained in a data field and identifiable by a position identifier, the data-sequence having transactions where a transaction includes a set of items, a word mapped to a single-item transaction in a data-sequence; mapping phrases to a sequential-pattern of data contained in the data field and identifiable by a position identifier, the sequential-pattern of data having sets of items, a phrase mapped to a sequential-pattern having one item in each set of items; generating a time stamp for each word of a plurality of words mapped in a data field, the time stamp specifying a data field location; partitioning the database into discrete portions using the time stamp for each word; determining a support value for a phrase, the support value representing a number of data-sequences in a selected data partition contain the phrase; and outputting trends based upon the support values of the phrases, by: determining frequent phrases using the mapping of each phrase, a phrase being frequent if the presence of the phrase in the selected partition of the database exceeds a minimum required support value; and outputting trends using only the frequent phrases.
Claim 8
Dependent Claim
46 words
The signal-bearing medium recited in claim 5 and used in performing a method for discovering trends in a database, where the method step of identifying trends further comprises pruning the frequent phrases based upon user-defined constraints to reduce the number of phrases used to identify trends.
Claim 9
Dependent Claim
33 words
The signal-bearing medium recited in claim 6 and used in performing a method for discovering trends in a database, the method including cleansing the database to remove undesired data from each data field.
Claim 10
Dependent Claim
28 words
The signal-bearing medium recited in claim 6 and used in performing a method for discovering trends in a database, the method including caching histories of the support values.
Claim 11
Dependent Claim
260 words
A digital processing machine used to discover trends in a database, the device comprising: a database; a digital processing apparatus, the digital processing apparatus configured to receive data and commands from a signal-bearing medium tangibly embodying a program of machine-readable instructions executable by the digital processing apparatus and used to perform a method for discovering trends in a database, said method comprising: mapping words in a plurality of words to a data-sequence of data contained in a data field and identifiable by a position identifier, the data-sequence having transactions where a transaction includes a set of items, a word mapped to a single-item transaction in a data-sequence; mapping phrases to a sequential-pattern of data contained in the data field and identifiable by a position identifier, the sequential-pattern of data having sets of items, a phrase mapped to a sequential-pattern having one item in each set of items; generating a time stamp for each word of a plurality of words mapped in a data field, the time stamp specifying a data field location; partitioning the database into discrete portions using the time stamp for each word; determining a support value for a phrase, the support value representing a number of data-sequences in a selected data partition contain the phrase; and outputting trends based upon the support values of the phrases, by: determining frequent phrases using the mapping of each phrase, a phrase being frequent if the presence of the phrase in the selected partition of the database exceeds a minimum required support value; and outputting trends using only the frequent phrases.
Claim 12
Dependent Claim
260 words
A digital processing machine used to discover trends in a database, the device comprising: a database; a digital processing apparatus, the digital processing apparatus configured to receive data and commands from a signal-bearing medium tangibly embodying a program of machine-readable instructions executable by the digital processing apparatus and used to perform a method for discovering trends in a database, said method comprising: mapping words in a plurality of words to a data-sequence of data contained in a data field and identifiable by a position identifier, the data-sequence having transactions where a transaction includes a set of items, a word mapped to a single-item transaction in a data-sequence; mapping phrases to a sequential-pattern of data contained in the data field and identifiable by a position identifier, the sequential-pattern of data having sets of items, a phrase mapped to a sequential-pattern having one item in each set of items; generating a time stamp for each word of a plurality of words mapped in a data field, the time stamp specifying a data field location; partitioning the database into discrete portions using the time stamp for each word; determining a support value for a phrase, the support value representing a number of data-sequences in a selected data partition contain the phrase; and outputting trends based upon the support values of the phrases, by: determining frequent phrases using the mapping of each phrase, a phrase being frequent if the presence of the phrase in the selected partition of the database exceeds a minimum required support value; and outputting trends using only the frequent phrases.
Claim 13
Dependent Claim
39 words
The machine recited in claim 9, where the method step of outputting trends performed by the digital processing apparatus further comprises pruning the frequent phrases based upon user-defined constraints to reduce the number of phrases used to identify trends.
Claim 14
Dependent Claim
27 words
The machine recited in claim 10, where the method performed by the digital processing apparatus includes cleansing the database to remove undesired data from each data field.
Claim 15
Dependent Claim
22 words
The machine recited in claim 11, where the method performed by the digital processing apparatus includes retaining histories of the support values.
Claim 16
Dependent Claim
270 words
A digital processing machine for discovering trends in a database, the device comprising: a database; a means for processing the database, the processing means configured to receive data and commands from a signal-bearing medium tangibly embodying a program of machine-readable instructions executable by the processing means and used to perform a method for discovering trends in a database, said method comprising: cleansing the database to remove undesired data from each data field; mapping words in a plurality of words to a data-sequence of data contained in a data field and identifiable by a position identifier, the data-sequence having transactions where a transaction includes a set of items, a word mapped to a single-item transaction in a data-sequence; mapping phrases to a sequential-pattern of data contained in the data field and identifiable by a position identifier, the sequential-pattern of data having sets of items, a phrase mapped to a sequential-pattern having one item in each set of items; generating a time stamp for each word of a plurality of words mapped in a data field, the time stamp specifying a data field location; partitioning the database into discrete portions using the time stamp for each word; determining a support value for a phrase, the support value representing a number of data-sequences in a selected data partition contain the phrase; and outputting trends based upon the support values of the phrases, by: determining frequent phrases using the mapping of each phrase, a phrase being frequent if the presence of the phrase in the selected partition of the database exceeds a minimum required support value; and outputting trends using only the frequent phrases.
Claim 17
Dependent Claim
270 words
A digital processing machine for discovering trends in a database, the device comprising: a database; a means for processing the database, the processing means configured to receive data and commands from a signal-bearing medium tangibly embodying a program of machine-readable instructions executable by the processing means and used to perform a method for discovering trends in a database, said method comprising: cleansing the database to remove undesired data from each data field; mapping words in a plurality of words to a data-sequence of data contained in a data field and identifiable by a position identifier, the data-sequence having transactions where a transaction includes a set of items, a word mapped to a single-item transaction in a data-sequence; mapping phrases to a sequential-pattern of data contained in the data field and identifiable by a position identifier, the sequential-pattern of data having sets of items, a phrase mapped to a sequential-pattern having one item in each set of items; generating a time stamp for each word of a plurality of words mapped in a data field, the time stamp specifying a data field location; partitioning the database into discrete portions using the time stamp for each word; determining a support value for a phrase, the support value representing a number of data-sequences in a selected data partition contain the phrase; and outputting trends based upon the support values of the phrases, by: determining frequent phrases using the mapping of each phrase, a phrase being frequent if the presence of the phrase in the selected partition of the database exceeds a minimum required support value; and outputting trends using only the frequent phrases.
Claim 18
Dependent Claim
31 words
The digital processing machine recited in claim 13 where outputting trends further comprises pruning the frequent phrases based upon user-defined constraints to reduce the number of phrases used to identify trends.
Claim 19
Dependent Claim
20 words
The digital processing machine recited in claim 13 including cleansing the database to remove undesired data from each data field.
Claim 20
Dependent Claim
15 words
The digital processing machine recited in claim 13 including caching histories of the support values.
References Cited (Backward Citations)
US5787386A
Cited
US5794178A
Cited
US5675819A
Cited
US5790848A
Cited
US5729730A
Cited
US5615341A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-12-20 | 2003-06-21 | 2003-12-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-12-20 | 2007-06-21 | 2007-12-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-12-20 | 2011-06-21 | 2011-12-21 | $7700.00 | Window Closed / Lapsed |