US20070282809A1

Movatterモバイル変換

Info

Publication number: US20070282809A1
Application number: US11/526,409
Authority: US
Inventors: Orland Hoeber; Xue-Dong Yang; Yiyu Yao
Original assignee: Individual
Current assignee: Blackbird Tech LLC
Priority date: 2006-06-06
Filing date: 2006-09-25
Publication date: 2007-12-06
Also published as: US7809717B1; CA2549536A1; CA2549536C

Abstract

A method and apparatus is provided for visually coding or sorting search results based on the similarity of the search results to one or more concepts. A search query containing search terms is used to conduct a web search and obtain search results comprising a number of document surrogates describing the located web pages. Concepts are obtained using the search terms and the similarities between the obtained concepts and the search results are evaluated. The search results are then displayed in a manner that indicates the relative similarity of search results to one or more of the determined concepts, such as by sorting the search results based on the level of similarity of the search results to one or more concepts or by providing an accordance indicator with each displayed search result the accordance indicators indicating the similarity of the corresponding search result with one ore more of the concepts.

Description

RELATED APPLICATION

The present application claims the benefit of Canadian Patent Application Serial No. 2,549,536 filed Jun. 6, 2006, which is incorporated herein in its entirety by reference.

BACKGROUND

The World Wide Web has given computer users on the Internet access to vast amounts of information in the form of billions of Web pages. Each of these pages can be accessed directly by a user typing the URL (universal resource locator) of a web page into a web browser on the user's computer, but often, a person is more likely to access a website by finding it with the use of search engine. A search engine allows a user to input a search query made up of words or terms that a user thinks will be used in the web pages containing the information he or she is looking for. The search engine will attempt to match web pages to the terms in the search query and will then return the located web pages to the user.

The search results generated from a user's query typically consist of a collection of document surrogates, each of which contains summary information, attributes, and other meta-data about the matched documents. These documents surrogates are often presented in a simple list-based format, displaying the title of the document, a snippet containing.

the query terms in context, and the uniform resource locator (the URL). A user can then select one of the returned entries to view the corresponding web page.

With the continued growth of web pages available on the Internet making the task of search engines more and more difficult, web search engines have greatly increased the size of their indexes and made significant advances in the algorithms used to match a user's query to these indexes. However, while it is clear that significant effort has gone into creating web search engines that can index billion of documents and return the search results in a fraction of a second, this has resulted in the creation of the problem of search queries returning numerous results.

While relevant documents might be present in the search results returned from a search engine, often the returned search results consist of tens or hundreds of individual documents making it hard for a user to determine which of the search results may or may not be relevant to the information the user is looking for.

While information retrieval techniques used by web search engines have improved substantially over the years, the search results are still typically represented in a simple list-based format. Although this list-based representation makes it easy to evaluate a single document, it does not support the users in the broader tasks of manipulating the search results, comparing documents, or finding a set of relevant documents. Even though this simple list-based representation provides the search results in a clear and effective manner for determining the relevance of individual document surrogates, it requires that each document surrogate be evaluated in turn, and to some degree, in the order provided. If hundreds of documents are returned it is inefficient if not completely impractical to have a user review hundreds of results to determine the most relevant document located in the search. Requiring users to evaluate each document surrogate individually, often with only ten documents per page, leads to a common user search trait of evaluating only a few pages of search results before either re-formulating their query or giving up.

One solution that can be used to address these numerous search results is for the user to reformulate his or her search query to narrow the search with the result that fewer document are located mating the search query, however, in many cases there may be high quality relevant documents buried in the search results set that were missed because the users did not look at enough search result pages.

Another method Mat has also been used is to cluster the search results such that documents that are similar to one another are grouped together. In such a system, a user navigates the clusters in order to narrow down the search results and avoid clusters of relevant documents. Ideally, the user will select the relevant clusters and view lists of the returned documents in which a large portion are relevant to the requirements of the user.

One of the problems with these systems is that determining what the clusters should be centered around and determining an adequate description of the cluster. If the information does not correctly describe the document contained in the cluster, a user may either choose clusters that are not relevant or entirely miss clusters that may contain relevant documents.

SUMMARY OF THE INVENTION

It is an object of the present invention to provide a system and method that overcomes problems in the prior art.

In a first aspect of the invention, a method is provided for visually coding search results based on at least one concept. The method comprises: using a search query containing a plurality of search terms to conduct a search of a plurality of computer readable documents and obtain the search results, the search results comprising at least one returned documents; obtaining the at least one concept by matching the plurality of search terms to the at least one concept; evaluating the similarity between the at least one returned document and the at least one concept; and displaying the at least one returned document with an accordance indicator. The accordance indicator indicates tee similarity between the at least one returned document and the at least one concept.

In a second aspect of the invention, a data processing system for visually coding search results based on at least one concept. The data processing system comprises: at least one processor, a memory operatively coupled to the at least one processor; a display device operative to display data; and a program module stored in the memory and operative for providing instructions to the at least one processor. The at least one processor is responsive to the instructions of the program module. The program module operative is for: using a search very containing at least one search term to conduct a seal of a plurality of computer readable documents and obtain search results comprising a plurality of returned documents; obtaining the least one concept by matching the at least one search term to the at least one concept; evaluating the similarity between a returned document and the at least one concept; and displaying on the display device the returned document with an accordance indicator. The accordance indicator indicates the similarity between the returned document and the at least one concept.

In a third aspect of the invention, a method of visually sorting search results based on at least one concept is provided. The method comprises: using a search query containing a plurality of search terms to conduct a search of a plurality of computer readable documents and obtain the search results, the search results comprising a first returned document and a second returned document; obtaining the least one concept by matching the plurality of search terms to the at least one concept; determining a first accordance value by evaluating the similarity between the first returned document and the at least one concept and a second accordance value by evaluating the similarity between the second returned document and the at least one concept; and displaying the first returned document and second returned document sorted in an order based on the fist accordance value and the second accordance value.

In a fourth aspect of the invention, a data processing system for visually sorting search results based on at feast one concept. The data processing system comprises: at least one processor, a memory operatively coupled to the at least one processor, a display device operative to display data; and a program module stored in the memory and operative for providing instructions to the at least one processor. The at least one processor is responsive to the instructions of the program module. The program module operative is for: using a search query containing a plurality of search terms to conduct a search of a plurality of computer readable documents and obtain the search results, the search results comprising a first returned document and a second returned document; obtaining the least one concept by matching the plurality of search terms to the at least one concept; determining a first accordance value by evaluating the similarity between the first returned document and the at least one concept and a second accordance value by evaluating the similarity between the second returned document and the at least one concept; and displaying the first returned document and second returned document sorted in an order based on the first accordance value and the second accordance value.

In a further aspect of the invention, a computer readable memory having recorded thereon statements and instructions for execution by a computer to carry out the above methods is provided.

DESCRIPTION OF THE DRAWINGS

While the invention is claimed in the concluding portions hereof, preferred embodiments are provided in the accompanying detailed description which may be best understood in conjunction with the accompanying diagrams where like parts in each of the several diagrams are labeled with like numbers, and where:

FIG. 1 is a schematic illustration of a data processing system suitable for supporting the operation of methods in accordance with the present invention;

FIG. 2A is a schematic illustration of a network configuration suitable for supporting the operation of methods in accordance with the present invention wherein the data processing system is connected over a network to a plurality of servers operating as a search engine;

FIG. 2B is a schematic illustration of a network configuration suitable for supporting the operation of methods in accordance with the present invention wherein the data processing system is configured as a server and a remote device is used to access the data processing system;

FIG. 3 is an architectural schematic of a data structure for a concept knowledge base in accordance with an aspect of the present invention;

FIG. 4 illustrates a flowchart of a method of automatically creating a data structure containing a concept knowledge base in accordance with the present invention;

FIG. 5 is a schematic diagram of an overview of a software system in accordance with an aspect of the present invention;

FIG. 6 illustrates a flowchart of a method for generating a set of concepts based on the search terms in the search query in accordance with an aspect of a present invention;

FIG. 7 is a typical document surrogate data object, which is commonly provided as a returned document by a search engine as one of a set of search results;

FIG. 8 is a flowchart of a method of determining accordance values for each returned document in a set of search results;

FIG. 9 is an embodiment of a graphical interface displaying a number of returned documents with accordance indicators;

FIG. 10 is another embodiment of a graphical interface displaying a number of returned documents with accordance indicators and sorted by accordance values; and

FIG. 11 is an embodiment of a graphical interface displaying a number of returned documents with a plurality of accordance indicators for each displayed returned document.

DETAILED DESCRIPTION OF THE ILLUSTRATED EMBODIMENTS

Data Processing System

FIG. 1 illustrates adata processing system1 suitable for supporting the operation of methods in accordance with the present invention. Thedata processing system1 could be a personal computer, server, mobile computing device, cell phone, etc. Thedata processing system1 typically comprises: at least oneprocessing unit3; amemory storage device4; at least one input device5; a display device6 and aprogram module8.

Theprocessing unit3 can be any processor that is typically known in the art with the capacity to run the program and is operatively coupled to thememory storage device4 through a system bus. In some circumstances thedata processing system1 may contain more than oneprocessing unit3.

Thememory storage device4 is operative to store data and can be any storage device that is known in the art, such as a local hard-disk, etc. and can include local memory employed during actual execution of the program code, bulk storage, and cache memories for providing temporary storage. Additionally, thememory storage device4 can be a database that is external to thedata processing system1 but operatively coupled to thedata processing system1.

The input device5 can be any suitable device suitable for inputting data into thedata processing system1, such as a keyboard, mouse or data port, such as a network connection, and is operatively coupled to theprocessing unit3 and allowing theprocessing unit3 to receive information from the input device5.

The display device6 is a CRT, LCD monitor, etc. operatively coupled to thedata processing system1 and operative to display information. The display device6 could be a stand-alone screen or if thedata processing system1 is a mobile device, the display device6 could be integrated into a casing containing theprocessing unit3 and thememory storage device4.

Theprogram module8 is stored in thememory storage device4 and operative to provide instructions toprocessing unit3 and theprocessing unit3 is responsive to the instructions from theprogram module8.

Although other internal components of thedata processing system1 are not illustrated, it will be understood by those of ordinary skill in the art that only the components of thedata processing system1 necessary for an understanding of the present invention are illustrated and that many more components and interconnections between them are well known and can be used.

FIG. 2A illustrates a network configuration wherein thedata processing system1 is connected over anetwork55 to a plurality ofservers50 operating as a search engine.FIG. 2B illustrates a network configuration wherein thedata processing system1 is configured as a server and aremote device60, such as another computer, a PDA, cell phone or other mobile device connected to the Internet, is used to access thedata processing system1. Thedata processing system1 runs the majority of the software and methods, in accordance with the present invention, and accesses a plurality ofservers50 operating as a search engine to conduct a web search. By having thedata processing system1 configured as a server, theremote device60 does not need to have the capacity necessary to contain all the necessary data structures and run all the methods.

Furthermore, the invention can take the form of a computer readable medium having recorded thereon statements and instructions for execution by adata processing system1. For the purposes of this description, a computer readable medium can be any apparatus that can contain, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device. The medium can be an electronic, magnetic, optical, electromagnetic, infrared or semiconductor system (or apparatus or device) or a propagation medium. Examples of a computer-readable medium include a semiconductor or solid state memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk and an optical disk. Current examples of optical disks include compact disk—read only memory (CD-ROM), compact disk—read/write (CD-R/W) and DVD.

Concept Knowledge Base

FIG. 3 illustrates an architectural schematic of a data structure for aconcept knowledge base10, in accordance with an aspect of the present invention. The data structure is stored on a memory and is accessible by an application program being executed by a data processing system, such as thedata processing system1 illustrated inFIG. 1. The data structure contains information that is accessible by the application program.

Theconcept knowledge base10 contains information relating to a field of knowledge. For example, theconcept knowledge base10 could contain information related to the field of science. Theconcept knowledge base10 contains a number of concept data objects12, a number of term data objects14 and a number of edge data objects16.

Each concept data object12 contains aconcept field13 containing a concept that is related to a specific concept falling within the field of knowledge of theconcept knowledge base10. Theconcept field13 typically contains a text string identifying the concept. For example, if theconcept knowledge base10 is for computer science, there may be concept data objects12 with theconcept field13 containing the text string of “computer graphics”, another concept data object12 with theconcept field13 containing the text string of “distributed computing”, another concept data object12 with theconcept field13 containing the text string “artificial intelligence”, etc.

Each term data object14 contains aterm field15 containing a text string. The text string contains a word or phrase that describes a concept of one of the concept data objects12.

Each concept data object12 is associated with one or more term data objects14 and eachterm data object14 is associated with one ore more concept data objects12. The association of aconcept data object12 and aterm data object14 is defined by an edge data object16 which contains aweight field18. Aterm data object14 that is associated with a concept data object12 contains a term in theterm field15 that describes the concept contained in theconcept field13 of the concept data object12. The relevancy of the term in theterm field15 of the term data object14 to the concept in theconcept field13 of an associated concept data object12 is represented by a weight in theweight field18 of the edge data object16.

While it is possible to manually construct the data structure containing theconcept knowledge base10,FIG. 4 illustrates a flowchart of a method of automatically creating a data structure containing a concept knowledge base in accordance with the present invention.

Method

100 comprises the steps of: determining aconcept110; selecting a document describing theconcept120; determining terms in the document to be analyzed130; determining the frequency of the selectedterms140; checking if there are any remaining documents describing aconcept150; calling apreliminary weight160; checking if there are any more concepts170; and normalizing all of theweights180.

The method takes a number of documents and/or descriptions in computer readable form that describe a number of different concepts in a knowledge area and uses the documents to automatically generate a data structure of aconcept knowledge base10, as shown inFIG. 3.

Themethod100 begins withstep110. A concept falling within the concept knowledge base is determined and a concept data object is created with information identifying the concept contained in the concept field.

Each concept will be described by one or more document or descriptions in computer readable format. Once a concept has been determined atstep110, one or more documents describing the concept are identified and atstep120 one of these documents is selected to be analyzed.

At step130, themethod100 determines the terms to be analyzed in the document. For each term to be analyzed,method100 creates a term data object for each selected term with the term field containing the term, if a term data object containing the term does not already exist. An edge data object indicating the association of the term data object and the concept data object is also created and after themethod100 is completed will contain a weight indicating the relation of the term data object with the associated concept data object containing the concept described by the document being analyzed.

The terms that are analyzed can include all of the words used in the document or only specific words in the documents. For example, common words that are basically non-descriptive, such as “the”, “a”, “this”, etc. may be excluded from the selected terms that are selected for analysis at step130.

Atstep140 the frequency of each of the selected terms in the selected document is determined. The occurrence of each selected term in the document is determined. The occurrence of a selected term t_jin the document being analyzed can easily be determined, via text matching, and is defined by the function:

f(d_ik,t_i)

Each of the terms appearing in the document are then averaged based on the number of occurrences of all of the terms in the document. For example, the averaging could be done using the following equation:

f^{*} (d_{k}, t_{j}) = \frac{f (d_{ik}, t_{j})}{\sum_{l = 1}^{m} f (d_{ik}, t_{t, ik})}

where d_lkis the document bet analyzed for the set of terms t_ik=(t_l,ik, . . . , t_m,ik) with m being the number of terms in document d_ik. This equation simply divides the frequency or tally of a term being analyzed by the total number of terms being analyzed in document d_ik. By conducting this averaging, the eventual weight determined for each association between a term node and a concept node takes into account the number of occurrences of a term in the document and provides a potentially more relevant indicator of the relation between the term data object to the concept data object because words or terms that appear often relative to the total number of terms will be given more weight. This preliminary averaging is used to try to prevent a single large document describing a concept from providing term weights that overshadow the weights provided by a number of smaller documents.

Next, atstep150, themethod100 checks to see if there are any more documents related to the concept that have not been analyzed. If there are more documents to be analyzed related to the concept, themethod100 returns to step120, selects the next unanalyzed document and repeats

steps

130,140 and150. As long as more documents related to the concept exist,step150, causes themethod100 to analyze all of the documents. When there are no more documents related to the concept to be analyzed, themethod100 continues on to step160.

Atstep160 themethod100 calculates a preliminary weight for each of the terms used in the documents related to a single concept. For each term an interim weight w_ij* is calculated taking into account the average term frequency of the documents related to the concept.

w_{ij}^{*} = \frac{\sum_{k = 1}^{n} f^{*} (d_{ik}, t_{j})}{n}

Wherein there are 1 . . . n documents.

This equation, in its entirety, is as follows:

w_{ij}^{*} = \frac{\sum_{k = 1}^{n} \frac{f (d_{ik}, t_{j})}{\sum_{l = 1}^{m} f (d_{ik}, t_{1, ik})}}{n}

This calculation is used to prevent concepts with a large numbers of documents from producing term weights that overshadow term weights from concepts with fewer documents describing the concept.

At step170, themethod100 checks to see if there are any more concepts left to be evaluated. If there are concepts remaining that have not been analyzed, themethod100 returns to step110 and the next concept is selected to be analyzed. Themethod100 then repeats

steps

120,130,140,150 and160 determining a preliminary weight for each of the terms appearing in the documents describing the selected document. Themethod100 continues to analyze each

concept repeating steps

110,120,130,140,150,160 and170 until all of the concepts have been analyzed, at which point, themethod100 continues on to step180.

Atstep180 themethod100 determines a normalized weight for each of the terms associated with the concepts. The preliminary weight w_lj* previously determined for each association between a term t_iand a concept is divided by the sum of all of the weights determined for the term t_iconnected to r concepts. This equation is shown as follows:

w_{ij} = \frac{w_{ij}^{*}}{\sum_{k = 1}^{r} w_{if}^{*_{(k)}}}

Wherein the index f(k) is given by f(x), x=1 . . . r, representing the r concepts to which term i is connected to in the concept knowledge base.

The normalization of the weights is used to prevent common terms that are included in many of the documents for many concepts from having higher weight values than other less common terms. These terms are often of little value in describing a concept. By using normalization, the weights of common terms are significantly reduced. Without this normalization step, common terms that are included in many documents for many different concepts would have a very high weight, even though these terms are of little value in describing the concept. With this normalization step, the weights of these common terms are significantly reduce.

Additionally, rather than using the terms exactly as they appear in the documents or descriptions, in a further aspect of the invention, the stems of the roots of the terms are used to construct the knowledge base allowing terms to be matched based on their stems or roots rather than being based on exact text matches.

Additionally, in some circumstances it may not be necessary to analyze every term in a document. In a further aspect, themethod100 will focus on only specific terms in a document that are highlighted in a particular way, i.e. in an abstract. Alternatively, there could be a list of terms that are not analyzed, such as common terms that are not descriptive of a concept, for example terms such as the, and, etc. may be excluded from being selected.

At the conclusion of the method100 a concept knowledge base as illustrated inFIG. 3 will have been automatically constructed by themethod100.

Overview of System

FIG. 5 illustrates a software system in accordance with the present invention. Thesoftware system200 contains: asearch query module210; aconcept generator module220; aconcept knowledge database230; asearch module240; asearch engine module250; aconcept accordance module260; and avisualization interface module270.

A search query is input to thesystem200 at thesearch query module210. The search query contains one or more search terms and usually at least two or three search terms. From thesearch query module210 this search query containing one or more search terms is passed to theconcept generator module220, which uses theconcept knowledge database230 to select a set of concepts and generate a concept vector for each selected concept.

The search terms and the concept vectors are passed from theconcept generator module220 to thesearch module240 where thesearch module240 requests a search from thesearch engine250 using the search query and receives search results. Typically, the results returned by thesearch engine module250 are a list of returned documents, where each returned document is typically a document surrogate that describes the actual documents located by thesearch engine module250.

As the search results are received from thesearch engine module250, thesearch engine module250 passes the returned document to theconcept accordance module260 where a document vector is determined for each of the returned document and an accordance value indicating the similarity of the returned document to each of the concepts in the concept set is formulated. A fuzzy membership score is typically determined for the returned document relative to each of the concepts in the concept set and is used for the accordance value.

Thesearch module240 can wait until all the search results are returned from thesearch engine module250 before passing the search results all together to theconcept accordance module260, however, in one embodiment, thesearch module240 passes each returned document of the search results to theconcept accordance module260 as thesearch module250 receives the returned document to decrease the time required by thesystem200 to display the search results.

Finally, the concept set and the search results (comprising a plurality of returned document), with each returned document having an accordance value indicating the similarity of the returned document to each of the concepts in the concept set, are passed to thevisualization interface module270 wherein thevisualization interface module270 displays the search results to a user.

Thesoftware system200 can be implemented wholly on a data processing system, such as thedata processing system1 shown inFIG. 2A, with only thesearch engine module250 resident on aserver50 connected to thedata processing system1 over thenetwork55. Alternatively, various components of thesoftware system100, such as thesearch query module210 could be resident on amobile device60 operably connected to adata processing system1 which contains other components of thesoftware system200, (such as theconcept generator220,search module240, etc.) as shown inFIG. 2B.

Obtaining the Concepts

Thesoftware system200 begins with an initial search query being input to thesearch query module210 which passes the search query to theconcept generator module220. Theconcept generator module220 accesses theconcept knowledge database230 and uses the information in theconcept knowledge database230 to generate a concept set and a respective set of concept vectors using the search query.

FIG. 6 illustrates a flowchart of amethod400 for generating a set of concepts based on the search terms in the search query.Method400 is implemented by theconcept generator module220 inFIG. 4, using theconcept knowledge database230. When a search query is passed to theconcept generator module220, themethod400 uses theconcept knowledge database230 to generate a list of concepts using relationships between the search terms and concepts.

Method

400 comprises the steps of: matching terms in the search query to term data objects in the concept knowledge base to obtain afirst term set410; obtaining a concept set of concept data objects associated with thefirst term set420; obtaining a second term set of term data objects associated with the concepts objects in the concept set430; and formulating a set ofconcept vectors440.

Themethod400 begins withstep410 and matching the terms in the search query to term data objects in theconcept knowledge database230. Theconcept knowledge database230 is accessed and the terms making up the search query are matched with any term data objects that have a term in the term field matching the term in the search query. A fist term set containing these selected term data objects is obtained. Afterstep410 is completed, all of the term data objects in theconcept knowledge database230 that have a term in the term field that corresponds to one of the terms in the search query are identified and these term data objects have been added to a first term set.

Atstep420, the first term set is used to obtain a concept set containing concept data objects from theconcept knowledge database230 associated with one or more term data objects in the first term set. The term data objects making up the first term set are used to obtain a number of concept data objects from theconcept knowledge database230. Concept data objects associated with one or more term data objects in the first term set are selected to form the concept set.

Concept data objects that are not strongly associated with term data objects in the first term set can be excluded from the concept set using a first weight threshold and a term ratio threshold. The first weight threshold is used to exclude concept data objects that are not strongly associated with one of the term data objects in the first term set by comparing the weight assigned to an association between a concept data object and a term data object and excluding the concept data object from the concept set if the weight determined for the association is less than the first weight threshold. By using this first weight threshold, the concept set is limited to only the more relevant concepts. Additionally, a term ratio threshold is used to further exclude concept data objects from the concept set. If a concept data object is associated with one of the term data objects in the first term set with a weight greater than the first weight threshold, the concept data object is evaluated to determine the ratio of all of the term data objects in the first term set to which the concept data object is associated with a weight greater than the first weight threshold. If this ratio is less than the term ratio threshold, the concept data object is excluded from the concept set.

Through experiments, the first weight threshold, term ratio threshold and second weight threshold can be determined. For example, some initial studies found that a first weight threshold of 0.05, a term ratio threshold of 0.26 and a second weight threshold of 0.10 provided satisfactory results.

At step430 a second term set is obtained for each of the concept data objects in the concept set. Each of the concept data objects in the concept set are evaluated to determine term data objects, in theconcept knowledge database230, associated with each of these concept data objects. Term data objects associated with the concept data objects selected for the concept set are added to the second term set. A second weight threshold may be used to exclude term data objects from the second term set if they are associated with concept data objects in the concept sets by a weight that is less than the second weight threshold.

Atstep440, the concept set is used to formulate a set of concept vectors. For each concept represented by a concept data object in the concept set, a concept vector is created using the first term set and second term set obtained for the concept data object atstep430. Each term data object in the first term set and second term set for a concept data object is defined as a dimension of the concept vector and the weight of the association between the term data object and the concept data object is used to set the magnitude of the concept vector in that assigned dimension.

At this point, themethod400 ends and a set of concepts and their corresponding concept vectors C={c1, c2, . . . , cm)have been determined.

Referring again toFIG. 5, from theconcept accordance module260, the concept set and the respective concept vectors are passed to thesearch module240 to request a search using the search query.

Search Module

When thesearch module240 receives the search query, the concept set and the set of concept vectors, thesear module240 requests thesearch engine module250 to conduct a search using the search query. Thesearch module240 is typically resident on thedata processing system1 and thesearch engine module250 is typically a web search engine, such as the web search engine running onservers50 inFIGS. 2A and 2B, with the search being conducted on a number of computer readable documents, such as searching for web pages on the World Wide Web. However, thesearch engine module240 could be used in any computerized document storage system capable of searching a large number of computer readable documents.

Thesearch engine module240, could return the results of the search in the form of a list of complete documents located in the search, however, due to the likelihood that a relatively large number of documents can be located with the search and to save overhead on the data processing system, the search results are typically returned in the form of list of document surrogates, with a document surrogate returned for each document located in the search.

FIG. 7 illustrates a typical document surrogate data object160 which is commonly provided as a returned document by a search engine as one of a set of search results. Rather than a search engine returning each complete document that is located in a search, search engines typically provide a set ofdocument surrogates160 in place of supplying the completed documents.Document surrogates160 are the primary data objects in the list-based representation used by search engines. Eachdocument surrogate160 provides information describing the corresponding complete document which commonly consists of: atitle162; a URL164; a summary166; and any other additional other assorted information. Thetitle162 provides the tile of the corresponding complete document described by thedocument surrogate160, the URL164 provides the address of the complete document and the summary166 contains a short description or snippet of the complete document and usually provides he query terms of the search term in context.

Referring again toFIG. 5, the search results obtained by thesearch module240 are passed to theconcept accordance module260 where accordance values for each return document indicating the degree of similarity between the returned document and the concepts in die concept set are formulated.

Concept Accordance

FIG. 8 illustrates amethod500 of determining accordance values for each returned document of the search results. Each returned document has an accordance value determined for each concept in the concept set and indicating the degree of similarity between the returned document and the concept. The accordance value is typically based on a fuzzy membership score with each concept in the concept set treated as a centroid to determine the clustering of the returned documents around the concepts. A returned document might have a higher fuzzy membership score in relation to one concept as compared to another concept, indicating that the first concept has a higher degree of similarity to the returned document than the second concept.

Method

500 comprises the steps of: selecting a first returneddocument510; analyzing the returneddocument520; generating adocument vector530 for the selected returned document; selecting afirst concept540; determining an accordance value for the selected returned document in relation to a selectedconcept550; checking if more concepts remain in the concept set to be analyzed560 in relation to the selected returned document and selecting thenext concept570, if more concepts remain in the concept set; once the selected returned document has been analyzed in relation to all the concepts in the concept set, checking if more returned documents are present580 and selecting the next returneddocument590, if there are more returned documents; and ending when all the returned documents have an accordance indicator determined for each of the concepts in the concept set.

Themethod500 begins with the selection of a first returned document atstep510. As the search results are returned, themethod500 selects one of the returned documents returned as the search results.

Next atstep520, the returned document is analyzed to determine a frequency of each unique word or term in the returned document. If the returned document is the entire document, the occurrence of each unique term in the entire document is determined. If the returned document is a document surrogate the occurrence of each unique term can be determined based on the summary of the complete document and optionally in the title.

In some cases it may be preferable to use the roots of the words rather than the words themselves, such as using Porter's stemming algorithm, so words with various prefixes and suffixes are not counted as separate terms. Each unique term in a returned document will be based on the root or stem of the term so that the frequencies determined are not reduced by the use of terms that use different suffixes, prefixes, etc. Match based on the stems or roots of the search terms can be more effective than exact word matches, since it takes into account different variations of the same root word.

The frequencies determined for the unique terms in the selected returned document are then used to generate a document vector atstep530. The document vector represents the frequency of unique terms in the returned document in a multidimensional vector form. Each unique term is used to define a dimension of the document vector and the magnitude of the document vector in that dimension is then set as the frequency of the term in the returned document.

A first one of the concepts in the concept set is selected atstep540 and an accordance value indicating the degree of similarity between the returned document and the selected concept is determined atstep550. The accordance value is assigned by determining a fuzzy membership score of the returned document relative to the selected concept. Given the concept set, the corresponding concept vector set, C={c₁, c₂, . . . , c_m}, and the document vector d_l, determined for the returned document determined atstep530, the fuzzy membership score, u_ij, of the returned document can be determined with respect to a concept c_jby the following equation:

u_{i, j} = \frac{1}{\sum_{k = 1}^{m} {(\frac{sim (d_{i}, c_{j})}{sim (d_{i}, c_{k})})}^{2}}

Where sim(d_ic_j) or the similarity between a document vector and a concept vector is given by the Euclidean distance metric:

sim (x_{i}, x_{j}) = {(\sum_{k = 1}^{p} {(x_{i, k} - x_{j, k})}^{2})}^{1 / 2}

where x_iis the document vector and x_jis the concept vector.

Although a specific clustering algorithm is provided a person skilled in the art will appreciate that other clustering algorithms could also be used.

Themethod500 then checks, atstep560, to see if more concepts remain in the concept set and if more concepts remain, the next concept in the concept set is selected atstep570 and an accordance value consisting of a fuzzy membership score for the newly selected concept is determined atstep550. Themethod500 will continue to repeat

steps

550,560 and570 until all the concepts in the concept set of been selected and an accordance value determined for each of the returned document has been established for each of the concepts in the concept set.

At step580, if more returned documents are remaining, the next unit returned document is selected atstep590 and

steps

520,530,540,550,560,570,580 and590 are repeated until all of the repeated documents have been returned.

In this manner, themethod500 determines a document vector for each of the returned documents and uses the document vector to determine a fuzzy membership score for the returned document and each concept in the concept set, which is used then to assign an accordance value indicating the similarity between the returned document and each of the concepts in the concept set.

In one embodiment of the present invention, each returned document in a set of search results is evaluated as the returned document is returned from thesearch engine module250 to decrease the amount of time the system requires before displaying the search results to a user.

At the end of themethod500 each of the returned documents will have an accordance value determined in relation to each of the concepts in the concept set.

From theconcept accordance module260, the search results comprising the plurality of returned documents and the formulated accordance values are passed to thevisualization interface module270.

Vizualization Interface

Thevisualization interface module270 displays the search results in a manner that allows a user to quickly determine the degree of similarity between one or more concepts in a concept set and a returned document. Additionally, the search results are displayed in such a way that a user can determine whether a first returned document is more or less similar to one or more selected concepts than a second returned document. Referring toFIG. 5, the search results in the form of a list of returned documents (with the accordance values determined for each returned document) and the concept set are passed, from theconcept accordance module260, to thevisualization interface module270 where the search results are displayed to a user.

FIG. 9 illustrates a screen shot of an embodiment of agraphical interface600 that may be generated by thevisual interface module270 shown inFIG. 5, for displaying the search results. A compressed level of detail provides the user with a large overview of a large number of the search results and a more detailed level of view provides more detailed information about a smaller number of the search results.

Afirst portion610 of the list of returned documents is shown in thegraphical interface600. Typically, each returned document shown in thefirst portion610 comprises anaccordance indicator614 and atitle636. Thetitle636 provides readable text showing the title of the returned document and is typically a hyperlink to the actual located document, such as the webpage located in a web search or the document in an information retrieval system.

Each returned document in thefirst portion610 can be displayed with the summary of the returned document. Alternatively, each returned document in thefirst portion610 can display the summary of the returned document only when a user moves a cursor over the returned document in thefirst portion610. When the user moves a cursor over the returned document in thefirst portion610, a popup field (tool tip) can appear containing the summary of the returned document.

Each returned document in thefirst portion610 is displayed with anaccordance indicator614. Theaccordance indicator614 is based on the accordance values formulated for the returned documents and indicates the similarity between a returned document and one or more of the concepts in the concept set generated using the search terms in the search query.

The accordance values consisting of the fuzzy membership scores determined for each returned document in relation to the concepts in the concept set, usingmethod500, illustrated inFIG. 8, are used to formulate theaccordance indicators614. Eachconcept685 in the set of concepts is displayed in aviewing pane680. A user can select one or more of theconcepts685. If a user selects only asingle concept685, theaccordance indicator614 shows the accordance value of each turned document in relation to the selected concept. However, if the user selects more than one of theconcepts685 in the concept set, theaccordance indicator614 is the result of the addition of the accordance values of each returned document in relation to all of the selected concepts.

Typically, a color shade is assigned to eachaccordance indictor614 based on the accordance values of the selected concepts for each returned document. Typically, returned documents with higher accordance values for the selected concepts (more similarity between a selected concept and a returned document) are assigned a color shade that is more intense or deeper. For example, anaccordance indicator614 indicating a relatively low accordance may have a very pale yellow color, while anaccordance indicator614 indicating a higher accordance may be a color shade of a much darker red.

Asecond portion630 of the list of returned documents is shown in thegraphical interface600. Thefirst portion610 is a subset of the returned documents shown in thesecond portion630. Thesecond portion630 displays each returned document in a much smaller format so that thesecond portion630 displays more of the returned documents than thefirst portion610 however, thefirst portion610 provides more information regarding each displayed returned documents than the returned documents displayed in thesecond portion630.

Each of the returned documents in thesecond portion630 is displayed in a format which provides a compressed or small view of the returned document. Each returned document shown in thesecond portion630 is displayed with anaccordance indicator614, and, typically, atitle representation616.

Thetitle representation616 represents the title of the returned document; however, thetitle representation616 does not necessarily have to provide the title in a readable format. Returned documents displayed in thesecond portion630 may be displayed so small that a solid line is used to provide thetitle representation616 and thetitle representation616 merely indicates the approximate length of the title of the returned document in relation to the length of the titles of the other returned documents.

By displaying a more detailedfirst portion610 of the list of returned documents and a less detailedsecond portion630 of the list of returned documents, where thesecond portion630 contains many more returned documents than thefirst portion610 theinterface600 provides two levels of detail to a user about returned documents provided in the list returned as the search results.

Each of the returned documents displayed in thesecond portion630 corresponds to a returned document displayed in thefirst portion610, such that all of the returned documents in thefirst portion610 are contained in thesecond portion630, with the returned documents in thefirst portion610 occurring in the same order that they occur in thesecond portion630. Thesecond portion630 represents a subset of list of returned documents making up the search results from the search engine and thefirst portion610 represents a subset of the returned documents show in thesecond portion630. The first format allows a user to see a large number of the returned documents in a compressed view in thesecond portion630 and then also see some of these returned shown in thesecond portion630 in a larger, more detailed view in thefirst portion610.

Theaccordance indicators614 displayed with the returned documents in thefirst portion610 indicates the same accordance values as theaccordance indicators614 associated with the same returned document in thesecond portion630.

Thesecond portion630 displays a much greater portion of the list of returned documents than thefirst portion610. In some cases, more than one hundred (100) returned documents may be displayed in thesecond portion630. On the other hand thefirst portion610 displays a relatively smaller number of the returned documents because the returned documents displayed in thefirst portion610 provides more details and therefore the returned documents must be shown in a large enough size that a user can read thetitles636 of the returned documents shown in thefirst portion610. For example, while thesecond portion630 may display one hundred (100) returned documents in the first format thefirst portion610 may display fewer than twenty five (25) returned documents.

While each of theaccordance indicators614 could be an assigned number such as a percentage, the use of a color shade as the accordance indicators614 (or as part of the accordance indicators614) allows the information to be conveyed to the user even though the returned document in thesecond portion630 may be displayed too small for a user to either easily read or even be able to read text. Using a color shade for theaccordance indicators614, theaccordance indicators614 do not have to be very large in order to convey the necessary information to a user; just large enough to convey to a user a shade of color. While numbers, text or geometric shapes cannot be illustrated using a single pixel; a color shade can be. In some cases, theaccordance indicator614 may be made as small as a single pixel of a display screen.

Anindicator frame650 is positioned over the returned documents in thesecond portion630 that are also shown in thefirst portion610. Theindicator frame650 indicates the returned documents shown in thesecond portion630 that are also shown in thefirst portion610.

When a user makes a selection that changes the returned documents shown in thefirst portion610, such as by using ascroll bar660 to scroll to a new set of returned documents displayed in thefirst portion610, thesecond portion630 is updated to indicate the same returned documents shown in thefirst portion610 in thesecond portion630, by moving theindicator frame650 along thesecond portion630.

In this manner, a user can quickly look over theaccordance indicators614 for each returned document shown in thefirst portion610 to determine which returned documents correlate to the desired concepts. Additionally, using thesecond portion630, a user can quickly look over theaccordance indicators614 for each returned document in thesecond portion630 and quickly determine which returned documents shown in thesecond format630 correlate to the desired concepts closer then the other returned documents without requiring the user to perform any in-depth analysis of each returned document. By simply scanning over the accordance indicators614 a user can quickly and easily visually locate theaccordance indicators614 that indicate a returned document that has a high correlation with a concept by the various shades of color shown in theaccordance indicators614.

A user can also visually analyze the returned documents shown in thefirst portion610, checking for returned documents that containaccordance indicators614 indicating the similarity of a returned document to one or more of the concepts. Once a user identifies a returned document or a grouping of returned documents in thefirst portion610 that the user wishes to examine in more detail, the user can then move theindicator frame660 so that the selected returned documents or grouping of returned documents in thesecond portion630 are displayed in the second format in thefirst portion610. A user can then examine thetitles636 of the represented documents and click on a desired returneddocument title636 to go to the document.

FIG. 10 illustrates a screen shot of a further embodiment of agraphical interface700 that may be generated by the visual interface module470 shown inFIG. 5, for displaying the search results wherein the accordance values of the returned documents in relation to the selected concept or concepts in the concept set are used to sort the returned documents in thefirst portion610 andsecond portion630. The returned documents are sorted based on the accordance values for the returned documents in relation to a selected concept. Returned documents that have a higher degree of similarity to a selected concept (shown with the accordance indicators614) appear higher in the list than other returned documents that are less similar to the selected concept or concepts.

FIG. 11 illustrates a screen shot of a further embodiment of agraphical interface800 that may be generated by the visual interface module470 shown inFIG. 5, for displaying the search results.Graphical interface800 is similar to graphical interface600 (illustrated inFIG. 9) in that afirst portion610 of a list of returned documents is displayed with each returned document displaying thetitle636 and any other information. However, instead of displaying asingle accordance indicator614 with each returned document wherein when more than one concept from the concept set is selected thesingle accordance indicator614 is made up of the sums of the accordance values of the selected concepts,graphical interface800 provides aseparate accordance indicator814 for each selected concept. Eachaccordance indicator814 displays a single accordance value indicating the similarity between a returned document and a specific concept in the concept set. By simply viewing the accordance indicators813 a user can see how similar each of the displayed returned documents are to a specific concept. In this manner a user can compare the similarity of a returned document to two or more of the concepts in a concept set.

A user can sort the list of the returned documents displayed in thegraphical interface800 based on one concept over the one or more others by selecting one of the concepts to sort the list by. In one embodiment, a user selects the concept the user desires the list to be sorted by. The list of returned documents is then resorted to place a precedent on the selected concept and thefirst portion610 of returned documents and thesecond portion630 of the returned documents are updated to reflect the newly sorted list.

A user can also conduct a nested sort by selecting a second concept. The list of returned documents is then resorted to place a primary weight on returned documents with high accordance values with the first selected concept and then a secondary weight on returned documents with high accordance values with relation to the second selected concept. Thefirst portion60 of returned documents of and thesecond portion60 of the returned documents are updated to reflect the newly sorted list.

The foregoing is considered as illustrative only of the principles of the invention. Further, since numerous changes and modifications will readily occur to those skilled in the art, it is not desired to limit the invention to the exact construction and operation shown and described, and accordingly, all such suitable changes or modifications in structure or operation which may be resorted to are intended to fall within the scope of the claimed invention.

Claims

1. A method of visually coding search results based on at least one concept, the method comprising:

using a search query containing a plurality of search terms to conduct a search of a plurality of computer readable documents and obtain the search results, the search results comprising at least one returned documents;

obtaining the at least one concept by matching the plurality of search terms to the at least one concept;

evaluating the similarity between the at least one returned document and the at least one concept; and

displaying the at least one returned document with an accordance indicator, the accordance indicator indicating the similarity between the at least one returned document and the at least one concept.

2. The method ofclaim 1 wherein the at least one concept is matched to the plurality of search terms by:

accessing a concept knowledge base data structure having a plurality of concept data objects and a plurality of term data objects, each term data object defining a term and associated with at least one of the concept data objects and each concept data object defining an object;

generating a first term set containing term data objects from the concept knowledge base data structure wherein each term data object in the first term set matches at least one of the plurality of search terms; and

generating a concept set containing concept data objects from the concept knowledge base data structure wherein each concept data object in the concept set is associated with one or more of the term data objects in the first term set.

3. The method ofclaim 2 wherein a concept vector is generated for each concept in the concept set and a document vector is generated for the at least one returned document and wherein the accordance indicator is based on a fuzzy membership score determined by comparing the concept vector to the document vector.

4. The method ofclaim 3 further comprising allowing a user to select more than one concept from the concept set and having the accordance indicator based on the combined fuzzy membership scores determined for the at least one returned document and the selected concepts.

5. The method ofclaim 3 her comprising displaying at least two accordance indicators with the at least one returned document, each of the at least two accordance indicators corresponding to one of the concepts in the concept set.

6. The method ofclaim 1 wherein the accordance indictors consist of a color shade.

7. The method ofclaim 6 wherein the returned documents of the search results are ordered in a list and wherein the at least one returned document is displayed in a first portion of the list of returned documents and simultaneously displayed in a second portion of the list of returned documents on a display screen, and wherein the number of returned documents displayed in the second portion is greater than the number of returned documents displayed in the first portion.

8. The method ofclaim 7 wherein the returned documents are ordered in the list based on the similarity between the at least one returned document and the at least one concept.

9. The method ofclaim 3 wherein the returned document is a document surrogate.

10. A data processing system for visually coding search results based on at least one concept, the data precessing system comprising:

at least one processor;

a memory operatively coupled to the at least one processor;

a display device operative to display data; and

a program module stored in the memory and operative for providing instructions to the at least one processor, the at least one processor responsive to the instructions of the program module, the program module operative for:

using a search query containing at least one search term to conduct a search of a plurality of computer readable documents and obtain search results comprising a plurality of returned documents;

obtaining the at least one concept by matching the at least one search term to the at least one concept;

evaluating the similarity between a returned document and the at least one concept; and

displaying on the display device the returned document with an accordance indicator, the accordance indicator indicating the similarity between the returned document and the at least one concept.

11. The apparatus ofclaim 10 wherein the at least one concept is matched to the at least one search term by:

accessing a concept knowledge base data structure having a plurality of concept data objects and a plurality of term data objects, each term data object defining a term and associated with at least one of the concept data objects, each concept data object defining an object;

12. The apparatus ofclaim 11 wherein a concept vector is generated for each concept in the concept set and a document vector is generated for the at least one returned document and wherein the accordance indicator is based on a fuzzy membership score determined by comparing the concept vector to the document vector.

13. The apparatus ofclaim 12 further comprising allowing a user to select more than one concept from the concept set and having the accordance indicator based on the combined the fuzzy membership scores determined for the at least one returned document and the selected concepts.

14. The apparatus ofclaim 12 further comprising displaying at least two accordance indicators with the at least one returned document, each of the at least two accordance indicators corresponding to one of the concepts in the concept set.

15. The apparatus ofclaim 10 wherein the accordance indictors consist of a color shade.

16. The apparatus ofclaim 12 wherein the returned documents of the search results are ordered in a list and wherein the at least one returned document is displayed in a first portion of the list of returned documents and simultaneously displayed in a second portion of the list of returned documents on a display screen, and wherein the member of returned documents displayed in the second portion is greater than the number of returned documents displayed in the first portion.

17. The apparatus ofclaim 16 wherein the returned documents are ordered in the list based on the similarity between the at least one returned document and the at least one concept.

18. The apparatus ofclaim 12 wherein the returned document is a document surrogate.

19. A computer readable memory having recorded thereon statements and instructions for execution by a computer to carry out the method ofclaim 1.

20. A method of visually sorting search results based on at least one concept, the method comprising:

using a search query containing a plurality of search terms to conduct a search of a plurality of computer readable documents and obtain the search results, the search results comprising a first returned document and a second returned document;

obtaining the least one concept by matching the plurality of search terms to the at least one concept;

determining a first accordance value by evaluating the similarity between the first returned document and the at least one concept and a second accordance value by evaluating the similarity between the second returned document aid the at least one concept; and

displaying the first returned document and second returned document sorted in an order based on the first accordance value and the second accordance value.

21. The method ofclaim 20 wherein the at least one concept is matched to the plurality of search terms by:

22. The method ofclaim 21 wherein a concept vector is generated for each concept in the concept set, a first document vector is generated for the first returned document, and a second document vector for the second returned document, and wherein the first accordance indicator is based on a fuzzy membership score determined by comparing the concept vector of the at least one concept to the first document vector and the second accordance indicator is based on a fuzzy membership score determined by comparing the concept vector of the at least one concept to the second document vector.

23. The method ofclaim 22 further comprising displaying the first returned document with a first accordance indicator based on the first accordance value and the second returned document with a second accordance indicator based on the second accordance value.

24. The method ofclaim 23 further comprising displaying at least two accordance indicators with the first returned document, each of the at least two accordance indicators corresponding to one of the concepts in the concept set.

25. The method ofclaim 24 wherein the accordance indictors consist of a color shade.

26. The method ofclaim 22 wherein the search results comprise of list of returned documents containing the first returned document and second returned document and wherein the first returned document and second returned document are displayed in a first portion of the list of returned documents and simultaneously displayed in a second portion of the list of returned documents, and wherein the number of returned documents displayed in the second portion is greater than the number of returned documents displayed in the first portion.

27. The method ofclaim 20 wherein the first returned document and second returned document are document surrogates.

28. A data processing system for visually sorting search results based on at least one concept, the data processing system comprising:

at least one processor;

a memory operatively coupled to the at least one processor;

a display device operative to display data; and

determining a first accordance value by evaluating the similarity between the first returned document and the at least one concept and a second accordance value by evaluating the similarity between the second returned document and the at least one concept; and

29. The apparatus ofclaim 28 wherein the at least one concept is matched to the plurality of search terms by:

30. The apparatus ofclaim 29 wherein a concept vector is generated for each concept in the concept set, a first document vector is generated for the first returned document, and a second document vector for the second returned document, and wherein the first accordance indicator is based on a fuzzy membership score determined by comparing the concept vector of the at least one concept to the first document vector and the second accordance indicator is based on a fuzzy membership score determined by comparing the concept vector of the at least one concept to the second document vector.

31. The apparatus ofclaim 30 further comprising displaying the first returned document with a first accordance indicator based on the first accordance value and the second returned document with a second accordance indicator based on the second accordance value.

32. The method ofclaim 31 further comprising displaying at least two accordance indicators with the first returned document, each of the at least two accordance indicators corresponding to one of the concepts in the concept set.

33. The method ofclaim 31 wherein the first accordance indictor and second accordance indicator consist of a color shade.

34. The method ofclaim 30 wherein the search results comprise of list of returned documents containing the first returned document an second returned document and wherein the first returned document and second returned document are displayed in a rust portion of the list of returned documents and simultaneously displayed in a second portion of the list of returned documents, and wherein the number of returned documents displayed in the second portion is greater than the number of returned documents displayed in the first portion.

35. The method ofclaim 28 wherein the first returned document and second returned document are document surrogates.

36. A computer readable memory having recorded thereon statements and instructions for execution by a computer to carry out the method ofclaim 20.