Efficient algorithms for local ranking
Journal
Information Processing Letters
Journal Volume
112
Journal Issue
13
Pages
517-522
Date Issued
2012
Author(s)
Abstract
The trend of a time series can be represented as a ranking sequence, which reveals the ups and downs with the passage of time. In some applications, one might need to find the trend in some specific period of time or search for the period of time with some specific trend. We formulate three related problems: the local ranking problem, the local ranking sequence problem and the ranking sequence matching problem. The first two are to find the rankings given a segment of the time sequence and the last one is to search for the matching positions to the query sequence. For all the problems, we propose different algorithms utilizing a modified segment tree data structure. It takes O(nlogn) time and space to build the segment tree where n is the length of the target ranking sequence. The query time of the three algorithms are O(logk), O(k) and O(nlogk), respectively, where k is the size of the query range. © 2012 Elsevier B.V. All rights reserved.
Type
journal article