Hierarchical data-driven search and navigation system and method for information retrieval
1 Assignment
0 Petitions
Accused Products
Abstract
A data-driven, hierarchical information search and navigation system and method enable search and navigation of sets of documents or other materials by certain common attributes that characterize the materials. The invention includes several aspects of a data-driven, hierarchical search and navigation system that employs this search and navigation mode. The search and navigation system of the present invention includes features of an navigation interface, a search interface, a knowledge base and a taxonomy definition process and a classification process for generating the knowledge base, a graph-based navigable data structure and method for generating the data structure, World Wide Web-based applications of the system, and methods of implementing the system. Users are able to search or browse a particular collection of documents by selecting desired values for the attributes or by searching the attribute-value pairs. A data-driven, hierarchical information search and navigation system and method enable this navigation mode by associating terms with the materials, defining a set of hierarchical relationships among the terms, providing a guided navigation mechanism based on the relationship between the terms, and providing a search mechanism that can respond to free-text queries with single-term or multi-term interpretations. In another aspect of the invention, implementations of the invention may be scalable through parallel or distributed computation.
200 Citations
109 Claims
-
1-43. -43. (canceled)
-
44. A computer-implemented method for providing an information navigation system comprising:
-
providing an information navigation system including a set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each of the values having an association with at least one of the attributes, each association defining an attribute-value pair, and a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of the materials, wherein for each navigation state the particular subset of the materials corresponding to the navigation state consists of those materials in the navigation system that are each described by every attribute-value pair in the particular set of attribute-value pairs corresponding to that navigation state;
wherein a first navigation state includes a first attribute-value pair having a first attribute, in which the first attribute-value pair does not describe all the materials in the navigation system that the first attribute characterizes; and
wherein a second navigation state includes a second attribute-value pair having the first attribute, in which the second attribute-value pair refines the first attribute-value pair; and
wherein at least one of the first navigation state and the second navigation state includes a third attribute-value pair having a third attribute, which is not the same as the first attribute, wherein the third attribute-value pair is mutually incomparable with the first attribute-value pair and is mutually incomparable with the second attribute-value pair, and the third attribute-value pair does not describe all the materials in the navigation system that the third attribute characterizes;
computing the navigation states, wherein for at least one navigation state the particular set of attribute-value pairs corresponding to that navigation state includes a plurality of mutually incomparable attribute-value pairs;
storing the navigation states in a data structure;
providing an interface to the information navigation system, the interface including a free-text search tool for searching descriptive information associated with the set of materials, and the interface providing a plurality of transitions, each transition providing a direct path, with no intervening navigation states, between two of the navigation states, wherein each transition represents a change from the set of attribute-value pairs corresponding to an originating navigation state to the set of attribute-value pairs corresponding to a destination navigation state, wherein a series of one or more transitions provides a path between any two navigation states, and wherein the interface provides a direct path, with no intervening navigation states, between the first navigation state and the second navigation state;
accepting a query to the navigation system; and
retrieving a stored navigation state responsive to the query. - View Dependent Claims (45, 46, 47, 48)
-
-
49. A computer-implemented method of providing an information navigation system
providing an information navigation system including a set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each of the values having an association with at least one of the attributes, each association defining an attribute-value pair, and a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of the materials, wherein for each navigation state the particular subset of the materials corresponding to the navigation state consists of those materials in the navigation system that are each described by every attribute-value pair in the particular set of attribute-value pairs corresponding to that navigation state; -
wherein a first navigation state includes a first attribute-value pair having a first attribute, in which the first attribute-value pair does not describe all the materials in the navigation system that the first attribute characterizes; and
wherein a second navigation state includes a second attribute-value pair having the first attribute, in which the second attribute-value pair refines the first attribute-value pair; and
wherein at least one of the first navigation state and the second navigation state includes a third attribute-value pair having a third attribute, which is not the same as the first attribute, wherein the third attribute-value pair is mutually incomparable with the first attribute-value pair and is mutually incomparable with the second attribute-value pair, and the third attribute-value pair does not describe all the materials in the navigation system that the third attribute characterizes;
generating a partial set of pre-computed navigation states;
storing the partial set of pre-computed navigation states in a data structure, the partial set of pre-computed navigation states stored in the data structure including at least one of the first navigation state and the second navigation state;
providing an interface to the information navigation system, the interface including a free-text search tool for searching descriptive information associated with the set of materials, and the interface providing a plurality of transitions, each transition providing a direct path, with no intervening navigation states, between two of the navigation states, wherein each transition represents a change from the set of attribute-value pairs corresponding to an originating navigation to the set of attribute-value pairs corresponding to a destination navigation state, wherein a series of one or more transitions provides a path between any two navigation states, and wherein the interface provides a direct path, with no intervening navigation states, between the first navigation state and the second navigation state;
accepting a query to the navigation system; and
returning a responsive navigation state by retrieving a responsive pre-computed navigation state or computing a responsive navigation state. - View Dependent Claims (50, 51, 52)
-
-
53. A computer-implemented method of providing an information navigation system comprising:
-
providing an information navigation system including. a set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each of the values having an association with at least one of the attributes, each association defining an attribute-value pair, and a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of the materials, wherein for each navigation state the particular subset of the materials corresponding to the navigation state consistes of those materials in the navigation system that are each described by every attribute-value pair in the particular set of attribute-value pairs corresponding to that navigation state;
wherein a first navigation state includes a first attribute-value pair having a first attribute, in which the first attribute-value pair does not describe all the materials in the navigation system that the first attribute characterizes; and
wherein a second navigation state includes a second attribute-value pair having the first attribute, in which the second attribute-value pair refines the first attribute-value pair; and
wherein at least one of the first navigation state and the second navigation state includes a third attribute-value pair having a third attribute, which is not the same as the first attribute, wherein the third attribute-value pair is mutually incomparable with the first attribute-value pair and is mutually incomparable with the second attribute-value pair, and the third attribute-value pair does not describe all the materials in the navigation system that the third attribute characterizes;
using a data structure to permit at least some of the navigation states to be computed dynamically;
providing an interface to the navigation system, the interface including a free-text search tool for searching descriptive information associated with the set of materials, and the interface providing a plurality of transitions, each transition providing a direct path, with no intervening navigation states, between two of the navigation states, wherein each transition represents a change from the set of attribute-value pairs corresponding to an originating navigation state to the set of attribute-value pairs corresponding to a destination navigation state, wherein a series of one or more transitions provides a path between any two navigation states, there being more than one path between at least a third navigation state and a fourth navigation state;
accepting a query to the navigation system;
generating a responsive navigation state using the data structure; and
presenting the responsive navigation state. - View Dependent Claims (54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101)
-
-
102. A computer program product, residing on a computer-readable medium, for use in providing an information navigation system, the computer program product comprising instructions for causing a computer to:
-
provide an information navigation system including a set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each of the values having an association with at least one of the attributes, each association defining an attribute-value pair, and a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of the materials, wherein for each navigation state the particular subset of the materials corresponding to the navigation state consists of those materials in the navigation system that are each described by every attribute-value pair in the particular set of attribute-value pairs corresponding to that navigation state;
wherein a first navigation state includes a first attribute-value pair having a first attribute, in which the first attribute-value pair does not describe all the materials in the navigation system that the first attribute characterizes; and
wherein a second navigation state includes a second attribute-value pair having the first attribute, in which the second attribute-value pair refines the first attribute-value pair; and
wherein at least one of the first navigation state and the second navigation state includes a third attribute-value pair having a third attribute, which is not the same as the first attribute, wherein the third attribute-value pair is mutually incomparable with the first attribute-value pair and is mutually incomparable with the second attribute-value pair, and the third attribute-value pair does not describe all the materials in the navigation system that the third attribute characterizes;
compute the navigation states, wherein for at least one navigation state the particular set of attribute-value pairs corresponding to that navigation state includes a plurality of mutually incomparable attribute-value pairs;
store the navigation states in a data structure;
provide an interface to the information navigation system, the interface including a free-text search tool for searching descriptive information associated with the set of materials, and the interface providing a plurality of transitions, each transition providing a direct path, with no intervening navigation states, between two of the navigation states, wherein each transition represents a change from the set of attribute-value pairs corresponding to an originating navigation state to the set of attribute-value pairs corresponding to a destination navigation state, wherein a series of one or more transitions provides a path between any two navigation states, and wherein the interface provides a direct path, with no intervening navigation states, between the first navigation state and the second navigation state;
accept a query to the navigation system; and
retrieve a stored navigation state responsive to the query. - View Dependent Claims (103, 104, 105)
-
-
106. A computer program product, residing on a computer-readable medium, for use in providing an information navigation system, the computer program product comprising instructions for causing a computer to:
-
provide an information navigation system including a set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each of the values having an association with at least one of the attributes, each association defining an attribute-value pair, and a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of the materials, wherein for each navigation state the particular subset of the materials corresponding to the navigation state consistes of those materials in the navigation system that are each described by every attribute-value pair in the particular set of attribute-value pairs corresponding to that navigation state;
wherein a first navigation state includes a first attribute-value pair having a first attribute, in which the first attribute-value pair does not describe all the materials in the navigation system that the first attribute characterizes; and
wherein a second navigation state includes a second attribute-value pair having the first attribute, in which the second attribute-value pair refines the first attribute-value pair; and
wherein at least one of the first navigation state and the second navigation state includes a third attribute-value pair having a third attribute, which is not the same as the first attribute, wherein the third attribute-value pair is mutually incomparable with the first attribute-value pair and is mutually incomparable with the second attribute-value pair, and the third attribute-value pair does not describe all the materials in the navigation system that the third attribute characterizes;
use a data structure to permit at least some of the navigation states to be computed dynamically;
provide an interface to the navigation system, the interface including a free-text search tool for searching descriptive information associated with the set of materials, and the interface providing a plurality of transitions, each transition providing a direct path, with no intervening navigation states, between two of the navigation states, wherein each transition represents a change from the set of attribute-value pairs corresponding to an originating navigation state to the set of attribute-value pairs corresponding to a destination navigation state, wherein a series of one or more transitions provides a path between any two navigation states, there being more than one path between at least a third navigation state and a fourth navigation state;
accept a query to the navigation system; and
generate a responsive navigation state using the data structure; and
present the responsive navigation state. - View Dependent Claims (107, 108, 109)
-
Specification