Patent ID: 7467047
Filing Date: 2008-12-16
Classification: G16B

Abstract:
1. A method of discovering one or more patterns in a set of k sequences of symbols, called a k-tuple, where k is greater than or equal to two, within an overall set of w sequences having sequence numbers 1, 2, . . . , w , the symbols being members of an alphabet, each sequence of symbols having respective lengths L 1 , L 2 , . . . , L w , comprising the steps of: a) translating the sequences of symbols into a table of ordered (symbol, position index) pairs, where the position index refers to the location of the symbol in a sequence; b) for each of the w sequences, grouping the (symbol, position index) pairs by symbol to form a respective master offset table, thus creating w master offset tables; c) using the position indices in the w master offset tables to determine the difference-in-position value between each occurrence of a symbol in one of the sequences and each occurrence of that same symbol in the other sequence in each master offset table, forming a k-tuple table associated with the k-tuple, the table comprising k columns, one of the k columns being a primary column and the remaining (k−1) columns being suffix columns, each column corresponding to one of the k sequences; d) creating a sorted k-tuple table by performing a multi-key sort on the k-tuple table, the sort keys being selected respectively from the difference-in-position values of the last suffix column (k e) identifying one or more patterns by collecting adjacent rows of the sorted k-tuple table whose suffix columns contain identical difference-in-position values, the relative positions of the symbols in each pattern being determined by the primary column position indices, the one or more patterns being common to the k sequences; and f) reading out the identified one or more patterns to a user.