Methods and apparatus for lexicographically sorting cyclic data

Details Methods and apparatus for lexicographically sorting cyclic data Methods and apparatus for lexicographically sorting cyclic data

2007-04-24

2007-04-24

Wu, Yicun (Department: 2165)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

10689901

ABSTRACT:
Methods and apparatus for lexicographically sorting cyclic data are disclosed. In one illustrative example, a method of lexicographically sorting data includes the acts of receiving a set of N cyclic shifts of N characters identifiable by an array of indexes {0, 1, 2, . . . , N−1}; sorting the set of cyclic shifts based on a comparison of a first character of each cyclic shift; and for an nth sorting iteration of the set of cyclic shifts, where n=1, 2, 3, . . . , up to 2n>N: sorting at least a subset of the cyclic shifts which are identifiable by a subset array of indexes in the array in accordance with a previous sort of cyclic shifts associated with the subset array of indexes plus 2(n−1)*modulo(N); and repeating the sorting for a next nth sorting iteration as necessary until the set of cyclic shifts are lexicographically sorted.

REFERENCES:
patent: 5790599 (1998-08-01), Wright et al.
patent: 6075470 (2000-06-01), Little et al.
patent: 6751624 (2004-06-01), Christal et al.
patent: 2001/0051941 (2001-12-01), Tonomura
patent: WO 99/05828 (1999-02-01), None
patent: WO 99/23836 (1999-05-01), None
patent: WO 2004/043098 (2004-05-01), None
patent: WO 2004/084568 (2004-09-01), None
Sadakane, K., “A Fast Algorithm for Making Suffix Arrays and for Burrows-Wheeler Transformation,” Data Compression Conference, 1998 IEEE, pp. 129-138.
Mukherjee, A., et al., “Prototyping of Efficient Hardware Algorithms for Data Compression in Future Communication Systems,” Proceedings 12th International Workshop on Rapid System Prototyping, 2001 IEEE, pp. 58-63.
Manber, U., et al., “Suffix Arrays: A New Method For On-Line String Searches,” Siam Journal on Computing, Society for Industrial and Applied Mathematics, 1993, vol. 22, No. 5, pp. 935-948.
Nelson, M., “Data Compression with the Burrows Wheeler Transform,” Dr. Dobb's Journal, M&T Publ., Redwood City, CA, US, vol. 21, No. 9, Sep. 1996, pp. 46-50.
3rd Generation Partnership Project: 3GPP“Technical Specification Group Services and System Aspects”,Mar. 2004, 35 pgs, retreived from http://www.3gpp.org.
International Search Report & Written Opinion for PCT Application PCT/IB2005/002217, Jan. 5, 2005.

Affiliated with

Also associated with

Rating

Methods and apparatus for lexicographically sorting cyclic data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods and apparatus for lexicographically sorting cyclic data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for lexicographically sorting cyclic data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3737162