Inverse Range Selection Queries

Külekci M. O.

23rd International Symposium on String Processing and Information Retrieval (SPIRE), Beppu, Japan, 18 - 20 October 2016, vol.9954, pp.166-177 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 9954
  • Doi Number: 10.1007/978-3-319-46049-9_17
  • City: Beppu
  • Country: Japan
  • Page Numbers: pp.166-177
  • Istanbul Technical University Affiliated: Yes


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.