MANAGING TIME SERIES DATABASES

• US 20150169654A1
• Filed: 12/13/2013
• Published: 06/18/2015
• Est. Priority Date: 12/13/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Xiao Yan, Chen, Yao Liang, Huang, Sheng, Liu, Kai, Wang, Chen
• Granted Patent: US 9,361,329 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: G06F 16/86 Mapping to a database

Abstract

A method for building indices for a time sequence in a time series database includes dividing, using a processing device, a time sequence in the time series database into a plurality of subsequences based on a sliding window; building spatial indices for the plurality of subsequences, the spatial indices being used for defining spatial locations of subsequences in the plurality of subsequences in the time sequence; and building content indices for the plurality of subsequences, the content indices being used for defining content ranges of subsequences in the plurality of subsequences.

Claims

1. A method for building indices for a time sequence in a time series database, comprising:

dividing, using a processing device, a time sequence in the time series database into a plurality of subsequences based on a sliding window;

building spatial indices for the plurality of subsequences, the spatial indices being used for defining spatial locations of subsequences in the plurality of subsequences in the time sequence; and

building content indices for the plurality of subsequences, the content indices being used for defining content ranges of subsequences in the plurality of subsequences.

2. The method according to claim 1, wherein the building content indices for the plurality of subsequences comprises:

mapping a subsequence in the plurality of subsequences to a symbol value corresponding to a content range of the subsequence.

3. The method according to claim 2, further comprising:

storing a symbol value corresponding to a subsequence in the plurality of subsequences as metadata associated with the spatial indices.

4. The method according to claim 1, wherein the building spatial indices for the plurality of subsequences comprises:

converting the plurality of subsequences to a frequency domain based on Linear Discrete Transform; and

building spatial indices for the plurality of subsequences according to characteristic frequencies in the frequency domain.

5. The method according to claim 4, wherein the converting the plurality of subsequences to the frequency domain based on Linear Discrete Transform comprises:

dividing the plurality of subsequences into segments based on Segmentation Dimension Reduction; and

converting the plurality of subsequences to the frequency domain based on the segments.

6. The method according to claim 1, further comprising a pre-processing operation of:

in response to the time sequence being a multi-dimensional time sequence, decomposing the time sequence into a plurality of one-dimensional time sequences.

7. A method for querying in a time series database, comprising:

based on spatial indices for a time sequence in the time series database, searching with a processing device in the time sequence in the time series database for a spatial location that corresponds to a query sequence;

based on content indices for the time sequence in the time series database, obtaining a content range of a subsequence at the found spatial location; and

in response to the obtained content range being the same as a content range of the query sequence, outputting the subsequence at the found spatial location;

wherein the spatial indices are used for defining spatial locations of subsequences of the time sequence in the time sequence, and the content indices are used for defining content ranges of subsequences of the time sequence.

8. The method according to claim 7, wherein the content index comprises a symbol value corresponding to a content range of a subsequence of the time sequence.

9. The method according to claim 8, wherein a symbol value corresponding to a subsequence in the plurality of subsequences is stored as metadata associated with the spatial indices.

10. The method according to claim 7, wherein the based on spatial indices for a time sequence in the time series database, searching in the time sequence in the time series database for a spatial location that corresponds to a query sequence comprises:

converting the query sequence to a frequency domain based on Linear Discrete Transform; and

according to characteristic frequencies in the frequency domain, searching in the time sequence in the time series database for a spatial location that corresponds to the query sequence via the spatial indices.

11. The method according to claim 10, wherein the converting the query sequence to the frequency domain based on Linear Discrete Transform comprises:

dividing the query sequence into segments based on Segmentation Dimension Reduction; and

converting the query sequence to the frequency domain based on the segments.

12. The method according to claim 7, further comprising:

dividing the query sequence into a plurality of query subsequences; and

integrating spatial locations that are found and outputted for the plurality of query subsequences.

13. The method according to claim 7, further comprising a pre-processing operation of:

in response to the query sequence being a multi-dimensional time sequence, decomposing the query sequence into a plurality of one-dimensional query sequences.

14. An apparatus for building indices for a time sequence in a time series database, comprising:

a dividing module configured to divide a time sequence in the time series database into a plurality of subsequences based on a sliding window;

a spatial index building module configured to build spatial indices for the plurality of subsequences, the spatial indices being used for defining spatial locations of subsequences in the plurality of subsequences in the time sequence; and

a content index building module configured to build content indices for the plurality of subsequences, the content indices being used for defining content ranges of subsequences in the plurality of subsequences.

15. The apparatus according to claim 14, wherein the spatial index building module comprises:

a mapping module configured to map a subsequence in the plurality of subsequences to a symbol value corresponding to a content range of the subsequence.

16. The apparatus according to claim 15, further comprising:

a storage module configured to store a symbol value corresponding to a subsequence in the plurality of subsequences as metadata associated with the spatial indices.

17. The apparatus according to claim 14, wherein the spatial index building module comprises:

a converting module configured to convert the plurality of subsequences to a frequency domain based on Linear Discrete Transform; and

a building module configured to build spatial indices for the plurality of subsequences according to characteristic frequencies in the frequency domain.

18. The apparatus according to claim 17, wherein the converting module comprises:

a segmenting module configured to divide the plurality of subsequences into segments based on Segmentation Dimension Reduction; and

a segment converting module configured to convert the plurality of subsequences to the frequency domain based on the segments.