Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-09-29
2001-08-07
Breene, John (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06272507
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to the field of analysis and design of linked collections of documents, and in particular to ranking the results of a search for documents in a linked collection of documents.
BACKGROUND OF THE INVENTION
Users of large linked collections of documents, for instance as found on the World Wide Web (“the Web”), are motivated to improve the rate at which they gain information needed to accomplish their goals. Hypertext structures such as those found on the Web primarily afford information seeking by the sluggish process of browsing from one document to another along hypertext links. This sluggishness can be partly attributed to three sources of inefficiency in the basic process. First, basic hypertext browsing entails slow sequential search by a user through a document collection. Second, important information about the kinds of documents and content contained in the total collection cannot be immediately and simultaneously obtained by the user in order to assess the global nature of the collection or to aid in decisions about what documents to pursue. Third, the order of encounter with documents in basic browsing is not optimized to satisfy users' information needs. In addition to exacerbating difficulties in simple information seeking, these problems may also be found in the production and maintenance of large hypertext collections.
Making sense of very large collections of linked documents and foraging for information in such environments is difficult without specialized aids. As noted above, collections of linked documents are often connected together using hypertext links. The basic structure of linked hypertext is designed to promote the process of browsing from one document to another along hypertext links, which is unfortunately very slow and inefficient when hypertext collections become very large and heterogeneous. Two sorts of aids have evolved in such situations. The first are structures or tools that abstract and cluster information in some form of classification system. Examples of such would be library card catalogs and the Yahoo!® Web site (URL: www.yahoo.com).
The second type of systems are those that attempt to predict the information relevant to a user's needs and to order the presentation of information accordingly. Examples would include search engines such as those found on the Yahoo Web site, Lycos (URL: www.lycos.com), InfoSeek (URL: www.infoseek.com), Excite (URL: www.excite.com) and Alta Vista (URL: www.altavista.com). In each of these systems a user's search request (i.e. information need), typically in the form of words and phrases, is processed and ordered lists of documents or information that are predicted to be relevant to the user's search request are presented.
The presentation of search results from Yahoo, Excite, Lycos and InfoSeek is by some classification, e.g. by the web site containing the information. However, Excite and Lycos permit alternate specifications for ranking and ordering documents. Generally, these tools “order and rank” the search based on their similarity to the user's topical query, which may include frequency of the terms of the search within the documents, where the term occurred (e.g. in title or body of document) or the proximity of the search terms to each other.
However, the aforementioned techniques for presenting the search results may not be optimal for many situations. For example, it may be desirable to order search results based on the documents frequency of access or based on a historical context of interest. The present invention addresses such a need.
SUMMARY OF THE INVENTION
A system and method for ranking the results of a search on a collection of linked documents, such as those found on the World Wide Web (hereinafter the Web) is disclosed. Documents found on the Web are typically referred to as Web pages. The system utilizes various kinds of information relating to the collection of linked documents, such as the topology, content and historical usage of the linked collections of documents to create the ranking. The ranking is based on historical patterns and information about the current context of interest (e.g. what the user or group appears to be currently interested in doing).
The present invention utilizes a spreading activation technique to identify the activation of the web pages identified in the search results. Spreading activation techniques are based on representations of Web pages as nodes in graph networks representing, for example, usage, content, and hypertext relations among Web pages. Activation is pumped into one or more of the graph networks at nodes representing the web pages/documents identified in the search result and it flows through the arcs of the graph structure, with the amount of flow modulated by the arc strengths (which might also be thought of as arc flow capacities) and a probability function which indicates the likelihood a user will continue to traverse through links in the document collection. The asymptotic pattern of activation over nodes will define the degree of activation of Web pages to the starting set of Web pages. The degree of activation will provide a measure by which to rank the search results.
The present invention is practiced by performing the steps of: gathering historical usage data for said collection of linked documents; providing said search results as initial activation information, said initial activation information indicating a set of focus documents in said collection of linked documents; generating page to page transition information from said usage data, said page to page transition information indicating a strength of association between documents in said collection of linked documents; generating link probability information from said historical usage data and topology and content data, said link probability information indicating a distribution of the number of documents a user will access in said collection of linked documents; performing a spreading activation operation based on said initial activation information, page to page transition information and said link probability information based on a network representation of said collection of linked documents; extracting said ranking information resulting from said spreading activation step when a stable pattern of activation across all nodes of said network representation of said collection of linked documents is reached; and ranking said search results based on said ranking information, said ranking based on the level of activation achieved.
REFERENCES:
patent: 5418948 (1995-05-01), Turtle
patent: 5668988 (1997-09-01), Chen et al.
patent: 5754939 (1998-05-01), Herz
patent: 6028601 (2000-02-01), Machiraju
patent: 6038560 (2000-03-01), Wical
patent: 6038574 (2000-03-01), Pitkow
patent: 6067552 (2000-05-01), Yu
patent: 6078916 (2000-06-01), Culliss
patent: 6098064 (2000-08-01), Pirolli
Savoy, j., “A new problaistic scheme for information retrieval in hypertext” New review for Hypermedia and Multimedia, vol. 1 pp. 107-134, 1995.*
Mendelzon et al., “Querying the World Wide Web”, Proceedings of the 4th International Conference on Parallel and Distributed Information Systems; Dec. 18-20, 1996, Miami Beach, Florida, pp. 80-91.
Savoy, J., “Searching information in hypertext systems using multiple sources of evidence”,Int'l. J. Man-Machine Studies(1993) 38, pp. 1017-1030.
Huberman Bernardo A.
Pirolli Peter L.
Pitkow James E.
Breene John
Domingo Richard B.
Robinson David J
Xerox Corporation
LandOfFree
System for ranking search results from a collection of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for ranking search results from a collection of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for ranking search results from a collection of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2450329