Using dotplots for comparing and finding patterns in sequences of data points

• US 9,037,528 B2
• Filed: 05/06/2013
• Issued: 05/19/2015
• Est. Priority Date: 11/11/2008
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Helfman, Jonathan, Goldberg, Joseph H.
• Primary Examiner(s): Hill, Stanley K
• Application Number:
  US13/887,494
• Publication Number:
  US 20130246331A1
• Time in Patent Office: 743 Days
• Field of Search: None
• US Class Current: 706/54
• CPC Class Codes: A61B 3/113 for determining or recording eye movement
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids

Abstract

Embodiments of the invention provide systems and methods for analyzing sequential data. The sequential data can comprise a sequence of data points arranged in a particular order and thus representing a sequence. A number of such sequences can be analyzed, for example, to identify patterns or commonalities within the sequences or portions of sequences represented by the data. According to one embodiment, a method of identifying patterns in sequences of data points can comprise reading a set of sequential data. The sequential data can comprises a plurality of sequences and each of the plurality of sequences can represent an ordered sequence of tokens. A dotplot representing matches between each sequence of the plurality sequences can be generated. One or more patterns within the sequential data can then be identified based on the dotplot.

Claims

1. A method for identifying one or more patterns in a plurality of sequences, the method comprising:

reading a set of sequential data with an analysis system, wherein the sequential data comprises a plurality of sequences, each of the plurality of sequences representing an ordered sequence of tokens;

generating, with the analysis system, a dotplot based on and representing the tokens and-matches between each sequence of the plurality sequences;

identifying, with the analysis system, tokens representing at least one pattern within the sequential data based on the dotplot using a line fitting technique identifying linear relationships between the tokens represented in the dotplot;

removing, with the analysis system, tokens representing the identified at least one pattern from the dotplot; and

repeating, by the analysis system, said identifying and said removing until the line fitting technique fails to identify any linear relationship between remaining tokens of the dotplot.

2. The method of claim 1, wherein identifying linear relationships between the tokens comprises:

determining a dotplot sub-matrix plotting tokens from two sequences;

identifying a set of points in the sub-matrix that corresponds to matching tokens in corresponding sub-sequences;

filtering the identified points against a pre-determined high-pass threshold; and

fitting a linear regression line to the filtered points.

3. The method of claim 2, wherein identifying tokens representing at least one pattern further comprises:

computing variance criterion based on Euclidean distances between the regression line and the filtered points;

filtering the filtered points to those within the variance criterion;

re-fitting a linear regression line using the points within the variance criterion; and

identifying points within the variance criterion based on the recomputed linear regression line.

4. The method of claim 1, wherein the tokens represent data points comprising fixation points of eye tracking data and the sequences represent scanpaths.

5. The method of claim 1, wherein the tokens represent data points comprising Uniform Resource Locators (URLs) and the sequences represent sequences of requested URLs in a client web browsing session.

6. The method of claim 1, wherein the tokens represent data points comprising Uniform Resource Locators (URLs) and the sequences represent sequences of requested URLs in a web server log file.

7. The method of claim 1, wherein the tokens represent data points comprising text strings and the sequences represent sequences of the strings within one or more documents.

8. The method of claim 1, wherein the tokens represent data points comprising stock prices and the sequences represent the stock prices over time.

9. The method of claim 1, wherein the tokens represent genes and the sequences represent sequences of DeoxyriboNucleic Acid (DNA) or RiboNucleic Acid (RNA).

10. The method of claim 1, further comprising aggregating one or more identified patterns into an aggregate scanpath.

11. A system for identifying one or more patterns in a plurality of sequences, the system comprising:

a processor; and

a memory communicatively coupled with and readable by the processor and having stored therein a series of instructions which, when executed by the processor, cause the processor to read a set of sequential data, wherein the sequential data comprises a plurality of sequences, each of the plurality of sequences representing an ordered sequence of tokens, generate a dotplot based on and representing the tokens and matches between each sequence of the plurality sequences, identify tokens representing at least one pattern within the sequential data based on the dotplot using a line fitting technique identifying linear relationships between the tokens represented in the dotplot, remove tokens representing the identified at least one pattern from the dotplot, and repeat said identifying and said removing until the line fitting technique fails to identify any linear relationship between remaining tokens of the dotplot.

12. The system of claim 11, wherein identifying tokens representing at least one pattern within the sequential data based on the dotplot comprises identifying linear relationships between the tokens and wherein identifying linear relationships between the tokens comprises:

determining a dotplot sub-matrix plotting tokens from two sequences;

identifying a set of points in the sub-matrix that corresponds to matching tokens in corresponding sub-sequences;

filtering the identified points against a pre-determined high-pass threshold; and

fitting a linear regression line to the filtered points.

13. The system of claim 12, wherein identifying tokens representing at least one pattern further comprises:

computing variance criterion based on Euclidean distances between the regression line and the filtered points;

filtering the filtered points to those within the variance criterion;

re-fitting a linear regression line using the points within the variance criterion; and

identifying points within the variance criterion based on the recomputed linear regression line.

14. The system of claim 11, wherein the tokens represent data points selected from a group consisting of:

fixation points of eye tracking data;

Uniform Resource Locators (URLs);

text strings;

stock prices; and

genes.

15. The system of claim 11, further comprising aggregating one or more identified patterns into an aggregate scanpath.

16. A machine-readable memory device comprising a set of instructions stored therein which, when executed by a processor, cause the processor to identify one or more patterns in a plurality of sequences by:

reading a set of sequential data, wherein the sequential data comprises a plurality of sequences, each of the plurality of sequences representing an ordered sequence of tokens;

generating a dotplot based on and representing the tokens and-matches between each sequence of the plurality sequences;

identifying tokens representing at least one pattern within the sequential data based on the dotplot using a line fitting technique identifying linear relationships between the tokens represented in the dotplot;

removing tokens representing the identified at least one pattern from the dotplot; and

repeating said identifying and said removing until the line fitting technique fails to identify any linear relationship between remaining tokens of the dotplot.

17. The machine-readable memory device of claim 16, wherein identifying tokens representing at least one pattern within the sequential data based on the dotplot comprises identifying linear relationships between the tokens and wherein identifying linear relationships between the tokens comprises:

determining a dotplot sub-matrix plotting tokens of two sequences;

identifying a set of points in the sub-matrix that corresponds to matching tokens in the corresponding sub-sequences;

filtering the identified points against a pre-determined high-pass threshold; and

fitting a linear regression line to the filtered points.

18. The machine-readable memory device of claim 17, wherein identifying tokens representing at least one pattern further comprises:

computing variance criterion based on Euclidean distances between the regression line and the filtered points;

filtering the filtered points to those within the variance criterion;

re-fitting a linear regression line using the points within the variance criterion; and

identifying points within the variance criterion based on the recomputed linear regression line.

19. The machine-readable memory device of claim 16, wherein the tokens represent data points selected from a group consisting of:

fixation points of eye tracking data and wherein the sequences represent scanpaths;

Uniform Resource Locators (URLs) and wherein the sequences represent sequences of requested URLs in a client web browsing session or requested URLs in a web server log file;

text strings and wherein the sequences represent sequences of the strings within one or more documents;

stock prices and wherein the sequences represent the stock prices over time; and

genes and wherein the sequences represent sequences of DeoxyriboNucleic Acid (DNA) or RiboNucleic Acid (RNA).

20. The machine-readable memory device of claim 16, further comprising aggregating one or more identified patterns into an aggregate scanpath.