KR20060048778A - Phrase-based searching in an information retrieval system - Google Patents

Abstract

An information retrieval system uses phrases to index, retrieve, organize and describe documents. Phrases are identified that predict the presence of other phrases in documents. Documents are the indexed according to their included phrases. Related phrases and phrase extensions are also identified. Phrases in a query are identified and used to retrieve and rank documents. Phrases are also used to cluster documents in the search results, create document descriptions, and eliminate duplicate documents from the search results, and from the index.

Description

Phrase-based search in information retrieval system {PHRASE-BASED SEARCHING IN AN INFORMATION RETRIEVAL SYSTEM}

1 is a block diagram of a software architecture of one embodiment of the present invention.

2 illustrates a method of identifying phrases in a document.

3 shows a document having a phrase window and a secondary window;

4 illustrates a method of identifying relevant phrases.

5 illustrates a method of indexing a document for related phrases.

6 illustrates a method of retrieving a document based on a phrase.

7 illustrates the operation of a presentation system for providing search results.

8 a and b are diagrams showing a relationship between a document to be referred to and a referenced document.

Explanation of reference numerals

100 Search System 110 Indexing System

130 Presentation System 140 Front End Servers

150 Index 160 Stationery Data

170 Client 180 Internet

190 website

The present invention relates to an information retrieval system for indexing, searching, and classifying documents in large-scale materials such as the Internet.

Today's information retrieval system (commonly called a search engine) is an essential tool for finding large, diverse, and growing resources such as the Internet. In general, the search engine creates an index that associates documents (or “pages”) with individual words present in each document. In response to a query containing many query terms, the document is typically retrieved based on having some query terms that exist in the document. The retrieved documents are then ranked according to other statistical measures, such as the frequency of occurrences of query terms, host domains, link analysis, and the like. The retrieved documents are then presented to the user, typically without any additional grouping or imposing hierarchy in the ranked order. In some cases, the text of the selected portion of the document is provided so that the user can see the contents of the document.

Direct "boolean" matching of query terms has well-known limitations, in particular, documents that do not have a query term and have related words are not identified. For example, in a typical boolean system, the search for "Australian Shepherds" does not bring up documents for sheepdogs such as Border Collie that do not have exact queries. Rather, this system searches and ranks documents about Australia (not related to dogs) and generally about "shepherds".

The problem here is that conventional systems index documents based on individual terms rather than concepts. Concepts are often expressed in phrases such as "Australian Shepherd", "President of the United States", or "Sundance Film Festival". At most, some prior systems index documents for some very limited set of 'known' phrases that are typically selected by human operators. Indexing of phrases is typically avoided due to perceived computational memory requirements to identify all possible phrases, ie 3, 4, or 5 or more words. For example, assuming that any five words make up a phrase, and that large material has at least 200,000 unique terms, there are approximately 3.2 × 10 ²⁶ possible phrases, and there are far more systems than existing. It may be stored in memory or otherwise manipulated programmatically. Another problem is that the phrases are input and output from the dictionary as they are used more and more often than new individual words are generated. New phrases are always generated from materials such as science and technology, arts, world events, and law. Other phrases decrease in use over time.

Some existing information retrieval systems attempt to provide conceptual retrieval using co-occurrence patterns of individual words. In such a system, a search for a word such as "President" also searches for documents with other words that often appear with "President", such as "White" and "House". While this method can produce search results with conceptually related documents at the level of individual words, this typically does not capture the underlying relationships inherent between concurrent phrases.

Thus, an information retrieval system and method that can comprehensively identify phrases in large-scale materials, index documents according to phrases, search and rank documents according to those phrases, and provide additional clustering and descriptive information about the documents. It is necessary to provide.

Information retrieval systems and methods use phrases to index, search, rank, and describe documents in document collections. This system is used quite often in document collections and is suitable for identifying phrases that indicate "valid" or "good" phrases. In this way a plurality of phrases may be identified, for example four, five, or more terms. This solves the problem of identifying and indexing every possible phrase that results from every possible sequence of a given number of words.

The system is also suitable for identifying correlated phrases based on their ability to predict the presence of other phrases in a document. More specifically, a predictive measure is used that associates the common occurrence of the actual two phrases with the common appearance of the two phrases being predicted. The information gain as a ratio between the actual common prevalence and the expected common prevalence is one such expected measure. Two phrases are relevant if the expected measurement exceeds a predetermined threshold. In that case, the second phrase has a significant information gain over the first phrase. Semantically, related phrases are those commonly used to discuss or describe a given subject or concept, such as "President of the United States" and "White House." For a given phrase, related phrases may be arranged according to their relevance or importance based on each expected measurement.

The information retrieval system indexes documents in the document collection by valid or good phrases. For each phrase, a posting list identifies the document containing the phrase. In addition, for a given phrase, a second list, vector, or other structure is used to store data indicating which of the relevant phrases of the given phrase are also present in each document containing the given phrase. In this way, the system can easily identify which documents contain which phrases in response to a search query, as well as which documents also contain phrases related to the query phrases, and thus the subject or concept expressed in the query phrases. It is likely to be specific about.

The use of phrases and related phrases also allows the creation and use of clusters of related phrases that represent groupings of semantically significant phrases. The cluster is identified from the relevant phrase with a very high expected measure among all phrases in the cluster. Clusters can be used to organize search results, including removing documents from the search results as well as selecting which documents are to be included in the search results and their arrangement.

Information retrieval systems are also suitable for using phrases when searching for documents in response to a query. The query is processed to identify any phrases present in this query to retrieve the associated posting list for the query phrase and related phrase information. Also, in some cases, the user may enter incomplete phrases in a search query, such as "President of the." Such incomplete phrases may be identified and replaced by phrase extensions, such as "President of the United States." This helps to ensure that the user's most likely search is actually executed.

Relevant phrase information may also be used by the system to identify or select which documents are included in the search results. Relevant phrase information is represented by a given phrase and a given document, and the relevant phrase of this given phrase is present in a given document. Thus, for a query containing two query phrases, the posting list for the first query phrase is processed to identify the document containing the first query phrase, and then the relevant phrase information is also the second of these documents. It is processed to identify whether it contains a query phrase. This latter document is then included in the search results. This provides faster search time by eliminating the need for the system to individually process the posting list of the second query phrase. Of course, this method can be extended to many phrases in a query, resulting in significant computational time consumption.

The system may also be suitable for ranking documents in a set of search results using phrases and related phrase information. Relevant phrase information of a given phrase is preferably stored in a format such as a bit vector, which indicates the relative importance of each related phrase for a given phrase. For example, the relevant phrase bit vector has a bit for each relevant phrase of a given phrase, and the bits are arranged in accordance with the expected measurement (eg, information gain) for the relevant phrase. The most significant bit of the relevant phrase bit vector is associated with the relevant phrase with the highest expected measurement, and the least significant bit is associated with the relevant phrase with the lowest expected measurement. In this way, for a given document and a given phrase, relevant phrase information can be used to score the document. The value of the bit vector itself (as the value) can be used as the document score. In this way, documents containing higher-order related phrases of the query phrase are more likely to be related to the query in principle than having lower-order related phrases. Bit vector values can also be used as components in more complex scoring functions, and can additionally be weighted. The document can then be ranked according to the document score.

The phrase information may also be used in an information retrieval system to personalize a search for a user. The user is modeled, for example, as a collection of phrases derived from a document accessed by the user (eg, shown on screen, printed, stored, etc.). More specifically, when a document is accessed by a user, the relevant text present in this document is included in the user model or profile. Subsequently, during the search, the phrase in the user model is used to filter the phrase of the search query and weight the document score of the retrieved document.

The phrase information may also be used in an information retrieval system to generate a description of a document, such as a document included in a set of search results. Given a search query, the system identifies phrases that exist in the query and their phrase extensions, along with relevant phrases. For a given document, the sentence of each document has a count of how many query phrases, related phrases, and phrase extensions exist within the sentence. Sentences in the document may be ranked by these counts (individually or in combination), and some top ranking sentences (eg, five sentences) are selected to form the document description. The document description can then be provided to the user when the document is included in the search results, so that the user can better understand the document with respect to the query.

With the sophistication of this process of generating document descriptions, the system can provide a personalized description that reflects the user's interest. As before, the user model stores information that identifies relevant phrases of interest to the user. This user model intersects the list of phrases related to the query phrase to identify phrases common to both groups. The common set is then arranged according to the relevant phrase information. The resulting set of related phrases is used to rank sentences in the document according to the number of instances of these related phrases present in each document. Many sentences with the highest number of common related phrases are selected as the personalized document description.

The information retrieval system can also use the phrase information to identify and eliminate duplicate documents during indexing (crawl) of document collections or when processing search queries. For a given document, each sentence in the document has a count of how many related phrases are present in the sentence. Sentences in the document can be ranked by this count, and many top ranking sentences (eg, 5 sentences) are selected to form the document description. This description is then stored in association with the document, for example as a string or hash of a sentence. During indexing, newly crawled documents are processed in the same way to generate document descriptions. The new document description can be matched (eg hashed) against the previous document description, and if a match is found, the new document is a copy. Similarly, while preparing the results of a search query, documents in the search result set can be processed to remove copies.

The present invention has additional embodiments in system and software architectures, computer program deliverables and computer implemented methods, and computer generated user interfaces and presentations.

The foregoing is only a feature of some of the text-based information retrieval systems and methods. Those skilled in the information retrieval will appreciate that the universal flexibility of phrase information may be used and applied in a variety of ways in document analysis and processing in indexing, document annotation, search, ranking, and other fields.

The drawings herein show a preferred embodiment of the present invention for purposes of illustration only. Those skilled in the art will readily appreciate from the following discussion that modified embodiments of the structures and methods illustrated herein may be used without departing from the principles of the invention described herein.

I. System Overview

1, a software architecture of an embodiment of a search system 100 in accordance with an embodiment of the present invention is shown. In this embodiment, the system includes an indexing system 120, a presentation system 130, and a front end server 140.

Indexing system 110 is responsible for accessing various websites 190 and other document collections to identify phrases in documents and index documents according to those phrases. The front end server 140 receives a query from a user of the client 170 and provides the query to the search system 120. The search system 120 searches for documents related to the search query (search results), including identifying any phrases in the search query, and then ranks the documents in the search results using the presence of the phrases to affect the ranking ranking. In charge of work. The search system 120 provides the search results to the presentation system 130. Presentation system 130 modifies the search results, including eliminating nearly duplicate documents, generates topic descriptions of the documents, and sends the modified search results back to front end server 140 (results client 170). Provided). The system 100 further includes an index for storing indexing information related to the document, a phrase data storage 160 for storing the phrase, and related statistical information.

In the context of the present application, a "document" is understood to be any type of media that can be indexed and searched by the search engine, including web documents, images, multimedia files, text documents, PDF or other image format files, and the like. . A document has one or more pages, partitions, segments, or other components appropriate to its content and type. Equivalently, a document is called a document on the Internet and may be called a "page" as is commonly used. The use of the generic term "document" does not entail any limitation as to the scope of the invention. The search system 100 handles documents of large material such as the Internet and the World Wide Web, but may likewise be used for all limited collections, such as libraries or collections of private companies. In either context, it will be understood that documents are typically distributed via many different computer systems and sites. Without losing generality, documents are generally referred to collectively as materials or document collections, regardless of format or location (eg, a website or database). Each document has an associated identifier that uniquely identifies the document, and the identifier is preferably a URL, but other types of identifiers (eg, document numbers) may also be used. In this specification, it is assumed that a URL is used to identify a document.

II. Indexing system

In one embodiment, indexing system 110 provides three major functional operations: 1) identification of phrases and related phrases, 2) indexing of documents to phrases, and 3) generation and maintenance of phrase based taxonomy. Those skilled in the art will understand that the indexing system 110 implements other functions while supporting the conventional indexing function, and thus other operations are not described herein any further. Indexing system 110 acts on data store 160 and index 150 of stationery data. This data store is further described below.

1. Identify phrases

The phrase identification operation of indexing system 110 is useful for indexing and searching for documents, and identifies "good" and "bad" phrases within the collected document. In one aspect, good phrases are distinguished, such as phrases that tend to occur in a certain percentage of documents in a collection document, and / or as defined by letter tags or other morphology, format, or grammatical markers in such documents. It is shown as having a shaped appearance. Another feature of good phrases is that they can predict other good phrases and are not just word sequences that appear in the vocabulary list. For example, the phrase "President of the United States" is a phrase that predicts other phrases such as "George Bush" and "Bill Clinton". However, idioms and colloquial expressions such as "fell down the stairs" or "top of the morning" and "out of the blue" tend to appear with many different and irrelevant phrases, so other phrases are not predicted. Do not. Thus, the phrase identification step determines which phrase is a good phrase and which phrase is a bad phrase (ie, lacks predictive capability).

Referring to Figure 2, the phrase identification process includes the following functional steps.

200: Collect possible and good phrases, along with frequency of phrases and common appearance statistics.

202: Classify possible phrases as either good or bad phrases based on the frequency statistics.

204: Simplify the good phrase list based on the predicted measure derived from the common occurrence statistics.

Each of these steps will now be described in more detail.

In a first step 200 the indexing system 110 crawls the document sets of the collected document, while creating repeated partitions of the collected document for a period of time. One partition is processed per pass. The number of documents crawled for each pass can vary, with approximately 1,000,000 being preferred per partition. Before all documents are processed or meet different termination criteria, it is desirable that only documents that have not already been crawled be processed at each partition. In fact, crawling continues because new documents are continuously added to the collected documents. The next step is processed by the indexing system 110 for each document that was not crawled.

Traverse the words of the document to the phrase window length n, where n is the desired maximum phrase length. The length of the window is generally at least 2, preferably 4 or 5 phrases (words). Preferably, the phrase includes all words in the phrase window and includes things that can be characterized differently as stop words, such as "a", "the", and the like. The phrase window may be terminated by the end of a line, a paragraph return, a letter tag, or other indication of change within the context or format.

3 shows a portion of document 300 during traverse, showing a phrase window 302 starting at the word "stock" and extending to the right by five words. The first word of window 302 is candidate phrase i, and each sequence i + 1, i + 2, i + 3, i + 4, and i + 5 is likewise a candidate phrase. Thus, in this example, the candidate phrases are "stock", "stock dogs", "stock dogs for", "stock dogs for the", "stock dogs for the Basque", and "stock dogs for the Basque shepherds".

In each phrase window 302, each candidate phrase is checked in turn to determine if it already exists in the good phrase list 208 or the possible phrase list 206. If the candidate phrase is not present anywhere in the good phrase list 208 or the possible phrase list 206, the candidate is already determined to be "bad" and skipped.

If a candidate phrase exists as entry g _j in good phrase list 208, index 150 entry for phrase g _j is updated to include the document (eg, its URL or other document identifier), Indicates that this candidate phrase g _j is currently appearing in the document. The index 150 entry for phrase g _j (or phrase) is referred to as a posting list of phrase g _j . The posting list includes the document list d in which the phrase occurred (by its document identifier, eg document number or alternatively a URL).

Further, as will be described later, the common appearance matrix 212 is updated. In the first pass, the good and bad lists will be empty, so most phrases will be added to the possible phrase list 206.

If the candidate phrase is not present in the good phrase list 208, it is added to the possible phrase list 206, unless it is already present in the possible phrase list 206. Each entry p of possible phrase list 206 has three related counts:

P (p): number of documents in which possible phrases appeared

S (p): Number of all instances of possible phrases

M (p): Number of instances of interest in possible phrases

The possible phrases are of interest because they are distinguished from the adjacent context, either syntactically in the document or by format markers such as bold or underline, or as anchor texts in hyperlinks, or within question marks. These (and other) distinct appearances are represented by various HTML markup language tags and grammatical markers. If the phrase is present in the good phrase list 208, these statistics are maintained for the phrase.

In addition, in the various lists, a common appearance matrix 212 (G) for good phrases is maintained. The matrix G is in the mxm dimension, where m is the number of good phrases. Each entry G (j, k) of the matrix represents a pair of good phrases g _j , g _k . The common occurrence matrix 212 is logically (not necessarily morphologically) centered around the current word i, with each pair of good phrases g _j for the second window 304 extended with +/− h words. , g _k ) maintains three separate counts for. In one embodiment, as shown in FIG. 3, the second window 304 is 30 words. The common appearance matrix 212 thus maintains the next count.

R (j, k): Raw Co-occurrence count. The number of times the phrase g _j appears in the second window 304 with the phrase g _k .

D (j, k): Disjunctive Interesting count. The number of times either phrase g _j or phrase gk appears as distinguished text in the second window.

C (j, k): Conjunctive Interesting count: The number of times the phrase g _j and the phrase gk both appear as distinct text in the second window. The use of connection related counts is particularly beneficial to avoid environments where phrases (eg, copyright notices) frequently appear in sidebars, footers, or headers, and do not substantially predict other text.

Referring to the example of FIG. 3, it is assumed that the phrases "Australian Shepherd" and "Australian Shepard Club of America" as well as "stock dogs" are on the good phrase list 208. Both of these latter phrases now appear in the second window 304 around the phrase "stock dogs". However, the phrase "Australian Shepherd Club of America" appears as anchor text for hyperlinks (indicated by underline) to the website. Thus, the raw common appearance count for the pair {"stock dogs", "Australian Shepherd"} increases, and the raw appearance count and split interest count for {"stock dogs", "Australian Shepherd Club of America"} Both increase because they appear as distinct text.

The process of traversing each document to both the sequence window 302 and the second window 304 is repeated for each document in the partition.

Once the documents in the partition have been traversed, the next step in the indexing operation is to update 202 the good phrase list 208 from the possible phrase list 206. The possible phrases p on the possible phrase list 206 are referred to as a good phrase list 208 when the phrase is shown to be sufficiently used as a meaningful phrase, depending on the frequency of occurrence of the phrase and the number of documents in which the phrase appears. Is moved.

In one embodiment, this is tested as follows. The possible phrase p is removed from the possible phrase list 206 and placed on the good phrase list 208 in the following cases.

a) P (p)> 10 and S (p)> 20 (when the number of documents including the phrase p is 10 or more and the number of occurrences of the phrase p is 20 or more); or

b) M (p)> 5 (if the number of instances of interest in phrase (p) is 5 or greater)

These thresholds are scaled by the number of documents in the partition. For example, if 2,000,000 documents are crawled within a partition, the thresholds are approximately doubled. Of course, it will be apparent to those skilled in the art that the specific value of the threshold or logic for testing the threshold may vary depending on the embodiment.

If the phrase p is not suitable for the good phrase list 208, it is checked whether it corresponds to the bad phrase. The phrase p is a bad phrase in the following cases.

a) the number of documents containing the phrase, if P (p) <2; And

b) number of instances of interest in the phrase, where M (p) = 0

These conditions indicate that the phrases are both infrequent and never used again to indicate an important context, and that these thresholds can be scaled over the number of documents in the partition.

It should be noted that the good phrase list 208 naturally includes individual words as phrases, in addition to compound-word phrases, as described above. This is because in the phrase window 302 each first word is always a candidate phrase, and an appropriate instance count will accumulate. Thus, indexing system 110 can automatically index both individual words (ie, phrases with one word) and compound word phrases. In addition, the good phrase list 208 will be significantly less than the theoretical maximum based on all possible combinations of m phrases. In an exemplary embodiment, the good phrase list 208 may include approximately 6.5 × 10 ⁵ phrases. Since the system only needs to keep track of possible and good phrases, the list of bad phrases does not need to be stored.

By the final pass through the collection document, the list of possible phrases will be relatively short due to the expected distribution of the use of phrases in large data. Thus, when referred to by the tenth pass (i.e., 10,000,000 documents), the very first phrase appearing is then very difficult to be a good phrase at that time. It will be a new phrase that has just been used and thus becomes increasingly common during the next crawl. In this case, each count of it will increase and eventually meet the threshold to be a good phrase.

The third step of the indexing operation is to populate 204 the good phrase list 208 using predictive measures derived from the common appearance matrix 212. Without battery operation, the good phrase list 208 would contain many phrases that would not sufficiently predict the presence of other phrases during regular appearances in the lexical list, or would be longer phrase strings. By eliminating these weak good phrases, the good phrases are greatly enhanced. To identify good phrases, predictive measures are used that express an increase in the likelihood that one phrase appears in a given document in which another phrase exists. This is done in one embodiment as follows.

As mentioned above, the common appearance matrix 212 is an m × m matrix that stores data related to good phrases. Each column j of the matrix represents a good phrase g _j , and each row k represents a good phrase g _k . For each good phrase gj, the predicted value E (g _j ) is calculated. The predicted value E is the proportion of documents in the collection that are expected to contain the phrase g _j . For example, this is calculated as the ratio of the total number T of crawled collected documents to the number of documents containing the phrase g _j . That is, P (j) / T.

As described above, the number of documents including the phrase gj is updated each time the phrase gj appears in the document. The value for E (gj) may be updated each time the count for phrase gj increases, or during this third step.

Next, for each other good phrase (eg, rows of the matrix), determine whether the phrase g _j predicts the phrase g _k . The predictive measure for the phrase g _j is determined as follows.

i) Calculate the expected value E (gk). In the case where the phrase g _j and the phrase g _k are not related to each other, the expected common prevalence E (j, k) is E (g _j ) * E (g _k ).

ii) Calculate the real common prevalence A (j, k) of phrases (gj) and (gk). This is the raw common appearance count R (j, k) divided by the total number of documents T.

iii) If the real common prevalence A (j, k) exceeds the expected common prevalence E (j, k) by a threshold amount, the phrase g _j is said to predict the phrase g _k .

In one embodiment, the predictive measure is information gain. Thus, if the information gain I of the phrase g _{k in} the presence of the phrase g _j exceeds the threshold, the phrase g _j predicts another phrase g _k . In one embodiment, this is calculated as follows.

I (j, k) = A (j, k) / E (j, k)

In the following case, the good phrase g _j predicts the good phrase g _k .

I (j, k)> Information Gain Threshold

In one embodiment, the gain information threshold is 1.5 but preferably between 1.1 and 1.7. Raising the threshold above 1.0 reduces the likelihood that two other unrelated phrases appear more common than randomly predicted.

As mentioned, the calculation of the information gain is repeated in each row k of the matrix G for a given column j. Once one column is completed, if the information gain of any of the good phrases g _k does not exceed the information gain threshold, this means that the phrase g _j does not predict any other good phrases. In this case, the phrase g _j is removed from the good phrase list 208 and becomes essentially a bad phrase. It should be noted that the line j for the phrase g _j is not removed because this phrase itself may be predicted by other good phrases.

This step is performed after all columns of the common appearance matrix 212 are evaluated.

The final step in this process is to populate the good phrase list 208 to remove incomplete phrases. An incomplete phrase is a phrase that predicts only the expansion of the phrase and a phrase that begins at the far left of the phrase (ie, the beginning of the phrase). The phrase phrase expansion of phrase p is a super-sequence starting with phrase p. For example, the phrase "President of" predicts "President of the United States", "President of Mexico", "President of AT & T", and the like. These latter phrases all start with "President of" and are therefore an extension of the phrase "President of" and its super-sequence.

Thus, each phrase g _j remaining in the good phrase list 208 will predict several other phrases based on the information gain threshold described above. Now, for each phrase g _j , indexing system 110 performs string matching with each predicted phrase g _k . The string match checks whether each predicted phrase g _k is a phrase extension of the phrase g _j . If, for all predicted phrases (gk) is a phrase extension of the phrase (g _j), phrases (g _j) is incomplete, and removed from the good phrase list 208. Then, the incomplete phrase list 216 is added. Thus, if at least one stationary (g _k) a non-extension of the phrases (g _j) exist, phrases (g _j) is complete, maintaining the good phrase list 208. For example, "President of the United" is an incomplete phrase because the other phrase that it predicts is only "President of the United States", an extension of that phrase.

The incomplete phrase list 216 itself is very useful in actual search. When a search query is received, it may be compared against the incomplete phrase list 216. If a query (or a portion thereof) matches an entry in this list, the search system 120 may find the most similar phrase extension of the incomplete phrase (the phrase extension with the highest information gain given in the incomplete phrase). You can suggest phrase extensions to your users, or automatically search for phrase extensions. For example, if the search query is "President of the United", search system 120 may automatically suggest "President of the United States" as a search query to the user.

After the last step of the indexing process, the good phrase list 208 will contain a large number of good phrases that appear in the material. Each of these good phrases will predict at least one other phrase that is not a phrase extension. That is, each good phrase is used with sufficient frequency and independence to express meaningful concepts or ideas expressed in the data. Unlike current systems that use predetermined or hand selected phrases, the good phrase list reflects the actual phrases used in the material. Furthermore, since the crawling and indexing process is repeated every time a new document is added to a collected document, the indexing system 110 automatically searches for new phrases as they enter the vocabulary list.

2. Identify related phrases and related phrase clusters

Referring to FIG. 4, the relevant phrase identification process includes the following functional operations.

400: Identify relevant phrases with high information gain values.

402: Identifies a cluster of related phrases.

404: Store the cluster bit vector and cluster number.

Now, each of these operations will be described in detail.

First, recall a common appearance matrix 212 that includes good phrases g _j . Here, each good phrase g _j predicts at least one other good phrase g _{k with an} information gain higher than the information gain threshold. Thereafter, to identify 400 relevant phrases, the information gain for each good phrase pair g _j , g _k is compared with a relevant phrase threshold, eg, 100. That is, in the following case, the phrase g _j and the phrase g _k are related phrases.

I (g _j , g _k )> 100

This high threshold is used to identify common occurrences of good phrases that are statistically well above expectations. Statistically, this means that the phrases g _j and g _k are 100 times more common than the expected common occurrence. For example, if the phrase "Monica Lewinsky" is given within one document, and the phrase "Bill Clinton" is likely to appear more than 100 times in the same document, the phrase "Bill Clinton" may appear in any document selected arbitrarily. will be. Since the incidence is 100: 1, in other words, the accuracy of the prediction is 99.999%.

Thus, the fact that any entry g _j , g _k is less than the relevant phrase threshold means that the phrase g _j and the phrase g _k are not related and are therefore deleted. Now, any entries remaining in the common appearance matrix 212 are all related phrases.

Thereafter, the rows g _k of each column g _j of the common appearance matrix 212 are sorted by the information gain value I (g _j , g _k ), so that the relevant phrase g _k having the highest information gain is obtained. Is listed first. Thus, this sorting identifies other phrases most likely to be relevant in terms of information gain for a given phrase g _j .

The next step is to determine 402 which related phrases form a cluster of related phrases with each other. A cluster is a set of related phrases, where each phrase has a high information gain for at least one other phrase. In one embodiment, clusters are identified as follows.

Within each column g _j of the matrix, there will be one or more other phrases related to the phrase g _j . This set is the relevant phrase set Rj, where R = {g _k , g _l , ..., g _m }.

For each related phrase m in the related phrase set R _j , the indexing system 110 determines whether each of the other related phrases in R is also related to the phrase g _j . Thus, if I (g _k , g _l ) is nonzero, g _j , g _k , and g _l are part of the cluster. This cluster check is repeated for each pair (g _l , g _m ) in R.

For example, because the information gain of each of these phrases for "Bill Cliton" exceeds the Related Phrase threshold, the good phrase "Bill Cliton" is the phrase "President", "Monica Lewinsky". Assume that it is related to It is also assumed that the phrase "Monica Lewinsky" is related to the phrase "purse designer". These phrases then form the set R. To determine the cluster, the indexing system 110 evaluates the information gain for each of these phrases by determining the corresponding information gain of those phrases. Thus, indexing system 110 determines the information gain I for all pairs in R, such as information gain I (" President ", " Monica Lewinsky "), I (" President ", " purse designer ") and the like. In this example, "Bill Cliton", "President", and "Monica Lewinsky" form one cluster, "Bill Cliton", and "President" form a second cluster, and "Monica Lewinsky", and "purse designer" forms a third cluster, and "Monica Lewinsky", "Bill Cliton", and "purse designer" form a fourth cluster. This is because "Bill Clinton" does not predict "purse designer" with sufficient information gain, while "Monica Lewinsky" predicts both of these phrases.

In order to record the cluster information 404, each cluster is assigned a unique cluster number (cluster ID). This information is then recorded in association with each good phrase g _j .

In one embodiment, the cluster number is determined by a cluster bit vector, indicating orthogonal relationships between phrases. The cluster bit vector is a series of bits of length n that is the number of good phrases in the good phrase list. For a given good phrase g _j , the bit position corresponds to the classified related phrases R of g _j . The bit is set if the relevant phrase g _k in R belongs to the same cluster as the phrase g _j . More generally, this means that when there is an information gain in any one direction between g _j and g _k , the corresponding bit in the cluster bit vector is set.

And the cluster number is the value of the resulting bit string. This embodiment has the feature that related phrases having multiple or one-way information gains appear in the same cluster.

An example of a cluster bit vector using the above phrases is as follows.

Bill Clinton President Monica Lewinsky purse designer Cluster ID Bill Clinton One One One 0 14 President One One 0 0 12 Monica Lewinsky One 0 One One 11 purse designer 0 0 One One 3

And in summary, after this process, for each good phrase g _j , a set R of related phrases whose information gain I (g _j , g _k ) is sorted in order from the highest value to the lowest value will be identified. In addition, for each good phrase g _j , there will be a cluster bit vector whose value is the cluster number identifying the first cluster that contains the phrase g _j as a member, and g _j from among the relevant phrases in R. Orthogonality value (1 or 0 for each bit position) indicating the relevant phrase corresponding to the same cluster. Thus in the above example, "Bill Clinton", "President", and "Monica Lewinsky" belong to cluster 14, based on the bit value in the column of the phrase "Bill Cliton".

To store this information, two basic presentation methods can be used. First, as noted above, the information may be stored in a common appearance matrix (co-occurrence) 212, where:

entry G [row j, col. k] = (I (j, k), clusterNumber, ClusterBitVector)

to be.

Instead, without using the matrix representation method, all the information can be stored in the good phrase list 208, where each column represents good phrase g _j :

Phrase column _j = list [phrase g _k , (I (j, k), cluster number, cluster bit vector)]

This approach is useful for organizing clusters. First of all, this approach, rather than strictly-and often arbitrarily-defined taxonomy of topics and concepts, when indicated by relevant phrases, forms a complex graph of relevance, where some phrases are many different. Are related to phrases, and some phrases have a more limited scope, and the relevance may have interactivity (each phrase predicts another phrase) or one-way (some phrase predicts another phrase, but vice versa) It does not.) As a result, clusters may be characterized as "local" for each good phrase, and some clusters may overlap by having one or more common related phrases.

Ranking related phrases by information gain for a given good phrase g _j provides a taxonomy for naming the cluster of phrases: The cluster name is the name of the relevant phrase with the highest information gain in the cluster.

The above method provides a very robust method for identifying important phrases that appear in document collections, and this method is advantageous in that these related phrases are used together in the natural "cluster" used in practice. As a result, according to the data-driven clustering of related phrases, the choice of any "editor" for related terms and concepts, such as those commonly used in many systems, is a factor. Inherent deflections can be avoided.

3. Indexing Documents with Phrases and Related Phrases

Given the good phrase list 208 containing relevant phrases and information related to the cluster, the next functional operation of the indexing system 110 is to index the documents in the document collection for the good phrases and clusters, and 150) to store the updated information. This process is illustrated in Figure 5, where there are the following functional steps for indexing a document:

500: Posts a document to a posting list of good phrases found in the document.

502: Update the instance count and the associated phrase bit vector for the relevant phrase and the secondary related phrase.

504: Annotate documents with relevant textual information.

506: Reorder index entries according to posting list size.

These steps will now be described in more detail.

As before, traverse or crawl the document set: this can be the same document set or a different document set. For a given document d, in the same manner as described above, 500 document words per word are traversed from position i using a sequence window 302 of length n.

At a given phrase window 302, starting at position i, all good phrases within the window are identified. Each good phrase is denoted by g _i . Thus, g ¹ Is the first good phrase and g ² is the second good phrase.

Each good phrase g _i (for example, g ¹ Is "President", g ⁴ Posts a document identifier (eg, a URL) to the posting list for the good phrase g _i of index 150, for " President of ATT &quot;. By this update, it is identified that the good phrase g _i appears in this particular document.

In one embodiment, the posting list for the phrase g _i has the following logical form:

Phrases g _j : List: (Document d, [List: Relevant Phrases Count] [Related Phrases Information])

For each phrase g _j , there is a list of documents d in which the phrase appears. For each document, there is a list of counting the number of times the relevant phrases R of the phrase g _j appearing in the document d appear.

In one embodiment, the relevant phrase information may be an associated phrase bit vector. This bit vector is characterized as a "2-bit" vector in that there are two bit positions, g _k -1 and g _k -2 for each relevant phrase g _k . The first bit position stores a flag indicating whether or not the relevant phrase g _k is present in document d (ie, the count for g _k in document d is greater than zero). The second bit position stores a flag indicating whether or not the relevant phrase g _i of the phrase g _k exists in the document d. Related phrase g _i of the phrase g _j is a related phrase g _k in this case is referred to as the "secondary related phrases of g _j". The count and bit position correspond to the canonical order of phrases in R (sorted in order of decreasing information gain). This sorting order causes the relevant phrase g _k most predicted by g _j to be associated with the most significant bit of the relevant phrase bit vector, and the related phrase g _l least predicted by g _j is associated with the least significant bit. It works.

It is useful to note that for a given phrase g, the length of the relevant phrase bit vector, and the association of the relevant phrases for each bit of the vector, will be the same for all documents containing the phrase g. This embodiment has a feature that allows the system to easily compare the relevant phrase bit vectors for any (or all) documents containing the phrase g so as to see which document has the given relevant phrase. This has the advantage of facilitating the search process of identifying documents in response to a search query. Thus, a given document will appear in the posting list of many different phrases, and in each such posting list, the relevant phrase vector for that document will be specific to the phrase having the posting list. This aspect maintains the locality of the relevant phrase bit vector for individual phrases and documents.

Thus, the next step 502 traverses the second window 304 of the current index position, e.g. iK to i + K, in the document (+/- K term, eg 30 term as before). It involves doing. For each relevant phrase g _k of g _i appearing in the second window 304, the indexing system 110 increments the count of g _k for document d in the relevant phrase count. If g _i appears later in the document and the relevant phrase is found again in the second window behind it, the count is incremented again.

As mentioned, the corresponding first bit g _k -1 in the relevant phrase bit map is set based on the count, if the count for g _k is> 0, the bit is set to 1, or the count If is 0, it is set to 0.

Next, look up the relevant phrase g _k at index 150, identify whether document d is in the posting list of g _k , and then count the second relevant phrase (or bit) for any of its related phrases. ), The second bit g _k -2 is set. If any of these second related phrase counts / bits are set, this indicates that a second related phrase of g _j is also present in document d.

In the case where document d is fully processed in this manner, indexing system 110 will identify the following:

i) each good phrase g _j in document d;

ii) for each good phrase g _j , which of its related phrases g _k is present in document d;

iii) For each relevant phrase g _k present in document d, which of its related phrases g _i (second related phrase of g _j ) is also present in document d.

a) determine the topic for the document

Indexing a document by phrases and using clustering information provides another advantage of indexing system 110, which is the ability to determine the topic of a document based on relevant phrase information.

For a given good phrase g _j and given document d, assume that the posting list entry is:

g _j : document d: related phrase count: = {3,4,3,0,0,2,1,1,0}

             Related Phrases Bit Vectors: = {11 11 10 00 00 10 10 10 01}

Here, the relevant phrase bit vector is shown in bi-bit pairs.

From the relevant phrase bit vector, it is possible to determine the first and second topic of document d. The first topic is indicated by bit pair (1, 1), and the second topic is indicated by bit pair (1, 0). The relevant phrase bit pair (1, 1) indicates that both the relevant phrase g _k for the bit pair together with the second related phrase g _i are present in the document d. This can be interpreted by the author of document d using several related phrases g _j , g _k , and g _i together in writing the document. Bit pair (1,0) indicates that both g _j and g _k are present, but there is no longer a second relevant phrase other than g _k , so this is a less important topic.

b) Document annotation for improved ranking

Another aspect of indexing system 110 is the ability 504 to annotate each document d during the indexing process with information providing improved ranking in subsequent search processes. Annotating process 506 is as follows.

A given document d in a document collection can have any number of outlinks to other documents. Each outlink (hyperlink) includes an anchor text and a document identifier of the target document. For convenience of explanation, it is assumed that the document d currently being processed is URL0, and the target document which is an outlink of the document d is URL1. For later use in the ranking document that appears in the search results for each link in URL0 that points to some other URLi, the indexing system 110 adds an outlink score to the anchor phrase of that link to URL0, and URLi. Generate an inlink score for that anchor phrase for. In other words, each link in the document collection has a pair of scores, outlink and inlink. These scores are calculated as follows.

For a given document URL0, indexing system 110 identifies each outlink to another document URL1, where anchor text A is a phrase in good phrase list 208. 8A graphically illustrates this relationship, where the anchor text "A" in document URL0 is used for hyperlink 800.

In the posting list for phrase A, URL0 is posted as outlink of phrase A, and URL1 is posted as inlink of phrase A. In the case of URL0, the relevant phrase bit vector is completed as described above, identifying the relevant phrase of A and the second related phrase present in URL0. This relevant phrase bit vector is used as the outlink score for the link from URL0 to URL1 containing anchor phrase A.

Next, the inlink score is determined as follows. For each inlink to URL1 that includes anchor phrase A, indexing system 110 scans URL1 and determines whether phrase A appears in the body of URL1. If the phrase A not only indicates URL1 (via an outlink to URL0) but also appears in the content of URL1, it can be said that URL1 is consciously related to the concept represented by phrase A. 8B illustrates this case, where the phrase A appears both in the body of URL0 and URL1 (as anchor text). In this case, the relevant phrase bit vector of phrase A for URL1 is used as the inlink score for the link from URL0 to URL1 containing phrase A.

If anchor phrase A does not appear in the body of URL1 (as shown in FIG. 8A), another step is used to determine the inlink score. In this case, indexing system 110 generates an associated phrase beater vector of URL1 for phrase A (as if phrase A was in URL1) to indicate which related phrase of phrase A appears in URL1. This relevant phrase bit vector is used as the inlink score for the link from URL0 to URL1.

For example, suppose that the following statements first exist in URL0 and URL1.

 document Anchor stationery Related phrase bit vector Australian Shepherd Aussie blue merle red merle tricolor agility training URL0 One One 0 0 0 0 URL1 One 0 One One One 0

(The second and relevant phrase bits are not indicated in the table above and in the following table). Column URL0 is the outlink score from anchor text A, and URL1 column is the inlink score of the link. Here, URL0 includes "Australian Shep'hrd" which targets URL1. Of the five relevant phrases of "Australian Shephard", only one relevant phrase, "Aussie", appears in URL0. Intuitively, you can see that URL0 is very weakly related to Anstralian Shepherd. URL1, in contrast, contains "Australian Shephard" in the body of the document, as well as many related phrases such as "blue merle", "red merle", and "tricolor". Thus, since the anchor phrase "Australian Shepard" appears in both URL0 and URL1, the outlink score of URL0 and the inlink score of URL1 are as shown in the respective columns of the table.

In the second case described above, the anchor phrase A does not appear in URL1. In this case, indexing system 110 scans URL1, and any of the relevant phrases, ie, "Aussi", "blue merle", "red merle", "tricolor", and "agility training" are present in URL1. To determine whether or not, generate the relevant phrase bit vector, for example:

 document Anchor stationery Related phrase bit vector Australian Shepherd Aussie blue merle red merle tricolor agility training URL0 One One 0 0 0 0 URL1 0 0 One One One 0

Here, the table shows that URL1 does not include the anchor phrase "Australian Shepard", but includes related phrases "blue merle", "red merle", and "tricolor".

This approach has the advantage of completely preventing any manipulation of the web page (which is part of the document) to distort the results of the search. A search engine that uses a ranking algorithm that depends on the number of links pointing to a given document to rank that document is "exploded" by artificially generating a large number of pages with a given anchor text that points to the desired page. "Can be. As a result, when a search query using anchor text is entered, the desired page is typically found even if this page has little or no relation to the anchor text. Importing the relevant phrase vector from the target document URL1 into the relevant phrase bit vector of phrase A for document URL0 causes the search system to rely only on the relevance of phrase A at URL0 as indicating the importance or URL1 for the anchor text phrase. You can get rid of it.

In addition, based on the frequency appearing in the data, a phrase number is assigned to each phrase of the index 150. The more universal the phrase, the smaller the number of phrases in the index. The indexing system 110 then sorts 506 all posting lists in index 150 in decreasing order, depending on the number of documents listing the phrase numbers of each posting list, resulting in the most frequent phrases. Is posted first. The phrase number can then be used to look up a particular phrase.

III. Search system

Search system 120 operates to take a query, find documents related to the query, and provide a list of these documents (with a link to that document) in the set of search results. 6 illustrates the main functional operation of the search system 120.

600: Identify phrases for queries

602: retrieve documents related to the query phrase

604: Rank documents in search results according to the phrase

A detailed description of each of these steps follows.

1. Identify phrases in queries and query extensions

The first step 600 of the search system 120 is to identify phrases present in the query in order to search for indexing effectively. The following terms are used in this section:

q: query received by search system 120 as input.

Qp: Phrases that exist in a query.

Qr: Qp related phrases

Qe: Qp phrase extension

Q: merging Qp and Qr

The query q is received from the client 190 and has up to some maximum number of letters or words.

The search system 120 traverses the terms of the query q using a phrase window of size N (eg 5). The phrase window expands N terms to the right, starting with the first term in the query. This window is then shifted right M-N times, where M is the number of terms in the query.

In each window position, there may be N (or few) terms in the window. These terms are made up of possible query phrases. Possible phrases are found in the good phrase list 208 to determine whether there is good phrase. If a possible phrase exists in the good phrase list 208, the phrase number is called in place of the phrase. This possible phrase is the current candidate phrase.

After testing all possible phrases in each window to determine if they are good candidate phrases, the search system 120 will have a set of phrase numbers for the corresponding phrases in the query. Then, these phrase numbers are sorted (descending).

The search system 120 determines whether there are other candidate phrases within a certain numerical interval within the sorted list, that is, whether the difference between phrase numbers is within a threshold amount, for example 20000, starting with the highest phrase number as the primary candidate phrase. . If there is a candidate phrase, the leftmost phrase in the query is selected as a valid query phrase Qp. This query phrase and all its subphrases are removed from the candidate list and the list is rearranged to repeat the process. The result of this process is a set of valid query phrases Qp.

For example, suppose the search query is "Hillary Rodham Clinton Bill on the Senate Floor." The search system 120 will identify the following candidate phrases: "Hillary Rodham Clinton Bill on", "Hillary Rodham Clinton Bill", and "Hillary Rodham Clinton". The first two are discarded, and the last one is kept as a valid query phrase. Next, search system 120 identifies "Bill on the Senate Floor" and sub-phrases "Bill on the Senate", "Bill on the", "Bill on", and: Bill "to validate" Bill ". Finally, the search system 120 would have parsed "on the senate floor" to identify "Senate Floor" as a valid query phrase.

The search system 120 then adjusts the valid phrase Qp for capital letters. When analyzing a query, search system 120 identifies potential capital letters within each valid phrase. This can be done using a known capitalization table such as "united states" capitalized as "United States" or using a grammar-based capitalization algorithm. This produces a set of properly capitalized query phrases.

The search system 120 then passes the capitalized phrase twice to select and capitalize only the leftmost phrase in which both the phrase and its sub-phrase are present in the set. For example, a search for "president of the united states" may be capitalized as "President of the United States."

In a next stage, the search system 120 identifies the documents associated with the query phrase Q (602). The search system 120 then searches the posting lists of the query phrase Q and intersects these lists to determine which documents will appear in all (or some) of the posting list for the phrase. If the phrase Q in the query has a set of phrase extensions Qe (as described below), the search system 120 first merges the posting list of phrase extensions before doing the intersection with the posting list. The search system 120 identifies each phrase phrase by finding each query phrase Q in the incomplete phrase list 216 as described above.

The result of the intersection is a set of documents associated with the query. Indexing a document by phrases and related phrases, identifying phrase Q in the query, and then enlarging the query to include phrase expansion results in the selection of a document set more relevant to the query will result in documents containing query terms. It would be the same as a conventional Boolean algebra based search system that selects only.

In one embodiment, search system 120 uses an optimized mechanism to identify documents that respond to the query without having to intersect all posting lists of query phrase Q. As a result of the index 150 structure, for each phrase g _j , the relevant phrase g _k is known and identified in the relevant phrase bit vector of this g _k . Thus, this information can be used to simplify two or more interrogation phrases, or a cross-process with common phrases. In this case, the relevant phrase bit vector can be accessed directly and then used to retrieve the corresponding document. This process is described more fully as follows.

Given any two query phrases Q1 and Q2, there are three possible case relationships.

1) Q2 is the relevant phrase of Q1.

2) Q2 is not a related phrase of Q1 and their respective related phrases Qr1 and Qr2 do not intersect (ie there is no common related phrase).

3) Q2 is not a related phrase of Q1, but their respective related phrases Qr1 and Qr2 intersect.

For each pair of query phrases, search system 120 finds the relevant phrase bit vector of query phrase Qp to determine if it is appropriate.

The search system 120 retrieves the posting list for the query phrase Q1 containing the documents containing Q1 and the relevant phrase bit vector for each of these documents. The relevant phrase bit vector of Q1 will indicate whether the phrase Q2 (and each remaining query phrase, if any) is a relevant phrase of Q1 and is present in the document.

When the first case is applied to Q2, the search system 120 scans the relevant phrase bit vector for each document d in the posting list of Q1 to determine whether the bit for Q2 is set. If this bit is not set for each document d in Q1's posting list, it means that Q2 does not appear in that document. As a result, this document can be immediately erased from further consideration. The remaining document can then be scored. This also means that the search system 120 does not need to process which document is present in the posting list of Q2, thus saving computation time.

Applying the second case to Q2, the two phrases are not related to each other. For example, the query "cheap bolt action rifle" has two phrases "cheap" and "bolt action rifle". These phrases are not related to each other and their respective phrases do not overlap, i.e. "cheap" means the relevant phrases "low cost", "inexpensive", "discount", "bargain basement", and "lousy". In contrast, since the "bolt action rifle" has the relevant phrases "gun", "22 caliber", "magazine fed", and "Armalite AR-30M", the list is not crossed. In this case, the search system 120 performs normal intersection of the posting lists of Q1 and Q2 to obtain a document for scoring.

Applying the third case, here the two phrases Q1 and Q2 are not relevant but have at least one related phrase in common. For example, the phrases "bolt action rifle" and "22" may both have "gun" as related phrases. In this case, search system 120 retrieves the posting lists of both phrases Q1 and Q2 and intersects this list to produce a list of documents that contain both phrases.

The search system 120 can then quickly score each of the generated documents. First, the search system 120 determines a score adjustment value for each document. The score adjustment value is a mask formed of bits at positions corresponding to query phrases Q1 and Q2 in the relevant phrase bit vector of the document. For example, Q1 and Q2 correspond to the third and sixth bi-bit positions in the relevant phrase bit vector of document d, and the bit value of the third position is (1, 1) and the sixth pair. If the bit value of is (1, 0), the score adjustment value is a bit mask "00 00 11 00 00 10". Then, after masking the relevant phrase bit vector of the document using the score adjustment value, the modified phrase bit vector is passed to a ranking function (described below) to be used to calculate the body score of the document.

2. Ranking (Ranking)

a) Ranking Documents Based on Contained Phrases

The search system 120 provides a ranking stage 604 in which the documents in the search results are ranked using the phrase information in the relevant phrase bit vector of each document, and the cluster bit vector of the query phrase. This approach ranks documents according to phrases contained within them, or colloquially "body hits."

As mentioned above, for any given phrase g _j , each document d in g _j 's posting list is associated with the relevant phrase bit vector identifying that the relevant phrase g _k and the secondary related phrase g _l are present in document d. Have If more relevant phrases and secondary related phrases exist in a given document, more bits will be set in the relevant phrase bit vector of the document for the given phrase.

Thus, in one embodiment, search system 120 sorts the documents in the search results according to the value of the relevant phrase bit vector. The document containing the phrase most relevant to the query phrase Q will have the highest value associated phrase bit vector, and these documents will be the highest ranking document in the search results.

This approach is desirable because, semantically, these documents are most principally related to the query phrase. This approach provides a highly relevant document even if the document does not contain a high frequency of input query term q because the relevant textual information is used to identify the relevant document. Documents with a low frequency of input query terms may still have a large number of phrases for query terms and phrases, so that they are more relevant than documents with no relevant phrases but high frequency query terms and phrases.

In a second embodiment, the search system 120 scores each document in the result set according to the relevant phrase of the query phrase Q that the document contains. This is done as follows.

Given each query phrase Q, there will be some number N of phrases Qr related to the query phrase, identified during the phrase identification process. As mentioned above, the relevant query phrase Qr is arranged according to their information gain from the query phrase Q. Then, these relevant phrases start with N points of the first relevant phrase Qr1 (i.e., the relevant phrase Qr having the highest information gain from Q), followed by N-1 points of the next relevant phrase Qr2, followed by N of Qr3. Points, such as -2 points, are allocated and one point is allocated to the last relevant phrase QrN.

Each document in the search results is then scored by determining if there is a related phrase Qr of the query phrase Q, and assigning the document a point assigned to each of these related phrases Qr. Thereafter, documents are sorted from the highest score to the lowest score.

More precisely, search system 120 can extract certain documents from the result set. In some cases, the documents may relate to a number of different topics, which is particularly the case for long documents. In most cases, users prefer documents that are emphasized about a single topic that is represented in a query over documents that relate to many different topics.

To extract these latter types of documents, search system 120 uses cluster information in the cluster bit vector of the query phrase to remove any document that is greater than the threshold number of clusters in the document. For example, the search system 120 can remove any document containing more than two clusters. This cluster threshold may be predetermined or set by the user as a search parameter.

b) Ranking Documents Based on Anchor Phrases

In one embodiment, in addition to ranking the documents in the search results based on the body hits of the query phrase, the search system 120 is based on the appearance of the query phrase Q and related query phrase Qr in anchors for other documents. It may also rank documents. In one embodiment, search system 1230 calculates a score for each document that is a function of two scores, a body hit score and an anchor hit score (eg, a linear combination).

For example, the document score of a given document can be calculated as follows.

Score = .30 * (body hit score) + .70 * (anchor hit score)

Weights of .30 and .70 can be adjusted as desired. The body hit score of the document is, as described above, the numerical value of the relevant phrase bit vector that is rated highest for the document given the query phrase Qp. Optionally, this value may be directly obtained by searching the document from the posting list of query phrase Q by finding each query phrase Q in index 150 in search system 120 and then accessing the relevant phrase bit vector. .

The anchor hit score of document d is a function of the relevant phrase bit vector of query phrase Q, where Q is the anchor term in the document that references document d. When indexing systems 110 index documents in a document collection, indexing system 110 maintains a list of documents for each phrase in which the phrase is anchor text in the outlink, and also maintains a list of inlinks (and associated anchor text) from each other document. Maintain per document. An inlink in a document is a reference (hyperlink) to a given document from another document (reference documents).

Then, in order to determine the anchor hit score for a given document d, the search system 120 then checks the set of documents R (i = 1 to the number of reference documents) to reference listed in the index by their anchor phrase Q. Iterate over and add up the following products:

Ri.Q. related phrase bit vector * D.Q related phrase bit vector

The value of the product here is a score of how topical the anchor phrase Q is in document D. This score is referred to herein as an "inbound score component." This product is efficiently imposed by the relevant bit vector of the anchor phrase in document R to refer to the relevant bit vector of the current document D. If the reference document R itself is related to the query phrase Q (and therefore has a higher phrase phrase vector evaluated higher), then the importance of the current document D score increases. Thereafter, as described above, the body score and the anchor score are combined to generate a document score.

Next, for each reference document R, the relevant phrase bit vector for each anchor phrase Q is obtained. This is a measure of how topical the anchor phrase Q is in document R. This value is referred to herein as the outbound score component.

Then, from the index 150, all (document to be referred to, referenced document) pairs are extracted for the anchor phrase Q. These pairs are then sorted by their association (outbound score component, inbound score component) values. In accordance with this implementation, either of these components may be the primary sort key and the other may be the secondary sort key. The sorting result is then displayed to the user. Sorting the documents by the outbound score component causes the documents with many related phrases to be ranked highest for the query as anchor hits, and display these documents as "expert" documents. Sorting by inbound document scores results in the highest ranking of documents frequently referenced by anchor terms.

3. Based Personalization of search phrases (Phrase Based Personalization of Search)

Another form of search system 120 is the ability to personalize 606 or customize the ranking of search results according to a model of particular interest to the user. As such, documents that are more likely to be relevant to the user's interest are ranked higher in the search results. Personalization of search results is as follows.

As a preliminary problem, it is useful to define a user's interest (eg, user model) within terms of the query and document that can be expressed in phrases. For the entered search query, the query is represented by the query phrase Q, the related phrase of Qr, and the phrase extension Qe of the query phrase Qp. As such, this set of terms and phrases express the meaning of the query. Next, the meaning of the document is represented by a phrase associated with the page. As noted above, given a query and a document, the relevant phrase of the document is determined from the body score (related bit vector) for all the phrases indexed in the document. Finally, the user can be represented by merging the set of documents with the set of queries in terms of the phrases representing each of these elements. Specific documents included in the set representing the user may be derived from any document selected by the user in the normal browsing (document access on the Internet) of previous search results or data, using a client-side tool that monitors the user's behavior and destination. Can be determined.

The process of building and using a personalized ranking user model is as follows.

First, for a given user, a list of the last K queries and P documents accessed is maintained, where K and P are each about 250 preferred. This list can be maintained in the user account database, where the user can be recognized by login or by a browser cookie. For a given user, the list will be empty at the first time the user makes a query.

Next, the query q is received from the user. As mentioned above, the relevant phrase Qr of q is retrieved according to the phrase extension. This forms the query model.

In the first pass (eg, when there is no query information of the user), the search system 120 operates to simply retrieve the relevant document in the search results for the user's query, without further customized ranking.

The client-side browser tool monitors the documents in the search results that the user accesses, for example by clicking on a document link in the search results. These accessed documents, which are the basis for selecting a phrase, will be part of the user model. For each such accessed document, search system 120 retrieves the document model for the document, which is a list of phrases related to the document. Each phrase associated with the accessed document is added to the user model.

Next, given the phrases associated with the accessed document, the clusters associated with these phrases may be determined from the cluster bit vector for each phrase. In each cluster, each phrase that is a member of the cluster is determined by looking for the phrase in the cluster bit vector representation, or in the associated phrase table containing the cluster number, as described above. This cluster number is added to the user model. Also, in each cluster, each time a phrase in the cluster is added to the user model, the count is maintained and incremented. This counter can be used as a weight as described below. Thus, the user model is constructed from phrases contained in clusters in documents that the user has accessed and has expressed interest.

The same general approach can be more precisely focused to obtain phrase information indicated by the user at a higher level of interest than simply accessing the document (the user will simply determine whether the document is really relevant). For example, collection of phrases into a user model can be a document that a user prints, saves, registers as a favorite or link, emails another user, or opens a browser window for a long time (eg, 10 minutes). It may be limited to. These and other actions represent a high level of interest in the document.

If another query is received from the user, the relevant query phrase Qr is retrieved. The relevant query phrase Qr is intersected with the phrases listed in the user model to determine which phrases exist in both the query and the user model. The mask bit vector is initialized for the relevant phrase of the query Qr. This bit vector is a 2-bit vector as described above. For each relevant phrase Qr of the query also present in the user model, both bits for the related phrase are set in the mask bit vector. Thus, the mask bit vector represents the relevant phrase that exists in both the query and the user model.

The mask bit vector is used to AND the associated phrase bit vector and the mask bit vector to mask the relevant phrase bit vector for each document in the current set of search results. This has the effect of adjusting the body score and anchor hit score by the mask bit vector. The document is scored and presented to the user for body score and anchor score as before. This access necessitates that the document include query phrases included in the user model in a highly ranked order.

As another embodiment that does not impose the above strict constraints, a mask bit vector can be computed in an array so that each bit is used to weight the cluster count for the relevant phrase of the user model. Thus, each cluster counter is multiplied by zero or one, effectively zeroing or maintaining the count. Next, if a weight is also used to multiply the relevant phrase for each document to be scored, this count itself is used as the weight. This approach has the advantage that documents that do not have a query phrase as a related phrase can still be properly scored.

Finally, the user model can be limited to the current session, where one session is the interval of active periods in the search, after which the user model is dumped. In addition, the user model for a given user can be maintained and then reduced or aged.

Ⅳ. Result presentation

The presentation system 130 receives the scored and sorted search results from the search system 120 and further performs organization, annotating, and clustering operations before presenting the results to the user. This work helps the user understand the content of the search results, eliminates duplication, and provides a more representative sampling of the search results. 7 illustrates the main functional tasks of the presentation system 130.

700: Clustering Documents by Topic Cluster

702: Generate document description

704: Remove duplicate documents

Each of these tasks takes a search result 701 as input and outputs a modified search result 703. As shown in FIG. 7, the order of these tasks is independent and can be changed if desired in the embodiment so that the input can be pipelined instead of being done in parallel as shown.

1. Create a dynamic taxonomy for presentations

For that query, it is common to return hundreds or even thousands of documents that satisfy the query. In many cases, specific documents with different content are sufficiently related to form meaningful groups of related documents, essentially clusters. However, most users do not review more than the first 30-40 documents in the search results. Thus, for example, if the first 100 documents appear from three clusters, but the next 100 documents correspond to four additional clusters and there is no further adjustment, the user typically does not review those later documents. Do not. In fact, such later documents may be very relevant to the user's query because they represent various different topics related to the query. Thus, by providing the user with a sample of the document from each cluster, it is desired to give the user a wide selection of different documents from the search results. Presentation system 130 does this as follows.

As another aspect of system 100, presentation system 130 uses an associated phrase bit vector for each document d in the search results. More specifically, for each document d in each posting phrase of each query phrase Q and Q, the relevant phrase bit vector indicates which relevant phrase Qr is present in the document. For the document set of the search result, for each relevant phrase Qr, a count is determined by summing the bit values of the bit positions corresponding to Qr to indicate how many documents contain the relevant phrase Qr. When summed and sorted for search results, the most frequently appearing related phrase Qr is indicated, each of which will be a cluster of documents. The most often appearing related phrase is the first cluster, which takes its related phrase Qr as its name, and the other top three to top five clusters. Thus, each parent cluster is identified with the phrase Qr as the title or name of the cluster.

Documents from each cluster are presented to the user in several ways. In one application, a fixed number of documents from each cluster, such as the top 10 documents in each cluster, is presented. In other applications, a proportional number of documents from each cluster may be represented. Therefore, if there are 50 documents in the search results, there are 50 documents in cluster 1, 30 in cluster 2, 10 in cluster 3, 7 in cluster 4, and 3 in cluster 5. The documents are selected as follows: ten documents from cluster 1, seven documents from cluster 2, two documents from cluster 3, and one document from cluster 4. The documents can then be presented to the user and grouped according to the appropriate cluster name as the title.

For example, if the search query is called "blue merle agility training", the search system 120 searches 100 documents. The search system 120 will identify "blue merle" and "agility training" as query phrases in advance. The relevant phrases of these query phrases are as follows:

"blue merle" :: "Australian Shepherd", "red merle", "tricolor", "aussie";

"agility training" :: "weave poles", "teeter", "tunnel", "obstacle", "border collie".

The presentation system 130 then determines, for each of the relevant phrases of each query phrase, a count of the number of documents containing such phrases. For example, assume that the phrase "weave poles" appears in 75 documents out of 100 documents, "teeter" appears in 60 documents, and "red merle" appears in 50 documents. At that time, the first cluster is referred to as "weave poles", the number of documents selected from that cluster is represented, the second cluster is referred to as "teeter", and the selected number is also represented. For fixed presentations, ten documents can be selected from each cluster. The proportional presentation will use the proportional number of documents from each cluster relative to the total number of documents.

2. Topic-related document description

A second function of the presentation system 130 is the generation of document descriptions that can be inserted into the search results presentation for each document (702). This description is based on the relevant text that appears in each document, thus helping the user to understand what the document is about in a way that is contextually relevant to the search. The document description can be general or personal to the user.

a) General topic document description

As mentioned above, given a query, the search system 120 determines the relevant query phrase Qr and the phrase extension of the query phrase and identifies the relevant document for the query. Presentation system 130 accesses each document in the search results and performs the following operations.

First, the presentation system 130 ranks the sentences of the document by the number of instances of the query phrase Q, the associated query phrase Qr, and the phrase extension Qp to maintain three aspects of count for each sentence of the document. .

The sentence is then sorted by such a count, the first sort key is the count of the query phrase Q, the second sort key is the count of the relevant query phrase Qr, and the last sort key is the count of the phrase extension Qp.

Finally, the top N (eg 5) sentences after sorting are used as the description of the document. This set of sentences may be included in the presentation of the document in the formatted search modified search results 703. This process is repeated for several documents in the search results, and can be done on demand whenever the user requests the next page of results.

b) personalized topic-based document description;

In embodiments where the specification of search results is provided, the document description may also be personalized to reflect user interest as represented in the user model. Presentation system 130 does this as follows.

First, as described above, the presentation system 130 determines the relevant phrase corresponding to the user by listing the query related phrase Qr with the user model (list the phrase in the document accessed by the user).

The presentation system 130 then stably sorts the set of user related phrases Ur according to the value of the bit vector itself, adds the sorted list to the list of query related phrases Qr, and removes any duplicate phrases. . A stable sort maintains the existing order of equally ranked text. This results in a set of related phrases related to the query or user and is called the set Qu.

Presentation system 130 uses an ordered list of phrases as a base for ranking the sentences in each document in the search results in a manner similar to the general document description process as described above. Thus, for the document, the presentation system 130 ranks the sentences of the document by the number of instances of each of the user-related phrase and the query-related phrase (Qu), sorts the ranked sentences according to the query count, and finally Each such phrase is sorted based on the number of phrase extensions. Previously, the sort keys were in order of query phrase Q, related query phrase Qr, and phrase extension Qp, but here the sort key is in order of the lowest ranked user related phrase Ur from the highest ranked user related phrase Ur.

This process is also repeated for documents in the search results (on request or in advance). In each such document, the resulting document description includes N high rank sentences from the document. Here, these sentences are those having the highest number of user-related phrases Ur, and thus represent important sentences in the document that represent concepts and topics that are most relevant to the user (at least according to the information captured in the user model).

3. Duplicate document detection and removal

In large data such as the Internet, there are complex examples of the same document, and it is very common for some parts of the document to exist in several different locations. For example, the news article produced by a news station such as "Associated Press" is repeated on several websites of individual newspapers. Including all of these duplicate documents in response to a search query burdens the user due to the duplicate documents and is not useful for responding to the query. Thus, the presentation system 130 provides additional capabilities 704 for identifying documents that are likely to overlap or nearly overlap each other, and include only one of these in the search results. Therefore, the user does not have to spend time receiving a more diversified and robust set of results and reviewing documents that overlap each other. The presentation system 130 provides the following functions.

Presentation system 130 processes each document in search result set 701. In each document d, the presentation system 130 first determines a list of relevant phrases R associated with the document. For each of these related phrases, presentation system 130 ranks the sentences of the document according to the frequency of appearance of each phrase, and selects the top N (eg, 5-10) sentences. This set of sentences is stored in association with the document. One way to do this is to concatenate the selected sentences and then use a hash table to store the document identifier.

The presentation system 130 then compares the selected sentences of each document d with the selected sentences of the other documents in the search results 701, and if the selected sentences match (within tolerance), the documents are duplicated. Are estimated and one of them is removed from the search results. For example, the presentation system 130 can hash linked statements, and if the hash table already has an entry of hash values, this indicates that the current document and the currently hashed document are duplicates. The presentation system 130 can update the table with one document ID in the document. Preferably, presentation system 130 maintains a high page rank or other query independent measure of document importance. The presentation system 130 also modifies the index 150 to remove duplicate documents so that they do not appear in future search results for any query.

The same deduplication process can be applied directly by the indexing system 110. If the document is crawled, the document description process described above is performed to obtain a selected sentence and a hash of the sentence. When the hash table is populated, the new crawled document is considered a duplicate of the old document. Then, again, indexing system 110 may maintain a document with a high rank or other query independent measure.

The invention has been described in particular detail for one possible embodiment. Those skilled in the art will appreciate that the present invention may be practiced in other embodiments. First of all, a specific name of a component, capitalization of terms, attributes, data structures, or other programming or structural aspects is not mandatory or important, and the mechanisms or features thereof for carrying out the invention may be defined by different names, formats, Or protocol. In addition, the system may be implemented via a combination of hardware and software, or with only hardware elements, as described. In addition, the specific division of action between the various system elements described herein is merely illustrative and not mandatory, and the functions performed by a single system element may be performed by the complex element, and may be performed by the complex element. The function may be performed by a single element.

Some of the foregoing descriptions illustrate features of the present invention in terms of algorithms and symbolic representations of operations on information. These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. Such operations, described functionally or logically, are understood to be performed by a computer program. In addition, it has sometimes proved convenient to refer to this configuration of operations as a module or as a functional name without loss of generality.

As is apparent from the foregoing description, unless otherwise specified, throughout the description, the terms "processing", "calculation", "calculation", "determination", "marking", and the like refer to computer system memory or registers or other information storage. , Computer system for manipulating and transmitting data represented as physical (electronic) quantities within a transmission or display device, or similar operations or processes of electronic computing devices.

Certain aspects of the present invention include process steps or instructions described herein in the form of algorithms. The process steps and instructions of the present invention may be implemented in software, firmware, or hardware and, if implemented in software, are downloaded and operated to stay on different platforms used by the real-time network operating system.

The invention also relates to an apparatus for performing an operation. Such apparatus may be specially configured for the required purpose or may comprise a general purpose computer which is reconfigured or selectively activated by a computer program stored in a computer readable medium accessible by the computer. Such computer programs include floppy disks, optical disks, CD-ROMs, magnetic-optical disks, read only memory (ROM), random access memory (RAM), EPROM, EEPROM, magnetic or optical cards, and special purpose integrated circuits (ASICs). Computer readable storage media such as, but not limited to, any type of disk, or any type of media suitable for storing electronic instructions and each connected to a computer system bus. In addition, a computer referred to within the specification may be an architecture that includes a single processor or employs a multiple processor design for increased computing power.

The algorithms and operations described herein are not inherently related to any particular computer or other apparatus. In addition, various general purpose systems may be used with the teachings of the teachings, or it may prove convenient to construct more specific apparatus for performing the required method steps. The required structure of the various systems will be apparent to those skilled in the art with equivalent variations. In addition, the present invention is not described with reference to any particular programming language. Various programming languages may be used to practice the teachings of the invention described in this specification, and any reference to a particular language is provided to disclose the functionality and best mode of the invention.

The present invention is well suited for a variety of computer network systems spanning numerous topologies. In this field, configuration and management of large networks includes computers and storage devices that are communicatively connected with other computers, and storage devices on the network, such as the Internet.

Finally, the language used herein is selected essentially for readability and teaching purposes, and is not selected to precisely describe or limit the subject matter of the invention. Accordingly, the disclosure of the present invention is intended to illustrate without limiting the scope of the invention described in the appended claims.

The present invention provides an information retrieval system capable of comprehensively identifying phrases in large-scale materials, indexing documents according to the phrases, searching and ranking documents according to these phrases, and providing additional clustering and descriptive information about the documents; A method is provided.

Claims (14)

A method of selecting a document from a document collection in response to a query. Receiving a query; Identifying a plurality of phrases in the query, the at least one phrase being a plurality of word phrases; Identifying at least one phrase extension of the identified phrases; Selecting a document from the document collection containing at least one phrase from a set comprising a phrase in the query and phrase extension Document selection method comprising a. The method of claim 1, Selecting the document Combining a posting list of identified phrases with a posting list of phrase extensions of the identified phrases to form a combined posting list; Selecting a document that appears in the combined posting list and in the posted list of other identified phrases; Document selection method comprising a. A method of selecting a document from a document collection in response to a query. Receiving a query; Identifying an incomplete phrase in the query; Replacing the incomplete phrase with a phrase extension; Selecting a document from the document collection containing the phrase extension Document selection method comprising a. The method of claim 3, wherein Identifying the incomplete phrase and replacing the incomplete phrase Identifying candidate phrases in the query; Matching incomplete phrases in the candidate phrase and incomplete phrase list; Replacing the candidate phrase with a phrase extension associated with the incomplete phrase Document selection method comprising a. The method of claim 3, wherein The phrase expansion of an incomplete phrase includes a super-sequence of the incomplete phrase starting with the incomplete phrase. A method of selecting a document from a document collection in response to a query. Receiving a query comprising a first phrase and a second phrase; Retrieving a posting list of the document containing the first phrase; For each document in the posting list, accessing a list representing relevant phrases of the first phrase present in the document and responsive to the list of related phrases indicating that the second phrase exists in the document. Selecting the document to be included in the results of the query without retrieving a posting list of documents containing Document selection method comprising a. The method of claim 6, In response to the list of relevant phrases indicating that the second phrase is not present in the document, excluding the document from the results of the query without retrieving a posting list of the document containing the second phrase. How to choose a document. The method of claim 6, In response to a list of related phrases indicating that the second phrase is not a related phrase of the first phrase, intersecting a posting list of the document for the first phrase with a posting list of the document for the second phrase; Selecting the document containing both the first phrase and the second phrase. The method of claim 6, Storing a list of relevant phrases for the first phrase for the document as a bit vector, wherein bits of the bit vector are set for each relevant phrase of the first phrase present in the document, And a bit is not set for each relevant phrase of the first phrase that does not exist in the document, and wherein the bit vector has an arithmetic value. A method of ranking documents included in a search result in response to a query including at least one query phrase, For each document in the search results, accessing an associated phrase bit vector for the query phrase, each bit of the bit vector indicating the presence or absence of an associated phrase of the query phrase; Sorting the documents in the search results by the value of the relevant phrase bit vector such that the document having the highest value of the relevant phrase bit vector is ranked highest in the search result. Ranking method of the document comprising a. The method of claim 10, Each bit of the relevant phrase bit vector is associated with a related phrase of the query phrase, The bit of the document is arranged such that the most significant bit of the bit vector is associated with a relevant phrase having the largest information gain for the query phrase and the least significant bit is associated with a relevant phrase having the least information gain for the query phrase. Ranking method. A method of ranking documents included in a search result in response to a query including at least one query phrase, For each document in the search results, Accessing an associated phrase bit vector for the phrase of the query, each bit of the bit vector indicating the presence or absence of an associated phrase of the query phrase; For each bit indicating the presence of a related phrase in the query phrase, adding a predetermined number of points associated with the bit to a score for the document; Sorting documents in the search results by the document scores Ranking method of the document comprising a. The method of claim 12, Each bit of the relevant phrase bit vector is associated with a related phrase of the query phrase, The bits are arranged such that the most significant bit of the bit vector is associated with an associated phrase having the largest information gain for the query phrase, the least significant bit is associated with an associated phrase having the least information gain for the query phrase, And the predetermined number of points associated with each bit ranges from the largest number of points associated with the most significant bit to the smallest number associated with the least significant bit. As a method of providing an information retrieval system, Automatically identifying a valid phrase in a document collection comprising a plurality of documents, the valid phrase containing a plurality of word phrases; Indexing the document according to valid text contained in the document; Receiving a search query, Identifying phrases contained in the query; Selecting a document according to the identified phrase; Ranking the selected document according to the identified phrase Method of providing an information retrieval system comprising a.

Images