In response to a query a search engine returns a ranked list of documents. If the query is broad (i.e., it matches many documents) then the returned list is usually too long to view fully. Studies show that users usually look at only the top 10 to 20 results. In this paper, we propose a novel ranking scheme for broad queries that places the most authoritative pages on the query topic at the top of the ranking. Our algorithm operates on a special index of "expert documents." These are a subset of the pages on the WWW identified as directories of links to non-affiliated sources on specific topics. Results are ranked based on the match between the query and relevant descriptive text for hyperlinks on expert pages pointing to a given result page. We present a prototype search engine that implements our ranking scheme and discuss its performance. With a relatively small (2.5 million page) expert index, our algorithm was able to perform comparably on broad queries with the best of the mainstream search engines.
1 Introduction
When searching the WWW broad queries tend to produce a large result set. This set is hard to rank based on content alone, since the quality and "authoritativeness" of a page (namely, a measure of how authoritative the page is on the subject) cannot be assessed solely by analyzing its content. In traditional information retrieval we make the assumption that the articles in the corpus originate from a reputable source and all words found in an article were intended for the reader. These assumptions do not hold on the WWW since content is authored by sources of varying quality and words are often added indiscriminately to boost the page's ranking. For example, some pages are created to purposefully mislead search engines, and are known popularly as "spam" pages. The most virulent of spam techniques involves deliberately returning someone else's popular page to search engine robots instead of the actual page, to steal their traffic. Even when there is no intention to mislead search engines, the WWW tends to be crowded with information on topics popular with users. Consequently, for broad queries keyword matching seems inadequate.
Prior approaches that have used content analysis to rank broad queries on the WWW cannot distinguish between authoritative and non-authoritative pages (e.g., they fail to detect spam pages). Hence the ranking tends to be poor and search services have turned to other sources of information besides content to rank results. We next describe some of these ranking strategies, followed by our new approach to authoritative ranking - which we call Hilltop.
1.1 Related Work
Three approaches to improve the authoritativeness of ranked results have been taken in the past:
Ranking Based on Human Classification: Human editors have been used by companies such as Yahoo! and Mining Company to manually associate a set of categories and keywords with a subset of documents on the web. These are then matched against the user's query to return valid matches. The trouble with this approach is that: (a) it is slow and can only be applied to a small number of pages, and (b) often the keywords and classifications assigned by the human judges are inadequate or incomplete. Given the rate at which the WWW is growing and the wide variation in queries this is not a comprehensive solution.
Ranking Based on Usage Information: Some services such as DirectHit collect information on: (a) the queries individual users submit to search services and (b) the pages they look at subsequently and the time spent on each page. This information is used to return pages that most users visit after deploying the given query. For this technique to succeed a large amount of data needs to be collected for each query. Thus, the potential set of queries on which this technique applies is small. Also, this technique is open to spamming.
Ranking Based on Connectivity: This approach involves analyzing the hyperlinks between pages on the web on the assumption that: (a) pages on the topic link to each other, and (b) authoritative pages tend to point to other authoritative pages.
PageRank [Page et al 98] is an algorithm to rank pages based on assumption b. It computes a query-independent authority score for every page on the Web and uses this score to rank the result set. Since PageRank is query-independent it cannot by itself distinguish between pages that are authoritative in general and pages that are authoritative on the query topic. In particular a web-site that is authoritative in general may contain a page that matches a certain query but is not an authority on the topic of the query. In particular, such a page may not be considered valuable within the community of users who author pages on the topic of the query.
An alternative to PageRank is Topic Distillation [Kleinberg 97, Chakrabarti et al 98, Bharat et al 98, Chakrabarti et al 99]. Topic distillation first computes a query specific subgraph of the WWW. This is done by including pages on the query topic in the graph and ignoring pages not on the topic. Then the algorithm computes a score for every page in the subgraph based on hyperlink connectivity: every page is given an authority score. This score is computed by summing the weights of all incoming links to the page. For each such reference, its weight is computed by evaluating how good a source of links the referring page is. Unlike PageRank, Topic Distillation is only applicable to broad queries, since it requires the presence of a community of pages on the topic.
A problem with Topic Distillation is that computing the subgraph of the WWW which is on the query topic is hard to do in real-time. In the ideal case every page on the WWW that deals with the query topic would need to be considered. In practice an approximation is used. A preliminary ranking for the query is done with content analysis. The top ranked result pages for the query are selected. This creates a selected set. Then, some of the pages within one or two links from the selected set are also added to the selected set if they are on the query topic. This approach can fail because it is dependent on the comprehensiveness of the selected set for success. A highly relevant and authoritative page may be omitted from the ranking by this scheme if it either did not appear in the initial selected set, or some of the pages pointing to it were not added to the selected set. A "focused crawling" procedure to crawl the entire web to find the complete subgraph on the query's topic has been proposed [Chakrabarti et al 99] but this is too slow for online searching. Also, the overhead in computing the full subgraph for the query is not warranted since users only care about the top ranked results.
1.2 Hilltop Algorithm Overview
Our approach is based on the same assumptions as the other connectivity algorithms, namely that the number and quality of the sources referring to a page are a good measure of the page's quality. The key difference consists in the fact that we are only considering "expert" sources - pages that have been created with the specific purpose of directing people towards resources. In response to a query, we first compute a list of the most relevant experts on the query topic. Then, we identify relevant links within the selected set of experts, and follow them to identify target web pages. The targets are then ranked according to the number and relevance of non-affiliated experts that point to them. Thus, the score of a target page reflects the collective opinion of the best independent experts on the query topic. When such a pool of experts is not available, Hilltop provides no results. Thus, Hilltop is tuned for result accuracy and not query coverage.
Our algorithm consists of two broad phases:
(i) Expert Lookup
We define an expert page as a page that is about a certain topic and has links to many non-affiliated pages on that topic. Two pages are non-affiliated conceptually if they are authored by authors from non-affiliated organizations. In a pre-processing step, a subset of the pages crawled by a search engine are identified as experts. In our experiment we classified 2.5 million of the 140 million or so pages in AltaVista's index to be experts. The pages in this subset are indexed in a special inverted index.
Given an input query, a lookup is done on the expert-index to find and rank matching expert pages. This phase computes the best expert pages on the query topic as well as associated match information.
(ii) Target Ranking
We believe a page is an authority on the query topic if and only if some of the best experts on the query topic point to it. Of course in practice some expert pages may be experts on a broader or related topic. If so, only a subset of the hyperlinks on the expert page may be relevant. In such cases the links being considered have to be carefully chosen to ensure that their qualifying text matches the query. By combining relevant out-links from many experts on the query topic we can find the pages that are most highly regarded by the community of pages related to the query topic. This is the basis of the high relevance that our algorithm delivers.
Given the top ranked matching expert-pages and associated match information, we select a subset of the hyperlinks within the expert-pages. Specifically, we select links that we know to have all the query terms associated with them. This implies that the link matches the query. With further connectivity analysis on the selected links we identify a subset of their targets as the top-ranked pages on the query topic. The targets we identify are those that are linked to by at least two non-affiliated expert pages on the topic. The targets are ranked by a ranking score which is computed by combining the scores of the experts pointing to the target.
1.3 Roadmap
The rest of the paper is organized as follows: Section 2 describes the selection and indexing of expert documents; Section 3 provides a detailed description of the ranking scheme used in query processing; Section 4 presents a user-based evaluation of our prototype implementation; and Section 5 concludes the paper.
2 Expert Documents
Broad subjects are well represented on the Web and as such are also likely to have numerous human-generated lists of resources. There is value for the individual or organization that creates resource lists on specific topics since this boosts their popularity and influence within the community interested in the topic. The authors of these lists thus have an incentive to make their lists as comprehensive and up to date as possible. We regard these links as recommendations, and the pages that contain them, as experts. The problem is, how can we distinguish an expert from other types of pages? In other words what makes a page an expert? We felt than an expert page needs to be objective and diverse: that is, its recommendations should be unbiased and point to numerous non-affiliated pages on the subject. Therefore, in order to find the experts, we needed to detect when two sites belong to the same or related organizations.
2.1 Detecting Host Affiliation
We define two hosts as affiliated if one or both of the following is true:
They share the same first 3 octets of the IP address.
The rightmost non-generic token in the hostname is the same.
We consider tokens to be substrings of the hostname delimited by "." (period). A suffix of the hostname is considered generic if it is a sequence of tokens that occur in a large number of distinct hosts. E.g., ".com" and ".co.uk" are domain names that occur in a large number of hosts and are hence generic suffixes. Given two hosts, if the generic suffix in each case is removed and the subsequent right-most token is the same, we consider them to be affiliated.
E.g., in comparing "www.ibm.com" and "ibm.co.mx" we ignore the generic suffixes ".com" and ".co.mx" respectively. The resulting rightmost token is "ibm", which is the same in both cases. Hence they are considered to be affiliated. Optionally, we could require the generic suffix to be the same in both cases.
The affiliation relation is transitive: if A and B are affiliated and B and C are affiliated then we take A and C to be affiliated even if there is no direct evidence of the fact. In practice some non-affiliated hosts may be classified as affiliated, but that is acceptable since this relation is intended to be conservative.
In a preprocessing step we construct a host-affiliation lookup. Using a union-find algorithm we group hosts, that either share the same rightmost non-generic suffix or have an IP address in common, into sets. Every set is given a unique identifier (e.g., the host with the lexicographically lowest hostname). The host-affiliation lookup maps every host to its set identifier or to itself (when there is no set). This is used to compare hosts. If the lookup maps two hosts to the same value then they are affiliated; otherwise they are non-affiliated.
2.2 Selecting the Experts
In this step we process a search engine's database of pages (we used AltaVista's crawl from April 1999) and select a subset of pages which we consider to be good sources of links on specific topics, albeit unknown. This is done as follows:
Considering all pages with out-degree greater than a threshold, k (e.g., k=5) we test to see if these URLs point to k distinct non-affiliated hosts. Every such page is considered an expert page.
If a broad classification (such as Arts, Science, Sports etc.) is known for every page in the search engine database then we can additionally require that most of the k non-affiliated URLs discovered in the previous step point to pages that share the same broad classification. This allows us to distinguish between random collections of links and resource directories. Other properties of the page such as regularity in formatting can be used as well.
2.3 Indexing the Experts
To locate expert pages that match user queries we create an inverted index to map keywords to experts on which they occur. In doing so we only index text contained within "key phrases" of the expert. A key phrase is a piece of text that qualifies one or more URLs in the page. Every key phrase has a scope within the document text. URLs located within the scope of a phrase are said to be "qualified" by it. For example, the title, headings (e.g., text within a pair of
tags) and anchor text within the expert page are considered key phrases. The title has a scope that qualifies all URLs in the document. A heading's scope qualifies all URLs until the next heading of the same or greater importance. An anchor's scope only extends over the URL it is associated with.
The inverted index is organized as a list of match positions within experts. Each match position corresponds to an occurrence of a certain keyword within a key phrase of a certain expert page. All match positions for a given expert occur in sequence for a given keyword. At every match position we also store:
An identifier to identify the phrase uniquely within the document
A code to denote the kind of phrase it is (title, heading or anchor)
The offset of the word within the phrase.
In addition, for every expert we maintain the list of URLs within it (as indexes into a global list of URLs) and for each URL we maintain the identifiers of the key phrases that qualify it.
To avoid giving long key phrases an advantage, the number of keywords within any key phrase is limited (e.g., to 32).
3 Query Processing
In response to a user query, we first determine a list of N experts that are the most relevant for that query. E.g. N = 200 in our experiment. Then, we rank results by selectively following the relevant links from these experts and assigning an authority score to each such page. In this section we describe how the expert and authority scores are computed.
3.1 Computing the Expert Score
For an expert to be useful in response to a query, the minimum requirement is that there is at least one URL which contains all the query keywords in the key phrases that qualify it. A fast approximation is to require all query keywords to occur in the document. Furthermore, we assign to each candidate expert a score reflecting the number and importance of the key phrases that contain the query keywords, as well as the degree to which these phrases match the query.
Thus, we compute the score of an expert as as a 3-tuple of the form (S0, S1, S2). Let k be the number of terms in the input query, q. The component Si of the score is computed by considering only key phrases that contain precisely k - i of the query terms. E.g., S0 is the score computed from phrases containing all the query terms.
Si = SUM{key phrases p with k - i query terms} LevelScore(p) * FullnessFactor(p, q)
LevelScore(p) is a score assigned to the phrase by virtue of the type of phrase it is. For example, in our implementation we use a LevelScore of 16 for title phrases, 6 for headings and 1 for anchor text. This is based on the assumption that the title text is more useful than the heading text, which is more useful than an anchor text match in determining what the expert page is about.
FullnessFactor(p, q) is a measure of the number of terms in p covered by the terms in q. Let plen be the length of p. Let m be the number of terms in p which are not in q (i.e., surplus terms in the phrase). Then, FullnessFactor(p, q) is computed as follows:
If m <= 2, FullnessFactor(p, q) = 1
If m > 2, FullnessFactor(p, q) = 1 - (m - 2) / plen
Our goal is to prefer experts that match all of the query keywords over experts that match all but one of the keywords, and so on. Hence we rank experts first by S0. We break ties by S1 and further ties by S2. The score of each expert is converted to a scalar by the weighted summation of the three components:
Expert_Score = 232 * S0 + 216 * S1 + S2.
3.2 Computing the Target Score
We consider the top N experts by the ranking from the previous step (e.g., the top 200) and examine the pages they point to. These are called targets. It is from this set of targets that we select top ranked documents. For a target to be considered it must be pointed to by at least 2 experts on hosts that are mutually non-affiliated and are not affiliated to the target. For all targets that qualify we compute a target score reflecting both the number and relevance of the experts pointing to it and the relevance of the phrases qualifying the links.
The target score T is computed in three steps:
For every expert E that points to target T we draw a directed edge (E,T). Consider the following "qualification" relationship between key phrases and edges:
The title phrase qualifies all edges coming out of the expert
A heading qualifies all edges whose corresponding hyperlinks occur in the document after the given heading and before the next heading of equal or greater importance.
A hyperlink's anchor text qualifies the edge corresponding to the hyperlink.
For each query keyword w, let occ(w, T) be the number of distinct key phrases in E that contain w and qualify the edge (E,T). We define an "edge score" for the edge (E,T) represented by Edge_Score(E,T), which is computed thus:
If occ(w, T) is 0 for any query keyword then the Edge_Score(E,T) = 0.
Otherwise, Edge_Score(E,T) = Expert_Score(E) * Sum{query keywords w} occ(w, T)
We next check for affiliations between expert pages that point to the same target. If two affiliated experts have edges to the same target T, we then discard one of the two edges. Specifically, we discard the edge which has the lower Edge_Score of the two.
To compute the Target_Score of a target we sum the Edge_Scores of all edges incident on it.
The list of targets is ranked by Target_Score. Optionally, this list can be filtered by testing if the query keywords are present in the targets. Optionally, we can match the query keywords against each target to compute a Match_Score using content analysis, and combine the Target_Score with the Match_Score before ranking the targets.
4 Evaluation
In order to evaluate our prototype search engine, we conducted two user studies aiming to estimate the recall and precision. Both experiments also involved three other search engines, namely AltaVista, DirectHit and Google, for comparison and were done in August 1999. Note that the current rankings by these engines may differ.
4.1 Locating Specific Popular Targets
For the first experiment we asked seven volunteers to suggest the home pages of ten organizations of their choice (companies, universities, stores, etc.). Some of the queries are reproduced in the table below:
Alpha Phi Omega Best Buy Digital Disneyland
Dollar Bank Grouplens INRIA Keebler
Mountain View Public Library Macy's Minneapolis City Pages Moscow Aviation Institute
MENSA OCDE ONU Pittsburg Steelers
Pizza Hut Rice University SONY Safeway
Stanford Shopping Center Trek Bicycle USTA Vanguard Investments
The same query was sent to all four search engines. We assume that there is exactly one home page in each case. Every time the home page was found within the first ten results, its rank was recorded. Figure 2 summarizes the average recall for the ranks 1 to 10 for each of the four engines: our engine Hilltop (HT), Google (GG), AltaVista (AV), and DirectHit (DH). Average recall at rank k for this experiment is the probability of finding the desired home page within the first k results.
Figure 2. Average Recall vs. Rank
Our engine performed well on these queries. Thus, for about 87% of the queries, Hilltop returned the desired page as the first result, comparable with Google at 80% of the queries, while DirectHit and AltaVista succeeded at rank 1 only in 43% and 20% of the cases, respectively. As we look at more results, the average recall increases to 100% for Google, 97% for Hilltop, 83% for DirectHit, and 30% for AltaVista.
4.2 Gathering Relevant Pages
In order to estimate Hilltop's ability to generate a good first page of results for broad queries, we asked our volunteers to think of broad topics (i.e., topics for which it is likely that many good pages exist) and formulate queries. We collected 25 such queries, listed below:
Aerosmith Amsterdam backgrounds chess dictionary
fashion freeware FTP search Godzilla Grand Theft Auto
greeting cards Jennifer Love Hewitt Las Vegas Louvre Madonna
MEDLINE MIDI newspapers Paris people search
real audio software Starr report tennis UFO
We then used a script to submit each query to all four search engines and collect the top 10 results from each engine, recording for each result the URL, the rank, and the engine that found it. We needed to determine which of the results were relevant in an unbiased manner. For each query we generated the list of unique URLs in the union of the results from all engines. This list was then presented to a judge in a random order, without any information about the ranks of page or their originating engine. The judge rated each page for relevance to the given query on a binary scale (1 = "good page on the topic", 0 = "not relevant or not found"). Then, another script combined these ratings with the information about provenance and rank and computed the average precision at rank k (for k = 1, 5, and 10). The results are summarized in Figure 3.
Figure 3. Average Precision at Rank k
These results indicate that for broad subjects our engine returns a large percentage of highly relevant pages among the ten best ranked pages, comparable with Google and DirectHit, and better than AltaVista. At rank 1 both Hilltop and DirectHit have an average precision of 0.92. Average precision at 10 for Hilltop was 0.77, roughly equal to the best search engine, namely Google, with a precision of 0.79 at rank 10.
5 Conclusions
We described a new ranking algorithm for broad queries called Hilltop and the implementation of a search engine based on it. Given a broad query Hilltop generates a list of target pages which are likely to be very authoritative pages on the topic of the query. This is by virtue of the fact that they are highly valued by pages on the WWW which address the topic of the query. In computing the usefulness of a target page from the hyperlinks pointing to it, we only consider links originating from pages that seem to be experts. Experts in our definition are directories of links pointing to many non-affiliated sites. This is an indication that these pages were created for the purpose of directing users to resources, and hence we regard their opinion as valuable. Additionally, in computing the level of relevance, we require a match between the query and the text on the expert page which qualifies the hyperlink being considered. This ensures that hyperlinks being considered are on the query topic. For further accuracy, we require that at least 2 non-affiliated experts point to the returned page with relevant qualifying text describing their linkage. The result of the steps described above is to generate a listing of pages that are highly relevant to the user's query and of high quality.
Hilltop most resembles the connectivity techniques, PageRank and Topic Distillation. Unlike PageRank our technique is a dynamic one and considers connectivity in a graph specifically about the query topic. Hence, it can evaluate relevance of content from the point of view of the community of authors interested in the query topic. Unlike Topic Distillation we enumerate and consider all good experts on the subject and correspondingly all good target pages on the subject. In order to find the most relevant experts we use a custom keyword-based approach, focusing only on the text that best captures the domain of expertise (the document title, section headings and hyperlink anchor-text). Then, in following links, we boost the score of those targets whose qualifying text best matches the query. Thus, by combining content and connectivity analysis, we are both more comprehensive and more precise. An important property is that unlike Topic Distillation approaches, we can prove that if a page does not appear in our output it lacks the connectivity support to justify its inclusion. Thus we are less prone to omit good pages on the topic, which is a problem with Topic Distillation systems. Also, since we use an index optimized to finding experts, our implementation uses less data than Topic Distillation and is therefore faster.
The indexing of anchor-text was first suggested in WWW Worm [McBryan 94]. In some Topic Distillation systems such as Clever [Chakrabarti et al 1998] and in the Google search engine [Page et al 98] anchor-text is considered in evaluating a link's relevance. We generalize this to other forms of text that are seen to "qualify" a hyperlink at its source, and include headings and title-text as well. Also, unlike Topic Distillation systems, we evaluate experts on their content match to the user's query, rather than on their linkage to good target pages. This prevents the scores of "niche experts" (i.e., experts that point to new or relative poorly connected pages) from being driven to zero, as is often the case in Topic Distillation algorithms.
In a blind evaluation we found that Hilltop delivers a high level of relevance given broad queries, and performs comparably to the best of the commercial search engines tested.
