Method and apparatus for identifying items of information from a multi-user information system

[0002] 1. Field of the Invention

[0003] This invention relates to a method and apparatus for identifying items of information from an information system which is especially useful for identifying information from the world wide web.

[0004] 2. Description of the Prior Art

[0005] The world wide web and many other information systems contain vast amounts of information. It is hard for users to keep up with new information that may be relevant to them because of the difficulty of doing searches. The user needs to spend valuable time planning and constructing search strategies and ensuring these are kept up to date as new terminology comes into use. Even when this task has been completed, the search needs to be run and then the results managed. Many irrelevant items may be found in the search and the user still needs to spend valuable time evaluating these and pinpointing relevant items. Because of these problems many of the advantages of the information system are lost. The user finds the system too difficult to use or manage and does not gain the maximum benefit from the information system.

[0006] Known systems that have been developed to find relevant information on behalf of users include those based on profiles. These systems build up a profile of the user which is a description of the types of information that s/he is interested in and then use this profile as a gauge against which to assess the relevance of a piece of information to the user. However, these systems are problematic because in order to be effective the profiles have to accurately reflect the interests of the user. Consequently the profiles are difficult to create and maintain as the user's interests change and adapt. Also, these systems are typically used in conjunction with a conventional search process and the profiles are used to prioritise or filter the search results before presentation to the user. This means that the whole process is still limited by the performance of the conventional search process in finding the required information quickly and without finding spurious information. Conventional search processes are designed to search, for example, a database or an index of terms. However, for unstructured, large systems like the world wide web conventional search processes are difficult to implement.

[0007] International patent application number WO 96/29661 in the name of Interval Research Corporation describes a system for the retrieval of hyperlinked information resources using heuristics. In this system a first “exploration” heuristic is used to search an information system (such as a network of linked textual or multi-media information) and this process finds at least one information resource for presentation to the user. Then a second “presentation” heuristic is used to present selected resources to the user and the user provides feedback indicative of the degree of relevance of the presented information in the form of a rating, score, or binary parameter, such as yes/no. The first and second heuristics are then modified on the basis of the ranking functions. This process is disadvantageous because it requires the user to provide relevance feedback which is time consuming. Also, the system searches the information system itself which makes it less useful for large unstructured databases.

[0008] International application number WO 95/29451 in the name of Apple Computer, Inc. describes a system for ranking the relevance of information objects accessed by computer users. This system involves storing a profile of interests for each user having access to the system and items of information are displayed in order of ranking. This means that the system has the disadvantages of “profile” systems as described above. Also, this system is not intended to be used to search large databases but rather is designed for use with electronic mail messages and bulletin board systems.

[0009] U.S. Pat. No. 5,537,586 describes a method for extracting a preferred set of textual records from a database. However, this is fundamentally a criteria-based search system. It will not find data that is not indexed and it relies on maintaining a search profile for each user.

[0010] International Patent Application Number W0 97/26729 describes a system for identifying which advertisements to present to a particular user of the world wide web. Using a “Smart Ad Box” simultaneous viewers of the same web page can be presented with different advertisements and this document describes a way in which advertisers can decide which of a number of adverts to present. In order to do this a measure of similarity between several individual users of the World Wide Web is generated. For one user the individuals with the greatest calculated similarity to that user become that user's community. The system then determines which advertisements to show to the user based on characteristics of that user's community.

[0011] This system is designed for identifying advertisements from a limited number of possible items, rather than for identifying any items of potential interest from the whole World Wide Web. Also, under this system, users are presented with advertisements that they have previously seen. The system is described as being used in conjunction with demographic data such as the age and domicile of a user. This is similar to profile based systems and is therefore subject to the same disadvantages. The demographic data is complex to obtain, maintain and use.

[0012] It is accordingly an object of the present invention to provide an apparatus and method for identifying items of information from an information system which overcomes or at least mitigates one or more of the problems noted above.

[0013] According to a first aspect of the present invention there is provided a method of identifying items of information from an information system, for at least one of a group of users of the information system, said method comprising the steps of:

[0014] (i) obtaining a first record of items of information requested from the information system by each user in the group;

[0015] (ii) obtaining a second record of items of information requested from the information system on more than one occasion by the same user;

[0016] (iii) determining a score for each pair of users in the group said score being determined on the basis of a number of items from the second record requested by one user in the pair, that were also requested by the other user in the pair;

[0017] (iv) for each user allocating one or more group members as friends for that user on the basis of the scores for pairs containing that user; and

[0018] (v) for each user identifying items of information that have been requested by a friend of the user that have not been requested by the user.

[0019] The invention also encompasses a corresponding apparatus for identifying items of information from an information system, for at least one of a group of users of the information system, said apparatus comprising:

[0020] (i) an obtainer arranged to obtain a first record of items of information requested from the information system by each user in the group and also to obtain a second record of items of information requested from the information system on more than one occasion by the same user;

[0021] (ii) a determiner arranged to determine a score for each pair of users in the group said score being determined on the basis of a number of items from the second record requested by one user in the pair, that were also requested by the other user in the pair;

[0022] (iii) an allocator arranged to allocate, for each user, one or more group members as friends for that user on the basis of the scores for pairs containing that user; and

[0023] (iv) an identifier arranged to identify, for each user, items of information that have been requested by a friend of the user that have not been requested by the user.

[0024] A corresponding information system is also provided comprising an apparatus for identifying items of information from the information system, for at least one of a group of users of the information system, said apparatus comprising:

[0025] (i) an obtainer arranged to obtain a first record of items of information requested from the information system by each user in the group and also to obtain a second record of items of information requested from the information system on more than one occasion by the same user;

[0026] (ii) a determiner arranged to determine a score for each pair of users in the group said score being determined on the basis of a number of items from the second record requested by one user in the pair, that were also requested by the other user in the pair;

[0027] (iii) an allocator arranged to allocate, for each user, one or more group members as friends for that user on the basis of the scores for pairs containing that user; and

[0028] (iv) an identifier arranged to identify, for each user, items of information that have been requested by a friend of the user that have not been requested by the user.

[0029] This method, apparatus and system each provide the advantage that “interesting” information that a user has not previously requested is identified. The user does not have to spend time searching for information and is quickly and simply provided with new information that is potentially interesting. This helps the user to cope with and make use of the ever-increasing amount and variety of available information in the information system (for example, the world wide web). Information is identified for both novice and expert users of the information system and information-finding tasks of various kinds are aided, for example, answering a particular query, or casually browsing or surfing for information of interest in the absence of a specific query. Advantageously, no user profiles are created or maintained which greatly simplifies the process and helps to reduce errors that may arise and no demographic data needs to be obtained, maintained or used. Also, no actual search process is carried out and no access to the information system itself is needed. Information is identified by reference to information that other members of a group of users have requested. This means that no complex and lengthy search processes need to be carried out and the method is suitable for large unstructured information systems such as the world wide web as well as well organised data bases.

[0030] Another advantage is that, by using the second record, information identified for each user is removed from the identification process unless it is requested more than once by the same user. This helps to avoid suggesting things to users simply because these have previously been suggested to that user's friend(s). This is especially important when the method has been repeated several times. Also, use of the second record in conjunction with the first record was found to produce unexpectedly good results. Users were presented with items identified by the system that were particularly useful and the number of irrelevant or uninteresting items was reduced.

[0031] FIG. 1 is a flow chart illustrating a main sequence of steps for identifying information.

[0032] FIG. 2 is a schematic diagram of the world wide web.

[0033] FIGS. 3ato 3dshow an example of a computer program listing written in the language PERL for implementing a method for identifying information on a general purpose computer.

[0034] FIG. 4 is an example of a computer program listing written in the language PERL for use with the listing of FIG. 3, for implementing a method for obtaining data for use with the method of FIG. 3.

[0035] Embodiments of the present invention are described below by way of example only. These examples represent the best ways of putting the invention into practice that are currently known to the Applicant although they are not the only ways in which this could be achieved.

[0036] FIG. 1 shows the main steps for a method for identifying information. The method is for use with a group of users of an information system. That is, it would not be practical to use the method for only 2 or a small group of users. The method can be used with as large a group of users as possible, given the limitations of processing power of the computer system or other apparatus that is used to implement the method. For example, the method has been successfully implemented for 80 users with a conventional computer system. Smaller groups of users could also be used.

[0037] The term “information system” is used to refer to any source of items of information that may be similar or diverse in subject matter and type, that can be accessed by several users and for which a log or record of that access can be obtained. For example, an electronic database, an index of items, the world wide web, a library and an encyclopaedia.

[0038] The method is designed to identify items of information for one or more users of the information system. The idea is to identify items that a particular user may find interesting or useful and which they otherwise might not have found. The user is directed to new areas of information which they can then investigate further. This is achieved without the need for a search to be performed or for complex information about the preferences and interests of particular users to be stored and maintained.

[0039] FIG. 1 shows the main steps in the method. First a record of items of information that have been requested by the each user in the group of users is obtained (box 1 in FIG. 1). For example, if the information system is the world wide web, then access logs from a proxy server could be used. FIG. 2 illustrates this situation and this is described further below. The record can include information about requests that have been made over a certain period of time.

[0040] The next step (box 2 in FIG. 1) is to determine scores for each pair of users in the group. These scores are a rough measure of “correlation” between pairs of users with respect to which items of information they have requested. Then (box 3 in FIG. 1) friends are allocated for each user. A friend is another user in the group who has a certain degree of “correlation” with the user with respect to items of information requested.

[0041] Once friends have been allocated for each user, users can be “told” about information that their friends have requested that they have not requested. Box 4 shows how items of information are identified that have been requested by a friend of a user but which have not been requested by that user. These items will be of potential interest to the user, because they were of interest to his/her friends.

[0042] A specific example of the method is now described in detail. FIGS. 3 and 4 show examples of program listings in PERL for implementing this method. The first step involves obtaining a record of items of information requested from the information system by each user in the group. In this example, the information system is the world wide web and the record is obtained from access logs on a proxy server. As shown in FIG. 2, the world wide web 21 can be thought of as part of the internet 22. Internal networks 24, 25 are provided, for example, within the workplace and these are connected to the internet 22 via proxy servers 23, 26. For internal network 24, any users of this network must gain access to the world wide web via proxy server 23. A log of access to the world wide web 21 by users of internal network 24 is typically kept on the proxy server 23 and this log may be used for the method. Many conventional web browser applications keep an access log and these could also be used. In this case, the access log may be on the user's workstation or computer. Any means for recording or tracking the information that users have accessed can be used. The apparatus for effecting the method may also be located on the proxy server 23 but it can also be located at other points in the internal network 24 or internet 22.

[0043] Data from the access log is compiled into a file called a “seen file” because it contains information about which items of information users in the group have “seen” or requested. In the example, 80 users make up the group of users, and the seen file has a maximum size. In the example, the seen file contains information about access to the information system going back approximately 3 months with rolling contents. However, other sizes of group and time periods could be used. The seen file also contains information about the location or address of each user in order that the results of the method can be sent back to the users. In the example, the seen file effectively comprises a table with two columns, one for the web page address that was the subject of a request to the information system and a second for the user address associated with that request (i.e. what was requested and who requested it).

[0044] The next stage involves obtaining further information. This information comprises a “data file” which essentially lists what web pages have been accessed by the same person on two or more distinct dates. The data file can be made up from the information in the seen file as part of the method, or alternatively, it can be provided as input to the method.

[0045] After repeated uses of the method, the “seen” file will contain references to occasions when the group members accessed items as a consequence of being alerted to these by the method. This means that there is a danger that a type of cyclical behaviour for the method will result. This is because items identified by the method are items that friends have accessed which may have already been suggested by the method to those friends. In order to reduce the effects of this, the data file is used.

[0046] Use of the data file in conjunction with the “seen” file has been found to produce unexpectedly good results. Users are presented with items identified by the system that are particularly useful and the number of irrelevant or uninteresting items identified is reduced.

[0047] The next step is to calculate scores for each pair of users in the group. As already mentioned these scores provide a very rough measure of “correlation” between two users. Using the data file, the number of items that have been requested by both members of the pair of users is determined. The number of these items “common to both users” is then divided by the sum of the number of items seen by the first user in the pair and the second user in the pair. This is then multiplied by 100 to obtain a percentage value. Other similar measures of commonality between the users can be used.

[0048] The scores are then used to allocate friends for each user. For example, one user is considered, and for each pair of which he is a member, the other member will be his friend, if the score for that pair is above a threshold value. The threshold value is determined on a “trial and error” basis. In the example described the threshold value was 7 and in FIG. 3 this is referred to as “minscore”.

[0049] For each user, a maximum number of friends are allocated and in the example, this maximum value was 20. The 20 friends with the highest scores are used if the maximum is reached. However, many users may have less than 20 friends. It is not essential to limit the number of friends in this way although this does limit the computational complexity of the process and may be required depending on the resources available to implement the method.

[0050] The next stage is to take one user and list all the items of information that his friends have requested. Then using the “seen” file, items that the user has already requested are eliminated from this list. The list then represents items of information that are potentially interesting to the user and can be presented or communicated to him. However, in order to refine the list further the following additional steps can be taken.

[0051] The list is checked to see whether any of the items it contains have been requested by several friends (in the example, items are eliminated from the list unless they have been requested by at least 4 friends; see “minshared” in FIG. 3). Then three items which have been requested by the highest number of friends are selected and these are presented to the user. These additional steps are ways of prioritising, or honing down the number of items identified for the user. These steps are not essential and other similar steps could be used to perform these functions. For example, three items could be chosen at random. In the example, the method was run over night and the results presented to the group members each morning. The results are useful and interesting for the group members.

[0052] As already mentioned FIGS. 3 and 4 list program code for implementing an example of the method. Other programming languages could be used and alternative algorithms are possible as would be obvious to a person skilled in the art.

[0053] A range of applications are within the scope of the invention. These include situations in which it is required to identify information from an information system that is used by a large number of people and where the information requested by each individual is logged. For example, the world wide web, medical and technical databases and patent databases.