Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-10-25
2003-05-06
Corrielus, Jean M. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06560600
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to computerized information retrieval, and more particularly to identifying related pages in a hyperlinked database environment such as the World Wide Web.
2. Description of the Related Art
It has become common for users of host computers connected to the World Wide Web (the “Web”) to employ Web browsers and search engines to locate Web pages having specific content of interest to users. A search engine, such as Digital Equipment Corporation's AltaVista search engine, indexes hundreds of millions of Web pages maintained by computers all over the world. The users of the hosts compose queries, and the search engine identifies pages that match the queries, e.g., pages that include key words of the queries. These pages are known as a “result set.” In many cases, particularly when a query is short or not well defined, the result set can be quite large, for example, thousands of pages. The pages in the result set may or may not satisfy the user's actual information needs. The vast majority of users are not interested in retrieving the entire huge set of resources. Most users will be quite satisfied with a few authoritative results which are highly relevant to the topic of the query. The challenge is to retrieve only the most relevant resources to the query.
The Web is a hyperlinked collection. In addition to the textual content of the individual pages, the link structure of such collections contains information which can, and should, be tapped when searching for authoritative sources. Consider the significance of a link p. With such a link p suggests, or even recommends, that surfers visiting p follow the link and visit q. This may reflect the fact that pages p and q share a common topic of interest, and that the author of p thinks highly of q's content. Such a link, called an informative link, is p's way to confer authority on q. Note that informative links provide a positive critical assessment of q's contents which originates from outside the control of the author of q (as opposed to assessments based on q's textual content, which is under complete control of q's author).
The vicinity of a Web page is defined by the hyperlinks that connect the page to others. A Web page can point to other pages, and the page can be pointed to by other pages. Close pages are directly linked, farther pages is are indirectly linked via intermediate pages. This connectivity can be expressed as a graph where nodes represent the pages, and the directed edges represent the links. The vicinity of all the pages in the result set, up to a certain distance, is called the neighborhood graph.
Specifically, the Kleinberg algorithm attempts to identify “hub” pages and “authority” pages in the neighborhood graph for a user query. Hubs and authorities exhibit a mutually reinforcing relationship. The Kleinberg algorithm determines related pages starting with a single page. The algorithm works by first finding a set of pages that point to the page, and then running the base algorithm on the resulting graph. However, this algorithm for finding related pages does not deal with popular URLs, with neighborhood graphs containing duplicate pages, or with cases where the computation is totally dominated by a single “hub” page. The algorithm also does not include an analysis of the contents of pages when it is computing the most related pages.
The Google search engine uses a feature called PageRank to prioritize the results of web keyword searches. The PageRank technique examines a single random walk on the entire Web. PageRank assumes page A has pages Tl . . . Tn which point to it (i.e., are citations). The parameter d is a damping factor which can be set between 0 and 1. Also C(A) is defined as the number of links going out of page A. The PageRank (PR) of a page A is given as follows:
PR
(
A
)=(
l
-
d
)+
d
(
PR
(
Tl
)/
C
(
Tl
)+ . . . +
PR
(
Tn
)/
C
(
Tn
))
The PageRanks form a probability distribution over the web pages, so the sum of all web pages' PageRanks is one. PageRank or PR(A) corresponds to the principal eigenvector of the normalized link matrix of the web. The ranking of web sites is independent of the search query, and no distinction is made between hubs and authorities, as with the Kleinberg algorithm. There is also no provision for externally evaluating sites and using the evaluations to weigh the usefulness rankings.
Another method for ranking pages in a search result known in the art is disclosed in a paper entitled “The Stochastic Approach for Link-Structure Analysis (SALSA) and the TKC Effect”, by Ronnie Lempel and Shlomo Moran, which is published on the Web at the website for the Ninth International World Wide Web Conference, held in Amsterdam, The Netherlands, from May 15-19, 2000. The SALSA method examines random walks on graphs derived from the link structure among pages in a search result. While preserving the theme that Web sites pertaining to a given topic should be split into hubs and authorities, it replaces Kleinberg's Mutual Reinforcement method by a stochastic method, in which the coupling between hubs and authorities is less tight. The method is based on considering a bipartite graph G, whose two parts correspond to hubs and authorities, where an edge between hub r and authority s means that there is an informative link from r to s. Then, authorities and hubs pertaining to the dominant topic of the sites in G should be highly visible (reachable) from many sites in G. These sites are identified by examining certain random walks in G, under the proviso that such random walks will tend to visit these highly visible sites more frequently than other, less connected sites. The SALSA approach is based upon the theory of Markov chains, and relies on the stochastic properties of random walks performed on a collection of sites. It differs from Kleinberg's Mutual Reinforcement approach in the manner in which the association matrices are defined. The SALSA approach also initially assumes uniform probability over all pages, and relies on the random walk process to determine the likelihood that a particular page will be visited.
It is therefore desireable to provide a method for ranking the relative quality, or relevance, of pages with respect to one another, that factors in the probability of a page being viewed without requiring a random walk.
SUMMARY OF THE INVENTION
The invention provides a method whereby a linear combination of matrices that provide information about the pages can be used to rank the pages. This allows results to be ranked based on two or more “page qualities” that are sought by the user, thus providing highly relevant results to the user.
In one embodiment, a method of ranking a plurality of pages identified during a search of a linked database is provided that includes:
forming a linear combination of two or more matrices, wherein each matrix includes information about at least a portion of the plurality of pages;
determining an eigenvector of the linear combination; and
ranking the plurality of pages based on the eigenvector.
The coefficients of the eigenvector provide a measure of the quality of each page in relation to the other pages. The eigenvector used to rank the results can be the principal eigenvector or a secondary eigenvector. The matrices are generally normalized, stochastic matrices.
The invention accommodates external, subjective or objective judgment regarding the quality of a page in relation to it content or the number of linkages included in the page that are likely to be useful. The judgments are represented in attractor matrices to indicate desirable or “high quality” sites, while non-attractor matrices indicate sites that are undesirable. Attractor matrices and non-attractor matrices can be used alone or in combination with each other in the linear combination. Additional bias toward high quality sites, or away from undesirable sites, can be further introduced with probability weighting matrices for at
Alta Vista Company
Corrielus Jean M.
Pennie & Edmonds LLP
LandOfFree
Method and apparatus for ranking Web page search results does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for ranking Web page search results, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for ranking Web page search results will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3041841