GB2525574A

GB2525574A - Method for searching a database

Info

Publication number: GB2525574A
Application number: GB1400496.4A
Authority: GB
Inventors: Per Block
Original assignee: Oxford University Innovation Ltd
Current assignee: Oxford University Innovation Ltd
Priority date: 2014-01-13
Filing date: 2014-01-13
Publication date: 2015-11-04
Also published as: GB201400496D0

Abstract

A method of searching a plurality of records (e.g. academic publications, patent publications), where the plurality of records are connected by a plurality of connections (e.g. citations associated with the publications), the method comprises the steps of receiving a set of input records 40, identifying a plurality of intermediate records 41, each of the first plurality of records having at least one connection to at least one of the starting set of records, identifying a plurality of result records, each of the plurality of result records having at least one connection to at least one of the first plurality of intermediate records, calculating a ranking for each of the plurality of result records 42, and generating an output.

Description

Method for Searching a Database [0001] This invention relates to a method for searching a database, and a data storage and retrieval system.

Background to the Invention

[0002] When searching a database of records for records of interest, conventionally the search is performed by selecting key words, and then records are identified on the basis of the key words. The key words may be included in the body of the record, or in an abstract, or may be assigned by a creator of the records. A problem with this approach is that relevant records may not be associated with the key words used and thus will be overlooked by the search, or alternatively, if a larger number of key words are used, the search is more likely to identify and return irrelevant records. In addition, even where relevant records are returned, it is not straightforward to identify the most important records in the result. It is known to rank records, for example Google's PageRank system, but this still relies on calculating a rating for each record in a search independent of the search parameters.

Summary of the Invention

[0003] According to a first aspect of the invention there is provided a method of searching a plurality of records, where the plurality of records are connected by a plurality of connections, the method comprising the steps of receiving a set of input records, identifying a plurality of intermediate records, each of the first plurality of records having at least one connection to at least one of the starting set of records, identifying a plurality of result records, each of the plurality of result records having at least one connection to at least one of the first plurality of intermediate records, calculating a ranking for each of the plurality of result records, and generating an output.

[0004] The plurality of intermediate records may not include any of the set of input records.

[0005] The plurality of result records may not include any of the set of input records [0006] A record may be in both the plurality of intermediate records and the plurality of result records.

[0007] The ranking of each of the plurality of result records may be dependent on the records in the plurality of intermediate records to which the result record is connected.

[0008] The ranking of each of the plurality of result records maybe dependent on a quality rating of the records in the plurality of intermediate records to which the result record is connected.

[0009] The quality rating of each of the plurality of intermediate records may be dependent on the number of records in the set of input records to which the intermediate record is connected.

[0010] The ranking of each of the plurality of result records may be dependent on the number of the records in the plurality of intermediate records to which the result record is connected.

[0011] The connections may be directional, each connection having a starting record and a finishing record.

[0012] Identifying the plurality of intermediate records may comprise identifying connections where each of the input records is a starting record, and each of the intermediate records is a finishing record.

[0013] Identifying the plurality of intermediate records may comprise identifying connections where each of the input records is a finishing record, and each of the intermediate records is a starting record.

[0014] Identifying the plurality of result records may comprise identifying connections where each of the intermediate records is a starting record, and each of the result records is a finishing record.

[0015] Identifying the plurality of result records may comprise identifying connections where each of the intermediate records is a finishing record, and each of the result records is a starting record.

[0016] The records may comprise records identifying publications, and the connections may comprise citations associated with those publications.

[0017] The publications may comprise academic publications.

[0018] The publications may comprise patent publications.

[0019] The plurality of records may be stored in a plurality of databases, wherein at least some of the connections are between records in a first one of the plurality of databases and records in a second one of the plurality of database.

[0020] According to a second aspect of the invention there is provided a data storage and retrieval system, comprising a storage system storing a database, the database comprising a plurality of records, where the plurality of records are connected by a plurality of connections, and a retrieval system operable to access the database, the retrieval system being operable to perform a method according to the first aspect of the invention.

Brief Description of the Drawings

[0021] An embodiment of the invention is described by way of example only with reference to the accompanying drawings, wherein; [0022] Figure 1 is a diagrammatic illustration of a data storage and retrieval system, [0023] Figure 2 is a diagrammatic illustration of a plurality of connected records within the system of figure 1, [0024] Figure 3 is a diagrammatic illustration of an alternative plurality of connected records, [0025] Figure 4 is a diagrammatic illustration of connected records in a plurality of databases, [0026] FigureS is a flow diagram illustrating a method of searching records within the system of figure 1, and [0027] Figure 6 is a diagrammatic view of a plurality of input records, intermediate records and result records.

Detailed Description of the Preferred Embodiments

[0028] With specific reference now to the drawings in detail, it is stressed that the particulars shown are by way of example and for purposes of illustrative discussion of the preferred embodiments of the present invention only, and are presented in the cause of providing what is believed to be the most useful and readily understood description of the principles and conceptual aspects of the invention. In this regard, no attempt is made to show structural details of the invention in more detail than is necessary for a fundamental understanding of the invention, the description taken with the drawings making apparent to those skilled in the art how the several forms of the invention may be embodied in practice.

[0029] Before explaining at least one embodiment of the invention in detail, it is to be understood that the invention is not limited in its application to the details of construction and the arrangement of the components set forth in the following description or illustrated in the drawings. The invention is applicable to other embodiments or of being practiced or carried out in various ways. Also, it is to be understood that the phraseology and terminology employed herein is for the purpose of description and should not be regarded as limiting.

[0030] Example of possible data storage systems for holding a plurality of records to be searched are illustrated in figure 1. A first data storage system is shown at 10, comprising a storage system 11 and a retrieval system 12. The data storage system 10 may be accessed by a local client device 13, for example one attached to the system 10 or sharing a local area network. Alternatively, or in addition, the data storage system 10 may be accessed by a remote client device 14, for example via the Internet, generally illustrated at 15. In the present application, the term database' is generally used to refer to a stored and accessible plurality of records, for example held on the storage system 11 as shown at 16. However, the plurality of records may include records stored in a plurality of databases on a number of linked storage systems, as shown by second data storage system 10'.

[0031] In this description, record' generally refers to a discrete item or node in a database, usually relating to a single entity or, if appropriate, group of entities, and possibly also including ancillary information relating to that entity or group of entities. For example, where the database relates to academic papers, each record may identify a single entity comprising an academic paper, and the ancillary information may include such information as the authors, citations, other papers citing the paper, an abstract, publication details and so on.

[0032] The plurality of records 16 are connected, as illustrated in figures 2 to 4. In this application, connected' is intended to mean that a record includes a reference to at least one other record, for example by means of an identifier, a link or URI, a database key or keys, a text field, or otherwise.

The existence of a connection indicates that the records are related in some way. For example, in a database comprising a plurality of records each related to a published academic paper, the records may include references to other papers cited in the respective paper, by any suitable identifier.

[0033] In the example of figure 2, the plurality of records 16 are connected by directional connections 20, that is each connection 20 leads from a first record 16 to a second record. The connections may alternatively have any desired directionality, depending on the entities to which the records refer and the relationships between them.

[0034] An example of such connections is references to cited papers in a database of academic papers, for example. In this example, the connections 20 have a temporal implication, in that an academic paper can only reference an earlier academic paper, for example. In the example of figure 3, the plurality of records 16 are connected by connections which are not directional, so that each connection leads from the first record to the second record and vice versa. An example would be a database of academic papers where the connections represent authors of each paper.

[0035] Figure 4 is an illustration of a plurality of records being searchable across multiple databases.

The databases are shown at 22 and 23, with connections 24 extending between the records 16 of each database. Providing there are also connections 25 extending between records in each database 22, 23, the plurality of records 16 may be searched as a whole. The databases 22, 23 may be distributed across the internet, in which case the method described herein may be used to perform internet searching.

[0036] A method of searching a plurality of records 16 is shown at 30 in figureS. At step 31, an initial search parameter comprising a set of input records is supplied. That is, a user will supply an initial set of records of which they are aware, for example relating to a number of papers in an academic field. At step 32, a plurality of intermediate records are selected, by identifying all records which are connected to the set of input records) but excluding the input records themselves. In the example of figure 2, the input set of records are shown at 16a, and the intermediate records are shown at 16b. At step 33, a plurality of result records is identified by identifying all records with a connection to the intermediate records 16b, which may include some or all of the intermediate records 1Gb. In figure 2,3 plurality of result records are shown at 16c. Record X is in this example in both the plurality of intermediate records and the plurality of results records.

[0037] Where the connections 20 have a direction, the search may follow the connections only in that direction, in the opposite direction, or may simply select connected records irrespective of the direction of the connection.

[0038] At step 34, an intermediate rating is calculated for each of the plurality of intermediate records, in this example dependent on the number of input records to which each of the plurality of intermediate records is connected. The intermediate rating for an intermediate record may for example be the number of input records to which the intermediate record is connected, the square of that number or some other function thereof, the proportion of the set of input records which the intermediate record is connected, or any other function. The intermediate rating may also take into account the number of other intermediate records to which the intermediate record is connected.

The intermediate rating may be calculated as part of step 32, or before step 33, or even after step 33.

[0039] At step 35 a quality rating is calculated for each of the plurality of results records. The quality rating for each of the result records is then calculated on the number of intermediate records to

S

which the result record is connected, and/or the intermediate rating for each of those intermediate records. The quality rating may for example be a simple sum or a weighted sum of these ratings or any other function thereof.

[0040] At step 36, the plurality of result records are output ranked according to their respective quality scores) so that the result records with the higher quality ratings are presented higher in the list.

[0041] Examples of how the result records are ranked will be discussed with reference to Figure 6.

Figure 6 shows a plurality of input records 40, a plurality of intermediate records 41 and a plurality of result records 42. According to a first method, each intermediate record is given a score equal to the number of input records it is connected to, and the quality rating for each of the result records is the total score of the intermediate records to which the result record is connected. According to a second method, each intermediate record is given a score equal to the square of the number of input records it is connected to, and the quality rating for each of the result records is the total score of the intermediate records to which the result record is connected. According to a third method each intermediate record is given a score of 1 if the number of input records it is connected to is equal to or higher than a threshold, for example 2, and a score of 0 otherise, and the quality rating for each of the result records is the total score of the intermediate records to which the result record is connected.

[0042] The results of the three methods for each of the intermediate records is summarised in the

following table;

Record No.4 No.5 No.6 No.7 Methodl 1 3 2 1 Method2 1 9 4 1 Method3 0 1 1 0 [0043] Similarly, the score for each result record using the three methods is shown in the following

table;

Record No.8 No.9 No. 10 Methodl 6 5 1 Method 2 14 13 1 Method3 2 2 0 [0044] Accordingly, it will be clear that the results records based on the best quality or best-connected intermediate records are ranked highest. The score for each of the results records of course need not be a simple total of the intermediate records' scores, but similarly may be a weighted total, the total squared scores, a threshold score or otherwise.

[0045] The method is advantageous in that it uses pre-existing connections in a database to identify the most relevant records given a particular set of input records. The pre-existing connections reflect implicit knowledge that has been encoded in the records, for example by academic authors citing previous papers of which they are aware and consider relevant. The best-connected result records are likely to be those considered most important, for example in a particular discipline. The search does not rely the searcher correctly identifying keywords for the search, or on the records being manually abstracted or provided with keywords when they are added to the database. If the search can be performed by following connections between records, it will be apparent that the search will naturally halt after following two sets of connections, between the input and intermediate records and between the intermediate and result records, and therefore will not involve searching every record in the database for matching records.

[0046] Where the connections are directional) it will be apparent that different searches can be achieved by selecting in which direction the connections are followed. The directionality need not be the same in both steps 32 and 33. For example, where the records refer to academic papers and where the connections from a record for a paper lead to records corresponding to papers cited in the first paper, following the connections from multiple input records to the jointly cited intermediary records is effectively a search for the previous papers most relevant to the set of input records.

[0047] In the second step, finding other papers that cite the same set of intermediary records (i.e., searching connections in the opposite direction to the first step, in that the search will follow connections from the cited papers to the citing papers) will generate a set of result records that cite the same set of intermediary (older) records as the input records. Hence, following this directionality of connections will result in result records (academic papers) that draw from the same set of previous research as the input records.

[0048] Alternatively, in the second step, searching for papers which are cited in the intermediate paper will identify further earlier papers. The other records that these intermediary papers jointly cite are the result records and the further joint academic basis of the research of the intermediary records. Following the connections in this direction will deliver as result records the papers that jointly are the fundament of research with the input records.

[0049] Following the connections backwards at both steps) i.e. to papers which cite the input papers and then to papers which cite the intermediate papers, will identify subsequent papers which have used or built on the original search papers. This search may act as a new papers' search, by identifying newly added records which are connected directly or indirectly to the input records.

[0050] Following the connections at both steps with the intermediate records as starting records and the input records and result records as finishing records of the connections) will identify result records that are commonly cited alongside the input records. This search may be useful to find the papers that form the common basis of a research field alongside the specified input papers.

[0051] The final output list may be limited to the results papers, or may also include the intermediate papers. Where a comprehensive review of a field is being undertaken) for example, the intermediate papers may be of interest. For a current awareness search) which is only seeking to identify new citations, the intermediate papers may be of less value.

[0052] An alternative use would be to search a database of patent publications, where connections to a publication represent the citation of that publication against a later document and/or documents cited by that publication. A further alternative use would be to search a plurality of records relating to films, music or other media) on the basis of any desired connection, such as artist, year, subject or otherwise, providing only that the connections are present between the plurality of records to be searched.

[0053] In the above description) an embodiment is an example or implementation of the invention.

The various appearances of "one embodiment", "an embodiment" or "some embodiments" do not necessarily all refer to the same embodiments.

[0054] Although various features of the invention may be described in the context of a single embodiment, the features may also be provided separately or in any suitable combination.

Conversely, although the invention may be described herein in the context of separate embodiments for clarity, the invention may also be implemented in a single embodiment.

[0055] Furthermore, it is to be understood that the invention can be carried out or practiced in various ways and that the invention can be implemented in embodiments other than the ones

outlined in the description above.

[0056] Meanings of technical and scientific terms used herein are to be commonly understood as by one of ordinary skill in the art to which the invention belongs) unless otherwise defined.

Claims

CLAIMS1. A method of searching a plurality of records, where the plurality of records are connected by a plurality of connections, the method comprising the steps of; receiving a set of input records, identifying a plurality of intermediate records, each of the first plurality of records having at least one connection to at least one of the starting set of records, identifying a plurality of result records, each of the plurality of result records having at least one connection to at least one of the first plurality of intermediate records, calculating a ranking for each of the plurality of result records, and generating an output.
2. A method according to claim 1 wherein the plurality of intermediate records do not include any of the set of input records.
3. A method according to claim 1 or claim 2 wherein the plurality of result records do not include any of the set of input records.
4. A method according to any one of the preceding claims wherein a record may be in both the plurality of intermediate records and the plurality of result records.
5. A method according to any one of the preceding claims wherein the ranking of each of the plurality of result records is dependent on the plurality of intermediate records to which the result record is connected.
6. A method according to claim 5 wherein the ranking of each of the plurality of result records is dependent on a quality rating of the records in the plurality of intermediate records to which the result record is connected.
7. A method according to claim 6 wherein the quality rating of each of the plurality of intermediate records is dependent on the number of records in the set of input records to which the intermediate record is connected.
8. A method according to any one of claims 5 to 7 wherein the ranking of each of the plurality of result records is dependent on the number of the records in the plurality of intermediate records to which the result record is connected
9. A method according to any one of the preceding claims wherein the connections are directional, each connection having a starting record and a finishing record.
10. A method according to claim 9 wherein identifying the plurality of intermediate records comprises identifying connections where each of the input records is a starting record, and each of the intermediate records is a finishing record.
11. A method according to claim 9 or claim 10 wherein identifying the plurality of intermediate records comprises identifying connections where each of the input records is a finishing record, and each of the intermediate records is a starting record.
12. A method according to any one of claims 9 to 11 wherein identifying the plurality of result records comprises identifying connections where each of the intermediate records is a starting record, and each of the result records is a finishing record.
13. A method according to any one of claims 9 to 12 wherein identifying the plurality of result records comprises identifying connections where each of the intermediate records is a finishing record, and each of the intermediate records is a starting record.
14. A method according to any one of the preceding claims wherein the records comprise records identifying publications, and the connections comprise citations associated with those publications.
15. A method according to claim 14 wherein the publications comprise academic publications.
16. A method according to claim 14 wherein the publications comprise patent publications.
17. A method according to any one of the preceding claims wherein the plurality of records is stored in a plurality of databases, wherein at least some of the connections are between records in a first one of the plurality of databases and records in a second one of the plurality of database.
18. A data storage and retrieval system, comprising a storage system storing a database, the database comprising a plurality of records, where the plurality of records are connected by a plurality of connections, and a retrieval system operable to access the database, the retrieval system being operable to perform a method according to any one of the preceding claims.