Weighted term ranking for on-line query tool

• US 7,047,242 B1
• Filed: 03/31/1999
• Issued: 05/16/2006
• Est. Priority Date: 03/31/1999
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Verizon Laboratories Incorporated (Verizon Communications Inc.)
• Inventors: Ponte, Jay
• Primary Examiner(s): Pardo, Thuy N.
• Application Number:
  US09/282,730
• Time in Patent Office: 2,603 Days
• Field of Search: 345/440, 707/3, 707/5, 707/7, 707/100, 707/501, 707/10, 707/102, 707/104, 707/505, 704/9
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: G06Q 10/00 Administration; Management
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Disclosed is a system for performing online data queries. The system for performing online data queries is a distributed computer system with a plurality of server nodes each fully redundant and capable of processing a user query request. Each server node includes a data query cache and other caches that may be used in performing data queries. The data query, as well as request allocation, is performed in accordance with an adaptive partitioning technique with a bias towards an initial partitioning scheme. Generic objects are created and used to represent business listings upon which the user may perform queries. Various data processing and integration techniques are included which enhance data queries. An update technique is used for synchronizing data updates as needed in updating the plurality of server nodes. A multi-media data transfer technique is used to transfer non-text or multi-media data between various components of the online query tool. Optimizations for searching, such as the common term optimization, are included for those commonly performed data queries. Also disclosed is a system for targeting advertisements that are displayed to a user of the system.

Claims

1. A method executed in a computer system for ranking super-categories used in performing a data query, the method comprising:

establishing a super-category term list for each term appearing in one of a super-category and a category of document to be searched, each element of said super-category term list including terms in the super-category and terms in categories associated with that super-category;

obtaining terms in a data query;

obtaining terms in categories that are retrieved in response to the data query;

forming a modified query consisting of said terms in the data query and said terms in the categories;

weighting terms of the modified query; and

ranking the super-category term lists by applying the modified query to the super-category term lists to determine the most relevant super-category to the data query.

2. The method of claim 1, wherein ranking the super-category term lists comprises:

for the super-category term list corresponding to each term in the modified query, calculating a sum of all terms in the modified query of a product of a term frequency of each term in that super-category term list and an inverse document frequency of each term as related to all super-category term lists.

3. The method of claim 2, wherein the term frequency is calculated based on a logarithm of the number of terms from the modified query appearing in the super-category term list.

4. The method of claim 2, wherein the inverse document frequency is calculated based on Robertson'"'"'s term frequency.

5. The method of claim 2, wherein the ranking of documents according to an occurrence of terms is weighted according to information about the terms.

6. The method of claim 5, wherein the weighting is based on a number of documents associated with a category.

7. The method of claim 5, wherein the term frequency and the inverse document frequency are weighted for each term in the modified query according to whether said each term appears in a category that was manually mapped to a super-category or a category that was automatically mapped to a super-category.

8. The method of claim 1, further comprising, performing for all super-categories:

calculating a product associated with each term appearing in said modified query that includes terms from said data query and terms from said categories retrieved in response to said data query, said product being formed by multiplying a term frequency for said each term by an inverse document frequency for said each term as related to a frequency of occurrence of said term amongst all other terms associated with all super-category term lists;

calculating a sum of said each product for each of said all super-categories; and

ranking said all super-categories in accordance with said sum associated with each super-category.

9. The method of claim 2, wherein said inverse document frequency is calculated based on a logarithm of actual inverse document frequency defined as:

log(N−

actual inverse document frequency/log(N))

in which “

N”

represents a total number of documents over which said data query is being performed.

10. The method of claim 4, wherein said Robertson'"'"'s term frequency is defined as:

TF/((TF+0.5+1.5(DL/ADL))

wherein “

TF”

represents an actual term frequency associated with a document, “

DL”

represents a length of said document, and “

ADL”

represents an average length of any document in a set of documents being searched.

11. The method of claim 7, wherein a category that is manually mapped is given a greater weight of significance than another category that is automatically mapped.

12. A computer program product for ranking super-categories used in performing a data query comprising:

means for establishing a super-category term list for each term appearing, in, one of a super-category and a category of a document to be searched, each element of said super-category term list including terms in the super-category and terms in categories associated with that super-category;

means for obtaining terms in a data query;

means for obtaining terms in categories retrieved in response to the data query;

means for forming a modified query consisting of said terms in the data query and said terms in the categories;

means for weighting terms of the modified query; and

means for ranking the super-category term lists by applying the modified query to the super-category term lists to determine the most relevant super-category to the data query.

13. A computer program product for ranking super-categories used in performing a data query comprising:

machine executable code for establishing a super-category term list for each term appearing in one of a super-category and a category of a document to be searched, each element of said super-category term list including terms in the super-category and terms in categories associated with that super-category;

machine executable code for obtaining terms in a data query;

machine executable code for obtaining terms in categories retrieved in response to the data query;

machine executable code for forming a modified query consisting of said terms in the data query and said terms in the categories;

machine executable code for weighting terms of the modified query; and

machine executable code for ranking the super-category term lists by applying the modified query to the super-category term lists to determine the most relevant super-category to the data query.

14. The computer program product of claim 13, wherein said machine executable code for ranking the super-category term lists further comprises:

machine executable code for calculating, for the super-category term list corresponding to each term in the modified query, a sum of all terms in the modified query of a product of a term frequency of each term in that super-category term list and an inverse document frequency of each term as related to all super-category term lists.

15. The computer program product of claim 14, further including machine executable code for calculating the term frequency based on a logarithm of the number of terms from the modified query appearing in the super-category term list.

16. The computer program product of claim 14 further including machine executable code for calculating the inverse document frequency based on Robertson'"'"'s term frequency.

17. The computer program product of claim 14, further including machine executable code for ranking documents according to an occurrence of terms weighted according to information about the terms.

18. The computer program product of claim 17, further including machine executable code for weighting documents based on a number of documents associated with a category.

19. The computer program product of claim 17, further including machine executable code for weighting the term frequency and the inverse document frequency for each term in the modified query according to whether said each term appears in a category that was manually mapped to a super-category or a category that was automatically mapped to a super-category.

20. The computer program product of claim 13, further comprising:

machine executable code for calculating, for all super-categories, a product associated with each term appearing in said modified query that includes terms from said data query and terms from said categories retrieved in response to said data query, said product being formed by multiplying a term frequency for said each term by an inverse document frequency for said each term as related to a frequency of occurrence of said term amongst all other terms associated with all super-category term lists;

machine executable code for calculating, for all super-categories, a sum of said each product for each of said all super-categories; and

machine executable code for ranking said all super-categories in accordance with said sum associated with said each super-category.

21. The computer program product of claim 14, further including:

machine executable code for calculating said inverse document frequency based on a logarithm of actual inverse document frequency defined as;

log(N−

actual inverse document frequency/log(N))

in which “

N”

represents a total number of documents over which said data query is being performed.

22. The computer program product of claim 16, further including:

machine executable code for calculating said Robertson'"'"'s term frequency that is defined as;

TF/((TF+0.5+1.5(DL/ADL))

wherein “

TF”

represents an actual term frequency associated with a document, “

DL”

represents a length of said document, and “

ADL”

represents an average length of any document in a set of documents being searched.

23. The computer program product of claim 19, wherein a category that is manually mapped is given a greater weight of significance than another category that is automatically mapped.

24. A method executed in a computer system for searching a first set of documents comprising:

forming a modified query corresponding to terms included in a data query and terms included in categories associated with a second set of documents obtained by searching the data query; and

ranking said first set documents using a weighting factor associated with terms of the modified query, wherein the weighting factor varies in accordance with an occurrence of each term appearing in each of said first set of documents to determine a most relevant one of said second documents to said data query.

25. The method of claim 24, wherein said ranking said first set of documents includes performing, for each of said documents included in said first set:

calculating a product associated with each term appearing in said set of terms of the modified query, said product being formed by multiplying a term frequency for said each term by an inverse document frequency for said each term as related to a frequency of occurrence of said term amongst all other terms associated with said first set of documents;

calculating a sum of said each product for each of said first set of documents; and

ranking said first set of documents in accordance with said sum associated with said each document of said first set.

26. The method of claim 25, wherein the term frequency is calculated based on a logarithm of the number of terms from the set of terms appearing in each of said first set of documents.

27. The method of claim 25, wherein the inverse document frequency is calculated based on Robertson'"'"'s term frequency.

28. The method of claim 25, wherein the ranking of said first set of documents according to an occurrence of terms is weighted according to information about the terms.

29. The method of claim 28, wherein the weighting is based on a number of documents in said first set associated with a category.

30. The method of claim 28, wherein the frequency and the inverse document frequency are weighted for each term in the set of terms according to whether said each terms appears in a category that was manually mapped to one of said documents or a category that was automatically mapped to one of said documents included in said first set.

31. A computer program product for searching a first set of documents comprising:

machine executable code for forming a modified query corresponding to terms included in a data query and terms included in categories associated with a second set of documents obtained by searching the data query; and

machine executable code for ranking said first set documents using a weighting factor associated with terms of the modified query, wherein the weighting factor varies in accordance with an occurrence of each term appearing in each of said first set of documents to determine a most relevant one of said second documents to said data query.

32. The computer program product of claim 31, wherein said ranking said machine executable code for ranking said first set of documents includes:

machine executable code for calculating, for each of said documents included in said first set, a product associated with each term appearing in said set of terms of the modified query, said product being formed by multiplying a term frequency for said each term by an inverse document frequency for said each term as related to a frequency of occurrence of said term amongst all other terms associated with said first set of documents;

machine executable code for calculating, for each of said documents included in said first set, a sum of said each product for each of said first set of documents; and

machine executable code for ranking said first set of documents in accordance with said sum associated with said each document of said first set.

33. The computer program product of claim 32, wherein the term frequency is calculated based on a logarithm of the number of terms from the set of terms appearing in each of said documents included in said first set.