Method and apparatus of visual representations of search results

[0001] This invention is in the field of search techniques used by search engines and more specifically methods and systems for displaying the results of searches,

[0002] 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 a search engine. A search engine allows a user to input a search query made up of words or terms that a user than 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 search terms in the search query and will then return the located web pages to the user.

[0003] The search results generated from a user's search 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 document surrogates are often present 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.

[0004] 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 search 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 more results than the user can easily consider.

[0005] While many 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.

[0006] 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 all of these results to determine the most relevant documents 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.

[0007] 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 matching the search query. However, studies have shown that users seldom reformulate their queries, even when a poor set of search results are provided. 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.

[0008] It is an object of the present invention to provide an improved method and apparatus that overcomes problems in the prior art.

[0009] In a fist aspect of the present invention, a method of visually coding search results 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 search results containing a list of returned documents; for each returned document in the list, determining an occurrence frequency of a first search term in the returned document and formulating an occurrence indicator having a color shade based on the occurrence frequency for the first search term; and displaying a first portion of the list in a first format on a display screen, and simultaneously displaying a second portion of the list in a second format on the display screen, wherein the occurrence indicator for the first search term is displayed beside each returned document in the first format and second format. The number of returned documents displayed in the first portion is greater than the number of returned documents displayed in the second portion

[0010] In a second aspect of the present invention, a data processing system for visually coding search results is provided. 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 responsive to the instructions of the program module. The program module is operative for: using a search query containing a plurality of search terms to request a search of a plurality of computer readable documents and obtain search results containing a list of returned documents; for each turned document in the list, determining an occurrence frequency of a first search term in the returned document and formulating an occurrence indicator having a color shade based on the occurrence frequency for the first search term; and displaying a first portion of the list in a first format on the display screen, and simultaneously displaying a second portion of the list in a second format on the display screen, wherein the occurrence indicator for the first search term is displayed beside each returned document in the first format and second format. The number of returned documents displayed in the first portion is greater than the number of returned documents displayed in the second portion.

[0011] In a third aspect of the present invention, a data processing system product comprises a computer useable medium including a computer readable program for visually coding search results. The computer readable program when executed on a data processing system causes the data processing system to: use a search query containing a plurality of search terms to request a search of a plurality of computer readable documents and obtain search results containing a list of returned documents; for each returned document in the list, determine an occurrence frequency of a first search term in the returned document and formulating an occurrence indicator having a color shade based on the occurrence frequency for the first search term; and display a first portion of the list in a first format on a display screen, and simultaneously display a second portion of the list in a second format on the display screen, wherein the occurrence indicator for the first search term is displayed beside each returned document in the first format and second format. The number of returned documents displayed in the first portion is greater than the number of returned documents displayed in the second portions

[0021] The present invention provides a compact visual representation of a set of search results at two levels of detail and supports the interactive exploration of web search results. Returned documents, typically in the form of document surrogates, are retrieved from a search engine for a given search query and presented to a user using a visual representation that provides two levels of detail. A number of frequency occurrence indicators are associate with each displayed returned document to indicate to a user the potential relevance of each displayed returned document.

Data Processing System

[0022] FIG. 1 illustrates a data processing system 1 suitable for supporting the operation of methods in accordance with the present invention. The data processing system 1 could be a personal computer, server, mobile computing device, cell phone, etc. The data processing system 1 typically comprises: at least one processing unit 3; a memory storage device 4; at least one input device 5; a display device 6 and a program module 8.

[0023] The processing unit 3 can be any processor that is typically known in the art with the capacity to run the provided methods and is operatively coupled to the memory storage device 4 through a system bus. In some circumstances the data processing system 1 may contain more than one processing unit 3. The memory storage device 4 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, the memory storage device 4 can be a database that is external to the data processing system 1 but operatively coupled to the data processing system 1. The input device 5 can be any suitable device suitable for inputting data into the data processing system 1, such as a keyboard, mouse or data port such as a network connection and is operatively coupled to the processing unit 3 and operative to allow the processing unit 3 to receive information from the input device 5. The display device 6 is a CRT, LCD monitor, etc. operatively coupled to the data processing system 1 and operative to display information. The display device 6 could be a stand-alone screen or if the data processing system 1 is a mobile device, the display device 6 could be integrated into a casing containing the processing unit 3 and the memory storage device 4. The program module 8 is stored in the memory storage device 4 and operative to provide instructions to processing unit 3 and the processing unit 3 is responsive to the instructions from the program module 8.

[0024] Although other internal components of the data processing system 1 are not illustrated, it will be understood by those of ordinary skill in the art that only the components of the data processing system 1 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.

[0025] FIG. 2A illustrates a network configuration wherein the data processing system 1 is connected over a network 55 to a plurality of servers 50 operating as a search engine. FIG. 2B illustrates a network configuration wherein the data processing system 1 is configured as a server and a remote device 60, such as another computer, a PDA, cell phone or other mobile device connected to the Internet, is used to access the data processing system 1. The data processing system 1 runs the majority of the software and methods, in accordance with the present invention, and accesses a plurality of severs 50 operating as a search engine to conduct a web search. By having the data processing system 1 configured as a server, the remote client system 60 does not need to have the capacity necessary to contain all the necessary data structures and run all the methods.

[0026] Furthermore, the invention can take the form of a computer readable medium having recorded thereon statements and instructions for execution by a data processing system 1. 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.

Overview of System

[0027] FIG. 3 illustrates a software system in accordance with the present invention. The software system 100 contains: a search query module 110; a search module 120; a search engine module 130; a query term frequency module 140; and a visualization interface module 150.

[0028] A search query is input to the system 100 at the search query module 110. The search query contains one or more search teams and usually at least two or three search terms. From the search query module 110 this search query containing one or more search terms is passed to the search module 120, which requests a search engine module 130 to return the results of a search using the search query. Typically, the results returned by the search engine module 130 are a list of returned documents where each returned document is typically a document surrogate that describes the actual documents located by the search engine module 130.

[0029] When the results of the search are received from the search engine module 130, the search results and the search query are then passed from the search module 120 to the query term frequency module 140, where the occurrence frequency of each query term in the search query is determined for each of the documents returned in the search results.

[0030] Once the occurrence frequency of the search terms is added to each returned document in the search results, the search results are passed to the visualization interface module 150 where the search results are displayed to the user.

[0031] The software system 100 can be implemented wholly on a data processing system 1, as shown in FIG. 2A, with only the search engine module 130 resident on a server 50 connected to the data processing system 1 over the network 55. Alternatively, various components of the software system 100 could be resident on a mobile device 60 operably connected to a data processing system 100 which contains other components of the software system 100, as shown in FIG. 2B. For example, the search query module 110 and visualization interface 150 could be resident of the mobile device 60 with the search module 120 and the query term frequency module 140 resident on the data processing system 1 and the search engine module 130 resident on one of the servers 50 operably connected by the network 55 to the data processing system 1.

Search Module

[0032] When the search query module 110 passes the search query to the search module 120, the search module 120 requests the search engine module 130 to conduct a search using the search query. The search module 120 is typically resident on the data processing system 1 and the search engine module 130 is typically a web search engine, such as the web search engine running on servers 50 in FIGS. 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, the search engine module 130 could be used in any computerized document storage system capable of searching a large number of computer readable documents.

[0033] The search engine module 130 could return the results of the search in the form of a list of complete documents where each complete document contains the majority of the contents of a located document, 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 returned document where each returned document is a document surrogate, with a document surrogate returned for each document located as a results of search.

[0034] FIG. 4 illustrates a typical document surrogate data object 160 which is commonly provided as a returned document by a search engine as one of a set of search results. Rater than a search engine returning a document containing a complete textual copy of each located document that is located in a search, search engines typically provide a set of document surrogates 160 in place of supplying the completed documents. Document surrogates 160 are the primary data objects in the list-based representation used by search engines. Each document surrogate 160 provides information describing the corresponding complete document which commonly consists of: a title 162; a URL 164; a summary 166; and any other additional other assorted information. The title 162 provides the title of the corresponding complete document described by the document surrogate 160, the URL 164 provides the address of the complete document and the summary 166 contains a short description or snippet of the complete document and usually provides the query terms of the search term in context.

[0035] The search results obtained by the search module 120 are passed to the query term frequency module 140 where the occurrence frequency of query terms in the search query are determined for each of the returned documents in the search results.

Query Term Frequency

[0036] In the query term frequency module 140, the search results returned by the search engine module 130 are augmented by adding additional attributes to each returned documents in the list of returned documents, beyond the information provided by the search engine module 130. For example, the returned documents provided by the search engine module 130 are typically in the form provided by the document surrogate data object 160 illustrated in FIG. 4. Each of the returned documents are analyzed to determine an occurrence frequency for one or more of the search terms (typically each search term in the search query) and adds the occurrence frequency of each search term to the returned document as an additional attribute.

[0037] FIG. 5 is a flowchart of a method 200 for determining the occurrence frequencies of search terms in the search query for each of the returned documents and adding the occurrence frequency as an additional attribute to the returned document. The method 200 comprises the steps of: parsing the search query into query terms 210; selecting a returned document 220; tallying the occurrence frequency of a search term in a returned document 230; checking if more search terms must be tallied 240; if more search terms must be checked, moving to the next sea term to be tallied 250; adding the occurrence frequencies of the search term as attributes to the returned document 260; checking if there are more returned documents to be analyzed 270; and, if there are returned documents remaining to be analyzed, moving to the next document to be analyzed 280.

[0038] The method 200 begins with the search query consisting of a number of search terms and the returned documents from a search conducted using the search query. At step 210, the search query is parsed into the individual search terms that make up the search query.

[0039] At step 220, a first document returned in the search results is selected to be analyzed.

[0040] A tally of the frequency of a first selected search term is determined in the first document, at step 230. A count of the occurrence of the search term is conducted. If the document contains the entire textual contents of the document located in the search, the occurrence of the search term in the entire document is conducted. Otherwise, the occurrence of the search term can be determined based on the summary of the complete document and optionally in the title.

[0041] Typically, the stems and/or roots of each of the words in the document are matched to the stems or roots of the search terms so that the tally of the search terms does not exclude the use of words that use different suffixes, prefixes, etc. Matching 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.

[0042] At step 240, the method 200 checks to determine whether there are any more search terms to be analyzed in the selected returned document. If there are more search terms to be analyzed for the selected returned document, the next search term is selected at step 250 and step 230 is repeated, deeming the occurrence frequency of the next selected search term.

[0043] Steps 230, 240 and 250 are repeated until each search term in the search query has been used to determine the occurrence frequency of each of the search terms in the selected returned document.

[0044] At step 260, these occurrence frequencies for each of the search terms are added as an additional attribute to the selected returned document to form a modified returned document. For a given search query consisting of n search terms, the set of attributes {q₁, q₂, . . . , q_n}, wherein q_x is the occurrence frequency of a search term, is added to the selected returned document.

[0045] The method 200 then checks to see if there are any more returned documents to be analyzed at step 270, and if there are more returned documents remaining, the next returned document is selected at step 280 and steps 230, 240, 250, 260 are repeated for the next returned document to deter the occurrence frequency of each of the search terms in the next returned document and add the occurrence frequencies as additional attributes to the next ret document

[0046] Once all of the returned documents have been analyzed and the occurrence frequency of each of the search terms is determined for each of the returned documents and added as additional attributes of the returned documents to create a modified ret document, the method 200 ends.

[0047] In this manner, the method 200 analyzes each returned document in the list of returned documents provided as the search results to determine the occurrence frequency of each of the search terms in each of the returned documents and adds these occurrence frequencies to the returned documents as additional attributes creating a modified returned document.

[0048] FIG. 6 illustrates a modified returned document in the form of a modified document surrogate data object 260. The modified document surrogate data object 260 has additional attributes added; specifically, the occurrence frequencies of each of four search terms in the summary 166 of the document surrogate data object 260. Along with the title 162, URL 164 and summary 166, the modified document surrogate data object 160 also contains a first occurrence frequency 170A of a first search term, a second occurrence frequency 170B of a second term, a third occurrence frequency 170C of a third search term and a fourth occurrence frequency 170D. Although FIG. 6 illustrates a modified document surrogate data object 260 with four search terms, a person skilled in the art will appreciated that any number of search terms can be used with the occurrence frequencies of all the search terms added to a modified document surrogate data object so that the modified document surrogate data object contains occurrence frequency attributes for each of the more than four search terms.

[0049] The modified returned documents, with the occurrence frequency of each of the search terms of the search query added as additional attributes, are then passed from the search module 120 to the visualization interface module 150.

Visualization Interface

[0050] The visualization interface module 150 displays the search results using visual representations at two levels of detail. A compressed level of detail provides the user with an 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.

[0051] FIG. 7 illustrates a screen shot of an exemplary interface 500. The search results in the form of a list of returned documents is passed to the visualization interface module 150 and a first portion 510 of the list of returned documents is displayed in a first format, simultaneously with a second portion 530 of the list of returned documents in a second format, so that the interface 500 provides two levels of detail to a user about returned documents provided in the list returned as the search results. The first portion 510 represents a subset of the documents returned by the search engine and the second portion 530 represents a subset of the returned documents represented by the first portion 510. The first format allows a user to see a large number of the returned documents in a compressed view in the fist portion 510 and then also see a number of the returned documents shown in the first portion 510 in a larger, more detailed view in the second format in the second portion 530.

[0052] The first portion 510 displays a number of the returned documents in the list in the first format which provides a compressed or small view of the returned document. Each returned document shown in the first format in the first portion 510 is displayed with a number of occurrence indicators 514, and, typically, a title representation 516. Typically, there is an occurrence indicator 514 corresponding to each search term in the search query. FIG. 7 illustrates search results obtained by using a search query with four search terms and therefore a first occurrence indicator 514A, a second occurrence indicator 514B, a third occurrence indicator 514C and a fourth occurrence indicator 514D are displayed with each returned document in the first portion 510 and second portion 530, an occurrence indictor corresponding to each of the four search terms.

[0053] The title representation 516 represents the title of the returned document. However, the title representation 516 does not necessarily have to provide the title in a readable format. Returned documents displayed in the fit format may be displayed so small that a solid line is used to provide the title representation 516 and the title representation 516 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.

[0054] The second portion 530 displays a number of the returned documents in a second format. Each of the returned documents displayed in the second format in the second portion 530 corresponds to a returned document displayed in the first portion 510, such that all of the returned documents in the second portion 530 are contained in the first portion 510, with the returned documents in the second portion 530 occurring in the same order that they occur in the first portion 510.

[0055] The second portion 530 shown in the second format provides a much larger and more detailed view of returned documents than the first portion 510 of returned document shown in the first format. Typically, each returned document shown in the second format contains a number of occurrence indicators 514 and a title 536. Typically, each returned document shown in the first format contains an occurrence indicator 514 for each of the search terms. The title 536 provides readable text showing the title of the returned document. The title 536 is typically a hyperlink to the actual document, such as the webpage located in a web search, or a direct link to the document in a traditional information retrieval system.

[0056] The second format can display the summary of each returned document. Alternatively, the second format can show the summary of the returned document only when a user moves a cursor over the returned document in the second format. When the user moves a cursor over the returned document in the second portion 530, a popup field (tool tip) can appear containing the summary of the returned document.

[0057] The occurrence indicators 514 shown with the returned documents in the fist format and second format are displayed such that a user can identify which occurrence indictors 514 are associated with which search terms. In the interface 500 in FIG. 7, each search term of a search query is displayed as a column title 570 and the column located below the column title 570 holds the occurrence indicators 514 corresponding to that search term. The occurrence indicators 514 in the second portion 530 are positioned under the respective search term indicated in the column title 570 to which they relate. For instance, if the first occurrence indicator 514A indicates the occurrence of the first search term in a returned the occurrence indicator 514A is positioned in the column with the column title 570A indicating the first search term

[0058] The occurrence indicators 514 displayed with the returned documents in the first portion 510 displayed in the first format occur in the same order as the occurrence indicators 514 displayed with the returned documents in the second portion 530 displayed in the second format.

[0059] The additional attributes determined for each returned document, using method 200, illustrated in FIG. 5, indicating the occurrence frequency of search terms in the returned documents, are used to formulate the occurrence indicators 514. A color shade is assigned to each occurrence indictor 514 based on the occurrence frequency determined for the specific search term in the returned document. Typically, search terms that occur more frequently in a returned document (and therefore have a higher occurrence frequency than other search terms) are assigned a color shade that is more intense or rich. For example, a search term that appears few if any times in a document surrogate may be associated with an occurrence indicator 514 that has a color shade of very pale yellow, while a search term diet appears more frequently in a document surrogate will be associated with an occurrence indicator 514 that has a color shade of a much darker red.

[0060] The first portion 510 displays a much greater portion of the list of returned documents than the second portion 530. In some cases, more than one hundred (100) returned documents may be displayed in the first portion 510 in the first format. On the other hand the second portion 530 displays a relatively smaller number of the returned documents in the second format because the second format provides more details and therefore the returned documents must be shown in a large enough size that a user can read the titles 536 of the returned documents shown in the second format. For example, while the first portion 510 may display one hundred (100) returned documents in the first format the second portion 530 may display fewer than twenty five (25) returned documents in the second format

[0061] The use of a color shade in the occurrence indicators 514 allows the information to be conveyed to the user even though the returned document in the first portion 510 may be displayed too small for a user to either easily read or even be able to read text shown in the first format. In some embodiments, rather than the returned documents in the fist format containing a title of the returned document, the title of the returned document is represented by a title representation 516 which is a line simple indicating the relative length of the title of the returned document. Because a color shade is used for the occurrence indicators 514, the occurrence indicators 514 do not have 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, the occurrence indicator 514 may be made as small as a single pixel of a display screen (depending on the resolution of the display screen and limited to a user's ability to perceive a single pixel on the display screen). Especially for occurrence indicators 514 displayed with returned documents shown in the first format.

[0062] An indicator frame 550 is positioned over the returned documents in the first portion 510 that are also shown in the second portion 530. The indicator frame 550 indicates the returned documents shown in the first format in the first portion 510 that are also shown in the second format in the second portion 530.

[0063] When a user makes a selection that changes the returned documents shown in the second format in the second portion 530, such as by using a scroll bar 550 to scroll to a new set of returned documents displayed in the second portion 530, the first portion 510 is updated to indicate the same returned documents shown in the second portion 530 in the first portion 510, by moving the indicator frame 550 along the first portion 510.

[0064] In this manner, a user can quickly look over the occurrence indicators 514 for each returned document shown in the first format in the first portion 510 and each returned document shown in the second format in the second format 530 and see which returned documents have search terms occurring more frequently than other returned documents without requiring the user to perform any in-depth analysis of each returned document. By simply scanning over the occurrence indictors 514 a user can quickly and easily visually locate the occurrence indicators 514 that indicate a returned document that contains a high occurrence frequency of a specific search term by the various shades of color shown in the occurrence indicators 514.

[0065] A user can also visually analyze the returned documents shown in the first format in the first portion 510, checking for returned documents that contain occurrence indicators 514 indicating that a specific search term has a high occurrence frequency in the represented returned document. Once a user identifies a returned or a grouping of returned documents in the first portion 510 that the user wishes to examine in more detail, the user can then move the indicator frame 550 so that the selected returned documents or grouping of returned documents in the first portion 510 are displayed in the second format in the second portion 530. A user can then examine the titles 536 of the represented documents and click on a desired returned document title 536 to go to the document.

Interactivity

[0066] A user can sort the list of the returned documents based on one search term over the other by selecting one of the search terms to sort the list by. In one embodiment, a user selects the column title 570 corresponding with the desired search term to select the search term to sort by. The list of returned documents is then resorted to place a precedent on the selected search term and the first portion 510 of returned documents of the first list and the second portion 530 of the returned documents in the second format are updated to reflect the newly sorted list.

[0067] A user can also conduct a nested sort by selecting a second search term. The list of returned documents is then resorted to place a primary weight on the first selected search term and then a secondary weight with on the second search term and the first portion 510 of returned documents of the first list and the second portion 530 of the returned documents in the second format are updated to reflect the newly sorted list

[0068] 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 fail within the scope of the claimed invention.