US5953006A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods and apparatus for detecting and displaying similarities in large data sets
Assignee: Nokia of America Corp
•
Filing: 1992-03-18
•
Granted: 1999-09-14
•
Expires: 2012-03-18
Abstract
Abstract Interactive Methods and apparatus for studying similarities of values in very large data sets. The methods and apparatus employ a dotplot in an interactive graphical user interface to make the relationship between the similarities and the data set visible. A variety of filtering, weighting, and compression techniques make it possible to employ the dot plot with sequences of more than 10,000 tokens and to interactively magnify the dot plot, change weighting and display quantization, and view the underlying data. Also disclosed is a technique which is employed in the apparatus for identifying long sequences of similar tokens. The apparatus is used in the study of large bodies of text and code.
Inventors
- 👤 Brenda Sue Baker
- 👤 Kenneth Ward Church
- 👤 Jonathan Isaac Helfman
- 👤 Brian W. Kernighan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 11:45
CPC Classifications
G; G09; G09G; G09G5/00; G06; G06F; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90348; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99936
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
155 words
Apparatus for displaying similarities between lines of text in a sequence of n lines of text, the apparatus comprising: means for representing a n×n matrix wherein there is a first mark in element (i,j) of the matrix if a comparison of line (i) with line (j) indicates that line (i) and line (j) have similar values; means for mapping the n×n matrix onto a display matrix, the mapping being done such that second marks indicating significant first marks are displayed in the display matrix; pointing means for selecting a point in the display matrix; first attribute display means for responding when the pointing means designates a point in the display matrix onto which the element for line (i) and line (j) is mapped by displaying a set of lines including line (i); and second attribute display means for responding when the pointing means designates the point by displaying a set of lines including line (j).
Claim 2
Dependent Claim
155 words
Apparatus for displaying similarities between lines of text in a sequence of n lines of text, the apparatus comprising: means for representing a n×n matrix wherein there is a first mark in element (i,j) of the matrix if a comparison of line (i) with line (j) indicates that line (i) and line (j) have similar values; means for mapping the n×n matrix onto a display matrix, the mapping being done such that second marks indicating significant first marks are displayed in the display matrix; pointing means for selecting a point in the display matrix; first attribute display means for responding when the pointing means designates a point in the display matrix onto which the element for line (i) and line (j) is mapped by displaying a set of lines including line (i); and second attribute display means for responding when the pointing means designates the point by displaying a set of lines including line (j).
Claim 3
Dependent Claim
124 words
Apparatus for displaying similarities between lines of text in a sequence of n lines of text, the apparatus comprising: means for representing a n×n matrix wherein there is a first mark in element (i,j) of the matrix if a comparison of line (i) with line (j) indicates that line (i) and line (j) have similar values; and means for mapping the n×n matrix onto a display matrix, the mapping being done such that second marks indicating significant first marks are displayed in the display matrix, wherein the means for representing the n×n matrix includes means for modifying the data to produce tokens which are more easily comparable than the tokens of the data; and the comparison is done using the more easily comparable tokens.
Claim 4
Dependent Claim
124 words
Apparatus for displaying similarities between lines of text in a sequence of n lines of text, the apparatus comprising: means for representing a n×n matrix wherein there is a first mark in element (i,j) of the matrix if a comparison of line (i) with line (j) indicates that line (i) and line (j) have similar values; and means for mapping the n×n matrix onto a display matrix, the mapping being done such that second marks indicating significant first marks are displayed in the display matrix, wherein the means for representing the n×n matrix includes means for modifying the data to produce tokens which are more easily comparable than the tokens of the data; and the comparison is done using the more easily comparable tokens.
Claim 5
Dependent Claim
108 words
Apparatus for displaying values of an attribute of records in a sequence of n records, the apparatus comprising matrix display means (405) which displays a representation of an n×n matrix wherein each element (i,j) of the matrix represents record (i) and record (j) and pointing means (439) for selecting one element in the representation; and the apparatus being characterized by attribute display means (423,425) for responding when the pointing means designates the element for the record (i) and the record (j) by displaying the values of the attribute for a first set of records including the record (i) and a second set of records including the record (j).
Claim 6
Dependent Claim
108 words
Apparatus for displaying values of an attribute of records in a sequence of n records, the apparatus comprising matrix display means (405) which displays a representation of an n×n matrix wherein each element (i,j) of the matrix represents record (i) and record (j) and pointing means (439) for selecting one element in the representation; and the apparatus being characterized by attribute display means (423,425) for responding when the pointing means designates the element for the record (i) and the record (j) by displaying the values of the attribute for a first set of records including the record (i) and a second set of records including the record (j).
Claim 7
Dependent Claim
154 words
Apparatus for displaying similarities between sequences of tokens on a display device comprising: means (702) for producing the tokens in the sequences from data; and means (704) for receiving the tokens and making a dotplot (405) representing a comparison of each of the tokens in one of the sequences with all of the tokens in another of the sequences and providing the dotplot to the display device, the apparatus being characterized in that: the means for making the dotplot is able to make a dotplot wherein each sequence of tokens being compared contains at least n tokens, where n >>10,000; and the means for making the dotplot makes the dotplot of a size such that the dotplot fits in its entirety on the display device; and the means for obtaining the tokens includes means (1602) for modifying the data to produce tokens which are more easily comparable than tokens produced from the unmodified data.
Claim 8
Dependent Claim
154 words
Apparatus for displaying similarities between sequences of tokens on a display device comprising: means (702) for producing the tokens in the sequences from data; and means (704) for receiving the tokens and making a dotplot (405) representing a comparison of each of the tokens in one of the sequences with all of the tokens in another of the sequences and providing the dotplot to the display device, the apparatus being characterized in that: the means for making the dotplot is able to make a dotplot wherein each sequence of tokens being compared contains at least n tokens, where n >>10,000; and the means for making the dotplot makes the dotplot of a size such that the dotplot fits in its entirety on the display device; and the means for obtaining the tokens includes means (1602) for modifying the data to produce tokens which are more easily comparable than tokens produced from the unmodified data.
Claim 9
Dependent Claim
28 words
The apparatus set forth in claim 4 further characterized in that: the means for modifying the data replaces portions of the data with a symbol representing a parameter.
Claim 10
Dependent Claim
39 words
The apparatus set forth in claim 5 further characterized in that: the means for making the dotplot includes means (901) for weighting the significance of each comparison and representing only the results of more significant comparisons in the dotplot.
Claim 11
Dependent Claim
79 words
The apparatus set forth in claim 6 further characterized in that: each token has a type; the apparatus includes means (1001) for determining the frequency with which tokens of each type occur in the data; the dotplot indicates comparisons in which one token equals another token; and the means for weighting the significance of each comparison is means (1001) for weighting the significance inversely to the frequency of tokens having the type of the tokens which equal each other.
Claim 12
Dependent Claim
68 words
The apparatus set forth in claim 5 further characterized by: pointing means (439) for selecting a point in the dotplot representing the comparison of token (i) in one sequence with token (j) in another sequence; and means (401) for displaying a first portion (423) of the data which contains token (i) and a second portion (425) of the data which contains token (j) in addition to the dotplot.
Claim 13
Dependent Claim
30 words
The apparatus set forth in claim 5 further characterized in that: the means for displaying further displays an uncompressed dot plot (424) of a first region around the selected point.
Claim 14
Dependent Claim
37 words
The apparatus set forth in claim 9 further characterized in that: the means for displaying further displays an uncompressed dotplot (437) of a second region around the selected point which corresponds to the first and second portion.
Claim 15
Dependent Claim
64 words
The apparatus set forth in claim 8 further characterized in that: the means for displaying further displays a first histogram (431) of the frequencies of tokens having the types of the tokens in the data shown in the first portion and a second histogram (433) of the frequencies of tokens having the types of the tokens in the data shown in the second portion.
Claim 16
Dependent Claim
29 words
The apparatus set forth in claim 4 further characterized in that: the means for making the dotplot includes means (1301) for performing only more significant ones of the comparisons.
Claim 17
Dependent Claim
61 words
The apparatus set forth in claim 12 further characterized in that: each token has a type; the apparatus includes means (1001) for determining the frequency with which tokens of each type occur in the data; and the means for performing only more significant ones of the comparisons performs comparisons only of tokens belonging to types having frequencies smaller than a threshold.
Claim 18
Dependent Claim
24 words
The apparatus set forth in claim 4 further characterized in that: the tokens are values of an attribute of records in a sequence thereof.
Claim 19
Dependent Claim
18 words
The apparatus set forth in claim 4 further characterized in that: the tokens are words in a text.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-09-13 | 2003-03-15 | 2003-09-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-09-13 | 2007-03-15 | 2007-09-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-09-13 | 2011-03-15 | 2011-09-14 | $7700.00 | Window Closed / Lapsed |