Apparatus and method for sorting items using longest increasing subsequence

• US 10,664,235 B2
• Filed: 11/03/2014
• Issued: 05/26/2020
• Est. Priority Date: 05/27/2014
• Status: Active Grant

• Current Assignee: SK Planet Co., Ltd. (SK Telecom Co., Ltd.)
• Original Assignee: SK Planet Co., Ltd. (SK Telecom Co., Ltd.)
• Inventors: Moon, Dong-Sun
• Primary Examiner(s): Almani, Mohsen
• Application Number:
  US14/898,441
• Publication Number:
  US 20170068515A1
• Time in Patent Office: 2,031 Days
• Field of Search: 707737
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 7/08 Sorting, i.e. grouping record carriers in numerical or other ordered sequence according to the classification of at least some of the information they carry by merging two or more sets of carriers in ordered sequence G06F7/16
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence

Abstract

An apparatus and method for sorting items using a longest increasing subsequence are disclosed. Item sorting may be performed by selecting excluded items, which correspond to a longest increasing subsequence, from among items in an item list, selecting update items by excluding the excluded items from the items, and performing update for the update items. It is possible to more efficiently use a system by selecting items to be updated from among various items in an item list and updating them to reduce the system workload for updating the items.

Claims

1. A method for updating stored information, comprising:

identifying, with a processor, an item list including a plurality of items, the plurality of items ranked in the item list according to a first ranking, each of the plurality of items in the first ranking associated with a plurality of index values comprising a primary index value and a secondary index value;

changing, with the processor, a ranking of the plurality of items in the item list from the first ranking to a second ranking that is different from the first ranking;

selecting, with processor, excluded items from among the plurality of items in the item list with the second ranking, the excluded items having rankings in the second ranking that correspond to a longest increasing subsequence within the second ranking, wherein the longest increasing sequence is a longest sequence among value increasing subsequences of rankings within the second ranking of the plurality of items in the item list and is a subsequence having a longest length when rankings are selected in ascending order;

selecting, with the processor, at least one remaining item of the plurality of items in the item list other than the excluded items as an update item; and

updating the primary index value and the secondary index value for the update item based on the second ranking without updating the primary index values and the secondary index values for the excluded items,

wherein the secondary index value for the update item is updated responsive to the primary index value for the update item matching the primary index value for an item adjacent to the update item in the second ranking, and

wherein the secondary index value is updated in consideration of the items having a difference in ranking of 1 in the second ranking.

2. The method of claim 1, further comprising:

generating, with the processor, item groups by grouping adjacent items in the item list;

selecting, with the processor, excluded groups, which correspond to the longest increasing subsequence of item from among the item groups; and

selecting, with the processor, update groups by excluding the excluded groups from the item groups,

updating the primary index values and the secondary index values of the update groups.

3. The method of claim 2, wherein generating item groups comprises grouping items having an increase in ranking of 1 therebetween among the plurality of items in the item list.

4. The method of claim 3, wherein the primary index values and the secondary index values of the excluded groups are not updated.

5. The method of claim 4, wherein selecting excluded items comprises selecting, as the excluded items, items of which rankings are comprised in the longest increasing subsequence from among the items, and

selecting excluded groups comprises finding the longest increasing subsequence using startup orders respectively corresponding to the item groups, and selecting, as the excluded groups, item groups corresponding to the startup orders comprised in the longest increasing subsequence.

6. The method of claim 5, wherein selecting excluded groups comprises, when the longest increasing subsequence is two or more in number, selecting the excluded groups in consideration of sizes of the item groups corresponding to the startup orders comprised in the longest increasing subsequences.

7. The method of claim 1, wherein the updated primary index values and the updated secondary index values are changed according to the second ranking.

8. An apparatus comprising:

memory; and

a processor configured to execute instructions stored in the memory and to;

receive an item list from a server, the item list including a plurality of items, the plurality of items ranked in the item list according to a first ranking, each of the plurality of items in the first ranking associated with a plurality of index values comprising a primary index value and a secondary index value;

changing with the processor, a ranking of the plurality of items in the item list from the first ranking to a second ranking that is different from the first ranking;

selecting, with the processor, excluded items from among the plurality of items in the item list with the second ranking, the excluded items having rankings in the second ranking that correspond to a longest increasing subsequence within the second ranking, wherein the longest increasing sequence is a longest sequence among value increasing subsequences of rankings within the second ranking of the plurality of items in the item list and is a subsequence having a longest length when rankings are selected in ascending order;

selecting, with the processor, at least one remaining item of the plurality of items in the item list other than the excluded items as an update item; and

updating the primary index value and the secondary index value for the update item based on the second ranking without updating the primary index values and the secondary index values for the excluded items,

wherein the secondary index value for the update item is updated responsive to the primary index value for the update item matching the primary index value for an item adjacent to the update item in the second ranking, and

wherein the secondary index value is updated in consideration of the items having a difference in ranking of 1 in the second ranking.

9. The apparatus of claim 8, wherein the processor is further configured to:

generate item groups by grouping adjacent items in the list;

select excluded groups, which correspond to the longest increasing subsequence, from among the item groups; and

select update groups by excluding the excluded groups from the item groups, wherein the processor is configured to update the primary index values and the secondary index values of the update groups among the items.

10. The apparatus of claim 9, wherein the processor is configured to group items having an increase in ranking of 1 therebetween among the plurality of items in the item list.

11. The apparatus of claim 10, wherein:

the processor is configured to select, as the excluded items, items having rankings in the second ranking comprised in the longest increasing subsequence from among the items, and

the processor is configured to find the longest increasing subsequence by using startup orders respectively corresponding to the item groups and to select, as the excluded groups, item groups corresponding to the startup orders comprised in the longest increasing subsequence.

12. The apparatus of claim 11, wherein the updated primary index values and the updated secondary index values are changed according to the second ranking.