Query utilization

• US 7,958,141 B2
• Filed: 08/12/2008
• Issued: 06/07/2011
• Est. Priority Date: 11/01/2007
• Status: Active Grant

• Current Assignee: PayPal, Inc. (PayPal Holdings, Inc.)
• Original Assignee: eBay Inc.
• Inventors: Parikh, Nishith, Sundaresan, Neelakantan
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Nguyen; Kim T
• Application Number:
  US12/190,517
• Publication Number:
  US 20090119285A1
• Time in Patent Office: 1,029 Days
• Field of Search: 707/769, 707/779
• US Class Current: 707/769
• 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

Methods and system for query utilization are described. A rate of a plurality of queries to a data source may be determined for a plurality of time periods. The plurality of queries may be associated with a term. A cost may be associated with a normal-to-deviated query state transition and a deviated-to-normal query state transition. A normal query state or a deviated 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 normal-to-deviated query state transition and the deviated-to-normal query state transition. A query burst may be identified during the plurality of time periods based on assignment of the normal query state or the deviated query state to the plurality of queries. The query burst may have the normal query state, the normal-to-deviated query state transition, and the deviated query state during a time period.

Claims

1. A method comprising:

using one or more computer processors, determining, for each of a plurality of time periods, a rate of a plurality of queries to a data source, the plurality of queries associated with a term;

associating a cost with a normal-to-deviated query state transition and a deviated-to-normal query state transition;

assigning a normal query state or a deviated 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 normal-to-deviated query state transition and the deviated-to-normal query state transition; and

identifying a query burst during the plurality of time periods based on assignment of the normal query state or the deviated query state to each of the plurality of queries, the query burst having the normal query state, the normal-to-deviated query state transition, and the deviated query state during a plurality of associated time periods.

2. The method of claim 1, further comprising:

providing an output including identification of the query burst.

3. The method of claim 1, further comprising:

providing an output based a determination of the rate of the plurality of queries and on assignment of the normal query state or the deviated query state.

4. The method of claim 1, further comprising:

performing cost minimization analysis on the plurality of queries,

wherein the assigning being 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.

5. The method of claim 1, 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.

6. The method of claim 1, 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 being 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 converting of the frequency information.

7. The method of claim 1, wherein the plurality of time periods include a plurality of days.

8. A method comprising:

determining, for each of a plurality of time periods, a rate of a plurality of queries to a data source, the plurality of queries associated with a term;

performing cost minimization analysis on each of the plurality of queries for the plurality of time periods;

storing a result of the performing of the cost minimization analysis;

monitoring a plurality of additional queries to the data source, the plurality of additional queries associated with the term;

performing the cost minimization analysis on each of the plurality of additional queries for an additional time period;

assigning a normal query state or a deviated query state to a particular query for the additional time period based on the cost minimization analysis performed on the plurality of queries and the plurality of additional queries; and

identifying a query burst during the plurality of time periods and the additional time period based on assignment of the normal query state or the deviated query state to the particular query, the query burst having the normal query state, the normal-to-deviated query state transition, and the deviated query state during a plurality of associated time periods.

9. The method of claim 8, further comprising:

providing an output including identification of the query burst.

10. The method of claim 8, further comprising:

determining a rate of change of percentage volume for the plurality of additional queries to the data source; and

comparing the rate of change of percentage volume for the plurality of additional queries associated to a rate of change of absolute volume for the plurality of additional queries associated,

wherein the assigning of the normal query state or the deviated query state to the particular query is based on the cost minimization analysis performed on the plurality of queries and the plurality of additional queries and the comparing.

11. The method of claim 8, further comprising:

associating a cost with a normal-to-deviated query state transition and a deviated-to-normal query state transition,

wherein the assigning of the normal query state or the deviated query state for the particular query is based on the cost minimization analysis performed on the plurality of queries and the plurality of additional queries and the cost of the normal-to-deviated query state transition and the deviated-to-normal query state transition.

12. The method of claim 8, further comprising:

converting frequency information for the particular query into a time series, the time series indicating timestamps of the arrival of the plurality of additional queries associated with the term,

wherein the assigning of the normal query state or the deviated query state for the particular query is based on the cost minimization analysis performed on the plurality of queries and the plurality of additional queries and the converting of the frequency information.

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

determine, for each of a plurality of time periods, a rate of a plurality of queries to a data source, the plurality of queries associated with a term;

associate a cost with a normal-to-deviated query state transition and a deviated-to-normal query state transition;

assign a normal query state or a deviated query state to a particular query for a particular time period of the plurality of time periods, assignment 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 normal-to-deviated query state transition and the deviated-to-normal query state transition; and

identify a query burst during the plurality of time periods based on the assignment of the normal query state or the deviated query state to each of the plurality of queries, the query burst having the normal query state, the normal-to-deviated query state transition, and the deviated query state during a plurality of associated time periods.

14. The machine-readable medium of claim 13 further comprising instructions, which when implemented by one or more processors perform the following operations:

perform cost minimization analysis on the plurality of queries,

wherein the assignment 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.

15. A system comprising:

add 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, the plurality of queries associated with a term;

a cost association module to associate a cost with a normal-to-deviated query state transition and a deviated-to-normal query state transition;

a state assignment module to assign a normal query state or a deviated query state to a particular query for a particular time period of the plurality of time periods, assignment being based on a particular query rate of the rate of the plurality of queries for the particular time period determined by the query rate determination module and the cost of the normal-to-deviated query state transition and the deviated-to-normal query state transition associated by the cost association module; and

a query burst identification module to identify a query burst during the plurality of time periods based on the assignment of the normal query state or the deviated query state to each of the plurality of queries by the state assignment module, the query burst having the normal query state, the normal-to-deviated query state transition, and the deviated query state during a plurality of associated time periods.

16. The system of claim 15, 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.

17. The system of claim 16, 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.