Shape grammar extraction for efficient query-by-sketch pattern matching in long time series

Shape grammar extraction for efficient query-by-sketch pattern matching in long time series. Muthumanickam, P. K., Vrotsou, K., Cooper, M., & Johansson, J. In 2016 IEEE Conference on Visual Analytics Science and Technology (VAST), pages 121–130, October, 2016. ISSN: null
doi abstract bibtex

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 amplitudes. 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 constraint 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.

@inproceedings{muthumanickam_shape_2016,
	title = {Shape grammar extraction for efficient query-by-sketch pattern matching in long time series},
	doi = {10.1109/VAST.2016.7883518},
	abstract = {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 amplitudes. 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 constraint 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.},
	booktitle = {2016 {IEEE} {Conference} on {Visual} {Analytics} {Science} and {Technology} ({VAST})},
	author = {Muthumanickam, Prithiviraj K. and Vrotsou, Katerina and Cooper, Matthew and Johansson, Jimmy},
	month = oct,
	year = {2016},
	note = {ISSN: null},
	keywords = {WHEN - Real-Time Applications, HOW - Pattern Analysis, Type of Work: Tool/Software, WHY - Explain ML Model / Debug Algorithm / Query Plan, HOW: sequence (string) based representation, HOW: sketch-based querying, HOW: symbolic approximation using shape grammar, Maybe related. Temporal pattern searching, WHY: find temporal patterns, WHY - Model Steering / Active Learning, ENCODING - Grammar},
	pages = {121--130},
	file = {IEEE Xplore Abstract Record:C\:\\Users\\conny\\Zotero\\storage\\78PMGV8R\\7883518.html:text/html}
}

Downloads: 0

{"_id":"mSqr4xqHa6L6hvKQk","bibbaseid":"muthumanickam-vrotsou-cooper-johansson-shapegrammarextractionforefficientquerybysketchpatternmatchinginlongtimeseries-2016","authorIDs":[],"author_short":["Muthumanickam, P. K.","Vrotsou, K.","Cooper, M.","Johansson, J."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"Shape grammar extraction for efficient query-by-sketch pattern matching in long time series","doi":"10.1109/VAST.2016.7883518","abstract":"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 amplitudes. 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 constraint 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.","booktitle":"2016 IEEE Conference on Visual Analytics Science and Technology (VAST)","author":[{"propositions":[],"lastnames":["Muthumanickam"],"firstnames":["Prithiviraj","K."],"suffixes":[]},{"propositions":[],"lastnames":["Vrotsou"],"firstnames":["Katerina"],"suffixes":[]},{"propositions":[],"lastnames":["Cooper"],"firstnames":["Matthew"],"suffixes":[]},{"propositions":[],"lastnames":["Johansson"],"firstnames":["Jimmy"],"suffixes":[]}],"month":"October","year":"2016","note":"ISSN: null","keywords":"WHEN - Real-Time Applications, HOW - Pattern Analysis, Type of Work: Tool/Software, WHY - Explain ML Model / Debug Algorithm / Query Plan, HOW: sequence (string) based representation, HOW: sketch-based querying, HOW: symbolic approximation using shape grammar, Maybe related. Temporal pattern searching, WHY: find temporal patterns, WHY - Model Steering / Active Learning, ENCODING - Grammar","pages":"121–130","file":"IEEE Xplore Abstract Record:C\\:\\\\Users\\o̧nny\\\\Zotero\\\\storage\\\\78PMGV8R\\\\7883518.html:text/html","bibtex":"@inproceedings{muthumanickam_shape_2016,\n\ttitle = {Shape grammar extraction for efficient query-by-sketch pattern matching in long time series},\n\tdoi = {10.1109/VAST.2016.7883518},\n\tabstract = {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 amplitudes. 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 constraint 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.},\n\tbooktitle = {2016 {IEEE} {Conference} on {Visual} {Analytics} {Science} and {Technology} ({VAST})},\n\tauthor = {Muthumanickam, Prithiviraj K. and Vrotsou, Katerina and Cooper, Matthew and Johansson, Jimmy},\n\tmonth = oct,\n\tyear = {2016},\n\tnote = {ISSN: null},\n\tkeywords = {WHEN - Real-Time Applications, HOW - Pattern Analysis, Type of Work: Tool/Software, WHY - Explain ML Model / Debug Algorithm / Query Plan, HOW: sequence (string) based representation, HOW: sketch-based querying, HOW: symbolic approximation using shape grammar, Maybe related. Temporal pattern searching, WHY: find temporal patterns, WHY - Model Steering / Active Learning, ENCODING - Grammar},\n\tpages = {121--130},\n\tfile = {IEEE Xplore Abstract Record:C\\:\\\\Users\\\\conny\\\\Zotero\\\\storage\\\\78PMGV8R\\\\7883518.html:text/html}\n}\n\n","author_short":["Muthumanickam, P. K.","Vrotsou, K.","Cooper, M.","Johansson, J."],"key":"muthumanickam_shape_2016","id":"muthumanickam_shape_2016","bibbaseid":"muthumanickam-vrotsou-cooper-johansson-shapegrammarextractionforefficientquerybysketchpatternmatchinginlongtimeseries-2016","role":"author","urls":{},"keyword":["WHEN - Real-Time Applications","HOW - Pattern Analysis","Type of Work: Tool/Software","WHY - Explain ML Model / Debug Algorithm / Query Plan","HOW: sequence (string) based representation","HOW: sketch-based querying","HOW: symbolic approximation using shape grammar","Maybe related. Temporal pattern searching","WHY: find temporal patterns","WHY - Model Steering / Active Learning","ENCODING - Grammar"],"downloads":0},"bibtype":"inproceedings","biburl":"https://raw.githubusercontent.com/JKU-ICG/provenance-survey/master/assets/data/main.bib?token=AFMAFPFPO73YUVEBH3EL22C6YQDJU","creationDate":"2020-05-12T16:18:25.017Z","downloads":0,"keywords":["when - real-time applications","how - pattern analysis","type of work: tool/software","why - explain ml model / debug algorithm / query plan","how: sequence (string) based representation","how: sketch-based querying","how: symbolic approximation using shape grammar","maybe related. temporal pattern searching","why: find temporal patterns","why - model steering / active learning","encoding - grammar"],"search_terms":["shape","grammar","extraction","efficient","query","sketch","pattern","matching","long","time","series","muthumanickam","vrotsou","cooper","johansson"],"title":"Shape grammar extraction for efficient query-by-sketch pattern matching in long time series","year":2016,"dataSources":["iLdxLZjd62Nd3rAFg"]}