Name
Title | ||
|---|---|---|
Supporting exact indexing of arbitrarily rotated shapes and periodic time series under Euclidean and warping distance measures |
Abstract | ||
|---|---|---|
Shape matching and indexing is important topic in its own right, and is a fundamental subroutine in most shape data mining
algorithms. Given the ubiquity of shape, shape matching is an important problem with applications in domains as diverse as
biometrics, industry, medicine, zoology and anthropology. The distance/similarity measure for used for shape matching must
be invariant to many distortions, including scale, offset, noise, articulation, partial occlusion, etc. Most of these distortions
are relatively easy to handle, either in the representation of the data or in the similarity measure used. However, rotation
invariance is noted in the literature as being an especially difficult challenge. Current approaches typically try to achieve
rotation invariance in the representation of the data, at the expense of discrimination ability, or in the distance measure,
at the expense of efficiency. In this work, we show that we can take the slow but accurate approaches and dramatically speed
them up. On real world problems our technique can take current approaches and make them four orders of magnitude faster without
false dismissals. Moreover, our technique can be used with any of the dozens of existing shape representations and with all
the most popular distance measures including Euclidean distance, dynamic time warping and Longest Common Subsequence. We further
show that our indexing technique can be used to index star light curves, an important type of astronomical data, without modification. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s00778-008-0111-4 | The Vldb Journal |
Keywords | Field | DocType |
Shape,Indexing,Dynamic time warping | Longest common subsequence problem,Image warping,Dynamic time warping,Similarity measure,Computer science,Euclidean distance,Algorithm,Pattern matching,Offset (computer science),Distance measures | Journal |
Volume | Issue | ISSN |
18 | 3 | 1066-8888 |
Citations | PageRank | References |
56 | 2.26 | 30 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eamonn J. Keogh | 1 | 11859 | 645.93 |
| Li Wei | 2 | 1006 | 44.62 |
| Xiaopeng Xi | 3 | 531 | 24.76 |
| Michail Vlachos | 4 | 1899 | 113.39 |
| Sang-Hee Lee | 5 | 287 | 20.03 |
| Pavlos Protopapas | 6 | 127 | 14.73 |