Time Series Similarity Query Method Based on Inverted Index

Abstract

The invention discloses a time sequence similarity query method based on inverted indexes. The method comprises steps of index building and query processing, firstly, a real value type time sequence is converted into a discrete character string through symbol aggregate approximation representation, then a characteristic subsequence is extracted, codes are stored by vector approximation files, the subsequence is converted into word insertion inverted indexes with two types of granularity, and multi-granularity time sequence inverted indexes are built. According to the time sequence similarity query method based on the inverted indexes, an efficient two-stage filtration query method is designed for the indexes, k nearest neighbor similarity query can be realized, on the premise that a higher precision ratio is guaranteed, query time overhead is shorter, and good extendibility for the time sequence length, k nearest neighbor similarity query scale and data set scale is achieved; and the method can play an important role in daily activities and industrial production such as real-time query of stock volatility, on-line pattern recognition of sensor data flow and the like.

Description

technical field [0001] The invention relates to the fields of database, data mining and information retrieval, in particular to a time series similarity query method based on an inverted index. Background technique [0002] Time series widely exist in people's daily life and industrial production, such as real-time transaction data of funds or stocks, daily sales data in the retail market, sensor monitoring data in the process industry, astronomical observation data, aerospace radar, satellite monitoring data, real-time Weather temperature and air quality index, etc. [0003] Time series similarity query, also known as time series sample retrieval, has a wide range of application requirements in the industry. For example, in the real-time trading of the stock market, traders want to query the k historical sequences most similar to the current stock trend form from the massive historical stock data as a reference to obtain valuable knowledge and inspiration. Complete the tr...

AI Technical Summary

Problems solved by technology

Such methods include segmented aggregation approximation, segmented linear approximation, symbolic aggregation approximation, singular value decomposition, principal component analysis, etc. The first three methods need to segment the original time series first, and then process each sub-segment separately : The segmented aggregation approximation is to calculate the average value of each segment; the segmented linear approximation is to do line segment fitting on each segment; the symbolic aggregation approximation is to discretize the average value of each segment into symbols based on the segmental aggregation approximation; Different approximations to the original time series will lead to differences in their query performance

Singular value decomposition and principal component analysis are realized by performing a unified eigenmatrix decomposition on all time series; the typical defects of these two types of methods are that they have high computational complexity, and the decomposition process can only be done in memory, and the data Very low scalability at scale

[0005] Most of the indexing methods used in the industry so far are tree-based spatial indexing methods. B-trees were first used to index one-dimensional data and are the basis of many hierarchical index structures; R-tree series, such as R*-tree, R + -Trees, etc., use the minimum bounding rectangle to organize data, but the minimum bounding rectangle will cover a large amount of space without data, resulting in a large number of "false hits" in the query results, thereby reducing query efficiency; A-tree uses a vector approximation file to store the minimum The upper and lower boundaries of the bounding rectangle and virtual bounding rectangle, thus ensuring low indexing overhead and high query completeness

Due to the high-dimensional or ultra-high-dimensional characteristics of the time series in industrial production, even if the dimensionality reduction process is performed within the acceptable range of precision loss, it may still have a very high dimensionality. Therefore, the tree-based index method is prone to "dimensionality". "disaster" problem

Images