AMONG implied constraints for two families of time-series constraints

Ekaterina Arafailova; Nicolas Beldiceanu; Helmut Simonis

doi:10.1007/978-3-319-66158-2_3

AMONG implied constraints for two families of time-series constraints

Ekaterina Arafailova
, Nicolas Beldiceanu
, Helmut Simonis

UBL

Research output: Chapter in Book/Report/Conference proceedings › Conference proceeding › peer-review

Abstract

We consider, for an integer time series, two families of constraints restricting the max, and the sum, respectively, of the surfaces of the elements of the sub-series corresponding to occurrences of some pattern. In recent work these families were identified as the most difficult to solve compared to all other time-series constraints. For all patterns of the time-series constraints catalogue, we provide a unique per family parameterised AMONG implied constraint that can be imposed on any prefix/suffix of a time-series. Experiments show that it reduces both the number of backtracks/time spent by up to 4/3 orders of magnitude.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming - 23rd International Conference CP 2017, Proceedings
Editors	J.Christopher Beck
Publisher	Springer Verlag
Pages	38-54
Number of pages	17
ISBN (Print)	9783319661575
DOIs	https://doi.org/10.1007/978-3-319-66158-2_3
Publication status	Published - 2017
Event	23rd International Conference on the Principles and Practice of Constraint Programming, CP 2017 - Melbourne, Australia Duration: 28 Aug 2017 → 1 Sept 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10416 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	23rd International Conference on the Principles and Practice of Constraint Programming, CP 2017
Country/Territory	Australia
City	Melbourne
Period	28/08/17 → 1/09/17

Access to Document

10.1007/978-3-319-66158-2_3

Cite this

Arafailova, E., Beldiceanu, N., & Simonis, H. (2017). AMONG implied constraints for two families of time-series constraints. In J. C. Beck (Ed.), Principles and Practice of Constraint Programming - 23rd International Conference CP 2017, Proceedings (pp. 38-54). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10416 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-66158-2_3

Arafailova, Ekaterina ; Beldiceanu, Nicolas ; Simonis, Helmut. / AMONG implied constraints for two families of time-series constraints. Principles and Practice of Constraint Programming - 23rd International Conference CP 2017, Proceedings. editor / J.Christopher Beck. Springer Verlag, 2017. pp. 38-54 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a3449edb85aa4fe0ad2d5819fa38efee,

title = "AMONG implied constraints for two families of time-series constraints",

abstract = "We consider, for an integer time series, two families of constraints restricting the max, and the sum, respectively, of the surfaces of the elements of the sub-series corresponding to occurrences of some pattern. In recent work these families were identified as the most difficult to solve compared to all other time-series constraints. For all patterns of the time-series constraints catalogue, we provide a unique per family parameterised AMONG implied constraint that can be imposed on any prefix/suffix of a time-series. Experiments show that it reduces both the number of backtracks/time spent by up to 4/3 orders of magnitude.",

author = "Ekaterina Arafailova and Nicolas Beldiceanu and Helmut Simonis",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 23rd International Conference on the Principles and Practice of Constraint Programming, CP 2017 ; Conference date: 28-08-2017 Through 01-09-2017",

year = "2017",

doi = "10.1007/978-3-319-66158-2\_3",

language = "English",

isbn = "9783319661575",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "38--54",

editor = "J.Christopher Beck",

booktitle = "Principles and Practice of Constraint Programming - 23rd International Conference CP 2017, Proceedings",

address = "Germany",

}

Arafailova, E, Beldiceanu, N & Simonis, H 2017, AMONG implied constraints for two families of time-series constraints. in JC Beck (ed.), Principles and Practice of Constraint Programming - 23rd International Conference CP 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10416 LNCS, Springer Verlag, pp. 38-54, 23rd International Conference on the Principles and Practice of Constraint Programming, CP 2017, Melbourne, Australia, 28/08/17. https://doi.org/10.1007/978-3-319-66158-2_3

AMONG implied constraints for two families of time-series constraints. / Arafailova, Ekaterina; Beldiceanu, Nicolas; Simonis, Helmut.
Principles and Practice of Constraint Programming - 23rd International Conference CP 2017, Proceedings. ed. / J.Christopher Beck. Springer Verlag, 2017. p. 38-54 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10416 LNCS).

Research output: Chapter in Book/Report/Conference proceedings › Conference proceeding › peer-review

TY - GEN

T1 - AMONG implied constraints for two families of time-series constraints

AU - Arafailova, Ekaterina

AU - Beldiceanu, Nicolas

AU - Simonis, Helmut

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - We consider, for an integer time series, two families of constraints restricting the max, and the sum, respectively, of the surfaces of the elements of the sub-series corresponding to occurrences of some pattern. In recent work these families were identified as the most difficult to solve compared to all other time-series constraints. For all patterns of the time-series constraints catalogue, we provide a unique per family parameterised AMONG implied constraint that can be imposed on any prefix/suffix of a time-series. Experiments show that it reduces both the number of backtracks/time spent by up to 4/3 orders of magnitude.

AB - We consider, for an integer time series, two families of constraints restricting the max, and the sum, respectively, of the surfaces of the elements of the sub-series corresponding to occurrences of some pattern. In recent work these families were identified as the most difficult to solve compared to all other time-series constraints. For all patterns of the time-series constraints catalogue, we provide a unique per family parameterised AMONG implied constraint that can be imposed on any prefix/suffix of a time-series. Experiments show that it reduces both the number of backtracks/time spent by up to 4/3 orders of magnitude.

UR - https://www.scopus.com/pages/publications/85028697736

U2 - 10.1007/978-3-319-66158-2_3

DO - 10.1007/978-3-319-66158-2_3

M3 - Conference proceeding

AN - SCOPUS:85028697736

SN - 9783319661575

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 38

EP - 54

BT - Principles and Practice of Constraint Programming - 23rd International Conference CP 2017, Proceedings

A2 - Beck, J.Christopher

PB - Springer Verlag

T2 - 23rd International Conference on the Principles and Practice of Constraint Programming, CP 2017

Y2 - 28 August 2017 through 1 September 2017

ER -

Arafailova E, Beldiceanu N, Simonis H. AMONG implied constraints for two families of time-series constraints. In Beck JC, editor, Principles and Practice of Constraint Programming - 23rd International Conference CP 2017, Proceedings. Springer Verlag. 2017. p. 38-54. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-66158-2_3

AMONG implied constraints for two families of time-series constraints

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this