Managing time series databases

Patent metadata

Field	Value
Publication number	US-9361329-B2
Application number	US-201314105660-A
Country	US
Kind code	B2
Filing date	Dec 13, 2013
Priority date	Dec 13, 2013
Publication date	Jun 7, 2016
Grant date	Jun 7, 2016

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.

First claim

The invention claimed is:

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,
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.

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

5. 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.

6. 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,
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.

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

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

9. The method according to claim 6 , 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.

10. The method according to claim 6 , 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.

11. The method according to claim 6 , 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.

12. An apparatus for building indices for a time sequence in a time series database, comprising a computer processor that comprises:
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,
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.

13. The apparatus according to claim 12 , 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.

14. The apparatus according to claim 13 , wherein the computer processor further comprises:
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.

15. The apparatus according to claim 12 , 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.

Assignees

• IBM

Inventors

• Chen Xiao Yan
• Chen yao liang
• Huang Sheng
• Liu Kai
• Wang Chen

Classifications

• G06F17/30619

  Physics · mapped topic

• G06F17/30312 Primary

  Physics · mapped topic

• G06F17/30551

  Physics · mapped topic

• G06F16/2228

  Indexing structures · CPC title

• G06F16/2264 Primary

  Multidimensional index structures · CPC title