A novel join technique for similar-trend searches supporting normalization on time-series databases
Pages 481 - 486
Abstract
A time-series is defined to be a real-number sequence that is monitored in accordance with a particular time interval. To index a large volume of time-series data without excessive dimensionality expansions, the DFT (Discrete Fourier Transform) technique is widely accepted. It is a challenging task to support fast similarity searches on normalized time-series without false dismissals. Here, the normalization pre-processing on time-series is vital for similar-trend searches that are tackled in our work. To address this problem, we locate multiple sub-queries within a given user query, and map them into points in the normalized DFT index space. Then, a joinlike operation is executed using those points and newly computed Euclidian (similarity) distances. We propose a new cost function utilized for deciding sub-queries that may have the smallest intersection in the index space. With this approach, we can enhance the query performance significantly. Through performance evaluation, it is verified that our approach can reduce the query processing time by about 62%, compared to existing one.
References
[1]
R. Agrawal, C. Faloutsos, and A. Swami. 1993. Efficient Similarity Search in Sequence Databases. In Proc. Int'l Conf. on Foundations of Data Organization and Algorithms. 69--84.
[2]
A. Guttman. 1984. R-trees: A Dynamic Index Structure for Spatial Searching. In Proc. ACM Int'l Conf. on Management of Data. 47--57.
[3]
N. Beckmann, H. Kriegel, R. Schneider, and B. Seeger. 1990. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. In Proc. ACM Int'l Conf. on Management of Data. 322--331.
[4]
C. Faloutsos, M. Ranganathan, and Y. Manolopoulos. 1994. Fast Subsequence Matching in Time-Series Databases. In Proc. ACM Int'l Conf. on Management of Data. 419--429.
[5]
DQ. Goldin and PC. Kanellakis. 1995. On Similarity Queries for Time-Series Data: Constraint Specification and Implementation. In Proc. Int'l Conf. on Principles and Practice of Constraint Programming. 137--153.
[6]
E. Keogh and S. Kasetty. 2003. On the Need for Time Series Data Mining Benchmarks: A Survey and Empirical Demonstration. Data Mining and Knowledge Discovery 7 (2003), 349--371.
[7]
S. Kim, S. Park, and W. Chu. 2001. An Index-Based Approach for Similarity Search Supporting Time Warping in Large Sequence Databases. In Proc. IEEE Int'l Conf. on Data Engineering. 607--614.
[8]
S. Kim, S. Park, and W. Chu. 2004. Efficient Processing of Similarity Search under Time Warping in Sequence Databases: An Index-Based Approach. Information Systems 29 (2004), 405--420.
[9]
S. Kim, J. Yoon, S. Park, and T. Kim. 2002. Shape-based retrieval of similar subsequences in time-series databases. In Proc. ACM Symp. on Applied Computing. 438--445.
[10]
S. Lim, H. Park, and S. Kim. 2007. Using Multiple Indexes for Efficient Subsequence Matching in Time-Series Databases. Information Sciences 177 (2007), 5691--5706.
[11]
W. Loh, S. Kim, and K. Whang. 2001. Index interpolation: a subsequence matching algorithm supporting moving average transform of arbitrary order in time-series databases. IEICE Trans. on Information and Systems 84 (2001), 76--86.
[12]
W. Loh, S. Kim, and K. Whang. 2004. A Subsequence Matching Algorithm that Supports Normalization Transform in Time-Series Databases. Data Mining and Knowledge Discovery 9 (2004), 5--28.
[13]
Y. Moon, K. Whang, and W. Han. 2002. General Match: A Subsequence Matching Method in Time-Series Databases based on Generalized Windows. In Proc. ACM Int'l Conf. on Management of Data. 382--393.
[14]
Y. Moon, K. Whang, and W. Loh. 2001. Duality-Based Subsequence Matching in Time-series Databases. In Proc. IEEE Int'l Conf. on Data Engineering. 263--272.
[15]
S. Park, S. Kim, and W. Chu. 2001. Segment-Based Approach for Subsequence Searches in Sequence Databases. In Proc. ACM Symp. on Applied Computing. 248--252.
[16]
TK. Sellis, N. Roussopoulos, and C. Faloutsos. 1987. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. In Proc. Int'l Conf. on Very Large Data Bases. 507--518.
Index Terms
- A novel join technique for similar-trend searches supporting normalization on time-series databases
Recommendations
A Subsequence Matching Algorithm that Supports Normalization Transform in Time-Series Databases
In this paper, an algorithm is proposed for subsequence matching that supports normalization transform in time-series databases. Normalization transform enables finding sequences with similar fluctuation patterns even though they are not close to each ...
Supporting top-K join queries in relational databases
VLDB '03: Proceedings of the 29th international conference on Very large data bases - Volume 29Ranking queries produce results that are ordered on some computed score. Typically, these queries involve joins, where users are usually interested only in the top-k join results. Current relational query processors do not handle ranking queries ...
Supporting top-k join queries in relational databases
Ranking queries, also known as top-k queries, produce results that are ordered on some computed score. Typically, these queries involve joins, where users are usually interested only in the top-k join results. Top-k queries are dominant in many emerging ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 2018
2327 pages
ISBN:9781450351911
DOI:10.1145/3167132
- Conference Chairs:
- Hisham M. Haddad,
- Roger L. Wainwright,
- Richard Chbeir
Copyright © 2018 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 09 April 2018
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- National Research Foundation of Korea
Conference
SAC 2018
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,650 of 6,669 submissions, 25%
Upcoming Conference
SAC '25
- Sponsor:
- sigapp
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 86Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)1
Reflects downloads up to 10 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in