Method for using data from a data query cache

• US 6,519,592 B1
• Filed: 02/07/2002
• Issued: 02/11/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/068,938
• Time in Patent Office: 369 Days
• Field of Search: 707/6, 707/3, 707/4, 707/5, 707/7, 707/2, 707/1
• US Class Current: 1/1
• 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 computer-implemented method for obtaining search results, relating to a query request, from a data query cache, the method comprising:

determining if there is data in the data query cache that matches the query request;

retrieving the data from the data query cache as the search results for the query request when there is data in the data query cache matching the query request;

determining if one or more parent data sets corresponding to the query request are included in the data query cache when there is no data in the data query cache matching the query request; and

when one or more parent data sets are included in the data query cache;

calculating a cost for each of the parent data sets,

identifying one of the parent data sets with a minimum cost, and

applying a minimum cost derivation sequence based on the identified parent data set to obtain the search results.

2. The method of claim 1, further including:

when no parent data sets are included in the data query cache, using an alternate technique to obtain the search results relating to the query request.

3. The method of claim 2, wherein the alternate technique includes using a closest ancestor as a basis for forming the search results.

4. The method of claim 1, further including:

storing the search results in the data query cache if one or more parent data sets are included in the data query cache.

5. The method of claim 1, wherein the determining if one or more parent data sets corresponding to the query request are included in the data query cache includes:

dropping one or more terms of the query request to generate one or more parent query requests, and

determining whether the data query cache stores data that matches the one or more parent query requests.

6. The method of claim 5, wherein the dropping includes:

sequentially dropping each term of the query request, and

forming, for each of the dropped terms, one or more parent query requests from remaining terms of the query request.

7. The method of claim 5, wherein the dropping includes:

sequentially dropping pairs of terms of the query request, and

forming, for each of the dropped pairs of terms, one or more parent query requests from remaining terms of the query request.

8. The method of claim 5, wherein the dropping includes:

sequentially dropping a predetermined number of terms of the query request, and

forming, for each of the dropped terms, one or more parent query requests from remaining terms of the query request.

9. The method of claim 1, wherein the calculating a cost for each of the parent data sets includes:

identifying a number of entities associated with the parent data set, and

determining the cost for the parent data set based on the identified number of entities.

10. The method of claim 9, wherein the entities are business listings.

11. The method of claim 9, wherein the applying a minimum cost derivation sequence includes:

identifying one of the parent data sets with the least identified number of entities with respect to other ones of the parent data sets.

12. The method of claim 1, further including:

determining a threshold level of parentage, and

forming generations of combinations of search terms included in the query request in accordance with the threshold level.

13. The method of claim 12, wherein the determining if one or more parent data sets corresponding to the query request are included in the data query cache includes:

determining whether any of the combinations of search terms match data in the data query cache.

14. The method of claim 1, wherein the determining if there is data in the data query cache matching the query request includes:

identifying a subset of query terms that maps the query request to a name,

forming a query string using the subset of query terms as included in the query request, and

using the query string corresponding to the query request to determine if there is data in the data query cache matching the query request.

15. The method of claim 1, wherein the search results include one or more business listings.

16. The method of claim 1, wherein the data query cache includes cached data regarding total-city queries and multi-city queries, the total-city queries representing data corresponding to business listings having an association with every city that may be queried, and the multi-city queries representing data corresponding to business listings having an association with more than one city that may be queried.

17. The method of claim 16, further including:

incorporating data regarding the total-city and the multi-city queries with other data to form the search results.

18. A computer system for processing a query request, comprising:

a data query cache configured to store data sets; and

a query engine configured to;

determine if there is a data set in the data query cache that matches the query request,

retrieve the data set from the data query cache as a resulting data set associated with the query request when there is a data set in the data query cache matching the query request,

determine if one or more parent data sets corresponding to the query request are included in the data query cache when there is no data set in the data query cache matching the query request, and

when one or more parent data sets are included in the data query cache;

calculate a cost for each of the parent data sets,

identify one of the parent data sets with a minimum cost, and

apply a minimum cost derivation sequence based on the identified parent data set to obtain the resulting data set.

19. The computer system of claim 18, wherein the query engine is further configured to:

use an alternate technique to obtain the resulting data set when no parent data sets are included in the data query cache.

20. The computer system of claim 19, wherein the alternate technique includes using a closest ancestor as a basis for forming the resulting data set.

21. The computer system of claim 18, wherein the query engine is further configured to:

store the resulting data set in the data query cache if one or more parent data sets are included in the data query cache.

22. The computer system of claim 18, wherein when determining if one or more parent data sets corresponding to the query request are included in the data query cache, the query engine is configured to:

drop one or more terms of the query request to generate one or more parent query requests, and

determine whether the data query cache stores a data set that matches the one or more parent query requests.

23. The computer system of claim 22, wherein when dropping one or more terms of the query request, the query engine is configured to:

sequentially drop each term of the query request, and

form, for each of the dropped terms, one or more parent query requests from remaining terms of the query request.

24. The computer system of claim 22, wherein when dropping one or more terms of the query request, the query engine is configured to:

sequentially drop pairs of terms of the query request, and

form, for each of the dropped pairs of terms, one or more parent query requests from remaining terms of the query request.

25. The computer system of claim 22, wherein when dropping one or more terms of the query request, the query engine is configured to:

sequentially drop a predetermined number of terms of the query request, and

form, for each of the dropped terms, one or more parent query requests from remaining terms of the query request.

26. The computer system of claim 18, wherein when calculating a cost for each of the parent data sets, the query engine is configured to:

identify a number of entities associated with the parent data set, and

determine the cost for the parent data set based on the identified number of entities.

27. The computer system of claim 26, wherein the entities are business listings.

28. The computer system of claim 26, wherein when applying a minimum cost derivation sequence, the query engine is configured to:

identify one of the parent data sets with the least identified number of entities with respect to other ones of the parent data sets.

29. The computer system of claim 18, wherein the query engine is further configured to:

determine a threshold level of parentage, and

form generations of combinations of search terms included in the query request in accordance with the threshold level.

30. The computer system of claim 29, wherein when determining if one or more parent data sets corresponding to the query request are included in the data query cache, the query engine is configured to:

determine whether any of the combinations of search terms match data sets in the data query cache.

31. The computer system of claim 18, wherein when determining if there is a data set in the data query cache matching the query request, the query engine is configured to:

identify a subset of query terms that maps the query request to a name,

form a query string using the subset of query terms as included in the query request, and

use the query string corresponding to the query request to determine if there is a data set in the data query cache matching the query request.

32. The computer system of claim 18, wherein the resulting data set includes one or more business listings.

33. The computer system of claim 18, wherein the data query cache includes cached data regarding total-city queries and multi-city queries, the total-city queries representing data corresponding to business listings having an association with every city that may be queried, and the multi-city queries representing data corresponding to business listings having an association with more than one city that may be queried.

34. The computer system of claim 33, wherein the query engine is further configured to:

incorporate data regarding the total-city and the multi-city queries with other data to form the resulting data set.

35. A computer-readable medium that stores instructions that, when executed by a computer, cause the computer to perform a method for processing a query, the computer-readable medium comprising:

instructions for determining if there is data in a data cache that satisfies the query;

instructions for retrieving the data from the data cache as search results for the query when there is data in the data cache satisfying the query;

instructions for determining if one or more parent data sets corresponding to the query are included in the data cache when there is no data in the data cache satisfying the query;

instructions for determining a cost for each of the parent data sets when one or more parent data sets are included in the data cache;

instructions for identifying one of the parent data sets with a minimum cost; and

instructions for obtaining the search results using the identified parent data set.

36. A system for obtaining search results, relating to a query request, from a data cache, the system comprising:

means for determining if there is data in the data cache that satisfies the query request;

means for reading the data from the data cache as the search results for the query request when there is data in the data cache satisfying the query request;

means for determining if one or more parent data sets corresponding to the query request are included in the data cache when there is no data in the data cache satisfying the query request;

means for calculating a cost associated with each of the parent data sets when one or more parent data sets are included in the data cache;

means for identifying one of the parent data sets with a minimum cost among the one or more parent data sets; and

means for obtaining the search results based on the identified parent data set.