Method for performing a data query

• US 6,643,640 B1
• Filed: 02/07/2002
• Issued: 11/04/2003
• Est. Priority Date: 03/31/1999
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Verizon Laboratories Incorporated (Verizon Communications Inc.)
• Inventors: Getchius, Jeffrey, Scofield, Cary
• Primary Examiner(s): Shah, Sanjiv
• Application Number:
  US10/071,742
• Time in Patent Office: 635 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/10, 707/9, 707/104, 709/225, 380/25
• US Class Current: 707/719
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06Q 30/00 Commerce
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• 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/99936 Pattern matching access

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 processing a data query, comprising:

routing the data query to one of a plurality of nodes included in the computer system in accordance with partitioning characteristics of the data query and configuration information describing the computer system;

performing the data query using data stored in a data query cache and subsumption techniques to derive a result set from one or more previous result sets stored in the data query cache; and

storing the result set of the data query in the data query cache using highly redundant caching techniques.

2. The method of claim 1, wherein the routing is based on a geographic characteristic of the data query.

3. The method of claim 1, wherein the data query is a composition query that includes a plurality of terms combined using logical connectives.

4. The method of claim 3, wherein the logical connectives include at least one of a conjunctive and a disjunctive operation of search terms.

5. The method of claim 1, wherein the result set is formed from derivations of prior result sets in the data query cache.

6. The method of claim 5, wherein the derivations of prior result sets include at least one of a superset and one or more subsets of the result set.

7. The method of claim 1, further comprising:

associating a domain with each of the nodes in the computer system.

8. The method of claim 7, further comprising:

associating a server weight with each of the nodes.

9. The method of claim 8, wherein the routing the data query includes:

identifying one of the nodes based on a cost associated with processing the data query, the cost for each of the nodes being based on the domain and server weight associated with the node.

10. The method of claim 1, wherein the highly redundant caching techniques include storing at least one of the result set, one or more supersets of the result set, and one or more subsets of the result set in the data query cache.

11. The method of claim 1, wherein the partitioning characteristics include one of a zip code, a state, and an area code.

12. A computer system for processing a data query, comprising:

routing logic configured to;

receive a data query, and

route the data query in accordance with partitioning characteristics of the data query and configuration information describing the computer system; and

a plurality of nodes, each of the nodes including a data query cache and being configured to;

process the data query using data stored in the data query cache to derive a result set from one or more previous result sets stored in the data query cache, and

store the result set of the data query in the data query cache using highly redundant caching techniques.

13. The computer system of claim 12, wherein the routing logic is configured to route the data query based on a geographic characteristic of the data query.

14. The computer system of claim 12, wherein the data query is a composition query that includes a plurality of terms combined using logical connectives.

15. The computer system of claim 14, wherein the logical connectives include at least one of a conjunctive and a disjunctive operation of search terms.

16. The computer system of claim 12, wherein when processing the data query, each of the nodes is configured to generate the result set from derivations of prior result sets in the data query cache.

17. The computer system of claim 16, wherein the derivations of prior result sets include at least one of a superset and one or more subsets of the result set.

18. The computer system of claim 12, wherein a domain is associated with each of the nodes.

19. The computer system of claim 18, wherein a server weight is associated with each of the nodes.

20. The computer system of claim 19, wherein when routing the data query, the routing logic is configured to:

identify one of the nodes based on the domain and the server weight associated with the node.

21. The computer system of claim 12, wherein when using highly redundant caching techniques, each of the nodes is configured to:

store at least one of the result set, one or more supersets of the result set, and one or more subsets of the result set in the data query cache.

22. The computer system of claim 12, wherein the partitioning characteristics include at least one of a zip code, a state, and an area code.

23. A computer-readable medium that stores instructions that when executed by a computer system causes the computer system to perform a method for processing a data query, the computer-readable medium comprising:

instructions for transferring the data query to one of a plurality of nodes included in the computer system in accordance with partitioning characteristics of the data query and configuration information describing the computer system;

instructions for processing the data query using data stored in a data query cache to derive a result set from one or more previous result sets stored in the data query cache; and

instructions for storing the result set of the data query in the data query cache using highly redundant caching techniques.

24. The computer-readable medium of claim 23, wherein the transferring is based on a geographic characteristic of the data query.

25. The computer-readable medium of claim 23, wherein the data query is a composition query that includes a plurality of terms combined using logical connectives.

26. The computer-readable medium of claim 25, wherein the logical connectives include at least one of a conjunctive and a disjunctive operation of search terms.

27. The computer-readable medium of claim 23, wherein the result set is formed from derivations of prior result sets in the data query cache.

28. The computer-readable medium of claim 27, wherein the derivations of prior result sets include at least one of a superset and one or more subsets of the result set.

29. The computer-readable medium of claim 23, further comprising:

instructions for associating a domain with each of the nodes in the computer system.

30. The computer-readable medium of claim 29, further comprising:

instructions for associating a server weight with each of the nodes.

31. The computer-readable medium of claim 30, wherein the instructions for transferring the data query include:

instructions for selecting one of the nodes based on the domain and the server weight associated with the node.

32. The computer-readable medium of claim 23, wherein the highly redundant caching techniques include storing at least one of the result set, one or more supersets of the result set, and one or more subsets of the result set in the data query cache.

33. The computer-readable medium of claim 23, wherein the partitioning characteristics include one of a zip code, a state, and an area code.

34. A system for processing a data query, comprising:

means for routing the data query to one of a plurality of nodes included in the computer system in accordance with partitioning characteristics of the data query and configuration information describing the computer system;

means for performing the data query using data stored in a data query cache using subsumption techniques to derive a result set from one or more previous result sets stored in the data query cache; and

means for storing the result set of the data query in the data query cache using highly redundant caching techniques.