US 6,804,688 B2Grant
Detecting and tracking new events/classes of documents in a data base
Issue Date:2004-10-12
•31 Claims
•21 Drawing Sheets
Abstract
Detecting and tracking of new events/classes of documents are disclosed. A method for detecting new events and/or classes of documents and tracking evolution thereof in a database, said new events and/or classes of said documents being added to said database, said documents including attribute data related to a temporal parameter, said method includes the steps of providing vectors of said documents related to attribute data including said temporal parameter included therein, and detecting said new events and classes and tracking the evolution thereof using said vectors.
Metadata
Assignee
- International Business Machines Corporation
Inventors
- Mei Kobayashi
- Loic Malassis
- Romanos Piperakis
Application Information
Application Number:US 09/844,724
Filing Date:2001-04-27
Priority Date:2000-05-02
Art Unit:7
Classifications
IPC:
G06F 1730
Patent Drawings (21 sheets)
Description
FIELD OF THE INVENTION
[0002] The present invention relates to detecting and tracking evolution of new events and/or classes of documents in a large database, and more particularly relates to a method, a system, and a program product for detecting and tracking the evolution of the new events and/or classes of the documents in a very large database by simultaneously taking into account a temporal parameter such as time, a date, or a year and any combinations thereof in a vector modeled document.
BACKGROUND OF THE ART
[0003] Recent database systems must handle increasingly large amounts of data, such as news data, client information, stock data, etc. Users of such databases find it difficult to search desired information quickly and effectively with sufficient accuracy. Therefore, timely, accurate, and inexpensive detection of new topics and/or events from large databases may provide very valuable information for many types of businesses including, for example, stock control, futureS and options trading, news agencies which may afford to quickly dispatch a reporter without affording a number of reporters posted worldwide, and businesses based on the Internet or other fast paced actions which need to know major and new information about competitors in order to succeed thereof.
[0004] Conventionally, detection and tracking of new events in enormous databases is expensive, elaborate, and time consuming work, because a searcher of the database usually needs to hire extra persons for monitoring thereof.
[0005] Recent detection and tracking methods used for search engines mostly use a vector model for data in the database in order to cluster the data. These conventional methods generally construct a vector q (kwd1, kwd2, . . . kwdN) corresponding to the data in the database. The vector q is defined as the vector having the dimension equal to numbers of attributes, such as kwd1, kwd2, . . . kwdN which are attributed to the data. The most commonly used attributes are keywords, i.e., single keywords, phrases, names of person(s), place(s). Usually, a binary model is used to create the vector q mathematically in which the kwd1 is replaced to 0 when the data do not include the kwd1, and the kwd1 is replaced to 1 when the data include the kwd1. Sometimes, a weight factor is combined to the binary model to improve the accuracy of the search. Such weight factor includes, for example, appearance times of the keywords in the data.
[0006] In such vector model of the database, conventionally the clustering of the data in the database is first carried out based on the keywords. The procedure of the clustering mostly uses the scalar product of the vector q. In the clustering of the data, each vector corresponding to the data in the database is categorized into some clusters having a predetermined range of the scalar product. Then the clusters are further clustered using a date/time stamp attributed to the data for detecting and tracking the new event. The conventional search method uses a two-step clustering process for detecting and tracking the new events as described above, and therefore, the search procedure becomes elaborate and expensive work.
[0007] Therefore, there are needs for providing a system implemented with a novel method for detecting new events and/or classes and tracking evolution of the new events in an inexpensive and automatic manner.
DESCRIPTION OF RELATED ART
[0008] In “Maximizing text-mining performance”, IEEE Intelligent Systems, July/August, 1999, pp. 1307-1313 by S. Weiss et al. at IBM T. J. Watson Laboratory, a method for detecting and tracking new events, which uses a combination of decision tree algorithms and adaptive sampling, is disclosed. The method disclosed by Weiss et al. may provide a method for detecting and tracking new events, but has the disadvantage of requiring training sets of sample documents to compile a dictionary.
[0009] In “Topic detection and tracking pilot study final report”, Proc. of the DARPA Broadcast News Transcription and Understanding Workshop, February, 1998, Morgan Kaufmann San Francisco, pp. 194-218, 1998, by J. Allan et al., at University of Massachusetts, Amherst, CMU, “Dragon Systems” a probabilistic (Hidden Markov Model) approach is used to cluster documents based on words and sentences in articles. In the “Dragon Systems”, there is also the disadvantage of requiring a training set to start the system. UMass (University of Massachusetts) uses a content based LCA (local content analysis) method, and this method is very slow so that the search speed becomes unacceptably slow. The Carnegie-Mellon University's system is directed to search multimedia data such as audio news and video data. It is based on probabilistic methods.
[0010] In “Intelligent Information Retrieval”, IEEE Intelligent Systems, July/August, 1999, pp. 30-31 by Y. Young et al., a method which uses a group average clustering and an independent time stamp-weighting factor is disclosed. The weighting factor is also disclosed in “Clustering algorithms”, pp. 419-442 in W. Frakes and R. Baeza-Yates (Editor), “Information Retrieval: data structures and algorithms”, Prentice-Hall, Englewood Cliffs, N.J., 1992, and E. Rasmussen and “Recent trends in hierarchic clustering: a critical review”, Information Processing and Management, Vol. 24, No. 5, pp. 577-597, 1988.
[0011] In “CMU Infomedia-KNN-based Topic Detection”:
[0012] http://www.informedia.cs.cmu.edu./HDWBerk/tsld001.htm, a training index with pre-labeled topics is provided.
[0013] The detail is:
[0014] 45000 broadcast News stories from 1995 to 1996,
[0015] 3178 different news topics occurring appeared larger than 10 times
[0016] Search for top 10 related stories in training index
[0017] Lookup topics for related stories
[0018] Re-weight topics by story relevance (select top 5)
[0019] At 5 topics, Recall is reported to be 0.491 and Relevance is reported to be 0.482
[0020] In “NIST Topic Detection and Tracking Evaluation Project”:
[0021] http://www.itl.nist.gov/iaui/894.01/proc/darpa98/index.htm, U.S. National Institute of Standard and Technology (NIST) discloses the results conducted in 1997Xg as listed in Table I.
| TABLE I* | |||||
|---|---|---|---|---|---|
| RUN | % Miss | % f/a | % Recall | % Prec | |
SUMMARY OF THE INVENTION
[0022] An object of the present invention is to provide a novel method for detecting new events and/or classes of the documents and tracking evolution thereof in a database.
[0023] Another object of the present invention is to provide a novel system for detecting new events and/or classes of the documents and tracking evolution thereof in a database.
[0024] Further, another object of the present invention is to provide a novel program product for detecting new events and/or classes of the documents and tracking evolution thereof in a database.
[0025] The present invention essentially utilizes a novel method for detecting and tracking of the new events and/or classes of the documents in a very large database simultaneously taking into account a time stamp parameter such as date and time in a vector modeled document.
[0026] In a first aspect of the present invention, a method for detecting new events and/or classes of documents and tracking evolution thereof in a database, said new event and/or classes of said documents being added to said database, said documents including attribute data related to a temporal parameter, said method comprises steps of:
[0027] providing vectors of said documents based on attribute data simultaneously including said temporal parameter included in said document, and
[0028] detecting said new events and/or classes of said documents and tracking evolution thereof simultaneously using said vectors.
[0029] In the first aspect of the present invention, said attributed data may include at least one keyword, and said keyword is weighted with respect to a frequency of appearance in said document.
[0030] In the first aspect of the present invention, said detecting and tracking step may further include a step of providing a temporal window such that said detecting and tracking step is executed using said temporal window.
[0031] In the first aspect of the present invention, said temporal window may be a delta function with respect to a specific date.
[0032] In the first aspect of the present invention, said temporal window may be a symmetric Gaussian function.
[0033] In the first aspect of the present invention, said temporal window may be a step function
[0034] In the first aspect of the present invention, said temporal window may be formed interactively by a user on a display window.
[0035] In the first aspect of the present invention, said temporal parameter may be further weighted with respect to time elapse about a specific date, and a weight of said temporal parameter may be less than the total weight of said keywords.
[0036] In the first aspect of the present invention, said temporal window may be normalized before dimensional reduction for said vectors may be carried out if the number of said keywords in each document is relatively constant in said database and the same temporal window is used for all of the documents.
[0037] In the first aspect of the present invention, several different temporal windows may be provided so that the relative weights between said keywords and said temporal parameter becomes relatively constant from document to document if the number of said keywords in each document varies greatly.
[0038] In a second aspect of the present invention, a computer system including a database to which new events and/or classes of documents are added, said documents including data related to a temporal parameter, and detecting new events and/or classes of said documents and tracking evolution thereof being executed in said computer system comprises:
[0039] means for providing vectors of said documents based on attribute data simultaneously including said temporal parameter included in said document, and
[0040] means for detecting said new events and/or classes of said documents and tracking evolution thereof simultaneously using said vectors.
[0041] In the second aspect of the present invention, said attributed data may include at least one keyword, and said keyword is weighted with respect to a frequency of appearance in said documents.
[0042] In the second aspect of the present invention, said detecting and tracking means may further include means for providing a temporal window such that said temporal window is used by said detecting and tracking means.
[0043] In the second aspect of the present invention, said temporal window may be a delta function with respect to a specific date.
[0044] In the second aspect of the present invention, said temporal window may be a symmetric Gaussian function.
[0045] In the second aspect of the present invention, said temporal window may be a step function.
[0046] In the second aspect of the present invention, said temporal window may be formed interactively by a user on a display window.
[0047] In the second aspect of the present invention, said temporal parameter may be further weighted with respect to time elapse about a specific date, and a weight of said temporal parameter may be less than the total weight of said keywords.
[0048] In the second aspect of the present invention, said temporal window may be normalized before dimensional reduction for said vectors is carried out if the number of said keywords in each document is relatively constant in said database and the same temporal window is used for all of the documents.
[0049] In the second aspect of the present invention, several different temporal windows may be provided so that the relative weights between said keywords and said temporal parameter may become relatively constant from document to document if the number of said keywords in each document varies greatly.
[0050] In the second aspect of the present invention, said computer system may comprise a server and at least one client, and said detection and tracking step may be requested from at least one client computer which transmits to said server and receives a result from said detection and tracking step.
[0051] In a third aspect of the present invention, a program product for detecting new events and/or classes of documents and tracking evolution thereof in a database, said new events and/or classes of said documents being added to said database, said documents including attribute data related to a temporal parameter, said method comprising steps of:
[0052] providing vectors of said documents based on attribute data simultaneously including said temporal parameter included therein, and
[0053] detecting said new events and/or classes of said documents and tracking evolution thereof simultaneously using said vectors.
[0054] In the third aspect of the present invention, said attributed data include at least one keyword, and said keyword may be weighted with respect to a frequency appeared in said documents.
[0055] In the third aspect of the present invention, said detecting and tracking step may further include a step of providing a temporal window such that said detecting and tracking step is executed using said temporal window.
[0056] In the third aspect of the present invention, said temporal window may be a delta function with respect to a specific date.
[0057] In the third aspect of the present invention, said temporal window may be a symmetric Gaussian function.
[0058] In the third aspect of the present invention, said temporal window may be a step function.
[0059] In the third aspect of the present invention, said temporal window may be formed interactively by a user on a display window.
[0060] In the third aspect of the present invention, said temporal parameter may be further weighted with respect to time elapse from a specific date, and a weight of said temporal parameter may be less than the total weight of said keywords.
[0061] In the third aspect of the present invention, said temporal window may be normalized before dimensional reduction for said vectors is carried out if the number of said keywords in each document is relatively constant in said database and the same temporal window is used for all of the documents.
[0062] In the third aspect of the present invention, several different temporal windows may be provided so that the relative weight between said keywords and said temporal parameter may become relatively constant from document to document if the number of said keywords in each document varies greatly.
[0063] The present invention will be further understood by explaining the following non-limiting embodiments of the present invention along with drawings thereof.
BRIEF DESCRIPTION OF THE DRAWINGS
[0064] FIG. 1 shows a representative procedure to incorporate the temporal attributes into the document matrix.
[0065] FIG. 2 shows an alternative procedure to incorporate the temporal attributes into the document matrix.
[0066] FIG. 3 shows an example of the document matrix.
[0067] FIG. 4 shows a temporal window having a symmetric Gaussian shape.
[0068] FIG. 5 shows a representative construction of matrices U, S, and VT, and matrices UK, SK, and VKTwith reduced dimension.
[0069] FIG. 6 shows a representative embodiment of the combined matrix.
[0070] FIG. 7(a) shows a representative procedure for forming the document matrix and FIG. 7(b) shows the converted format of the document.
[0071] FIG. 8 shows the document matrix (a) and the detail of the combined matrix (b).
[0072] FIG. 9 shows a result of the detection and tracking.
[0073] FIG. 10 shows a result of the detection and tracking.
[0074] FIG. 11 shows a result of the detection and tracking.
[0075] FIG. 12 shows variations for categorizing the topics with respect to their relevancy.
[0076] FIG. 13 shows several types of the temporal window.
[0077] FIG. 14 shows a representative computer system embodying the method according to the present invention.
[0078] FIG. 15 shows a representative computer system embodying the method according to the present invention.
[0079] FIG. 16 shows a representative computer system embodying the method according to the present invention.
[0080] FIGS. 17-21 show typical GUIs displayed in the computer system.
[0081] FIG. 22 shows a procedure for taking into account the relevancy between documents.
BEST MODE FOR CARRYING OUT THE INVENTION
[0082] A method of the present invention may be used to detect new events and/or new classes of documents and to track evolution thereof in a database, more preferably in a very large database. New data and/or documents may be added to the database in appropriate time intervals such as, daily, weekly, monthly, or even annually. The present invention may be especially effective to detect new events and/or classes of the documents and tracking evolution thereof in such databases. The method of the present invention essentially is based on a vector space model of documents wherein a temporal parameter, i.e., the date/time stamp, is allowed to be treated as if the temporal attribute(s) were keyword attributes in an algorithm for clustering the documents and in reducing noises applied to the document-attribute matrix, e.g., latent semantic indexing, statistical method.
[0083] Detection and Tracking of New Events/Classes
[0084] Definition of Terms
[0085] Temporal parameter: the term “temporal parameter” means a parameter or an attribute included in the document, and contains information related to time such as time, date, year, and any combinations therebetween.
[0086] Date/time stamp: the term “date/time” stamp means a value derived from the temporal parameter and consists of an element of a combined matrix described hereinbelow.
[0087] Document matrix (vector): the term “document matrix (vector)” means a matrix or vector created from attributes, e.g., keywords, key phrases, names, etc., included in the documents.
[0088] Combined matrix (vector): the term “combined matrix (vector)” means a matrix or vector generated by adding the date/time stamps corresponding to the documents to the document matrix.
[0089] Temporal window: the term “temporal window” means a window to weight the date/time stamps utilized when detecting new events and/or classes and tracking evolution of the new events.
[0090] 1. Combined Matrix
[0091] A flow chart of an embodiment of the procedure according the present invention to include the temporal attributes into the matrix of the document is shown in FIG. 1. In FIG. 1, the procedure proceeds to step 101 and creates a document matrix from a document in a certain format using the vector model. The detail of elements in the vector will be discussed later. There is no substantial limitation for documents in the present invention, and documents in any format, such as, a text data, and image data, and audio or visual data may be used in the present invention so far as the keywords of the same kinds and the temporal parameters are positioned in a predetermined syntax.
[0092] Referring to FIG. 1, the procedure proceeds to step 102 wherein the date/time stamp is defined from the documents such as time, date, month, and year which are included in the temporal parameter. The procedure proceeds to step 103 and adds the date/time stamp to the previously obtained document matrix to create the combined matrix. This additional step may be carried out by any method well-known in the art.
[0093] Referring to FIG. 1, the procedure further proceeds to step 104 and executes singular value decomposition and dimension reduction of the combined matrix for realizing the search such as Doc/kwd query, New Event Detection, and Tracking of step 105.
[0094] FIG. 2 shows another embodiment of the procedure to combine the temporal parameter into the document matrix. The procedure shown in FIG. 2 proceeds to step 201 and first creates the document matrix. Next, the procedure executes singular value decomposition and dimension reduction in step 102. Then the procedure proceeds to step 103 and defines the date/time stamp from temporal parameters such as time, date, month, or year.
[0095] The procedure proceeds to step 104 and adds the date/time stamp to the document matrix in step 204 to create the combined matrix used for the search such as Doc/kwd query, new Event Detection, and Tracking of step 205.
[0096] As described in FIGS. 1 and 2, the combined matrix used in the present invention may be created any time before the steps of the search 105 and 205 depending on system environments and programming facilities as easily appreciated to a person skilled in the art.
[0097] FIG. 3 shows an example of the document matrix. The matrix comprises columns from document 1 (doc 1) to document n (doc n) which include elements derived from the keywords (kwd 1 . . . kwd n) included in the particular document. Numbers of documents and numbers of keywords are not limited in the present invention, and depend on the documents and size of the database. In FIG. 3, the elements of the document matrix are represented by the numerals 1, however other positive natural numbers may be used as described hereinbelow when weighting factors are used to create the document matrix.
[0098] FIG. 4 shows a typical temporal window applied to the date/time stamp and simultaneously weighting thereof. The temporal window shown in FIG. 4 is a symmetric Gaussian function with maximum height W at the T0. Here, T0corresponds to a specific date/time of the specific document and the height corresponds to the weighting factor. This type of the window may be used to detect new events and/or classes about the specific point T0with a weighting factor which is decreasing with respect to the time duration centered to T0. Other temporal windows available in the present invention may include a delta function, a step function, etc., depending on purposes of the search. The temporal window will be further discussed hereinafter.
[0099] FIG. 5 shows constructions of matrices, U, S, and VTobtained in the singular value decomposition and dimension reduction in steps 104 and 202 in FIGS. 1 and 2. Elements of the matrix within the marked region are set to be 0 in order to reduce the dimension of the matrix of the document, through the procedure for the singular value decomposition and dimension reduction which may be carried out using well-known methods in the art.
[0100] In FIG. 6, an embodiment of the combined matrix obtained by adding the time/date stamp to the document matrix is depicted. The combined matrix comprises the elements originally included in the document matrix followed by the elements used as the time/date stamp. The elements are given by a numeral 1 in FIG. 16, however, other natural numbers may be present as the elements when weighting factors are used to create the combined matrix. Such adding step may also be performed in any way well-known in the art.
[0101] In FIG. 7, a procedure for forming the document matrix is shown. In FIG. 7(a), a document written under SGML format is assumed. The method of the present invention generates keywords based on the document with which detection and tracking are executed and then converts the format of the document into another format, such as, for example, shown in FIG. 7(b), suitably used in the method according to the present invention. Formats of the documents are not limited to SGML, and other formats may be used in the present invention.
[0102] A procedure of the attributes generation is now described. In the example, attributes are considered to be keywords. Keywords generation may be performed as follows:
[0103] (1) Extract words with capital letters
[0104] (2) Ordering
[0105] (3) Calculate number of occurrence: n
[0106] (4) Remove word if n>Max or n<Min
[0107] wherein Max denotes a predetermined value for maximum occurrence per keyword, and Min denotes a predetermined value for minimum occurrence per keyword. The process listed in step (4) may often be effective to improve accuracy. There is not a substantial limitation on the order of executing the above procedures, and the order of the above process may be determined considering system conditions used, and programming facilities. This is one example of a keyword generation procedure. There may be many other procedures possible used in the present invention.
[0108] After generating the keywords and converting the SGML format, the document matrix thus built is shown in FIG. 8(a). A sample pseudo code for creating the document vector/matrix without using a weighting factor and/or function is as follows:
[0109] REM: No Weighting factor and/or function
[0110] If kwd(j) appears in doc (i)
[0111] Then M(i,j)=1
[0112] Otherwise M(i,j)=0
[0113] The similar procedure may be applied to the temporal parameter, whereas the following pseudo code may be used:
[0114] If time/date stamp equal to a specific time/date/year in doc (i)
[0115] Then W(i)=1
[0116] Otherwise W(i)=0
[0117] FIG. 8(b) shows detail of vectors in the combined matrix created from keywords simultaneously including the date/time stamp.
[0118] The present invention may use a weighting factor and/or a weighting function with respect to both of the keywords and the temporal parameters when the combined matrix is created. The weight factor and/or the weight function for the keyword WKmay include an occurrence time of the keywords in the document, a position of the keyword in the document, whether or not the keyword being described is in capital letters, but is not limited thereto. A weighting factor and/or weighting function WTfor the temporal parameter may also be applied to obtain the time/date stamp as well as the keyword according to the present invention. The weight factor WKmay be used for each keyword, and the weight factor WTmay be used together with a number of WK's as far as the detection and tracking according to the present invention are possible. However, for the purpose of the detection of new events and/or classes and tracking of evolution of new events, a ratio of the total of the weight factor WKmust be less than WTso as to obtain good results relevant to the time/date dependent topics. It may be possible to provide several different temporal windows so that the relative weight between the keywords and the temporal parameter becomes relatively constant from document to document if the number of said keywords in each document varies greatly.
[0119] 2. Ranking of the Documents
[0120] According to the present invention, several procedures to rank the document relative to the keyword and the time/date stamp together with the weight factors may be possible, and therefore the detection and tracking method/system of new events and/or classes is enhanced with respect to conventional search engines for the databases which first cluster the document matrix only created by keywords. Although the present invention may provide the result which picks up new events such as, for example, ten events from the top of the new event and/or classes hit, accuracy of the search, i.e., detection and tracking of new events and/or classes may be increased since the method according to the present invention creates the combined matrix simultaneously including the temporal attribute.
[0121] Typical results of the detection and tracking of new events and/or classes are shown in FIG. 9. In FIG. 9, the documents with the highest associated confidence doc 1 and doc 4 for a search query without considering the temporal attribute, which corresponds to a simple keyword search, are indicated by the longest lines and second and third documents doc 3 and doc 2 with lower confidences are indicated by shorter lines.
[0122] FIGS. 10 and 11 show results of the search when the search query includes the date/time stamps. Weighting factors on the date/time stamps are different between FIG. 10 and FIG. 11. FIG. 10 shows the result of the search using the query with a high weighting factor for the date/time stamp among the same documents described in FIG. 9.
[0123] As shown in FIG. 10, document doc 1 is still most relevant to the query, and document doc 2 becomes the document with the second highest associated confidence due to the time/date stamp used, and therefore, its relative order becomes higher than the documents doc 3 and doc 4. Since document doc 3 has the lowest confidence due to the date/time stamp used, its rank is lowered in the embodiment described in FIG. 10.
[0124] Alternatively, FIG. 11 shows the result of the search using a different query with medium weighting factor for the time/date stamp. Since document doc 1 still has the highest confidence with respect to the keywords and the time/date stamp, document doc 1 is placed in the left most position. However, the ranking of document doc 3 becomes higher than the ranking shown in FIG. 10 because of the medium weight on the date/time stamp. Since document doc 3 has better confidence to the keywords than document doc 2 as shown in FIG. 9, and the search query has the time/date stamp with a medium weight factor, the ranking of document doc 3 becomes higher than the document doc 2 and doc 4 as shown in FIG. 11. The document doc 4 matches well to the keywords included in the query compared with document doc 3 as shown on FIG. 9, however, document doc 4 has relatively low relevancy to the date/time stamp thereby document doc 4 being ranked lower than document doc 3. As described above, the present invention may provide significant improvement on the detection of new event/classes and tracking evolution of new events/classes in a database.
[0125] The method of the present invention may also pick up (i.e., identify) the top ten events from the search result as usual search engines do, however various procedures and processes may be possible to pick up the new events and/or classes by incorporating the temporal parameter into the combined matrix as date/time stamps. FIG. 12 shows such variations for ranking the documents with respect to the relative relevancy to the specific time/date stamp. In FIG. 12, the document “ref.doc” has just the time/date stamp included in the query. The document which has the closest relevancy with respect to the ref.doc is represented, for example, by “closest doe”. Other documents are represented by doc n and doc m. These documents may be searched from the database by the queries with and without including the time/date stamp.
[0126] FIG. 12(a) describes the method wherein the pick-up of the documents are performed until the difference of the confidences between the ref.doc and the document to be picked up last becomes the predetermined difference α. The value of α may be fixed to a predetermined value, or may be selected to any values depending on purposes and needs of a searcher.
[0127] FIGS. 12(b) and 12(c) show other methods for picking-up the documents from the search results. In FIG. 12(b), the inflection point of a confidence-document curve is first determined and the data will be picked up from the data having equal or higher rank than the inflection points. Any algorithms and processes well-known in the art may be applied when executing the above procedure. In FIG. 12(c), another embodiment for this method is described. The method described in FIG. 12(c) first determines a threshold F for the difference of two slopes derived from three adjacent documents in the confidence-document curve. The pick-up of the data will be terminated at the point where the difference between slope 1 and slope 2 exceeds a predetermined value:
[0128] Acceleration=|slope 1−slope 2|>ε
[0129] The value of ε is not substantially limited and may be optimized so as to pick up desired numbers of the documents.
[0130] FIG. 12(d) shows a method for categorizing the documents depending on relative relevance therebetween. In this method, the documents are grouped to the first block, second block and third block of the documents, for example, by sudden decrease of the confidences between the adjacent documents. The method which uses the inflection points and the difference in the slopes as described in FIGS. 12(b) and 12(c) will be effective in order to categorize the documents, and these procedures may be combined to evaluate the relative relevance of the documents.
[0131] Procedure for Detection of New Event
[0132] A. Construction of a Mathematical (vector space) Model of Documents in a Database
[0133] Each document, e.g., electronic text document and/or Web page news articles in a database is represented by a vector using attributes included in the documents such as author, name of source, and/or keywords in an electronic text document. When creating the vector representation, well-known refinement techniques for ensuring proper weighting of the attributes may be applied to the documents. Such refinement techniques are as follows:
[0134] (1) Concatenation of singular and plural forms of words;
[0135] (2) Removal of sensitivity to letters (capital/lower case);
[0136] (3) Weighting with respect to frequency of appearance; and
[0137] (4) Removal of words which appear infrequently or too frequently, e.g., words appearing less than three or more than 100 occurrences.
[0138] B. Construction/creation of the Document Matrix Including the Time/date Stamp Corresponding to the Temporal Attribute for each Document
[0139] The date/time stamp is then incorporated into the document matrix to create the combined matrix in the described manner so as to treat the date/time stamp simultaneously with keywords in the search. The detail of the incorporation of the date/time stamp to the document matrix has been described hereabove.
[0140] C. Define “New Event” Using Distances Between the Documents.
[0141] For detection of a new event, first a distance between two documents is defined using a function such as cosine of the angle defined by the two corresponding document vectors. This distance may be obtained by the scalar product of the document vectors in accordance with any conventional manner, however, the combined vectors include the information relating to the time/date stamp, thereby permitting evaluation of the distance between the documents having the same keywords simultaneously.
[0142] Here, assume that two documents have the same keywords when only the keyword attributes are compared. The distance between such documents is conventionally determined to be zero because the documents have the same keywords, and therefore, another clustering for detection of new events must be required. In the method according to the present invention, the distance between the two documents having the same keywords may be possible to have a non-zero value because the combined vector includes the date/time stamp simultaneously. The distance between the two combined vectors is typically classified as follows:
[0143] Follow-up Article
[0144] If the two documents are recorded within a period “dt”, then the document with more recent time/date stamp should be considered as a “follow-up article” to the earlier document.
[0145] New Event
[0146] If the two documents are recorded at times separated by a temporal distance greater than “dt”, then the document with the more recent time stamp is considered as a document on a “new event”.
[0147] The actual value of “dt” may be optimized considering various kinds of topics, a purpose of search, requirements by uses, etc. It may be possible to use a function, i.e., a temporal window about the time/date stamp which varies from one to zero within the time period “dt” smoothly and then directly indicate the “follow-up article”, for example, by making the scalar product between the combined vector and the temporal window function.
[0148] D. Temporal Window
[0149] Several types of the temporal window embodied according to the present invention are depicted in FIG. 13. In FIG. 13, the ordinate represents weighting factor and the abscissa represents time elapse about the specific date for the new event. The temporal windows used according to the present invention are selected from the group consisting of the symmetric Gaussian function, the delta function, the step function, a Heaviside step function, and the p temporal window which may be interactively input by users. The temporal window is useful both in detecting new events and/or classes and in tracking evolution of new events in a database.
[0150] FIG. 13(a) shows the temporal window represented by the delta function. This temporal window may be effective to determine the events occurring on a specific time/date.
[0151] FIG. 13(b) shows the temporal window in the symmetric Gaussian function. This temporal window has the highest weighting factor on the date for the new event, and has weight gradually decreasing with respect to the distance from the specific date. This type of temporal window may be effective, for example, when a certain time/date of the new event is somewhat ambiguous or when a user wishes to know topics around the specific date and/or when tracking of follow-up articles is carried out. The Gaussian function may be used with and without normalization in the present invention, however, the Gaussian function may be preferably used in the normalized form. A plurality of temporal windows in the form of the Gaussian functions may be embodied in the present invention to simultaneously track events on week, month, and annual bases.
[0152] FIG. 13(c) shows the temporal window in the step function having the weighting factors to be zero before the specific time and/or date and constant weighting factors for events after the specific time and/or date. This temporal window is effective to track topics occurring after the specific event or time and/or date. The temporal window having a weighting factor of zero after the specific time and/or date and a constant weighting factor before the specific date, i.e., “Heaviside step function” may be used, for example, when a searcher ensures that the event is first occurred on the specific time and/or date.
[0153] FIG. 13(d) shows the temporal window which is input by a user interactively through a computer system. The temporal window shown in FIG. 13(d) may be altered by the user so as to detect and track a desired event. This alternation on the temporal window may be achieved interactively in any way well-known in the art through a keyboard, a stylus, a mouse or some kind of pointing device.
[0154] The above described temporal windows may be implemented to the present invention in any combinations depending on purpose of the detection and tracking. When the number of said keywords in each document is relatively constant in said database and the same temporal window is used for all of the documents, the temporal window may be normalized before dimensional reduction for said vectors is carried out.
[0155] Procedure for Tracking Evolution of Events in a Database
[0156] The constructions of the document vectors and the combined vectors was explained in foregoing paragraphs A and B (in the section entitled “Procedure for Detection of New Events”), and therefore, is not explained in detail in this section and essential procedures for the tracking will be explained.
[0157] A. See paragraph A in previous section.
[0158] B. See paragraph B in previous section.
[0159] C. Compute the “Distance” Between Two Documents Using the Temporal Window
[0160] The distance between the two documents is defined as the cosine of the angle between the two corresponding combined vectors as described above. Next, a “window” about the date/time stamp may be applied to each combined vector to determine the documents which address the same keywords and were created on or near the same time, or are closer to each other than those which address the same topic but were recorded far apart in time.
[0161] D. Define the Notion of “Documents Covering the Same Event”
[0162] The two documents may be defined to be “covering the same event” when the distance between the corresponding document vectors is small. The threshold for what is small may be determined by a searcher, and there is no substantial limitation thereto. “Small” can be defined in absolute quantitative terms and/or changes in the ranking versus relevancy curve, i.e., the slope of the ranking versus confidence curve when one of the documents is input as a query vector in a database.
[0163] E. Track Anniversary of Events
[0164] To track anniversaries of events, e.g., weekly, monthly, and annually, another window such as an “anniversary window” around the time of the anniversaries of interest as well the temporal window around the time/date stamp may be incorporated. The above anniversary window may be applied in the tracking as the temporal window, whereas its time duration must be set for each anniversary.
[0165] F. Track Only Events Which Occur Before a Specified Date (or after a specified date)
[0166] To track only events which occur before a specified date, a Heaviside “step function” which takes on the value one before the date and becomes zero after the date may be effective. When a precise date has some ambiguity, or when the delay time before a news report is submitted and posted must be taken into account, a “softer curve” which transfers unity to zero more gradually may also be used. The transfer of the softer curve may be selected according to a specific case of concern and there is no substantial limitation thereto. When tracking evolution of the events which occur after a specific date, a step function which is zero before the date and becomes unity after the date may be used as the temporal window. Both step functions may be, of course, modified so as to take into account the ambiguity of the date, etc.
[0167] G. Reducing Noise in the Data
[0168] To reduce the noise in the data and to take into account polysemy and synonymy, an appropriate clustering algorithm may be used to determine the inter-relationship ranking and % relevancy of a specified document to others in the database. Such algorithm may include a latent semantic indexing, but not limited thereto, for example, see M. Berry, S. Dumais, G. O'Brien, “Using linear algebra for intelligent information retrieval”, SIAM Review, Vol. 37, No. 4, pp. 573-595, December, 1995, and S. Deerwester et al., “Indexing by latent semantec analysis”, Journal of the American Society for Information Science, Vol. 41, No. 6, pp. 391-407 (1990), although sometimes two documents related to the same event may fail to be identified as being relevant to each other using the algorithm above. However, when enough documents on the topic exist in the database concerned, such error may be recovered in the method according to the present invention.
[0169] Computer System
[0170] Referring to FIG. 14, a representative embodiment of the computer system according to the present invention is described. The computer system according to the present invention may include a stand alone computer system, a client-server system and/or LAN/WAN communicated with any conventional protocols, or a computer system included communicated through an Internet infrabase. In FIG. 14, the representative computer system effective in the present invention is described using client-server systems.
[0171] The computer system shown in FIG. 14 compromises at least one client computer and server host computer. The client computer and the server host computer are communicated through a communication protocol of TCP/IP, however any other communication protocols may be available in the present invention. As described in FIG. 14, the client computer issues a request 1 to RMI registry of the server host computer to carry out the search of the new events/classes of the documents stored in memory means of the server host computer.
[0172] The server host computer executes detection and/or tracking of the database depending on the request from the client computer. A result of the detection and/or tracking is then downloaded by the client computer from the server host computer through the server stub so as to be used by a user of the client computer. In FIG. 14, the server host computer is described as the Web server, but is not limited thereto; server hosts in any other types may be used in the present invention so far as the computer system provides the above described function.
[0173] FIG. 15 shows another embodiment of the computer system. In FIG. 15, the client computer issues the request 3 for detecting and tracking the new events and/or classes to a service agent through a network communicated with TCP/IP, of course, protocols other than TCP/IP may be used in the present invention. The server host computer to which the program for executing the method of the present invention is implemented starts the detection and tracking upon receiving the request from the client. In FIG. 15, the search results are downloaded by a service agent and then transmitted to the client computer through service stubs of the Web server.
[0174] FIG. 16 shows another embodiment of the computer system according to the present invention. In the embodiment shown in FIG. 16, client computers communicate to each of a plurality of remote service agents independently through the network with TCP/IP. Each of the remote service agents issues the requests 5 for the detection and tracking to the server host computer placed at a provider of data, such as Reuters, etc., through a native interface accessing to each request from the clients. The server computer of the data provider stores a native code and data within memory means and starts the program for detection and/or tracking of the new data and/or classes upon receiving the request 5 from the client. When the search results are obtained, the results are returned to each remote service agent and further communicated to each of the clients originally issuing the requests 5. As described above, the embodiments of FIGS. 14-16 have been explained using networked computer systems. Of course, the present invention may be effective in a stand alone computer system into which a very large database is implemented.
[0175] Embodiments for executing the procedure of the present invention will be explained using FIGS. 17-21 which represent GUI displays when the computer system runs the procedure according to the present invention, but the invention is not limited thereto; other various suitable GUI may be possible in the present invention. A sample GUI shown in FIG. 17 is the GUI for a search by document number, and the field for selecting the method for the search “Method used for searching”, the field for selecting the query type “Query type”, the field for inputting number of documents to be retrieved “Number of documents to be retrieved by query”, and the field for inputting query type “Query by document” is provided thereto. A user may input such information into the corresponding field thereby initializing the search conditions.
[0176] In FIG. 18, a sample GUI for the keyword search is depicted. In the sample GUI shown in FIG. 18, a user selects “by a list of keywords” from the field of “query type”, and the user is allowed to select the keywords from the fields. The keywords may be selected among the predetermined keywords and/or may be input by the user for a specific purpose. FIG. 19 shows an embodiment for inputting the keywords into the field of the keyword list. In the embodiment shown in FIG. 19, the field for inputting the keyword is open and the user is allowed to input his/her desired keywords therein in a predetermined format.
[0177] A typical GUI for displaying the result of the search is shown in FIG. 20. The query type, and the keywords used in the search are displayed in the fields opened above the field for displaying the results. The search results are displayed with the ranking thereof, the title of the event detected and/or tracked, and the date. The results may be hard-copied from printer means in an appropriate format.
[0178] The user of the search engine to which the method according to the present invention is embodied may input his/her desired temporal window interactively moving selection means such as selection bars in the illustrated embodiments for the weight and the time/date stamp with suitable means such as a keyboard, a stylus, a mouse or other pointing devices so as to obtain customized results for a specific purpose.
[0179] FIG. 21 shows an embodiment of a GUI for altering the temporal window in which a width of the temporal window, specific temporal parameters such as time, date, or year are displayed in the GUI. A user of the system may input the specific temporal window as shown in FIG. 21 interactively so as to obtain more precise and confident search results guided by the numerical displays for the temporal window.
[0180] Hereunder, the present invention will be further explained by non-limiting examples thereof.
EXAMPLES
[0181] Sample Database
[0182] The present invention was tested using sample databases extracted from a Reuters-21578 news database; one database contained 83 articles and the other database contained over 20,000 articles, respectively.
[0183] The database of 83 articles from the larger Reuters database was set to examine effectiveness of the present invention, and the articles were selected from new events, subsequent follow-up articles, articles on isolated new events, and irrelevant “noise”, i.e., articles with no bearing on the main subjects which are listed as below:
[0184] planes (airbus, boeing, douglas)
[0185] plane crash and takeover
[0186] earthquake (New Zealand, Japan)
[0187] computers (att, ibm, apple)
[0188] gulf war
[0189] British elections
[0190] noise
[0191] The sample database is listed in Table II (83 news).
| TABLE II |
|---|
| New Events Detected |
[0192] Keywords
[0193] A keyword list was generated by looking for words which contained an uppercase letter (capital) in any position in the word. We found a set of simple keywords can provide sufficient results, however, better results may be provided when a better set of keywords may be selected. Words with too frequent or too infrequent occurrences were eliminated from the keyword list for ensuring the accuracy of the search. Then a keyword list including approximately 150 words was constructed by taking into account only the keywords which contain an uppercase (capital) letter in the words whether or not the capital letter can occur in the top and/or middle of the word, hence the capital letter does not necessarily have to be the first letter of the word.
[0194] Results From Detecting New Events
Example 1
[0195] The results from detection of new events are also listed in the right two columns in Table II. The second column from the right lists the determination from the algorithm according to the present invention, and the term “NEW” represents that the algorithm determined the topic to be new, and the term “OLD” represents that the algorithm determined the topic to be old. The right most row represents judgements for the determination given by the algorithm. In the right most row, the terms “OK” represent that the determination was correct, and in turn the terms other than “OK” denote that the determination was incorrect. As shown in Table II, the determinations made by the algorithm are almost all correct except for Document No. 2, 6, and 79, however, the determination was carried out with sufficient accuracy when one considered the noise data was incorporated into the sample database.
[0196] Results From Tracking Experiments
[0197] When tracking the evolution of the new events, the relevance of all documents d(i) created after a document d(new) describing a new event for its “closeness” to d(new) was tested at 222. If d(i) had a relevance higher than the threshold e which was designated by a user as determined at 223, then the document d(i) was labeled as a follow-up document for d(new) and added to the list of d relevant(i) at 224 If d(i) has a relevance lower than ε, then d(i) was not considered as a follow-up document for d(new) and proceeds to evaluation at 225.
[0198] After all documents were tested directly for their relevance with respect to d(new), then the set of documents d_relevant(i) which had a relevancy higher than εwith respect to d(new) was determined. All documents d_relevant2 (j) which were highly relevant to each d_relevant(i) were taken into account in the tracking experiments. If the product of each relevancy for a document d_relevant2 (i) is higher than a relevancy threshold εxη (η: attenuation factor) as determined at 225, then d_relevant2 (j) was also considered to be a follow-up document for d(new) and added at 224. All others with lesser relevance are ignored at 226.
[0199] The above procedure is summarized in FIG. 22.
[0200] Progressive layers of documents d_relevant3(k), d_relevant4(l), etc., shown in FIG. 22 were tested to check whether the progressive layers should be considered as the follow-up documents for d(new). For each layer an additional attenuation factor η was multiplied by the threshold value. The documents connected by broken lines in FIG. 22 were regarded not to be relevant in present examples. In the present example, the attenuation factor η has the same value in each layer. The user of the search engine of which the method according to the present invention is embodied may instead input his/her desired attenuation factors for each layer, i.e., ηonefor the first layer, ηtwofor the second layer and so forth for successive layers.
Example 2
[0201] To facilitate the detection of new events and tracking their evolution, the temporal window was placed in the appropriate position about the date/time stamp for the date in each document vector.
[0202] In this example, the ε (threshold) and η (attenuation) were set to 0.3 and 0.9, respectively.
[0203] QUERY: 4 19870301 strong earthquake hits New Zealand
[0204] The result is listed in Table III
| TABLE III | ||||
|---|---|---|---|---|
| Rank | No | Date | Document title | Result |
| 1 | 4 | 19870301 | strong earthquake hits new | OK |
| zealand | ||||
| 2 | 7 | 19870303 | earthquakes continue to shake northern | OK |
| new zealand | ||||
| 3 | 11 | 19870304 | earthquakes continue in northern | OK |
| new zealand | ||||
| — second choice — | ||||
| 4 | 55 | 19870409 | strong quake jolts central japan | |
Example 3
[0205] In this example, the same procedure described in Example 2 was adopted while the ε (threhold) and η (attenuation) were set to 0.3 and 0.44, respectively, and therefore, a sensitivity on the follow-up articles was lowered relatively with respect to Example 1.
[0206] QUERY: 0 19870226 Iran announces end of major offensive in gulf war
[0207] The result is listed in Table IV.
| TABLE IV | ||||
|---|---|---|---|---|
| Rank | No | Date | Document title | Result |
| 1 | 0 | 19870226 | iran announces end of major offensive | OK |
| in gulf war | ||||
| 2 | 3 | 19870227 | iran claims new victory near basra | OK |
| 3 | 63 | 19870412 | iraqi troops reported pushing back | OK |
| iranians | ||||
| — second choice — | ||||
| 4 | 20 | 19870314 | iraq says iran attack repulsed on | OK |
| southern front | ||||
| 5 | 67 | 19870413 | israeli helicopters raid south | OK |
| lebanon radio | ||||
| 6 | 68 | 19870414 | new gulf fighting not a major | OK |
| offensive us | ||||
| 7 | 18 | 19870312 | iraq says it crushed iranian attack in | OK |
| north | ||||
| 8 | 19 | 19870313 | iraq says it crushed iranian attack in | OK |
| north | ||||
| 9 | 66 | 19870413 | iran says it opens new offensive north | OK |
| of baghdad | ||||
| 10 | 65 | 19870412 | iran says it opens new offensive north | OK |
| of baghdad | ||||
| 11 | 61 | 19870411 | iran says offensive aimed at destroying | OK |
| iraq army | ||||
Example 4
[0208] In the example, the same procedure described in Example 2 was adopted while the ε (threhold) and η (attenuation) were set to 0.3 and 0.7, respectively, and therefore, a sensitivity on the follow-up articles was set between Example and Example 2.
[0209] QUERY 40 19870325 mcdonnell douglas gets 30 6 mln dlr
[0210] The result is listed in Table V.
| TABLE V | ||||
|---|---|---|---|---|
| Rank | No | Date | Document title | Result |
| 1 | 40 | 19870325 | mcdonnell douglas gets 30 6 mln dlr | OK |
| contract | ||||
| 2 | 72 | 19870601 | gull lt gll gets mcdonnell douglas lt md | OK |
| contract | ||||
| 3 | 45 | 19870405 | grumman lt gq unit wins mcdonnell | OK |
| douglas order | ||||
| — second choice — | ||||
| 4 | 73 | 19870601 | uk conservatives lead labour by seven | ERROR |
| points poll | ||||
| 5 | 74 | 19870602 | mcdonnell douglas lt md gets big thai | OK |
| air order | ||||
Example 5
[0211] Using the full Reuters-21578 database consisting of over 20,000 documents, a list of “new” documents was generated by looking for documents d(i) which are not relevant with respect to the user-specified threshold ε to any documents created up to 10 days before d(i). Results from the tracking experiment is listed in Table VI and Table VII, wherein Table VI shows answers expected and Table VII shows results obtained in the tracking experiment. As shown in Table VI and Table VII, the result obtained according to the present invention can pick-up the articles expected, and showed that the present invention is effective in such large databases.
| TABLE VI | ||
|---|---|---|
| Date | No | Document title |
| 19870316 | 5324 | thatcher party has nine point poll lead |
| 19870315 | 5160 | thatcher party has nine point poll lead |
| 19870407 | 13626 | british opinion polls keep conservatives ahead |
| 19870407 | 13533 | british opinion polls keep conservatives ahead |
| 19870407 | 13416 | british opinion polls keep conservatives ahead |
| 19870301 | 233 | british conservatives ahead of labour in new polls |
| 19870312 | 4165 | u k poll says tories have six-point lead |
| 19870312 | 4069 | new u k poll says tories have six-point lead |
| 19870405 | 13259 | british opinion polls confirm thatcher lead |
| TABLE VII | |||
|---|---|---|---|
| Rank | Date | No | Document title |
| 1 | 19870312 | 4069 | new u k poll says tories have six-point lead |
| 2 | 19870312 | 4165 | new u k poii says tories have six-point lead |
| 3 | 19870407 | 13626 | british opinion polls keep conservatives |
| ahead | |||
| 4 | 19870407 | 13416 | british opinion polls keep conservatives |
| ahead | |||
| 5 | 19870407 | 13533 | british opinion poiis keep conservatives |
| ahead | |||
| ----- second choice ----- | |||
| 6 | 19870316 | 5324 | thatcher party has nine-point poll lead |
| 7 | 19870309 | 3362 | noranda to spin of forest interests into |
| seperate company | |||
| 8 | 19870315 | 5160 | thatcher party has nine-point poll lead |
[0212] The foregoing Examples exhibited good results with respect to the detection of new events and tracking evolution thereof, and therefore, the present invention may provide novel and effective detection and tracking of the database.
[0213] As described above, the present invention has been described with respect to the specific embodiments thereof. However, a person skilled in the art may appreciate that various omissions, modifications, and other embodiments are possible within the scope of the present invention.
[0214] The present invention has been explained in detail with respect to the method for detection and tracking, however, the present invention also contemplates to include a system for executing the method described herein, a method itself, and a program product within which the program for executing the method according to the present invention may be stored. The true scope can be determined only by the claims appended.
Claims
What is claimed is:
1. A method for detecting new events and/or classes of documents and tracking evolution thereof in a database, said new events and/or classes of said documents being added to said database, said documents including attribute data related to a temporal parameter, said method comprising the steps of:
providing vectors of said documents based on attribute data that includes said temporal parameter, and
detecting said new events and/or classes of said documents and tracking evolution thereof using said vectors, wherein said tracking comprises evaluating vectors to determine whether said documents relate to new, follow-up, or old events and/or new, follow-up, or old classes.
2. The method according to claim 1, wherein said attribute data include at least one keyword, and said keyword is weighted with respect to a frequency of appearance in said document.
3. The method according to claim 2, wherein said temporal parameter is further weighted with respect to time elapse about a specific date, and a weight of said temporal parameter is less than the total weight of said keywords.
4. The method according to claim 1, wherein said detecting and tracking step further includes a step of providing a temporal window such that said detecting and tracking step is executed using said temporal window.
5. The method according to claim 4, wherein said temporal window is a delta function with respect to a specific date.
6. The method according to claim 4, wherein said temporal window is a symmetric Gaussian function.
7. The method according to claim 4, wherein said temporal window is a step function.
8. The method according to claim 4, wherein said temporal window is formed interactively by a user on a display window.
9. The method according to claim 4, wherein said temporal window is normalized before dimensional reduction for said vectors is carried out if the number of said keywords in each document is relatively constant in said database and the same temporal window is used for all of said documents.
10. The method according to claim 4, wherein several different temporal windows are provided so that the relative weights between said keywords and said temporal parameter becomes relatively constant from document to document if the number of said keywords in each document varies greatly.
11. A computer system including a database to which new events and/or classes of documents are added, said documents including data related to a temporal parameter, for detecting new events and/or classes of said documents and tracking evolution thereof, comprising:
means for providing vectors of said documents based on attribute data including said temporal parameter including in said document, and
means for detecting said new events and/or classes of said documents and tracking evolution thereof using said vectors, wherein said tracking comprises evaluating vectors to determine whether said documents relate to new, follow-up, or old events and/or new, follow-up, or old classes.
12. The computer system according to claim 11, wherein said attribute data include at least one keyword, and said keyword is weighted with respect to a frequency of appearance in said documents.
13. The computer system according to claim 12, wherein said temporal parameter is further weighted with respect to time elapse about a specific date, and weight of said temporal parameter is less than the total weight of said keywords.
14. The computer system according to claim 11, wherein said detecting and tracking means further includes means for providing a temporal window such that said temporal window is used by said detecting and tracking means.
15. The computer system according to claim 14, wherein said temporal window is a delta function with respect to a specific date.
16. The computer system according to claim 14, wherein said temporal window is a symmetric Gaussian function.
17. The computer system according to claim 14, wherein said temporal window is a step function.
18. The computer system according to claim 14, wherein said temporal window is formed interactively by a user on a display window.
19. The computer system according to claim 14, wherein said temporal window is normalized before dimensional reduction for said vectors is carried out if the number of said keywords in each document is relatively constant in said database and the same temporal window is used for all of said documents.
20. The computer system according to claim 14, wherein several different temporal windows are provided so that the relative weights between said keywords and said temporal parameter becomes relatively constant from document to document if the number of said keywords in each document varies greatly.
21. The computer system according to claim 11, wherein said computer system comprises a server and at least one client, and said detection and tracking step is requested from at least one client computer which transmits to said server and receives a result from said detection and tracking step.
22. A program product for detecting new events and/or classes of documents and tracking evolution thereof in a database, said new events and/or classes of said documents being added to said database, said documents including attribute data related to a temporal parameter, said method comprising steps of:
providing vectors of said documents based on attribute data that includes said temporal parameter, and
detecting said new events and/or classes of said documents and tracking evolution thereof using said vectors, wherein said tracking comprises evaluating vectors to determine whether said documents relate to new, follow-up, or old events and/or new, follow-up or old classes.
23. The program product according to claim 22, wherein said attribute data include at least one keyword, and said keyword is weighted with respect to a frequency of appearance in said documents.
24. The program product according to claim 2, wherein said time temporal parameter is further weighted with respect to time elapse from a specific date, and a weight of said temporal parameter is less than the total weight of said keywords.
25. The program product according to claim 22, wherein said detecting and tracking step further includes a step of providing a temporal window such that said detecting and tracking step is executed using said temporal window.
26. The program product according to claim 25, wherein said temporal window is a delta function with respect to a specific date.
27. The program product according to claim 25, wherein said temporal window is a symmetric Gaussian function.
28. The program product according to claim 25, wherein said temporal window is a step function.
29. The program product according to claim 25, wherein said temporal window is formed interactively by a user on a display window.
30. The program product according to claim 25, wherein said temporal window is normalized before dimensional reduction for said vectors is carried out if the number of said keywords in each document is relatively constant in said database and the same temporal window is used for all of said documents.
31. The program product according to claim 25, wherein several different temporal windows are provided so that the relative weight between said keywords and said temporal parameter becomes relatively constant from document to document it the number of said keywords in each document varies greatly.
Patent Citations (2)
Non-Patent Literature (20)
- Yang et al. (“Learning Approaches for Detecting and Tracking News Events”, IEEE Jul./Aug. 1999, pp. 32-43).Applicant
- “Topic Detection and Tracking Pilot Study Final Report” Proceedings of the DARPA Broadcast News Transcription and Understanding Workshop, 1998 James Allan et al.Applicant
- IEEE Intelligent Systems & their applications, (Guest Editors' Introduction)“Intelligent Informaton Retrieval” Yiming Yang & Jan Pedersen pp 30-31, Jul./Aug. 1999.Applicant
- IEEE Intelligent Systems & their applications, Intelligent Information Retrieval “Learning Approaches for Detecting and Tracking News Events” Yiming Yang et al pp. 32-43, Jul./Aug. 1999.Applicant
- IEEE Intelligent Systems & their applications, Intelligent Information Retrieval “Maximizing Text-Mining Performance” Sholom M. Weiss et al pp 63-69, Jul./Aug. 1999.Applicant
- Informedia Digital Video Library Research at Carnegie Mellon Univ. http://www.informedia.cs.cmu.edu/ Copyright 2000.Applicant
- Informedia-I Digital Video Library Project http://www.informedia.cs.cmu.edu/dli1/ Copyright 2000.Applicant
- Informedia-II Auto Summarization and Visualization Across Multiple Video Documents and Libraries http://www.informedia.cs.cmu.edu/dli2/ Copyright 2000.Applicant
- Proc. DARPA Broadcast News Workshop Feb. 28-Mar. 3, 1999 DARPA BNN Workshop Table of Contents http://www.itl.nist.gov/iaui/894.01/proc/darpa99/.Applicant
- Proc. DARPA Broadcast News Workshop Feb. 28-Mar. 3, 1999 DARPA BNN Workshop Abstracts http://www.itl.nist.gov/iaui/894.01/proc/darpa99/html/abstract.htm.Applicant
- Proc. DARPA Broadcast News Workshop Feb. 28-Mar. 3, 1999 “Dragon Systems' Automatic Transcription of New TDT Corpus” L. Gillick et al, http://www.itl.nist.gov/iaui/894.01/proc/darpa99.Applicant
- Proc. DARPA Broadcast News Workshop Feb. 28-Mar. 3, 1999 “Topic Detection & Tracking (TDT) Overview & Perspective” Charles L. Wayne. http://www.itl.nist.gov/iaui/894.01/proc/darpa98/html/tdl10/tdt10.htm.Applicant
- Proc. DARPA Broadcast News Workshop Feb. 28-Mar. 3, 1999 “The Topic Detection and Tracking Phase 2 (TDT2) Evaluation Plan” George Doddington http://www.itl.nist.gov/iaui/894.01/proc/darpa98/htm/tdt60/tdt60.htm.Applicant
- Proc. DARPA Broadcast News Workshop Feb. 28-Mar. 3, 1999 “GETRACKER: A Robust, Lightweight Topic Tracking System”T. Strzalkowski et al http://www.itl.nist.gov/iaui/894.01/proc/darpa99.Applicant
- Proc. DARPA Broadcast News Workshop Feb. 28-Mar. 3, 1999 “The Beta-Binomial Mixture Model and Its Appliction to TDT Tracking and Detection ”Stephen A. Lowe http://www.itl.nist.gov/iaui/894.01/proc/darpa99.Applicant
- Proc. DARPA Broadcast News Workshop Feb. 28-Mar. 3, 1999 “Topic Tracking in a News Stream” J.P. Yamron et al http://www.itl.nist.gov/iaui/894.01/proc/darpa99.Applicant
- Proc. DARPA Broadcast News Workshop Feb. 28-Mar. 3, 1999 “UMASS Approaches to Detection and Tracking at TDT2” Ron Papka et al http://www.itl.nist.gov/iaui/894.01/proc/darpa99.Applicant
- Proc. DARPA Broadcast News Workshop Feb. 28-Mar. 3, 1999 “NIST'S 1998 Topic Detection and Tracking Evaluation (TDT2)”J. Fiscus et al http://www.itl.nist.gov/iaui/894.01/proc/darpa99.Applicant
- Proc. DARPA Broadcast News Workshop Feb. 28-Mar. 3, 1999 “A Cluster-Based Approach to Tracking, Detection and Segmentation of Broadcast News” D. Eichmann et al http://www.itl.nist.gov/iaui/894.01/proc/darpa99.Applicant
- Proc. DARPA Broadcast News Workshop Feb. 28-Mar. 3, 1999 “Topic Detection in Broadcast News” F. Walls et al http://www.itl.nist.gov/iaui/894.01/proc/darpa99.Applicant