Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Shape Grammar Extraction for Efficient Query-by-Sketch Pattern Matching in Long Time Series
Linköping University, Department of Science and Technology, Media and Information Technology. Linköping University, Faculty of Science & Engineering. (Information Visualization)
Linköping University, Department of Science and Technology, Media and Information Technology. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0003-4761-8601
Linköping University, Department of Science and Technology, Media and Information Technology. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Science and Technology, Media and Information Technology. Linköping University, Faculty of Science & Engineering.
2016 (English)Conference paper, Published paper (Refereed)
Abstract [en]

Long time-series, involving thousands or even millions of time steps, are common in many application domains but remain very difficult to explore interactively. Often the analytical task in such data is to identify specific patterns, but this is a very complex and computationally difficult problem and so focusing the search in order to only identify interesting patterns is a common solution. We propose an efficient method for exploring user-sketched patterns, incorporating the domain expert’s knowledge, in time series data through a shape grammar based approach. The shape grammar is extracted from the time series by considering the data as a combination of basic elementary shapes positioned across different am- plitudes. We represent these basic shapes using a ratio value, perform binning on ratio values and apply a symbolic approximation. Our proposed method for pattern matching is amplitude-, scale- and translation-invariant and, since the pattern search and pattern con- straint relaxation happen at the symbolic level, is very efficient permitting its use in a real-time/online system. We demonstrate the effectiveness of our method in a case study on stock market data although it is applicable to any numeric time series data.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2016. , p. 10p. 121-130
Series
IEEE Conference on Visual Analytics Science and Technology, ISSN 2325-9442
Keywords [en]
User-queries, Sketching, Time Series, Symbolic ap-proximation, Regular Expression, Shape Grammar
National Category
Engineering and Technology Computer Sciences Computer Systems Computer Vision and Robotics (Autonomous Systems) Bioinformatics (Computational Biology)
Identifiers
URN: urn:nbn:se:liu:diva-134334DOI: 10.1109/VAST.2016.7883518ISI: 000402056500013ISBN: 978-1-5090-5661-3 (print)OAI: oai:DiVA.org:liu-134334DiVA, id: diva2:1071346
Conference
2016 IEEE CONFERENCE ON VISUAL ANALYTICS SCIENCE AND TECHNOLOGY (VAST), October 23-28, Baltimore, USA
Funder
Swedish Research Council, 2013-4939Available from: 2017-02-03 Created: 2017-02-03 Last updated: 2018-01-13Bibliographically approved

Open Access in DiVA

Shape Grammar Extraction for Efficient Query-by-Sketch Pattern Matching in Long Time Series(1700 kB)85 downloads
File information
File name FULLTEXT02.pdfFile size 1700 kBChecksum SHA-512
68107c8e4ed8e101b0abfc19eb73c658931ec5de4ed3dd3cbe6c0ce8a4ccff3188187a1d547b661e8a1122c53ea9fa48b00041948aa0eaa6143b4943a1f6e6f8
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Muthumanickam, PrithivirajVrotsou, KaterinaCooper, MatthewJohansson, Jimmy
By organisation
Media and Information TechnologyFaculty of Science & Engineering
Engineering and TechnologyComputer SciencesComputer SystemsComputer Vision and Robotics (Autonomous Systems)Bioinformatics (Computational Biology)

Search outside of DiVA

GoogleGoogle Scholar
Total: 85 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 119 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf