An encoding method for multifield sorting and indexing

ABSTRACT

Sequences of character strings with an order relation imposed between sequences are considered. An encoding scheme is described which produces a single, order-preserving string from a sequence of strings. The original sequence can be recovered from the encoded string, and one sequence of strings precedes another if and only if the encoding of the first precedes the encoding of the second. The strings may be variable length, without a maximum length restriction, and no symbols need be reserved for control purposes. Hence any symbol may occur in any string. The scheme is useful for multifield sorting, multifield indexing, and other applications where ordering on more than one field is important.

REFERENCES

• 1: M. M. Astrahan , D. D. Chamberlin, Implementation of a structured English query language, Communications of the ACM, v.18 n.10, p.580-588, Oct. 1975 [doi>10.1145/361020.361215]
• 2: M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
• 3: Bayer, R., and McCreight, E.M. Organization and maintenance of large ordered indexes. Acta Informatica 1 (1972), 173-189.
• 4: Blasgen, M.W., and Eswaran, K.P. On the evaluation of queries in a relational database system. Res. Rep. RJ1745, IBM Res. Lab., San Jose, Calif., April 1976.
• 5: Per Brinch Hansen, Operating System Principles, Prentice Hall PTR, Upper Saddle River, NJ, 1973
• 6: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 7: V. Y. Lum, Multi-attribute retrieval with combined indexes, Communications of the ACM, v.13 n.11, p.660-665, Nov 1970 [doi>10.1145/362790.362794]

INDEX TERMS

Keywords:
encoding, lexicographic order, multifield indexes, searching, sorting