Query utilization using query burst classification

• US 8,370,333 B2
• Filed: 05/31/2011
• Issued: 02/05/2013
• Est. Priority Date: 11/01/2007
• Status: Active Grant

• Current Assignee: PayPal, Inc. (PayPal Holdings, Inc.)
• Original Assignee: eBay Inc.
• Inventors: Sundaresan, Neelakantan, Parikh, Nishith
• Primary Examiner(s): Ortiz Ditren, Belix M
• Application Number:
  US13/149,151
• Publication Number:
  US 20110231439A1
• Time in Patent Office: 616 Days
• Field of Search: 707/779, 707/769
• US Class Current: 707/722
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: G06Q 30/0205 Location or geographical consideration
• CPC Class Codes: G06Q 30/0206 Price or cost determination based on market factors

Abstract

Query utilization in which a rate of a plurality of queries to a data source may be determined for a plurality of time periods. A cost may be associated with a query state transition. A query state may be assigned to a particular query on a particular time period of the plurality of time periods based on the rate of queries for the particular time period and the cost of the query state transition. A query burst may be identified during the plurality of time periods based on assignment of a query state to the plurality of queries. The query may exhibit a normal query state, a normal-to-deviated query state transition, and a deviated query state. A query burst identification module may identify a query burst during the plurality of time periods, a burst conversion module may convert the query burst to a wavelet using a wavelet transform, a clustering module may apply a clustering technique to the wavelet, and a query classification module may classify the query burst based on applying the clustering technique.

Claims

1. A method comprising:

using one or more computer processors to determine, for each of a plurality of time periods, a rate of a plurality of queries to a data source;

associating a cost with a query state transition;

assigning a query state to a particular query for a particular time period of the plurality of time periods; and

identifying a query burst during the plurality of time periods based on assignment of the query state to each of the plurality of queries.

2. The method of claim 1, wherein the query burst has a normal query state, a normal-to-deviated query state transition, and a deviated query state during a plurality of associated time periods.

3. The method of claim 2 wherein the cost is associated with the normal-to-deviated query state transition and the deviated-to-normal query state transition.

4. The method of claim 3 wherein the query state assigned to a particular query for a particular time period is a normal query state or a deviated query state.

5. The method of claim 4 wherein the assigning is based on a particular query rate of the rate of the plurality of queries for the particular time period and the cost of the normal-to-deviated query state transition and the deviated-to-normal query state transition.

6. The method of claim 1, wherein the plurality of queries is associated with a term.

7. The method of claim 6 further comprising providing an output based on a determination of the rate of the plurality of queries and on assignment of the normal query state or the deviated query state.

8. The method of claim 6 further comprising logging the plurality of queries to the data source,

wherein the determining of the rate is based on the logging of the plurality of queries.

9. The method of claim 6, further comprising performing cost minimization analysis on the plurality of queries, wherein the assigning is based on the particular query rate, the cost of the normal-to-deviated query state transition, the deviated-to-normal query state transition, and a result of the cost minimization analysis.

10. The method of claim 9 further comprising:

logging the plurality of queries to the data source,

wherein the determining of the rate is based on the logging of the plurality of queries.

11. The method of claim 9, further comprising:

converting frequency information for the particular query into a time series, the time series indicating timestamps of the arrivals of respective queries of the plurality of queries associated with the term, wherein the assigning is based on the particular query rate, the cost of the normal-to-deviated query state transition, the deviated-to-normal query state transition, and a result of the converting of the frequency information.

12. A non-transitory machine-readable medium comprising instructions, which when implemented by one or more processors perform the following operations:

determining, for each of a plurality of time periods, a rate of a plurality of queries to a data source;

associating a cost with a query state transition;

assigning a query state to a particular query for a particular time period of the plurality of time periods, the assigning being based on a particular query rate of the rate of the plurality of queries for the particular time period and the cost of the query state transition; and

identifying a query burst during the plurality of time periods based on assignment of the query state to each of the plurality of queries.

13. The machine-readable medium of claim 12 wherein the query burst has a normal query state, a normal-to-deviated query state transition, and a deviated query state during a plurality of associated time periods.

14. The machine-readable medium of claim 13 wherein the cost is associated with the normal-to-deviated query state transition and the deviated-to-normal query state transition.

15. The machine-readable medium of claim 14 wherein the query state assigned to a particular query for a particular time period is a normal query state or a deviated query state.

16. The machine-readable medium of claim 15 wherein the assigning is based on a particular query rate of the rate of the plurality of queries for the particular time period, the cost of the normal-to-deviated query state transition, and the deviated-to-normal query state transition.

17. The machine readable medium of claim 12 wherein the plurality of queries is associated with a term.

18. The machine-readable medium of claim 17, the operations further comprising performing cost minimization analysis on the plurality of queries, wherein the assigning is based on the particular query rate, the cost of the normal-to-deviated query state transition and the deviated-to-normal query state transition, and a result of the cost minimization analysis.

19. The machine-readable medium of claim 17, the operations further comprising logging the plurality of queries to the data source, wherein the determining of the rate is based on the logging of the plurality of queries.

20. The machine-readable medium of claim 17, the operations further comprising providing an output based on a determination of the rate of the plurality of queries and on assignment of the normal query state or the deviated query state.

21. A system comprising:

one or more computer processors and memory adapted to store and execute a query rate determination module to determine, for each of a plurality of time periods, a rate of a plurality of queries to a data source;

a cost association module to associate a cost with a query state transition;

a state assignment module to assign a query state for a particular time period of the plurality of time periods; and

a query burst identification module to identify a query burst during the plurality of time periods based on the assignment of the query state to each of the plurality of queries by the state assignment module.

22. The system of claim 21, further comprising:

a burst conversion module to convert the query burst identified by the query burst identification module to a wavelet using a wavelet transform;

a clustering module to apply a clustering technique to the wavelet created by the burst conversion module; and

a query classification module to classify the query burst based on the applying of the clustering technique by the clustering module.

23. The system of claim 21 further comprising:

a formation identification module to identify a graphic query formation among the plurality of queries based on the query burst; and

a ranking module to rank the query burst based on the graphic query formation identified by the format identification module.