Virtual structured information system

• US 5,983,232 A
• Filed: 09/28/1998
• Issued: 11/09/1999
• 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
• Primary Examiner(s): HO, RUAY L
• Application Number:
  US09/162,186
• Time in Patent Office: 407 Days
• Field of Search: 707/1-10, 707/100-104, 707/200-206, 345/419, 364/265.5, 364/285.4, 364/927.2, 395/185.03, 395/828
• 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/99943 Generating database or data structure, e.g. via user interface

Abstract

A virtual structured information system or a virtual database is developed and presented in the framework of an information theory for multiple source information systems such as databases. A virtual tree structure is built from virtual nodes in main memory which contain no raw data. The virtual nodes and virtual trees provide general non-data virtual structure, like cross-table nodes, for systematic information manipulations such as on-line analytical processing in a structured information system.

Claims

1. A method of building a virtual information structure with respect to an associative memory database, comprising the steps of:

providing an input tree structure representative of the associative memory database, the input structure including a plurality of memory nodes;

building a number of unstructured virtual information sources at a given memory node in an existing memory tree structure; and

building a virtual structure from the unstructured virtual sources.

2. The method of claim 1, wherein the unstructured virtual information sources are memory tokens associated with at least certain of the nodes of the input structure.

3. The method of claim 1, wherein the unstructured virtual information sources are indices associated with at least certain of the nodes of the input structure.

4. The method of claim 1, including memory nodes having tokens or indices associated with an closest common ancestor node in the input structure, enabling the tokens or indices to be propagated to the closest common ancestor node when building the virtual structure from the unstructured virtual sources.

5. A method of creating a virtual node in an information tree structure, comprising the steps of:

identifying two nodes a and b in an existing information tree structure, the two nodes having a common ancestor node n_a, wherein;

a) the closest common ancestor node has a child node that is an ancestor node of only one node of the two nodes a and b, and

b) the other child node of the common ancestor node n_a is an ancestor node of the other one of the two nodes a and b;

recalling the memory tokens, defined as the memory addresses of unique data values, of node a at the memory of node n₁, thereby replacing the original tokens stored at the n₁ memory with the recalled tokens of node a using one or more look-up tables;

recalling the memory tokens of node b at the memory of node n_r, thereby replacing the original tokens stored at the n_r memory with the recalled tokens of node a using one or more look-up tables;

removing the redundancy of the list indices, if any such redundancy is present, by combining all the lists that have the same list index, so that all the new lists have unique indices;

removing the redundancy of the list elements, if any such redundancy is present, by eliminating repetitious elements and storing a count the repeats in each new list,

the result after redundancy removal being a virtual node memory structure identical to a real node as if it were built from the output streams of two leaf nodes a and b.

6. The method of claim 5, wherein the values of a and b exist in rows or records enabling the values to be presented on the virtual node by replacing the memory tokens in pairs by the corresponding field values after recalling dictionaries.

7. The method of claim 5, further including the step of presenting a pattern by printing out a list of data values of node b pairing with the same list index representing the corresponding data value in node a.

8. The method of claim 5, wherein the existing information tree structure includes some form of hashing storing a set of lists indexing left and right child nodes.