Research Information System
23rd International Symposium on String Processing and Information Retrieval (SPIRE), Beppu, Japan, 18 - 20 October 2016, vol.9954, pp.166-177
On a given sequence X = x(1)x(2) . . . x(n), the range selection queries denoted by Q(i, j, k) return the kth -smallest element on x(i)x(i)+1 . . . x(j) . The problem has received significant attention in recent years and many solutions aiming to achieve this task with a cost lower than dynamically sorting the elements on the queried range have been proposed. The reverse problem interestingly has not yet received that much attention, although there exists practical usage scenarios especially in the time-series analysis. This study investigates the inverse range selection query (Q) over bar (v, k) that aims to detect all possible intervals on X such that the kth -smallest element is less than or equal to v. We present the basic solution first and then discuss how that basic solution can be implemented with different data structures previously proposed for regular range selection queries.