Inverse Range Selection Queries


Külekci M. O.

23rd International Symposium on String Processing and Information Retrieval (SPIRE), Beppu, Japonya, 18 - 20 Ekim 2016, cilt.9954, ss.166-177 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 9954
  • Doi Numarası: 10.1007/978-3-319-46049-9_17
  • Basıldığı Şehir: Beppu
  • Basıldığı Ülke: Japonya
  • Sayfa Sayıları: ss.166-177
  • İstanbul Teknik Üniversitesi Adresli: Evet

Özet

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.