Multi-dimensional pattern analysis

• US 6,018,734 A
• Filed: 09/28/1998
• Issued: 01/25/2000
• Est. Priority Date: 09/29/1997
• Status: Expired due to Term

• Current Assignee: Aggregate Knowledge Incorporated (Neustar Incorporated)
• Original Assignee: Triada Limited
• Inventors: Zhang, Tao, Raghavan, K. R.
• Primary Examiner(s): Choules, Jack M.
• Application Number:
  US09/162,187
• Time in Patent Office: 484 Days
• Field of Search: 707/6, 707/1, 707/2, 707/3, 707/4, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A pattern recognition method applicable to unique associated pattern recognition in a structured information system or structured database is presented. The process may be used to find patterns in a column which are associated with unique data values in another column, or to find the number of unique values in the second column which are paired with the same associated pattern in the first column. The technique is easily extended to more general cases in which both the condition field and the associated pattern field may be two groups of fields.

Claims

1. A method of rearranging data within a computer to perform certain query operations, comprising the steps of:

loading the computer with data having two fields corresponding to a left leaf node a having left leaf node tokens relating to left node data values and a right leaf node b having right leaf node tokens relating to right node data values of a tree structure, and wherein the left leaf node has a first immediate ancestor node n₁, wherein n₁ is an ancestor node of leaf node a, but not of leaf node b, and the right leaf node has a second immediate ancestor node n_r, wherein n_r is an ancestor node of leaf node b, but not of leaf node a,

locating the immediate ancestor node the left leaf node n₁ of n_a of n₁, wherein n₁ has left ancestor tokens associated therewith;

locating the immediate ancestor node n_r of the right leaf node wherein n_r has right ancestor tokens associated therewith;

recalling the left leaf node tokens to node n₁ and recalling the right leaf node tokens to node n_r, thereby propagating the left leaf node tokens to node n₁ and the right leaf node tokens to node n_r ;

replacing the left ancestor tokens of node n₁ with the recalled left leaf node tokens and replacing the right ancestor tokens of node n_r with the right leaf node tokens to form a plurality of lists;

combining right leaf node tokens that pair with the same left node tokens;

eliminating those of the plurality of lists which store the same right leaf node tokens;

accounting for those of the plurality of the lists which are eliminated; and

sorting the remaining elements.

2. A method for identifying unique data values in a computer loaded structured information system having a condition field and an associated pattern field, comprising the steps of:

relating the condition field to a first unique value leaf node having first leaf node tokens relating to first data values, and the pattern field to a second unique value leaf node having second leaf node tokens relating to second data values;

determining a first immediate ancestor of the first unique value leaf node, the first ancestor not also being an immediate ancestor to the second unique value leaf node, wherein the first ancestor has first ancestor tokens;

determining a second immediate ancestor of the second unique value leaf node, such that the second ancestor is not also an immediate ancestor to the first unique value leaf node, wherein the second ancestor has second ancestor tokens;

pairing the first and second ancestor tokens to form a list;

replacing the first ancestor tokens with the first leaf node tokens and the second ancestor tokens with the second leaf node tokens;

replacing the first leaf node tokens in the list with the first data values and the second leaf node tokens with the second data values.

3. The method of claim 2 further comprising the steps of:

eliminating redundant first and second leaf node tokens from the list prior to replacing the first and second leaf node tokens with the first and second data values respectively.

4. The method of claim 3 further comprising the steps of:

eliminating redundant second leaf node tokens and the corresponding first leaf node tokens from the list; and

accounting for eliminated token redundancies prior to replacing the first and second leaf node tokens in the list with the first and second data values, respectively.

5. The method of claim 2 wherein the first and second immediate ancestors have a common ancestor node therebetween.

6. The method of claim 2 wherein the step of pairing the first and second ancestor tokens to form a list utilizes a hashing list to store a plurality of the second ancestor tokens with one of the first common ancestor tokens.