Practical Implementation of Encoding Range Top-2 Queries

Abstract

We design a practical variant of an encoding for range Top-2 query (RT2Q) and evaluate its performance. Given an array |$A[1,n]$| of |$n$| elements from a total order, the range Top-2 encoding problem is to construct a data structure that answers |${\textsf{RT2Q}}{}$|⁠, which returns the positions of the first and second largest elements within a given range of |$A$|⁠, without accessing the array |$A$| at query time. We design the following two implementations: (i) an implementation based on an alternative representation of Davoodi et al.’s [Phil. Trans. Royal Soc. A, 2016] data structure, which supports queries efficiently. Experimental results show that our implementation is efficient in practice and gives improved time-space trade-offs compared with the indexing data structures (which keep the original array |$A$| as part of the data structure) for range maximum queries. (ii) Another implementation based on Jo et al.’s |${\textsf{RT2Q}}{}$| encoding on |$2 \times n$| array [CPM, 2016], which can be constructed in |$O(n)$| time. We compare our encoding with Gawrychowski and Nicholson’s optimal encoding [ICALP, 2015] and show that in most cases, our encoding shows faster construction time while using a competitive space in practice.