Wei Jay Fan

7287023, Oct 23, 2007

Nov 26, 2003

10/723206

Wei Fan - New York NY, US
Haixun Wang - Tarrytown NY, US
Philip Shi-Lung Yu - Chappaqua NY, US

International Business Machines Corporation - Armonk NY

G06F 17/30

707 3, 707100, 707102

The present invention provides a ViST (or “virtual suffix tree”), which is a novel index structure for searching XML documents. By representing both XML documents and XML queries in structure-encoded sequences, it is shown that querying XML data is equivalent to finding (non-contiguous) subsequence matches. A variety of XML queries, including those with branches, or wild-cards (‘*’ and ‘//’), can be expressed by structure-encoded sequences. Unlike index methods that disassemble a query into multiple sub-queries, and then join the results of these sub-queries to provide the final answers, ViST uses tree structures as the basic unit of query to avoid expensive join operations. Furthermore, ViST provides a unified index on both content and structure of the XML documents, hence it has a performance advantage over methods indexing either just content or structure. ViST supports dynamic index update, and it relies solely on BTrees without using any specialized data structures that are not well supported by common database management systems (hereinafter referred to as “DBMSs”).

7337161, Feb 26, 2008

Jul 30, 2004

10/903336

Wei Fan - New York NY, US
Haixun Wang - Tarrytown NY, US
Philip S. Yu - Chappaqua NY, US

International Business Machines Corporation - Armonk NY

G06F 17/30

707 1, 707100

Most recent research of scalable inductive learning on very large streaming dataset focuses on eliminating memory constraints and reducing the number of sequential data scans. However, state-of-the-art algorithms still require multiple scans over the data set and use sophisticated control mechanisms and data structures. There is discussed herein a general inductive learning framework that scans the dataset exactly once. Then, there is proposed an extension based on Hoeffding's inequality that scans the dataset less than once. The proposed frameworks are applicable to a wide range of inductive learners.

7418455, Aug 26, 2008

Nov 26, 2003

10/723229

Wei Fan - New York NY, US
Haixun Wang - Tarrytown NY, US
Philip Shi-Lung Yu - Chappaqua NY, US

International Business Machines Corporation - Armonk NY

G06F 7/00
G06F 17/00

707102

The present invention provides an index structure for managing weighted-sequences in large databases. A weighted-sequence is defined as a two-dimensional structure in which each element in the sequence is associated with a weight. A series of network events, for instance, is a weighted-sequence because each event is associated with a timestamp. Querying a large sequence database by events' occurrence patterns is a first step towards understanding the temporal causal relationships among the events. The index structure proposed herein enables the efficient retrieval from the database of all subsequences (contiguous and non-contiguous) that match a given query sequence both by events and by weights. The index structure also takes into consideration the nonuniform frequency distribution of events in the sequence data.

7424619, Sep 9, 2008

Oct 11, 2002

10/269694

Wei Fan - New York NY, US
Salvatore J. Stolfo - Ridgewood NY, US

The Trustees of Columbia University in the city of New York - New York NY

G06F 11/30
G06F 11/00
G06F 17/30
H04L 9/32
H04L 12/56
H04L 12/26
H04L 12/24
G05B 13/02

713188, 726 22, 726 23

In a method of generating an anomaly detection model for classifying activities of a computer system, using a training set of data corresponding to activity on the computer system, the training set comprising a plurality of instances of data having features, and wherein each feature in said plurality of features has a plurality of values. For a selected feature and a selected value of the selected feature, a quantity is determined which corresponds to the relative sparsity of such value. The quantity may correspond to the difference between the number occurrences of the selected value and the number of occurrences of the most frequently occurring value. These instances are classified as anomaly and added to the training set of normal data to generate a rule set or other detection model.

7464068, Dec 9, 2008

Jun 30, 2004

10/880913

Wei Fan - New York NY, US
Haixun Wang - Tarrytown NY, US
Philip S. Yu - Chappaqua NY, US

International Business Machines Corporation - Armonk NY

G06F 17/30

707 1, 707 5

In connection with the mining of time-evolving data streams, a general framework that mines changes and reconstructs models from a data stream with unlabeled instances or a limited number of labeled instances. In particular, there are defined herein statistical profiling methods that extend a classification tree in order to guess the percentage of drifts in the data stream without any labelled data. Exact error can be estimated by actively sampling a small number of true labels. If the estimated error is significantly higher than empirical expectations, there preferably re-sampled a small number of true labels to reconstruct the decision tree from the leaf node level.

7475070, Jan 6, 2009

Jan 14, 2005

11/035889

Wei Fan - New York NY, US
Haixun Wang - Irvington NY, US
Philip S. Yu - Chappaqua NY, US

International Business Machines Corporation - Armonk NY

G06F 17/30
G06F 17/00

707 6, 707 3, 707100

Sequence-based XML indexing aims at avoiding expensive join operations in query processing. It transforms structured XML data into sequences so that a structured query can be answered holistically through subsequence matching. Herein, there is addressed the problem of query equivalence with respect to this transformation, and thereis introduced a performance-oriented principle for sequencing tree structures. With query equivalence, XML queries can be performed through subsequence matching without join operations, post-processing, or other special handling for problems such as false alarms. There is identified a class of sequencing methods for this purpose, and there is presented a novel subsequence matching algorithm that observe query equivalence. Also introduced is a performance-oriented principle to guide the sequencing of tree structures. For any given XML dataset, the principle finds an optimal sequencing strategy according to its schema and its data distribution; there is thus presented herein a novel method that realizes this principle.

7565346, Jul 21, 2009

May 31, 2004

10/858541

Wei Fan - New York NY, US
Haixun Wang - Tarrytown NY, US
Philip S. Yu - Chappaqua NY, US

International Business Machines Corporation - Armonk NY

G06F 17/30

707 6

Unlike traditional clustering methods that focus on grouping objects with similar values on a set of dimensions, clustering by pattern similarity finds objects that exhibit a coherent pattern of rise and fall in subspaces. Pattern-based clustering extends the concept of traditional clustering and benefits a wide range of applications, including e-Commerce target marketing, bioinformatics (large scale scientific data analysis), and automatic computing (web usage analysis), etc. However, state-of-the-art pattern-based clustering methods (e. g. , the pCluster algorithm) can only handle datasets of thousands of records, which makes them inappropriate for many real-life applications. Furthermore, besides the huge data volume, many data sets are also characterized by their sequentiality, for instance, customer purchase records and network event logs are usually modeled as data sequences. Hence, it becomes important to enable pattern-based clustering methods i) to handle large datasets, and ii) to discover pattern similarity embedded in data sequences. There is presented herein a novel method that offers this capability.

7565369, Jul 21, 2009

May 28, 2004

10/857030

Wei Fan - New York NY, US
Haixun Wang - Tarrytown NY, US
Philip S. Yu - Chappaqua NY, US

International Business Machines Corporation - Armonk NY

G06F 17/30

707102, 7071041

A general framework for mining concept-drifting data streams using weighted ensemble classifiers. An ensemble of classification models, such as C4. 5, RIPPER, naive Bayesian, etc. , is trained from sequential chunks of the data stream. The classifiers in the ensemble are judiciously weighted based on their expected classification accuracy on the test data under the time-evolving environment. Thus, the ensemble approach improves both the efficiency in learning the model and the accuracy in performing classification. An empirical study shows that the proposed methods have substantial advantage over single-classifier approaches in prediction accuracy, and the ensemble framework is effective for a variety of classification models.