Management of query result complexity in hierarchical query result data structure using balanced space cubes

• US 6,571,249 B1
• Filed: 09/27/2000
• Issued: 05/27/2003
• Est. Priority Date: 09/27/2000
• Status: Expired due to Fees

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Weiss, Anton, Garrecht, Thomas, Loritz, Axel
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): Nguyen, Cindy
• Application Number:
  US09/669,888
• Time in Patent Office: 972 Days
• Field of Search: 707/100, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method, system, computer program product, server, and interface for managing query results includes receiving query results and semantic structuring information, and defining a root node corresponding to the query to which the results relate. A semantically structured tree descending from a root node has intermediate nodes in layers according to the semantic structuring information. The leaf nodes each correspond to a query result. The leaf nodes are attached to the tree based on an uptree relation. The tree has a space cube structure balanced on the basis of a semantic threshold.

Claims

1. A method of managing query result complexity for a set of query results of a query, said query having corresponding semantic structuring information including:

categories, each category having a corresponding category weight, each category having corresponding values, said categories having a category order based on said corresponding category weight, said method comprising;

(1) determining a semantic threshold;

(2) for each query result;

(2a) building an infoelement object;

(2b) based on the content of said query result, attributing to said infoelement object;

(2b1) a plurality of attributed category-values, each said attributed category-value corresponding to one of said categories,

(2b2) additional meta-information associated with said query result, and

(2b3) a respective weight, based on at least said additional meta-information, as an infoelement object weight;

(3) semantically structuring said query results in a tree-shaped hierarchy, including;

(3a) creating a root node;

(3b) setting as a present category the one of said categories first according to said category order, and setting as a set of immediately upward nodes said root node;

(3c) performing semantic node construction for said present category, comprising;

(3c1) for each value of said values corresponding to said present category;

(3c1a) for each immediately upward node in said set of immediately upward nodes;

 

(3c1a-i) identifying an upward path of nodes from said immediately upward node up to said root node;

 

(3c1a-ii) making a determination as to whether there exists at least one of said infoelement objects having one of said attributed category-values equivalent to a respective attributed node value of each of said said nodes in said upward path;

 

(3c1a-iii) when said determination indicates existence, creating a node attached to said immediately upward node;

 

(3c1a-iv) attributing to said node thus created said value of said values corresponding to said present category as said respective attributed node value;

 

(3c1a-v) defining a space cube with a space cube root node and space cube leaf nodes, wherein said immediately upward node is said space cube root node, and each said node created and attached to said node immediately upward is one of said space cube leaf nodes;

 

(3c1a-vi) determining, as a space cube fanout of said space cube root node, the number of space cube leaf nodes attached to said space cube root node; and

 

(3c1a-vii) when said space cube fanout exceeds said semantic threshold, performing a space cube restructuring operation to reduce said space cube fanout to or below said semantic threshold; and

then

(3d) in said category order;

(3d1) setting as said present category, in turn, each of said categories other than said category first according to said category order;

(3d2) setting as said set of immediately upward nodes each lowest level space cube leaf node; and

(3d3) performing said semantic node construction for said present category; and

then

(3e) for each lowest level said space cube leaf node defined in said semantic node construction of the one of said categories last according to said category order;

(3e1) identifying, as related infoelements, all of said infoelement objects comprising attributed category-values equivalent to the respective attributed node values of said lowest level space cube leaf node and said nodes in said upward path;

(3e2) defining said lowest level space cube leaf node as a space cube root node having, as respective space cube leaf nodes said related infoelements;

(3e3) determining said respective space cube fanout; and

(3e4) when said respective space cube fanout exceeds said semantic threshold, performing said space cube restructuring operation to reduce said respective space cube fanout to or below said semantic threshold;

wherein said space cube restructuring operation comprises;

(I) identifying, for each of said space cube leaf nodes, a respective relevant set of infoelement objects comprising ones of said infoelement objects having one of said attributed category-values equivalent to a respective attributed node value of each of said space cube leaf node and of said nodes in said upward path;

(II) determining, for each said space cube leaf node, a respective leaf node weight based on the respective weights for said infoelement objects in said respective relevant set;

(III) determining, for said space cube root node, an overall weight including said respective leaf node weights for each said respective relevant set of infoelements;

(IV) determining a balanced branch weight as a function of said overall weight and said semantic threshold;

(V) until said space cube fanout meets said semantic threshold;

(V-1) detaching ones of said space cube leaf nodes having said respective leaf node weight less than said balanced branch weight from said space cube root node to provide detached space cube leaf nodes;

(V-2) determining a combination of said detached space cube leaf nodes having a combined weight of approximately said balanced branch weight;

(V-3) attaching to said space cube root node a new space cube leaf node representing said combination of said detached space cube leaf nodes; and

(V-4) defining one of said space cubes having said new space cube leaf node as a new space cube root node thereof, and said combination of said detached space cube leaf nodes as said space cube leaf nodes thereof; and

then

(V-5) when said space cube fanout of said space cube thus defined exceeds said semantic threshold, performing said space cube restructuring operation to reduce said space cube fanout to or below said semantic threshold;

wherein, when said new space cube root node is defined during said space cube restructuring operation, said new space cube root node is attributed with a corresponding attributed node value based on a lexical function of said combination of detached space cube leaf nodes.

2. A method of managing query result complexity for a set of query results of a query, said query having corresponding semantic structuring information including:

categories, each category having a corresponding category weight, each category having corresponding values, said categories having a category order based on said corresponding category weight, said method comprising;

determining a semantic threshold;

for each query result, building an infoelement object with attributes comprising;

corresponding category-values,

additional meta-information, and

a respective weight, based on at least said additional meta-information, as an infoelement object weight;

semantically structuring said query results in a tree-shaped hierarchy of space cubes on the basis of said corresponding category-values, including performing semantic node construction for each of said categories in said category order, wherein space cube restructuring is performed when a space cube fanout of one of said space cubes exceeds said semantic threshold;

wherein a new space cube root node defined during said space cube restructuring is attributed with a corresponding attributed node value based on a lexical function of ones of said set of query results having an uptree relation to said new space cube root node.

3. A method of managing query results, comprising:

receiving said query results;

receiving semantic structuring information;

defining a root node corresponding to a query;

creating a semantically structured tree comprising said root node and intermediate nodes in layers, said intermediate nodes being arranged in said layers according to said semantic structuring information, said tree further comprising lowest level leaf nodes corresponding to ones of said query results, each of said leaf nodes being attached on the basis of an uptree relation;

wherein said tree has a space cube structure balanced on the basis of a semantic threshold.

4. The method of managing query results as set forth in claim 3, wherein said semantic threshold is 9.

5. A computer system for managing query results, comprising:

a processor;

a memory under control of said processor, and storing instructions adapted to enable said processor to perform steps of;

receiving said query results;

receiving semantic structuring information;

defining a root node corresponding to a query;

creating a semantically structured tree comprising said root node and intermediate nodes in layers, said intermediate nodes being arranged in said layers according to said semantic structuring information, said tree further comprising lowest level leaf nodes corresponding to ones of said query results, each of said leaf nodes being attached on the basis of an uptree relation;

wherein said tree has a space cube structure balanced on the basis of a semantic threshold.

6. The computer system for managing query results as set forth in claim 5, wherein said semantic threshold is 9.

7. A computer program product for implementing a method of managing query results, comprising:

a computer readable medium, and

instructions on said computer readable medium, adapted to enable a computer to implement the steps of;

receiving said query results;

receiving semantic structuring information;

defining a root node corresponding to a query;

creating a semantically structured tree comprising said root node and intermediate nodes in layers, said intermediate nodes being arranged in said layers according to said semantic structuring information, said tree further comprising lowest level leaf nodes corresponding to ones of said query results, each of said leaf nodes being attached on the basis of an uptree relation;

wherein said tree has a space cube structure balanced on the basis of a semantic threshold.

8. The computer system for managing query results as set forth in claim 7, wherein said semantic threshold is 9.

9. A computer-readable data structure for sending semantic structuring information, comprising:

a user information section;

a semantic structuring section; and

a query results section;

wherein said semantic structuring section includes information relating to categories, corresponding category weights, and a plurality of corresponding values for one of said categories; and

wherein said semantic structuring section is adapted to enable a computer system to perform an operation for creating a semantically structured tree shaped hierarchy of the results in said query results section, balanced according to a predetermined semantic threshold.

10. A search application server, comprising:

a processor;

a memory under control of said processor, and storing instructions adapted to enable said processor to perform steps of;

receiving semantic structuring information;

creating and sending a query based on said semantic structuring information;

receiving query results related to said query;

processing said query results, based on said semantic structuring information, to produce a semantically structured tree shaped hierarchy balanced on the basis of a predetermined semantic threshold; and

sending root node, intermediate node, and infoelement data structures based on said tree shaped hierarchy.