Efficient processing of subsequence matching with the euclidean metric in time-series databases

Sang Wook Kim, Dae Hyun Park, Heon Gil Lee

Research output: Contribution to journalConference article

Abstract

In this paper, we discuss efficient processing of subsequence matching in time-series databases. We first point out the performance problems of Dual-Match, a previous subsequence matching method, and then propose a new one resolving them. The proposed method starts with a new attempt that observes the index search occurred in subsequence matching as a window-join, a kind of the spatial-join. For effective processing of the window-join, we build an R*-tree for query window points within the main memory on the fly. We also propose a novel algorithm for efficient processing of the join on the two R*-trees; one for query window points residing in the main memory and the other for data window points residing in the disk. Performance evaluation via experiments shows the superiority of the proposed method compared with Dual-Match.

Original languageEnglish
Pages (from-to)124-128
Number of pages5
JournalProceedings of the IEEE International Conference on Systems, Man and Cybernetics
Volume1
StatePublished - 2002 Dec 1
Event2002 IEEE International Conference on Systems, Man and Cybernetics - Yasmine Hammamet, Tunisia
Duration: 2002 Oct 62002 Oct 9

Fingerprint

Time series
Processing
Data storage equipment
Experiments

Keywords

  • Index search
  • Subsequence matching
  • Time-series databases
  • Window join

Cite this

@article{f39107bcfe1b4d628412510245ea5c4a,
title = "Efficient processing of subsequence matching with the euclidean metric in time-series databases",
abstract = "In this paper, we discuss efficient processing of subsequence matching in time-series databases. We first point out the performance problems of Dual-Match, a previous subsequence matching method, and then propose a new one resolving them. The proposed method starts with a new attempt that observes the index search occurred in subsequence matching as a window-join, a kind of the spatial-join. For effective processing of the window-join, we build an R*-tree for query window points within the main memory on the fly. We also propose a novel algorithm for efficient processing of the join on the two R*-trees; one for query window points residing in the main memory and the other for data window points residing in the disk. Performance evaluation via experiments shows the superiority of the proposed method compared with Dual-Match.",
keywords = "Index search, Subsequence matching, Time-series databases, Window join",
author = "Kim, {Sang Wook} and Park, {Dae Hyun} and Lee, {Heon Gil}",
year = "2002",
month = "12",
day = "1",
language = "English",
volume = "1",
pages = "124--128",
journal = "Proceedings of the IEEE International Conference on Systems, Man and Cybernetics",
issn = "0884-3627",

}

Efficient processing of subsequence matching with the euclidean metric in time-series databases. / Kim, Sang Wook; Park, Dae Hyun; Lee, Heon Gil.

In: Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Vol. 1, 01.12.2002, p. 124-128.

Research output: Contribution to journalConference article

TY - JOUR

T1 - Efficient processing of subsequence matching with the euclidean metric in time-series databases

AU - Kim, Sang Wook

AU - Park, Dae Hyun

AU - Lee, Heon Gil

PY - 2002/12/1

Y1 - 2002/12/1

N2 - In this paper, we discuss efficient processing of subsequence matching in time-series databases. We first point out the performance problems of Dual-Match, a previous subsequence matching method, and then propose a new one resolving them. The proposed method starts with a new attempt that observes the index search occurred in subsequence matching as a window-join, a kind of the spatial-join. For effective processing of the window-join, we build an R*-tree for query window points within the main memory on the fly. We also propose a novel algorithm for efficient processing of the join on the two R*-trees; one for query window points residing in the main memory and the other for data window points residing in the disk. Performance evaluation via experiments shows the superiority of the proposed method compared with Dual-Match.

AB - In this paper, we discuss efficient processing of subsequence matching in time-series databases. We first point out the performance problems of Dual-Match, a previous subsequence matching method, and then propose a new one resolving them. The proposed method starts with a new attempt that observes the index search occurred in subsequence matching as a window-join, a kind of the spatial-join. For effective processing of the window-join, we build an R*-tree for query window points within the main memory on the fly. We also propose a novel algorithm for efficient processing of the join on the two R*-trees; one for query window points residing in the main memory and the other for data window points residing in the disk. Performance evaluation via experiments shows the superiority of the proposed method compared with Dual-Match.

KW - Index search

KW - Subsequence matching

KW - Time-series databases

KW - Window join

UR - http://www.scopus.com/inward/record.url?scp=0038684402&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0038684402

VL - 1

SP - 124

EP - 128

JO - Proceedings of the IEEE International Conference on Systems, Man and Cybernetics

JF - Proceedings of the IEEE International Conference on Systems, Man and Cybernetics

SN - 0884-3627

ER -