GB2386440A - Searching and navigating an information source - Google Patents

Abstract

The present invention provides a system for navigating an information source, the system comprising: <SL> <LI>a) a said information source in which items of information have been classified into different categories of information; <LI>b) a category server for storing or transmitting category information of the information source to a client; <LI>c) a search device for retrieving information items each along with an indication of their corresponding category; and <LI>d) a client for presenting the possible categories of information, collections of information items and individual information items to a user in response to a search request from the client to the search engine; </SL> the information items in the information source being arranged in categories according to a category model that is fixed for the information source, not being dynamically generated or configured for each search or user other than optionally for explicit user modification, and the category information is separately and individually defined being held in the category server and manipulable by the client. A method of navigating an information source is also disclosed comprising a combination of browsing and searching using the categories to partition the information and limit the search.

Description

À.. Ft.,', " Ly Improvements to Search Systems Field of the Invention

The present invention relates generally to a method and apparatus for navigating an information source, where the information source is defined to be a collection of information items that can be accessed and treated as a single collection of information items which may be heterogeneous in nature with items possibly including (but not limited 10 to) disk files accessed via an operating system directory structure, web (HTML) pages accessed via a web (HTTP) server and database records accessed via a database engine. Background to the Invention

The Internet provides instant access to information, communication and commerce yet people struggle to find the best information to achieve their goals. Users' ability to find the most relevant information is limited by current models of web navigation. These models force users to choose between browsing on the one hand and searching for 20 information on the other, using precise terms or key words.

When searching (i.e. providing selection criteria to return a subset of items) current technology does not make it easy for a user to enter the right query to bring back the information that they need. An underspecified query (e.g. computer patents) is likely to 25 bring back too much information for the user to evaluate (particularly given users are only guaranteed to read the first five results). An over-specified query (e.g. patents for search or navigation on the web using classification techniques) is likely to return no information.

When browsing (i.e. selecting a set of items to explore), the problems are similar. It is 30 difficult for the user to make the right choice of subjects to browse when they are presented with fixed, pre-determined categories, chosen by the site designer, that may not match the user's needs or understanding. The problem is made worse when each browse action may require a new page to be requested from the web-site, thereby slowing the process.

a-... c - it The applicants have realised that to make navigation easier, it is necessary to allow users to swap between browsing and searching in an effective fashion. This allows people to a) use the structures that they may be familiar with browsing as a way of interpreting and navigating search results; and/or 5 b) use a search to guide them to categories that they can browse for the right answer. By focussing on the presentation and exploration of the search results, a combined browsing and searching system will assist the user in narrowing down general queries, 10 expanding very specific searches to related items and understanding the range of information available.

Given the investment that organizations already have in information systems and services, it is also important that any solution can be integrated with and take advantage 15 of existing search-enabled websites without major restructuring of the web-site or the information that it contains.

Summary of the Invention

20 According to a first aspect of the present invention there is provided a system for navigating an information source, the system comprising: a) a said information source in which items of information have been classified into different categories of information; b) a category server for storing or transmitting category information of the information 25 source to a client; c) a search device for retrieving information items each along with an indication of their corresponding category; and d) a client for presenting the possible categories of information, collections of information items and individual information items to a user in response to a search 30 request from the client to the search device, the information items in the information source being arranged in categories according to a category model that is fixed for the information source, not being dynamically generated or configured for each search or user other than optionally for explicit user modification, and the category information is separately and individually defined being held in the 35 category server and manipulable by the client.

f C À À /. ' The system preferably further comprises an information server operatively linked to the category server, search device and client and which holds said items of information or information about individual said items of information.

5 Preferably the category model is held locally at the client in use, suitably being down-

loaded from the category server prior to use.

The client is preferably programmed to detect whether an information source is a said information source that has its information items categorised according to a said category 10 model. If it is not a said information source the client is suitably programmed to process and display information from the information source in a conventional manner.

Preferably the information source is tagged with address identifiers for the search device and category server. These identifiers or other labels may be used by the client for 15 detecting whether an information source is a said information source.

For a selected said information source the client is preferably programmed to request or, at least, receive, the category model, version information relating thereto or updates thereof from the category server and suitably to then display the category model. The 20 client is suitably programmed to initially display only the top level of the category model.

The client is particularly preferably programmed to enable the user to browse through the categories of information using the display device without further requests to either the search device or the information and category servers and to invoke the search device at 25 any point in the browsing process.

The client is suitably programmed to enable the user to customise or modify the category model to allow them to more easily access those categories of information that they use most frequently.

The client suitably enables the user to specify a set of search criteria using either free text or specific attributes to retrieve (through the search device) a limited set of information items to display. This ability is only restricted to the type of input criteria that the search device will accept or the information that is listed for each item of information on the 35 search results.

f - À r The client suitably also enables the user to specify a set of browse criteria using either free text or specific attributes to retrieve (through the information server) a limited set of information items to display. This ability is only restricted to the types of the information that are provided for each item of information in the search results.

The client is preferably programmed to enable the user (prior to the start of a search) to restrict the display of search results to those that are found in a particular category (the search results being the list of information items returned by the search device that match a given user-defined query). This is not reliant on the ability above and if no restriction is 10 provided by the user, the starting category is taken to be the root node of the category model. The system is preferably programmed to enable display of all sub-categories of information through the display device, not just those containing relevant information, to 15 allow users to select categories of information that they deem to be relevant even if the search device does not indicate that the category contains relevant information.

Preferably the client is programmed to enable the user to restrict the display of search 20 results to those that are found in a particular category (or its descendants) following a search. This can be done by recursively selecting sub-categories of the category currently being viewed using the display device.

Preferably the client is programmed to enable the user to expand the display of search 25 results by selecting the parent category of a displayed category.

Preferably the client is programmed to enable the user to exclude a category (and all its descendants) from any further consideration, thereby eliminating all the information items it contains from further display.

Preferably the client is programmed to enable the user to save a set of search results and redisplay it at another time without requests to either the search device or the information and category servers.

35 Preferably the client is programmed to enable the user to manipulate and combine sets of search results through the use of logical or Boolean operators such as AND, OR and NOT.

À<... ' ',T

O 6 . S C The present invention provides a method of navigating an information source where the information source consists of items of information that are classified into different groups or categories of information and the method comprises a combination of browsing and 5 searching using the categories of information to partition the information source and the search (es).

The method of navigating of the present invention is highly distinctive in its treatment of search results as persistent data that has intrinsic value and that needs to be stored, 10 visuaiised, explored and manipulated.

According to one aspect of the present invention there is provided a method for navigating an information source structured into categories according to a category model, which method comprises: 15 searching the information source by specifying one or more search criteria for selecting items of information to view; and browsing the category model by selecting a category, sub- or super-category to display, retrieving relevant items in the selected category, and, suitably, formatting the display to the desired category layout.

By way of explanation, a category model is defined to be a structure grouping items of information so that each item is assigned to one or more categories of information, and each category may be grouped with other sub-categories (a category that represents a partition of a higher level category) to form super-categories (a category that is split into 25 sub-divisions). A category is said to be an end category if it contains no sub-categories, i.e. is not further sub-divided. In the model illustrated in Figure 2 below, A is the top category; A, B and C are all super-categories; B. C, and D are corresponding sub-

categories; and D is an end category. In graph theory terminology A and D are often referred to as the root and leaf, whereas in lattice theory they would be the top and bottom 30 elements given a partial ordering that runs from A (highest) to D (lowest).

The only restriction on the arrangements of categories is that there are no cycles, e.g. If C is a sub-category of B which is a sub-category of A then A cannot be a sub-category of C (or B even).

The category model defines what categories exist and their relationships to each other and may be treated as substantially the totality of the category information for a given

- Us e: À: information space It does not generally include a list of the items that are in each category. The category server is a system for storing and transmitting information about individual 5 categories and their relationships with other categories and is used to store and transmit the category model.

The information server is a system for holding the individual items of information in their entirety, and may hold information about the individual items that includes how they are 10 arranged within a particular category model, in the form of web pages, database records, or electronic documents or files of some other format.

The search device, or search server, is a system for specifying user queries that will find and transmit information on items (accessible through the information server) that match 15 the user query, either totally (for Boolean methods such as SQL queries) or partially (for fuzzy or relevance-based search methods).

There are direct and active connections between the client (display device) and the three other main components - category server, information server and search device. These 20 are used to transmit information to and from the client during the execution of the "naviguidance" process of the present invention. The links between the information server and the search device and category model are suitably relatively static connections. For example, the category model information stored by and accessed through the category server may be generated from the information server. Similarly, the index used by the 25 search service may be generated through any number of processes but does not necessarily require real time access between the two components.

For the purpose of describing the process of navigation, the only requirement for the link between these processes is that information items stored by the information server should 30 be linked to at least one category held by the category server, and the search results returned by the search device should include this information and optionally additional information on the individual items accessible through the information server.

By way of simple exemplification prior to more detailed discussion below of the roles of 35 the search device/server and information server, one may consider the case where a supermarket stocks 30,000 products organised into 300 different categories (e.g. frozen foods sub-divided to frozen pizza as a sub-category). The category model would hold

* . : s r information on the product types (i.e. the categories) but may not hold any detail of the individual products. Instead, the information server would hold/access the detail of each individual product - e.g. the description of the wine and a picture of the label or a list of

the contents of a tin of baked beans. The search device/server may take a query 5 regarding one or more products and return summary information about those items

matching the query, including which categories each product fitted into. The search device/ server might, for example, reply with the name and price of a bottle of wine or tin of baked beans.

10 Brief Description of the Drawings

A preferred embodiment of the present invention will now be more particularly described by way of example and with reference to the accompanying drawings wherein: Figure 1 is a flowchart of the main steps of the preferred embodiment of the 15 "naviguidance" process of the present invention; Figure 2 is a diagram of a simple illustrative category model; Figure 3 is a simple schematic diagram of a suitable basic architecture for the system; Figure 4 illustrates screen shots for example alternative top level displays for a given category model; Figure 5 illustrates a DTD fragment for information items showing how this may be 25 suitably formatted; Figure 6 is a part of the flowchart of Figure 1 illustrating the browsing process; Figure 7 is a part of the flowchart of Figure 1 illustrating the searching process; Figure 8 is a part of the flowchart of Figure 1 illustrating a mixed mode navigation process combining browsing and searching; Figure 9 is a part of the flowchart of Figure 1 illustrating the naviguidance process; Figure 10 is a simple category model showing traditional context information which might normally be displayed to the user; and.

Figure 11 is a simple category model similar to Figure 10 for the system of the present 40 invention in which high context is displayed to the user.

r I,,, . . a Description of the Preferred Embodiment

5 For the purpose of describing a preferred embodiment of a web-based implementation of naviguidance, referred to through out as nay-e-guidance, the structure of the components of the preferred architecture are described in more detail as follows.

Referring firstly to Figure 3, the Category server CServ is a combination of a web (HTTP) 10 server and identified files / URLS www.site root domain for site www.site/navicat root domain for category server www site/navicaVversion.xml category model version info www.site/navicaVmodel. xml category model The Search Service. Sserv is an identifiable process or server that can be accessed via a URL with specified arguments that include: search criteria, either as free text or one or 15 more attribute / value pairs; (optional) search location, identifying which parts of the information space are to be considered; and (optional) processing of results including how many to return and in what order.

The client, or display device, Ddev Is sultab!y a combination of: 20 a client hardware device with appropriate operating system software a webbrowser capable of generating and processing HTTP requests including HTML and optionally XML; a Nav-e-guide client program that works in tandem with the web-browser to process nav e-guidance requests; and 25 designated local storage of information comprising a designated location or directory to store nay-e-guide files, nay-e-guide category model files, an optional catalogue of nav-e-

guide models, andformatting directives for category model The information server Iserv is suitably a web (HTTP) server that can present any 30 combination of: Static HTML pages, application documents, e.g. pdf files, Shockwave files etc; or dynamically generated pages based on server processes accessing structured databases or unstructured document stores

: 9. A Comparison with Existing Web Architectures The architecture of a nay-e-guidance information source has a number of distinctive features when compared to a standard web-site implementation. Some of these are listed in the table below.

Conventional Web-Site Nav-e-guide Information Source Undifferentiated storage of information with Explicit representation and processing of category info embedded in standard site category info distinct from information items architecture - or any other information Transfer and caching ofinformation done at Transfer and caching of information at page level catenorv model and result set level _ Manual requests for transfer of partitioned Automated, background downloading of

information from server, e.g. when user category information and search results selects new category or extra set of search results to browse Viewing new (unviewed) categories results Viewing new categories managed locally in request to server for new page and with no additional request to server requires additional transfer of info Search service not explicitly identified as Search service is identified process with separate component of architecture and is published machine-readable API.

treated the same as any other server side functionality. API is defined by user interface. It should be noted that in many cases, existing web sites can be converted into nav-e-

guidable information sources by the addition of: a) A processing means to extract the category model information from the web site, 10 either by running database reports on the database used to dynamically generate the website content, or by "crawling" (i.e. automatically following) the website links; b) a specification of the search input requirements and format;

c) a process to format the output of the search process so that it conforms to the nav-

e-guide data standards, which are specified through an XML document type definition 1 5 (DTD).

The process carried out by (a) is an occasional process that has to be run whenever the structure of the category model changes; the process of setting up (b) would typically be a one-off activity; while the process carried out by (c) is required whenever a user queries 20 the information source.

... . - t _ _ C .,.l, Basic Steps for navigation using the nay-e-guidance system (as set out in Figure 1) Step 1 The user needs to request the display of an information source via the naviguide-enabled 5 display device Ddev. In the case of web-based nay-e-guidance, this is done through the specification of a URL in a web-browser that supports the client Ddev...DTD: Step 2...

A check is performed to see if the source is naviguide-enabled. This is suitably done by labelling the information source in such a way that the display device can recognise that 10 the source is naviguideable. The labelling also indicates the location of the various naviguidance components required as shown in figure 3. In the case of web-based nav-

e-guidance, this is done by tagging the web page to include the component URLs of the category-server Cserv, information server Iserv, and search device Sserv.

The separate identification of the various components allows for distributed architecture in 15 which individual components can be exchanged without affecting other components, Step 3 If the information source is not naviguidable, then the information source is displayed in the conventional manner by the display device Ddev.

In the case of web-based nay-e-guidance, if the nay-e-guidance component URLs are not 20 present, then the web-browser will operate as normal, without the intervention of the nav-

e-guide client.

By embedding of naviguidance capability in info display the info source appears unaltered to non-naviguide display devices.

Step 4 25 If the information source is naviguidable, then the current category model (CatMod) version information is transferred from the category server Cserv, identified in step 2, to the display device Ddev.

In the case of web-based nay-e-guidance, this is done by passing control to the naviguide client program in the clienVdisplay device Ddev, which then requests the category model 30 version information. This is a standard HTTP request to the site HTTP server for an

o : i: ! identified page, which contains the version information and conforms to the Nav-e-guide XML DTD.

The use of version information allows users to establish whether the site structure has been updated since they last visited the site or whether they can expect to see a familiar 5 site layout.

Step 5 The current category model version information is then compared to existing category models available to the display device to identify if further transfer of information from the 10 category server Cserv to the display device Ddev is required. If a model CatMod is found that matches the version information (i.e. source, version and date) for the current information source then no further download is required.

In the case of web-based nay-e-guidance, this is done by comparing the current category model version information with that held in category model files directly accessible by the 15 nay-e-guide client. If a catalogue of category models is available then this will be scanned for matching models. If the directory is not available then a search will be made of the category model directory. Each category model file in the directory will be read to check the version information.

Given that version info can be used to track whether users have the most up to date info, 20 transfer time can be saved if no new info is required.

Step 6 If the current version of the category model is not stored locally by the display device Ddev then the display device makes a request to the category server Cserv to be updated to the current category model. The required category model information that is required to 25 make this update is then transferred from the category server to the display device. The new information is then merged with the existing information so that the display device is left with a version of the current, updated category model. If no category model is present, then the entire category model will be transferred.

In the case of web-based nay-e-guidance, this is a standard HTTP request to the site 30 HTTP server for an identified page, which contains the updated category model and conforms to the Nav-e-guide XML DTD.

-......

]P . D If an update is required this can be done in such a way as to minimise the transfer of information. Once the information is stored locally, users can navigate the category model without a need to request further information from the information source or category server Cserv.

5 Step 7 Once the display device has received (or retrieved from local storage) the category model, this is then formatted and displayed to the user, according to the formatting directives that are part of the category model. In particular, by default this will include: information about the top most category including title, description etc; and information about the sub

10 categories contained in the top most category The choice of information to be shown is contained in the formatting directives, including which category to display first. By default the first category shown will be the top most category, but it is possible to specify a different category further down in the model.

In the case of web-based nay-e-guidance, the category model is rendered as HTML 15 through the application of a style sheet to the underlying XMLbased representation of the category model.

Explicit representation of category model as distinct from any selected information to be displayed allows flexibility in choosing what information to display. Explicit separation of content from formatting allows flexibility in choosing how information is displayed.

20 Sten 8 Once information (i.e. title, description, sub-categories, etc) for the relevant category is

shown by the display device, the user can choose what information to navigate and how.

In general, they can choose to: a) search the information source, or some identified parts of it, using a particular 25 query or specified search criteria that expresses their goals and information requirements; b) browse a sub/super-category of information, where the choice of category is determined by the information displayed about the category, and the user's interpretation of that information in relation to their specific goals and requirements; or c) display the detail of a specific item of information that is referenced in the category, 30 such as the details of a specific product or news group posting.

In the case of web-based nay-e-guidance, this functionality is provided by having all the browse and search choices available through a single page displayed by the nav-e-guide

r 9 1F O

enabled browser. Selections of information items to display or categories to browse are made by a single click on a link identified through text and/or graphics. Selecting categories to search and specifying the criteria to use are described below.

5 Given that browse and search information is displayed in a unified fashion, users can more easily swap between browsing and searching information. In addition, the ability to restrict searches means that users will get a more focussed set of search results.

step 9 10 If the user chooses to search the information space, they must specify the search criteria to be used. The format for the search criteria, e.g. free text vs structured fields, is

contained within the specification of the search service which itself is down loaded along

with the category model during steps 4, 5 and 6.

If the search is free format text, then the user simply types the text and optionally specifies 15 a category as the area of the information space to search.

If the search is structured, then the user needs to specify legal values (based on type or the set of allowed values) for all mandatory attributes or fields, and optionally enter values

for other fields and a category to search.

Once the query has been specified, this is formatted into the appropriate command or 20 message for the search service using the specified input command format. The command has a number of placeholders for the user input. If the search service uses free-text, then the command will have two placoholders and the user search text and selected search category are merged into the search command. If the search is structured, then the command will have one placeholder for each possible attribute value, and one for the 25 search category. In the case of web-based nay-e-guidance, the specification of the search

input allows the

nay-e-guide to collect and validate user input which is then merged with a standard call to the search device by specifying a URL with appropriate arguments in order to invoke a server-side script or process.

30 It is easy to specify and change the interface behveen the basic search offered by the information space search device Sserv, and the naviguide enabled search process provided by the display device Ddev. In addition, the quality of the searching is not compromised, given there is client-side validation that occurs at the input device. Finally, given search results are stored locally and can be filtered by the display device, it is

l À. l. possible to add restrictive searches (i.e. limit searched to specific categories) to existing search services that do not offer that capability.

Step 10 5 Once the user has entered the appropriate search criteria, this information is transferred to the search device Sserv for execution. The details of the search mechanism are transparent to the other components of the system above and beyond the specification of

the search device (as part of the Category Model) and the required formatting of search results as specified by the results set.

10 In the case of web-based nay-e-guidance, the specification of the search is done entirely

through the construction of a URL that specifies: The address of the process or script to be invoked; The input arguments as specified by the user.

The execution of the search is initiated by the nay-e-guide client making an HTTP request 15 through the web-browser.

The transparency of the search device Sserv means that changes to any system component do not affect other components provided that the defined APls are respected.

The specification of a search device Sserv also allows sites to maintain identical but

separate search means for naviguidance as opposed to conventional services thereby 20 balancing demand between different user types.

Step 1 1 Following execution of the search, the search device Sserv will notify the display device Ddev of the results. If no results are found then, with the exception of an appropriate message being displayed, the information shown by the display device Ddev is essentially 25 unchanged. If the search does find some items that match the user-specified search criteria, then this information, i.e. the number of hits and relevant categories, is transmitted to the display device Ddev.

In the case of web-based nay-e-guidance, the notification of search results is done through the transmission of a results page, appropriately marked up using the search 30 results DTD. The notification of results is done through transmitting the total number of search results, and optionally the hit counts for the most relevant categories. The actual download of results is controlled by the results transfer process described below.

He.*.-. . . e The separation of notification of results from the actual transfer of results allows the download of information to be tailored to site, client and network requirements thereby maximising efficient use of band-width, memory and disk space. It also enables, if required, a fast visualization of search results prior to the download of any actual search 5 results.

Step 12 Once notification of the search results has been passed to the display device Ddev then the actual search results themselves will be transferred. This transfer may be done using a single uninterruptible transfer of the complete set of search results, or may be broken 10 into a number of different sets of data which are transferred by one or more processes.

in the case of web-based nay-e-guidance, the transfer of search results is done through the transmission of a results page, appropriately marked up using the search results DTD.

The search results will be self-contained and therefore contain the basic information about each item returned, including: its name, end (i.e. bottom most) category, and location for 15 the full item description; and (optionally) a short description, and a number of structured

attribute values to aid presentation and analysis, e.g. relevance, price, date etc In general, the search does not have to return any additional information about the item, about and beyond its identity and a pointer to a full description of the item. However, by

20 default almost all information spaces do a short item description and the majority also

return a relevancy score that is used to rank the search results. Despite the prevalence of relevance information, this information is not treated any differently than another attribute that might similarly be used to rank results and is a consequence of nay-e-guidance being designed for both structured database searching and free-format text retrieval.

The sequencing of the download is to cater for the trade-off between the number of results to be downloaded and the delay before users can view any information. At the two extremes: a minimal transfer just downloads the hit counts, i.e. the number of total hits and the 30 number of hits for the most relevant categories, without any item information. This allows a fast highlighting of the relevant categories (steps 13-15) before step 16 fills in additional detail. a maximal transfers all the information in one go (with step 16 eliminated), thereby presenting the most detailed and consistent view of the results but at the expense of the 35 download time.

c -: À i r: c Typically the results of Internet searches will be presented 10 items at a time as this provides a useful amount of information for users to read without imposing a long delay.

Users then have to manually request additional portions of the search results if they wish to look beyond the initial results set.

5 With a nay-e-guidance system, the initial search result information can be downloaded to provide useful information on how to explore the result set, prior to downloading a fuller set of results Incrementally and automatically downloading additional parts of the result set gives the user even more information to use in identifying the most relevant information. 10 The structuring of result information into category counts and detailed information makes it possible to minimize the cognitive delay in users starting to assess the types of results available and the possible directions in which to focus a review of the search results.

Step 13 Once the search results (including some, all or none of the actual search result items) 15 have been transferred to the display device, the categories that contain relevant information (i.e. items that match the search criteria to a lesser or greater extent) are identified and tagged. This is done by an upward traversal of the category graph, starting with the end category of individual items, or with identified sub-categories contained in the result set category counts.

20 In the case of web-based nay-e-guidance, the marking of the highlighted categories is done by setting an attribute on the category object, and the traversal of the category model is done through the super- category attribute. The traversal of the model (for highlighting purposes) stops when a previously highlighted item is encountered, although traversal to the root search node is required if item counts are being maintained for the 25 whole model.

Tagging highlighted categories means that users are free to browse the result set without losing track or becoming separated from the search results. Categories can be continually updated as more results are incrementally transferred.

Step 14 30 Once relevant categories are tagged for highlighting, search results are subject to a similar process. The search items are tagged so that only those that fall into the category being viewed will be shown. When the search results are initially retrieved, the result set to be displayed will be equal to the entire result set, assuming: search service provides a

< r À -, t restricted category search (or that the user chose to search the entire information source); the user is still viewing the top most category specified for the search.

If this is not the case (i.e. the search service does not offer category restrictions and/or the user has shifted the viewing focus to a different category), then some of the search results 5 will be removed from the set of items to be displayed.

In the case of web-based nay-e-guidance, the marking of the items to display is done by setting an attribute on the item object in the result set.

As the user chooses sub-categories to browse, the context of query becomes more and more specific. As this happens, the number of search results to display will decrease 10 monotonically thereby giving the users less and less information to review where the information itself is more and more relevant to the chosen context.

Step 15 The final step in displaying information is to update the display of the chosen category to show: the sub-categories within the chosen category, including any relevant description;

15 highlighted sub-categories to explore, i.e. that contain information items that match or are relevant to the entered search criteria; information items that match the search / browse criteria. Where the information is just being browsed, i.e. no search has been executed and steps 9-13 have been omitted, all information items in the category will be shown. If a search 20 has been executed, then the matching items will be shown separately from non-matching items. Non-matching items are typically only shown for end sub-categories, i.e. those categories with no sub-categories.

In the case of web-based nay-e-guidance, the selected category is rendered as HTML, as 25 discussed at step 7 with the initial display of the top-level category. The inclusion of highlighting information is easily incorporate through the use of a specific style for highlighted categories. This allows a number of different stylistic devices to be used to flag up the relevant categories including different colour schemes, text effects such as increased font sizes or emphasis through bold text; or the inclusion of graphic points, 30 including for example animated gifs The choice of which devices to employ is left to the site designer.

r:. . r ',, I. _

The use of a down-loaded category model and the use of highlighting attributes for relevant categories and information items makes the navigation and manipulation of search results fast and effective. Only new information is required to be downloaded, and it is easy to assess if items have been previously viewed. The use of style sheets and 5 semantic mark-up makes it easy to ensure the presentation of search results match any corporate and site style guidelines, while at the same time allowing experimentation to assess the most effective ways of guiding users to relevant information.

Step 16 At any point in time, the user can request additional information on an individual item of 10 information. The items can be selected either from the search results as they are presented, or from the choices presented when browsing a category. The additional information on the selected information is provided by the Information Server and is accessed via a unique key or location assigned to each item of information.

In the case of web-based nay-e-guidance, the item location (as specified in the item DTD 15 fragment of Figure 5) will be a URL that references a static web page, document or server-side script to extract the identified element from a dynamic data store.

The "Naviguidance" system of the present invention separates item information into that held by the search service Sserv(as shown above) and more detailed information that is 20 held by the Information Server Iserv. This allows a small amount of information to be held and presented to the user making it easier and faster to assess the potential information.

If the user believes the item is likely to be of interest they can then look at the detailed item information, thereby only incurring the extra down-load time penalty when required.

Traditional Navigation Processes 25 The basic process steps outlined above support the three main types of user behaviour through a single integrated interface. The three main types of navigation are: a) Browse only where the user chooses their own path through the various categories and sub-categories of information, moving up and down the various levels until they find the appropriate end category and can review individual items of information.

30 b) Search only where the user enters their search criteria, are presented with a list of search results and then choose the items they wish to review in more detail.

c) Mixed mode where the user switches between browsing and searching, either by navigating to a particular category and starting the search from there, or by moving from the search results to browse sub-categories.

.e ' ' 1 The nay-e-guide implementation of these three types of behaviour all share the same common start, namely steps 1 to 7. Referring to Figure 6, "Browse only" behaviour is represented by cycling through steps 8, 14, 15 and 16 although sten 14 is modified. As there are no search results to be shown, all the category items are displayed as a single 5 collection of browsabie items and Map 14 is effectively by-passed.

Referring To Figure 7, "Search only" behaviour is represented by steps 8 to 12 with step 16 repeated for each individual search result, and step 12 repeated for each new page of search results. Successive searches simply restart the navigation process at step 8.

10 Traditional "Mixed mode" navigation covers all the steps identified above. However, overlaying the steps makes it clear that there is a discontinuity in the process. Although it is possible to move from searching (step 12) to an identified item (step 16), and then browse related items (tens 15 & back to 16) the link with the search results is lost.

15 Getting back to relevant items found by the search requires backtracking through steps 15, 8, 16 and then 12. Switching from searching to browsing in this manner has additional problems. If a user simply ends up in the end category of the selected item then it will be more difficult to understand the context of the information. Even if the user is shown all the categories leading from the top most category to the current end category (and 20 thereby see some context information) they will not be able to easily explore or evaluate other possible choices of categories.

Referring to Figure 9 Naviguidance, by contrast, enables users to combine search and browsing in an effective manner that avoids the problems of discontinuity, missing context 25 and hidden choices. It is possible to switch between the search cycle (steps 8-15) to the browsing cycle (steps 14-16) without losing the focus on relevant information provided by the user specified search criteria.

Given the search results are presented in a top-down manner, the user is also provided 30 with a clear view of the context of search results, all the choices available to them, and the best paths to explore. In this way, naviguidance can combine the relevancy provided by search criteria with the direction provided by the human capability to interpret context and infer meaning.

Us I: À À . . For example,a query on "France beats Germany" might highlight the categories shown in Figure 10, depending on the amount of context shown, i.e. the number of levels of category shown.

5 However, naviguidance allows the user to more simply distinguish football from foreign affairs, or real news from old news and to get different perspectives from both sides by presenting all possible choices of information to browse or selectively search (see Figure 11 which shows high context - all possible choices shown, and best choices highlighted).

10 Extensions to Conventional Navigation The blurring of browsing and searching made possible by naviguidance can be seen in "restricted browsing". This is effectively a search where users specify very broad or indirect criteria, such as a price band between ú50 and ú100. Only those categories with products meeting the specified criteria are highlighted, and items meeting these criteria 15 are more easily visible within a specific category. However, the resulting experience has a feel that is more like browsing. The user is far more in control of where they search and their interests, and the specified criteria are more like a mask, hiding unwanted products, than a filter, which is effectively letting relevant products through.

20 Another benefit that comes from the interaction of searching and browsing comes from being able to actively discount or ignore particular parts of the information space. This is co.nn.on behaviour when browsing If an area or category initially appears relevant but turns out to contain irrelevant information then the user makes an active choice to stop exploring it. This is not possible using conventional search, or mixed mode behaviour.

25 However, using naviguidance it is possible to reject a category, thereby unhighlighting all sub-categories and removing all the search results they contain from the list potentially relevant items.

A final point to make is that as naviguidance is based on an explicit representation and 30 storage of the category model and result set within the Display Device, it is possible to explore a set of search results without further recourse to the Search Service or the Information Server. In the case of web-based nay-e-guidance, this means that review of search results is possible even when off-line from the Internet. In the case of byte-based or time metered services, e.g. mobile telephony services such as Wap or OPUS, this off 35 line model could result in substantial savings.

r e e À The system and method of the present invention can be implemented in existing information storage and retrieval devices by adding a display device capable of providing naviguidance to the existing architecture where the existing architecture can fulfil the roles of category server, search device and information server. This applies most notably to 5 web sites that have a search service, implicit category model, and links between information items and that category model.

The display device may be integrated into existing information presentation and search devices so that its presence (other than through the functionality it provides) is 10 undetectable to a user.

The information source provider may, if desired, customise the display of the search results by changing the position, size and layout of the categories, subcategories and search items.

Claims (1)

1. r À o ... t, t t. À Claims

   5 1. A system for navigating an information source, the system comprising: a) a said information source in which items of information have been classified into different categories of information; b) a category server for storing or transmitting category information of the information source to a client; 10 c) a search device for retrieving information items each along with an indication of their corresponding category; and d) a client for presenting the possible categories of information, collections of information items and individual information items to a user in response to a search request from the client to the search engine;

   15 the information items in the information source being arranged in categories according to a category model that is fixed for the information source, not being dynamically generated or configured for each search or user other than optionally for explicit user modification, and the category information is separately and individually defined being held in the category server and manipulable by the client.

   2. A system as claimed in claim 1, wherein the system further comprises an information server operatively linked to the category server, search device and client and which holds said items of information or information about individual said items of information. 3. A system as claimed in claim 1 or claim 2, wherein the category model is held locally at the client in use.

   4. A system as claimed in claim 1 or claim 2 wherein the client is programmed to 30 detect whether an information source is a said information source that has its information items categorised according to a said category model.

   5. A system as claimed in any preceding claim wherein the information source is tagged with address identifiers for the search device and category server.

   r À À ., -r 6. A system as claimed in claim 4 wherein labels are provided on the information source which are used by the client for detecting whether an information source is a said information source.

   5 7. A system as claimed in any preceding claim wherein, for a selected said information source, the client is programmed to request or, at least, receive, the category model, or version information relating thereto or updates thereof from the category server.

   8. A system as claimed in any preceding claim wherein the client is programmed to 10 enable the user to browse through the categories of information using the display device without further requests to either the search device or the information and category servers and to invoke the search device at any point in the browsing process.

   9. A system as claimed in any preceding claim wherein the client is programmed to 15 enable the user to customise or modify the category model to allow them to more easily access those categories of information that they use most frequently.

   10. A system as claimed in any preceding claim wherein the client is programmed to enable the user to specify a set of search criteria using either free text or specific 20 attributes to retrieve (through the search device) a limited set of information items to display. 11. A system as claimed in any preceding claim wherein the client is programmed to enable the user to specify a set of browse criteria using either free text or specific 25 attributes to retrieve (through the information server) a limited set of information items to display. 12. A system as claimed in any preceding claim wherein the client is programmed to enable the user (prior to the start of a search) to restrict the display of search results to 30 those that are found in a particular category.

   13. A system as claimed in any preceding claim wherein the system is programmed to enable display of all sub-categories of information through the display device, not just those containing relevant information, to allow users to select categories of information 35 that they deem to be relevant even if the search device does not indicate that the category contains relevant information.

   To ' À - À r c. . t: At-' . 14. A system as claimed in any preceding claim wherein the client is programmed to enable the user to restrict the display of search results to those that are found in a particular category (or its descendants) following a search.

   5 15. A system as claimed in any preceding claim wherein the client is programmed for use of visual highlighting (through text formatting, the inclusion of graphic symbols, or both) to indicate the sub-categories of the starting category (and by recursion to the relevant descendants) that contain results that are relevant to a particular user-deflned query. 16. A system as claimed in any preceding claim wherein the client is programmed to enable the user to expand the display of search results by selecting the parent category of a displayed category.

   15 17. A system as claimed in any preceding claim wherein the client is programmed to enable the user to exclude a category (and all its descendants) from any further consideration, thereby eliminating all the information items it contains from further display.

   18. A system as claimed in any preceding claim wherein the client is programmed to 20 enable the user to save a set of search results and redisplay it at another time without requests to either the search device or the information and category servers.

   19. A system as claimed in any preceding claim wherein the client is programmed to enable the user to manipulate and combine sets of search results through the use of 25 logical or Boolean operators such as AND, OR and NOT.

   20. A method of navigating an information source where the information source consists of items of information that are classified into different groups or categories of information according to a category model and the method comprises a combination of 30 browsing and searching using the categories of information to partition the information source and the search(es).

   21. A method as claimed in claim 20, which method comprises: searching the information source by specifying one or more search criteria for 35 selecting items of information to view; and browsing the category model by selecting a category, sub- or super-category to display using a category display selector, using retrieval means to retrieve relevant

   e to À À À r 0,, items In the selected category, and using a category layout selector to control formatting of display.

   22. A method as claimed in claim 19, wherein the method comprises looking at 5 detailed information by selecting a required item from a selected category and displaying the item.