# US 2008/0306948 A1 · String and binary data sorting

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0306948 A1
- Document ID: US20080306948A1
- Status: Published application
- Kind: A1
- Application number: 11/760,523
- Filed: 2007-06-08
- Published: 2008-12-11
- Earliest claimed: 2007-06-08
- Assignees: Yahoo! Inc.
- Inventors: RadhaKrishna Uppala; Sreenivasulu Pokuri
- Web page: https://patentgrep.com/patent/US20080306948A1

## CPC

- G06F 16/90344: {by using string matching techniques}
- G06F 16/2425: {Iterative querying; Query formulation based on the results of a preceding query}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A device, system, and method are directed towards sorting a set of string or binary data items. A segment of a fixed size from each data item is combined with a pointer to the data item in a word. The words are sorted, and words having equivalent string/binary segments are grouped together. The groups are recursively sorted until no groups remain or the end of the string or binary data in a group is sorted. Methods of the invention include determining a segment size based on a size of a pointer item and a word size, so that a segment and a pointer fit within a word, allowing comparisons and data manipulation to be performed on words.

## Claims

### Claim 1

A method of sorting a plurality of string/binary data items with a computer system having a processor, comprising:
a) setting the plurality of string/binary data items to be a target set of data items;
b) storing a segment of each data item of the target set of data items to a working set of elements, each segment having an offset position P in its respective target string/binary data item and having a length less than or equal to a length N;
c) sorting the elements of the working set corresponding to the target set of data items;
d) determining whether at least one equivalence group exists such that each equivalence group includes equivalent elements of the working set corresponding to the target set of data items; and
e) if at least one equivalence group exists, for each of at least one of the at least one equivalence group, setting the data items of the plurality of string/binary data items corresponding to the equivalence group elements to be the target set of data items, and repeating method elements b-d by employing an offset position P based on a depth of the equivalence group; and
wherein at least one equivalence group is determined to exist and steps a-d are repeated at least one time.

### Claim 2 (depends on 1)

The method of claim 1, wherein repeating elements b-d is performed recursively, and the position P employed to store a segment is incremented at each increased level of recursion.

### Claim 3 (depends on 1)

The method of claim 1, wherein repeating elements b-d is performed recursively, and the position P employed to store a segment is incremented by N at each increased level of recursion.

### Claim 4 (depends on 1)

The method of claim 1, further comprising, after determining whether at least one equivalence group exists, not sorting elements that have been determined to not be in an equivalence group.

### Claim 5 (depends on 1)

The method of claim 1, further comprising sorting elements corresponding to each of the plurality of string/binary data items a number of times, the number of times corresponding to each element based on its corresponding inclusion in an equivalence group.

### Claim 6 (depends on 1)

The method of claim 1, wherein the length N is based on a word size corresponding to the processor.

### Claim 7 (depends on 1)

The method of claim 1, wherein the length N is based on a word size corresponding to the processor and a length of a reference value field sufficient to reference each of the plurality of string/data items.

### Claim 8 (depends on 1)

The method of claim 1, further comprising combining a reference value corresponding to each string/binary data item of the plurality of data items in a word with a respective element of the working set of elements, and wherein sorting the elements of the working set comprises sorting a set of words, each word containing a string and a reference value.

### Claim 9 (depends on 1)

The method of claim 1, wherein sorting the elements of the working comprises comparing a plurality of words, each word including a string and a reference value corresponding to one of the plurality of string/binary data items, wherein the string is in the high order bits of the word.

### Claim 10 (depends on 1)

The method of claim 1, wherein sorting the elements of the working set comprises sorting a set of word items, each word item comprising exactly one word corresponding to each data item of the working set of data items.

### Claim 11 (depends on 1)

The method of claim 1, wherein the plurality of string/binary data items includes string/binary data items of differing lengths, at least some of the string/binary data items having lengths greater than a word size, and wherein segments of the string/binary data items beyond the length N are selectively compared.

### Claim 12 (depends on 1)

A modulated data signal configured to include program instructions for performing the method of claim 1.

### Claim 13

A system for sorting a plurality of string/binary data items, comprising:
a) a processor;
b) means for extracting a first segment of each string/binary data item;
c) means for performing an intermediate sort of the first segment corresponding to each string/binary data item; and
d) means for selectively extracting and sorting a second segment of each string/binary data item.

### Claim 14 (depends on 13)

The system of claim 13, wherein the means for extracting combines each first segment with a corresponding reference pointer to a corresponding string/binary data item.

### Claim 15 (depends on 13)

The system of claim 13, wherein the means for extracting combines each first segment with a corresponding reference pointer to a corresponding string/binary data item in a corresponding word, and wherein the means for performing an intermediate sort sorts said words.

### Claim 16 (depends on 13)

The system of claim 13, wherein the length of each first segment is based on a word size and a size of a reference pointer to each string/binary data item.

### Claim 17

A processor readable medium that includes data, wherein the execution of the data provides for sorting a set of string/binary data items by enabling actions, including:
a) extracting a segment of each string/binary data item of the set of string/binary data items;
b) for each segment, combining the segment with a reference pointer to a corresponding string/binary data item of the set of string/binary data items to produce an element within a word;
c) sorting the elements;
d) determining whether at least one equivalence group exists, each equivalence group comprising elements having equivalent segments; and
e) selectively repeating actions a-d based on whether an element corresponding to a string/binary data item of the set of string/binary data items is in an equivalence group.

### Claim 18 (depends on 17)

The processor readable medium of claim 17, wherein the actions further comprise recursively performing actions a-e until a sort completion criteria is reached.

### Claim 19 (depends on 17)

The processor readable medium of claim 17, wherein the action of extracting a segment of each string/binary data item is performed a selected number of times for each string/binary data item, the number of times based on a length of the string/binary data item and a number of times a corresponding element is included in an equivalence group.

### Claim 20

A method of sorting a plurality of string/binary data items with a computer system having a processor, comprising:
a) storing a segment of each data item to a set of words, each segment having an offset position P in its respective string/binary data item and having a length less than or equal to a length N;
b) combining, with each word of the set of words, a pointer to a corresponding string/binary data item of the plurality of string/binary data items;
c) sorting the set of words;
d) determining whether at least one equivalence group exists such that each equivalence group includes equivalent segments of data; and
e) if at least one equivalence group exists, for each of at least one of the at least one equivalence group, extracting a second segment of each data item corresponding to the equivalence group elements, and combining, in respective words, each second segment with a pointer to a corresponding string/binary data item of the plurality of string/binary data items, and sorting the words containing each combination of second segments and pointers; and
wherein at least one equivalence group is determined to exist.
