Patent application EP21173490A (EP), filed 2021-05-12
Publication number: EP3910561A1
Title: COMPUTER-IMPLEMENTED METHOD, COMPUTING DEVICE AND COMPUTER PROGRAM FOR PERFORMING TIME-SERIES RECONSTRUCTION
Abstract: Embodiments relate to a computer-implemented method, a computing device and a computer program for performing time-series reconstruction using a quantum processing unit. The method comprises obtaining a discretized representation of a time-series to be reconstructed. The discretized representation comprises a first ordered set of segments. The method comprises calculating set-based representations of an overlap between the first ordered set of segments and of second ordered sets of segments of discretized representations of a plurality of further time-series. Each set-based representation represents an overlap between subsets of the first ordered set of segments and subsets of a second ordered set of segments. The method comprises selecting one or more subsets of the second ordered sets of segments using a quantum-processing unit. The selection is based on the set-based representations of the overlap. The one or more subsets of the second ordered sets of segments are selected such, that, in combination, the one or more subsets of the sets of segments approximate the first ordered set of segments. The method comprises reconstructing the time-series using the selected one or more subsets of the second ordered sets of segments. By preprocessing the time-series and generating the set-based representations, the time-series reconstruction can be mapped to the set cover-problem, which is solvable on a quantum processing unit.
IPC codes: G06N  10/    00            A I
G06N   5/    00            A I
G06N  10/    60            A I
G06N   5/    01            A I
Claims: number: 1
text: A computer-implemented method for performing time-series reconstruction, the method comprising:
number: 2
text: The method according to claim 1, wherein the set-based representations are calculated by performing a plurality of pair-wise comparisons of subsets of the first ordered set of segments and subsets of the second ordered sets of segments.
number: 3
text: The method according to claim 2, wherein each ordered set of segment is represented by a string of letters, wherein the plurality of pair-wise comparisons are performed by successively moving a string of letters representing the first ordered set of segments along a second string of letters representing one of the second ordered set of segments, wherein the overlapping letters of the two strings of letters are compared in a pairwise manner, wherein matches between the letters are recorded as subsets of the respective second ordered set of segments.
number: 4
text: The method according to one of the claims 1 to 3, wherein the quantum-processing unit selects the one or more subsets of the second ordered sets of segments using an approach for solving a set cover-problem.
number: 5
text: The method according to claim 4, wherein the quantum-processing unit selects the one or more subsets of the second ordered sets of segments from all of the second ordered sets of segments at once using the approach for solving the set cover-problem.
number: 6
text: The method according to one of the claims 1 to 5, wherein the discretized representation of the time-series to be reconstructed is a string-based representation of the time-series, with each segment of the first ordered set of segments being represented by a letter of the string.
number: 7
text: The method according to one of the claims 1 to 6, wherein the discretized representation of the time-series to be reconstructed is obtained by encoding (112) the time-series.
number: 8
text: The method according to claim 7, wherein the time-series is encoded using symbolic Fourier approximation or using a mean windows-based technique.
number: 9
text: The method according to one of the claims 7 or 8, wherein the discretized representation of the time-series is, for each segment, based on a dominant Fourier component of a portion of the time-series being represented by the segment.
number: 10
text: The method according to one of the claims 7 to 9, wherein the time-series is encoded (112) by dividing (114) the time-series into the ordered set of segments, assigning (116) each of the segments a letter representing the respective segment, and combining (118) the letters representing the segments to obtain a string representation of the time-series.
number: 11
text: The method according to one of the claims 1 to 10, wherein the plurality of further time-series are labeled, wherein the method comprises labeling (150) the reconstructed time-series based on labels of further time-series associated with the one or more subsets.
number: 12
text: The method according to claim 11, wherein the reconstructed time-series are labeled based on a label of a further time-series being associated with a largest subset of the one or more subsets,
or wherein the reconstructed time-series are labeled based on a label of a further time-series being associated with a largest proportion of subsets of the one or more subsets.
number: 13
text: A computer program having a program code for performing the method of one of the claims 1 to 12, when the computer program is executed on a computer, a processor, a quantum-processing unit and/or a programmable hardware component.
number: 14
text: A computation device (10) comprising:
Office action: search_report, dated 2021-11-17
Prior art cited: ref_id: - PATRICK SCHAFERMIKAEL HOGQVIST: "Proceedings of the 15th International Conference on Extending Database Technology", 2012, ACM, article "Sfa: a symbolic Fourier approximation and index for similarity search in high dimensional datasets", pages: 516 - 527
ref_type: npl
severity: background
ref_id: - ANDREW LUCAS: "Ising formulations of many np problems", FRONTIERS IN PHYSICS, vol. 2, no. 5, 2014, XP055650743, DOI: 10.3389/fphy.2014.00005
ref_type: npl
severity: background
ref_id: - STEVEN ELSWORTH ET AL: "Time Series Forecasting Using LSTM Networks: A Symbolic Approach", ARXIV.ORG, CORNELL UNIVERSITY LIBRARY, 201 OLIN LIBRARY CORNELL UNIVERSITY ITHACA, NY 14853, 12 March 2020 (2020-03-12), XP081620015
ref_type: npl
severity: background
ref_id: - GLOVER FRED ET AL: "Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models", 4OR, SPRINGER BERLIN HEIDELBERG, BERLIN/HEIDELBERG, vol. 17, no. 4, 26 November 2019 (2019-11-26), pages 335 - 371, XP036936647, ISSN: 1619-4500, [retrieved on 20191126], DOI: 10.1007/S10288-019-00424-Y
ref_type: npl
severity: background
ref_id: - SCHÄFER PATRICK ET AL: "SFA : a symbolic fourier approximation and index for similarity search in high dimensional datasets", PROCEEDINGS OF THE 15TH INTERNATIONAL CONFERENCE ON EXTENDING DATABASE TECHNOLOGY, EDBT '12, 1 March 2012 (2012-03-01), New York, New York, USA, pages 516 - 527, XP055811284, ISBN: 978-1-4503-0790-1, Retrieved from the Internet <URL:https://dl.acm.org/doi/pdf/10.1145/2247596.2247656> DOI: 10.1145/2247596.2247656
ref_type: npl
severity: background
ref_id: - STEVEN ELSWORTH ET AL, "Time Series Forecasting Using LSTM Networks: A Symbolic Approach", ARXIV.ORG, CORNELL UNIVERSITY LIBRARY, 201 OLIN LIBRARY CORNELL UNIVERSITY ITHACA, NY 14853, (20200312), XP081620015 [I] 1-14 * section 2 *
ref_type: npl
severity: background
ref_id: - GLOVER FRED ET AL, "Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models", 4OR, SPRINGER BERLIN HEIDELBERG, BERLIN/HEIDELBERG, vol. 17, no. 4, doi:10.1007/S10288-019-00424-Y, ISSN 1619-4500, (20191126), pages 335 - 371, (20191126), XP036936647 [A] 1 * abstract * * section 5 *
ref_type: npl
severity: background
ref_id: - SCHÄFER PATRICK ET AL, "SFA : a symbolic fourier approximation and index for similarity search in high dimensional datasets", PROCEEDINGS OF THE 15TH INTERNATIONAL CONFERENCE ON EXTENDING DATABASE TECHNOLOGY, EDBT '12, New York, New York, USA, doi:10.1145/2247596.2247656, ISBN 978-1-4503-0790-1, (20120301), pages 516 - 527, URL: https://dl.acm.org/doi/pdf/10.1145/2247596.2247656, XP055811284 [A] 7,8 * figure 2 * * section 3 *
ref_type: npl
severity: background
Final disposition: pending (2021-11-17)