Method and system for URL autocompletion using ranked results

• US 7,499,940 B1
• Filed: 11/11/2004
• Issued: 03/03/2009
• Est. Priority Date: 11/11/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gibbs, Kevin A.
• Primary Examiner(s): MIZRAHI, DIANE D
• Application Number:
  US10/987,294
• Time in Patent Office: 1,573 Days
• Field of Search: 707/5, 707/1, 707/2, 707/3, 707/4, 707/6, 707/7, 707/100, 707/101, 707/102, 705/26, 709/206
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9566 URL specific, e.g. using aliases, detecting broken or misspelled links
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A set of ordered predicted completion strings are presented to a user as the user enters text in a text entry box (e.g., a browser or a toolbar). The predicted completion strings can be in the form of URLs or query strings. The ordering may be based on any number of factors (e.g., a query'"'"'s frequency of submission from a community of users). URLs can be ranked based on an importance value of the URL. Privacy is taken into account in a number of ways, such as using a previously submitted query only when more than a certain number of unique requestors have made the query. The sets of ordered predicted completion strings is obtained by matching a fingerprint value of the user'"'"'s entry string to a fingerprint to table map which contains the set of ordered predicted completion strings.

Claims

1. A method for processing URL information, comprising:

at a server;

receiving from a requestor a partial URL, the requester located remotely from the server;

the receiving including receiving the partial URL from the requestor prior to the requestor performing an action indicating entry of a complete URL that includes the partial URL;

obtaining a set of complete URLs corresponding to the partial URL, the complete URLs previously submitted by a community of users using a plurality of client devices;

ordering the set of complete URLs in accordance with a ranking criteria;

conveying the set as ordered to the requestor; and

prior to receiving the partial URL;

identifying a set of historical complete URL requests previously submitted by the community of users, each of the complete URLs in the set of historical complete URLs having at least one ranking value associated with the complete URL; and

generating a plurality of ordered subsets of the identified set of historical complete URLs, each ordered subset of historical complete URLs including a subset of the identified set of historical complete URLs ordered in accordance with the at least one ranking value associated with the historical complete URLs in the subset;

wherein the obtaining includes accessing one of the ordered subsets of historical complete URLs, selected in accordance with the received partial URL.

2. A method for processing URL information, comprising:

at a server;

receiving from a requestor a partial URL, the requester located remotely from the server;

the receiving including receiving the partial URL from the requestor prior to the requestor performing an action indicating entry of a complete URL that includes the partial URL;

obtaining a set of complete URLs corresponding to the partial URL, the complete URLs previously submitted by a community of users using a plurality of client devices;

ordering the set of complete URLs in accordance with a ranking criteria;

conveying the set as ordered to the requestor; and

prior to receiving the partial URL;

identifying a plurality of sets, each of the plurality of sets associated with a portion of a complete URL and comprising a plurality of historical complete URLs previously submitted by the community of users, each complete URL having a respective ranking value; and

for at least a portion of the plurality of sets, ordering the historical complete URLs in the set in accordance with the respective ranking value;

wherein the obtaining includes;

identifying two or more sets, from among the portion, wherein the identified sets correspond to the received partial URL, and

merging the sets in an interleaved fashion.

3. A method for processing URL information, comprising:

at a server;

receiving from a requestor a partial URL, the requester located remotely from the server;

the receiving including receiving the partial URL from the requestor prior to the requestor performing an action indicating entry of a complete URL that includes the partial URL;

obtaining a set of complete URLs corresponding to the partial URL, the complete URLs previously submitted by a community of users using a plurality of client devices;

ordering the set of complete URLs in accordance with a ranking criteria;

conveying the set as ordered to the requestor; and

prior to receiving the partial URL;

identifying a plurality of sets, each of the plurality sets associated with a portion of a complete URL and comprising a plurality of historical complete URLs previously submitted by the community of users, each complete URL having at least one respective ranking value; and

for at least a portion of the plurality of sets, ordering the complete URLs in the set in accordance with the at least one respective ranking value;

wherein the obtaining includes identifying the set of complete URLs, from among the plurality of sets, corresponding to the received partial URL.

4. A method for processing URL information, comprising:

at a server;

receiving from a requestor a partial URL, the requester located remotely from the server;

the receiving including receiving the partial URL from the requestor prior to the requestor performing an action indicating entry of a complete URL that includes the partial URL;

obtaining a set of complete URLs corresponding to the partial URL, the complete URLs previously submitted by a community of users using a plurality of client devices;

ordering the set of complete URLs in accordance with a ranking criteria;

conveying the set as ordered to the requestor; and

wherein the obtaining includes;

identifying a plurality of previously submitted historical complete URLs corresponding to the partial URL;

ordering at least a subset of the plurality of previously submitted historical complete URLs in accordance with the ranking criteria; and

identifying the set of complete URLs from the subset as ordered.

5. The method of claim 4, wherein:

the identifying includes identifying the plurality of previously submitted historical complete URLs from historical complete URLs submitted by the community of users; and

ordering includes ordering the subset in accordance with a frequency of submission of each complete URL in the subset.

6. The method of claim 4, wherein:

the identifying includes identifying the plurality from historical complete URLs submitted by the community of users; and

ordering includes ordering the subset in accordance with an importance factor associated with each complete URL in the subset.

7. The method of claim 4, further including generating, prior to receiving the partial URL, data representing the plurality of previously submitted complete URLs from URLs previously submitted by the community of users.

8. The method of claim 4, further including:

determining related URL request information from the partial URL;

identifying at least one obtained complete URL relevant to the related URL request information; and

including the at least one obtained complete URL relevant to the related URL request information in the subset.

9. The method of claim 4, wherein the obtaining further includes identifying at least one complete URL in accordance with a modified spelling of the partial URL.

10. A computer-implemented program product, for use with a computer system, the computer-implemented program product comprising:

one or more computer programs stored on a computer readable storage medium, which when executed by a processor cause the computer system;

to receive from a requestor a partial URL;

wherein the partial URL is received from the requestor prior to the requestor performing an action indicating entry of a complete URL that includes the partial URL;

to obtain a set of complete URLs previously submitted by a community of users, the complete URLs corresponding to the partial URL and ordered in accordance with a ranking criteria;

to convey the set of ordered complete URLs to the requestor; and

prior to receiving the partial URL;

to identify a set of historical complete URLs previously submitted by a community of users, each of the complete URLs in the set of historical complete URLs having at least one ranking value associated with the complete URL; and

to generate a plurality of ordered subsets of the identified set of historical complete URLs, each ordered subset of historical complete URLs including a subset of the identified set of historical complete URLs ordered in accordance with the at least one ranking value associated with the historical complete URLs in the subset;

wherein the one or more computer programs include instructions stored on a computer readable storage medium, which when executed cause the computer system to access one of the ordered subsets of historical complete URLs, selected in accordance with the received partial URL.

11. A computer-implemented program product, for use with a computer system, the computer-implemented program product comprising:

one or more computer programs stored on a computer readable storage medium, which when executed by a processor cause the computer system;

to receive from a requestor a partial URL, wherein the partial URL is received from the requestor prior to the requestor performing an action indicating entry of a complete URL that includes the partial URL;

to obtain a set of complete URLs previously submitted by a community of users, the complete URLs corresponding to the partial URL and ordered in accordance with a ranking criteria;

to convey the set of ordered complete URLs to the requestor; and

prior to receiving the partial URL;

to identify a plurality of sets, each of the plurality of sets associated with a portion of a complete URL and comprising a plurality of historical complete URLs previously submitted by the community of users, each complete URL having at least one respective ranking value; and

for at least a portion of the plurality of sets, to order the complete URLs in the set in accordance with the at least one respective ranking value;

wherein the one or more computer programs include instructions stored on a computer readable storage medium, which when executed cause the computer system to identify the obtained set of complete URLs, from among the plurality of sets, wherein the obtained set corresponds to the received partial URL.

12. A computer-implemented program product, for use with a computer system, the computer-implemented program product comprising:

one or more computer programs stored on a computer readable storage medium, which when executed by a processor cause the computer system;

to receive a partial URL from a requester, wherein the partial URL is received from the requestor prior to the requestor performing an action indicating entry of a complete URL that includes the partial URL;

to obtain an ordered set of complete URLs corresponding to the partial URL, by identifying a plurality of historical complete URLs previously submitted by a community of users corresponding to the partial URL and ordering at least a subset of the plurality in accordance with the ranking criteria, wherein the obtained ordered set of complete URLs comprises the ordered subset;

to convey the ordered set of complete URLs to the requestor; and

to generate, prior to receiving the partial URL, data representing the plurality of historical complete URLs previously submitted by the community of users.

13. The computer-implemented program product of claim 12, wherein the one or more computer programs include instructions stored on the computer readable storage medium, which when executed by a processor cause the computer system:

to order the subset in accordance with a historical frequency of submission of each complete URL in the subset.

14. The computer-implemented program product of claim 12, wherein the one or more computer programs include instructions stored on the computer readable storage medium, which when executed by a processor cause the computer system:

to order the subset in accordance with an importance factor of each complete URL in the subset.

15. The computer-implemented program product of claim 12, wherein the one or more computer programs further include instructions stored on the computer readable storage medium, which when executed by a processor cause the computer system:

to determine related URL request information from the partial URL;

to identify at least one complete URL relevant to the related URL request information; and

to include the at least one complete URL relevant to the related URL request information in the subset.

16. The computer-implemented program product of claim 12, wherein the one or more computer programs include instructions stored on the computer readable storage medium, which when executed by a processor cause the computer system to identify at least one complete URL in accordance with a modified spelling of the partial URL.

17. A system for processing URL information, comprising:

one or more processors for executing programs; and

memory to store data and to store programs to be executed by the one or more processors, the memory storing;

a receiving module for receiving a partial URL from a requester, wherein the partial URL is received from the requestor prior to the requestor performing an action indicating entry of a complete URL that includes the partial URL;

a prediction module for obtaining a set of complete URLs corresponding to the partial URL;

a transmission module for sending the set of complete URLs to the requestor;

a set of historical complete URLs previously submitted by the community of users, each of the complete URLs in the set of historical complete URLs having an associated frequency of submission information; and

a plurality of ordered subsets of historical complete URLs generated from the set of historical complete URLs, each subset ordered in accordance with the associated frequency of submission information;

wherein the prediction module is configured to obtain one of the ordered subsets as the obtained set of complete URLs corresponding to the received partial URL.

18. The system of claim 17 wherein the memory further stores:

a plurality of time/date values, each associated with a respective complete URL in the set of complete URLs; and

an ordering module for ordering the set of complete URLs in accordance with the time/date values.

19. The system of claim 17, wherein the prediction module is configured to identify at least one complete URL in accordance with a modified spelling of the URL request information.

20. The system of claim 17, wherein the memory further stores a personalization module for modifying the set based on characteristics associated with a user.

21. The system of claim 17, wherein the memory further stores:

a time/response module for determining that no selection corresponding to a sent complete URL is received from the requestor within a predetermined time period; and

wherein the transmission module is configured to send, in response to the time/response module, a subsequent set of complete URLs ordered in accordance with the ranking function.

22. A system for processing URL information, comprising:

one or more processors for executing programs; and

memory to store data and to store programs to be executed by the one or more processors, the memory storing;

a receiving module for receiving a partial URL from a requester, wherein the partial URL is received from the requestor prior to the requestor performing an action indicating entry of a complete URL that includes the partial URL;

a prediction module for obtaining a set of complete URLs corresponding to the partial URL;

a transmission module for sending the set of complete URLs to the requester;

a set of historical complete URLs previously submitted by the community of users, each of the complete URLs in the set of historical complete URLs having an associated importance factor; and

a plurality of ordered subsets of historical complete URLs generated from the set of historical complete URLs, each subset ordered in accordance with the associated importance factor;

wherein the prediction module is configured to obtain one of the ordered subsets as the obtained set of complete URLs corresponding to the received partial URL.

23. A system for processing URL information, comprising:

one or more processors for executing programs; and

memory to store data and to store programs to be executed by the one or more processors, the memory storing;

data representing historical complete URLs previously submitted by a community of users;

a receiving module for receiving a partial URL from a requester, wherein the partial URL is received from the requestor prior to the requestor performing an action indicating entry of a complete URL that includes the partial URL;

a prediction module for obtaining a set of complete URLs previously submitted by the community of users, ordered in accordance with a ranking function, the set relevant to the partial URL; and

a transmission module for sending the set of complete URLs to the requestor;

instructions to generate, prior to receiving the partial URL, the data representing the historical complete URLs;

an identification module for identifying historical complete URLs relevant to the partial URL from the data representing the historical complete URLs previously submitted by the community of users; and

an ordering module for ordering at least a subset of the identified historical complete URLs in accordance with the ranking function.

24. The system of claim 23, wherein the memory further stores:

a plurality of frequency of submission values, each associated with a respective one of the complete URLs previously submitted,

and

wherein the ordering module orders the subset in accordance with the frequency of submission values.

25. The system of claim 23, wherein the memory further stores:

a plurality of importance factors, each associated with a respective one of the complete URLs previously submitted,

and

wherein the ordering module orders the subset in accordance with the importance factors.

26. The system of claim 23, wherein the memory further stores:

a concept module for determining related information from the partial URL; and

the subset includes at least one complete URL relevant to the related information.