Scalable current leaderboard using delta-encoded updates

• US 9,489,447 B2
• Filed: 02/21/2014
• Issued: 11/08/2016
• Est. Priority Date: 02/21/2014
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wollenstein, Derek Alexander, Rodney, Daniel Alan, Sakai, Haruyoshi, Martin, Steve
• Primary Examiner(s): Morrison, Jay
• Application Number:
  US14/186,209
• Publication Number:
  US 20150242434A1
• Time in Patent Office: 991 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: A63F 13/30 Interconnection arrangements between game servers and game devices; Interconnection arrangements between game devices; Interconnection arrangements between game servers
• CPC Class Codes: A63F 13/79 involving player-related data, e.g. identities, accounts, preferences or play histories
• CPC Class Codes: A63F 13/798 for assessing skills or for ranking players, e.g. for generating a hall of fame computing the game score A63F13/46
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

Systems and techniques are provided for providing a scalable current leaderboard. Entries may be received. The entries may include an identifier and a score. The entries may be sorted according to a sorting criterion to obtain a leaderboard. The entries may be ranked with a rank according to the position of the entry on the leaderboard. The entry may include the rank. The leaderboard may be divided into buckets. Each bucket may include consecutive entries from the leaderboard. One of the entries may be included at the end of a first buckets and at the beginning of a second buckets. The buckets may be ordered sequentially. The bucket may be updated with score versions to produce an updated bucket, where the score versions may include new versions and old versions.

Claims

1. A computer-implemented method performed by a data processing apparatus comprising a snapshot generator, a server and a storage, the method comprising:

receiving, by the snapshot generator, entries, wherein each of the entries comprises an identifier and a score;

sorting, by the snapshot generator, the entries by the scores according to a sorting criteria to obtain a leaderboard;

ranking, by the snapshot generator, each of the entries with a rank according to the position of the entry on the leaderboard, wherein each of the entries further comprises the rank;

dividing, by the snapshot generator, the entries from the leaderboard into a plurality of groups, wherein each of the groups comprises consecutive entries from the leaderboard and at least one of the entries is included both in a position at the end of a first of the groups and at the beginning of a second of the groups, and wherein the groups are ordered sequentially;

storing, in the storage, the leaderboard in the form of the groups;

updating, by the snapshot generator, the first group with at least one score version comprising an entry that includes an addition indicator;

sorting, by the snapshot generator, the entries in the first group according to the sorting criteria to obtain an updated group; and

transmitting, by the server to the client device, the updated group.

2. The computer-implemented method of claim 1, further comprising:

receiving, by the snapshot generator, a request for at least a portion of the leaderboard, wherein the request comprises at least one item selected from the group consisting of;

an identifier for a desired entry, a score for a desired entry, a rank for a desired entry, and a general request for the leaderboard associated with a default desired entry; and

identifying, by the snapshot generator, the first group from the plurality of groups that includes the desired entry.

3. The computer-implemented method of claim 2, wherein the at least one score version comprises an entry for an old version associated with an entry for a new version, and the old version comprises one item selected from the group consisting of an entry that was in the entries sorted to obtain the leaderboard, and an entry that comprises the addition indicator.

4. The computer-implemented method of claim 3, wherein the entry for the old version comprises the addition indicator when the entry for the new version is to be added to the sorted listed of entries according to one of:

a user action, and the identifier for the entry for the new version is not in any other of the entries in the leaderboard.

5. The computer-implemented method of claim 2, wherein the at least one score version comprises an entry for a new version not associated with an entry for an old version, and the new version comprises one item selected from the group consisting of:

an entry that was not in the entries sorted to obtain the leaderboard, and an entry that comprises a removal indicator.

6. The computer-implemented method of claim 5, wherein the entry for the new version comprises a removal indicator indicating that the entry for the old version is to be removed from the sorted listed of entries according to one of a user action and an administrative action.

7. The computer-implemented method of claim 2, wherein the entry for the new version is not associated with an entry for an old version when the entry for the new version comprises an identifier not already in an entry in the leaderboard.

8. The computer-implemented method of claim 2, wherein updating the first group, sorting the entries in the first group, and ranking the entries in the first group each further comprise not changing the stored first group.

9. The computer-implemented method of claim 2, wherein the first group comprises a group rank, and wherein identifying, by the snapshot generator, the first group from the plurality of groups that includes the desired entry further comprises:

identifying, by the snapshot generator, the first group from among groups based on at least one of the identifier, the score, and the rank for the desired entry,

wherein the first group identified based on the score comprises the first group with the highest group rank and with a worst score that is worse than the score for the desired entry, and

wherein the first group identified based on the rank comprises the first group preceding the group with highest group rank that is also lower than the rank for the desired entry.

10. The computer-implemented method of claim 9, wherein the group rank of the first group is updated based on the score versions for entries in groups with higher group ranks.

11. The computer-implemented method of claim 10, wherein ranking the entries in the first group is based on the group rank of the group.

12. The computer-implemented method of claim 2, further comprising:

receiving, by the snapshot generator, an entry;

storing, in the storage, the received entry with the entries;

storing, in the storage, the received entry with the score versions as a score version comprising a new version and an old version, the new version comprising the received entry and the old version comprising an entry from the entries with a same identifier as the received entry;

discarding, by the snapshot generator, the score version from the score versions when the entries are sorted to obtain the leaderboard.

13. The computer-implemented method of claim 2, wherein the default desired entry comprises a rank of 1.

14. The computer-implemented method of claim 1, wherein the at least one entry is included in an overlap section of the first and second groups, and wherein the number of entries included in each overlap section is determined based the maximum number of entries displayed at one time by a client device.

15. The computer-implemented method of claim 14, wherein the number of entries in each overlap section is equal to or greater than one less than the maximum number of entries displayed at one time by the client device.

16. The computer-implemented method of claim 14, wherein the number of the entries in each overlap section is set such that the client device does not require two groups simultaneously to display any sequence of consecutive entries from the leaderboard.

17. The computer-implemented method of claim 1, wherein the score is associated with a game.

18. The computer-implemented method of claim 1, wherein the identifier is one of a real name, a user name, a group name, and an identification number.

19. The computer-implemented method of claim 1, wherein the receiving, sorting, ranking, and dividing are part of one of a leaderboard build and a leaderboard rebuild.

20. The computer-implemented method of claim 19, wherein the leaderboard rebuild is triggered by the accumulation of a preset number of score versions.

21. A computer-implemented method performed by a client device in communication with a computer that comprises a snapshot generator, a server and a storage, the method comprising:

transmitting, by the client device, a request for a leaderboard, wherein the request comprises at least one of an identifier for a desired entry, a score for a desired entry, a rank for a desired entry, and a general request for the leaderboard associated with a default desired entry, wherein entries for the leaderboard are divided into a plurality of groups, wherein each of the groups comprises consecutive entries from the leaderboard and at least one of the entries is included both in a position at the end of a first of the groups and at the beginning of a second of the groups, and wherein the groups are ordered sequentially, wherein the first group is updated with at least one score version comprising an entry that includes an addition indicator to indicate an addition of the desired entry into the first group, and wherein the entries in the first group are sorted according to a sorting criteria to obtain an updated group;

receiving, by the client device, the updated group comprising the desired entry; and

displaying the desired entry and entries consecutive with the desired entry from the updated group.

22. The computer-implemented method of claim 21, further comprising:

transmitting a second request for the leaderboard, where the second request comprises a request for an entry not in the updated group;

discarding the updated group;

receiving a second updated group comprising the desired entry; and

displaying the desired entry and entries consecutive with the desired entry from the second updated group.

23. The computer-implemented method of claim 22, wherein the displayed entries consecutive with the desired entry from the first group and the displayed entries consecutive with the desired entry from the second group comprise at least one of the same entry.

24. The computer-implemented method of claim 21, wherein the leaderboard is associated with a game.

25. A computer-implemented system for stitching tables comprising:

a storage comprising scores, score versions, and a leaderboard, wherein the leaderboard comprises groups, and configured to receive entries and store the entries with the scores and the score versions;

a snapshot generator configured to generate the leaderboard from the scores and divide the leaderboard into the groups, wherein each of the groups comprises consecutive entries from the leaderboard and at least one of the entries is included both in a position at the end of a first of the groups and at the beginning of a second of the groups, wherein the groups are ordered sequentially, wherein the first group is updated with at least one score version comprising an entry that includes an addition indicator, and wherein the entries in the first group are sorted according to a sorting criteria to obtain an updated group; and

a request server, coupled to the storage and configured to receive requests for the leaderboard, receive one of the groups, update the one of the groups with the score versions to generate an updated group, and transmit the updated group.

26. The computer-implemented system of claim 25, wherein the entries and requests are received from a client device, and wherein the updated group is transmitted to the client device.

27. The computer-implemented system of claim 26, wherein the client device is a mobile computing device.

28. The computer-implemented system of claim 25, wherein the leaderboard is associated with a game.

29. The computer-implemented system of claim 25, wherein the groups comprise overlap sections.

30. The computer-implemented system of claim 25, wherein the scores comprise entries, and wherein each entry comprises an identifier and a score, wherein the score is an ordinal value.

31. The computer-implemented system of claim 25, wherein the snapshot generator is further configured to generate the leaderboard by assigning ranks to the entries for the scores.

32. A system comprising:

one or more computers, wherein at least one of the one or more computers comprises a snapshot generator and a server, and one or more storage devices storing instructions which are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

receiving, by the snapshot generator, entries, wherein each of the entries comprises an identifier and a score;

sorting, by the snapshot generator, the entries by the scores according to a sorting criteria to obtain a leaderboard;

ranking, by the snapshot generator, each of the entries with a rank according to the position of the entry on the leaderboard, wherein each of the entries further comprises the rank;

dividing, by the snapshot generator, the entries from the leaderboard into groups, wherein each of the groups comprises consecutive entries from the leaderboard and at least two of the groups comprise a number of the same entries, wherein the same entries are in a position at the end of the first of the at least two groups and at the beginning of the second of the at least two groups, and wherein the groups are ordered sequentially;

updating, by the snapshot generator, the first group with at least one score version comprising an entry that includes an addition indicator;

sorting, by the snapshot generator, the entries in the first group according to the sorting criteria to obtain an updated group; and

storing, in the one or more storage devices, the leaderboard in the form of the groups.

33. The system of claim 32, wherein the instructions are operable, when executed by the one or more computers, to cause the one or more computers to perform operations further comprising:

receiving, by the snapshot generator, a request for the leaderboard, wherein the request comprises at least one of an identifier for a desired entry, a score for a desired entry, a rank for a desired entry, and a general request for the leaderboard associated with a default desired entry;

receiving the first group comprising the desired entry;

updating the first group with at least one score version, wherein the score version comprises an entry for an old version associated with an entry for a new version, the new version comprises one of an entry that was not in the entries sorted to obtain the leaderboard and an entry and an entry that comprises a removal indicator, and the old version comprises one of an entry that was in the entries sorted to obtain the leaderboard and the addition indicator; and

transmitting the updated group.