4
$\begingroup$

Problem: In the multidimensional range Max/Sum query problem (RMQ/RSQ) you are given a $d$-dimensional array with $n$ elements, and given a $d$-dimensional box, you wish to determine the max/sum of all elements in the range (if the elements are from semigroup, they have no inverses).

What is the state-of-art best algorithm for offline multidimensional RMQ/RSQ in query model (preprocessing of data allowed in offline, queries asked online)? Is there any gap between RMQ and RSQ in multidimensional case? What theoretical/practical interest does this problem have, if any?

I'm interested in it because looks like the best asymptotics for both RMQ and RSQ was achieved in this paper by Chazelle and Rosenberg in 1989, which was not cited a lot, though the problem looks very natural and interesting. By best asymptotics I mean $O(\alpha^d(m,n))$ query time, where $m$ is the amount of storage available per element, $d$ --- number of dimensions of the array, $\alpha$ --- inverse Ackerman function, $n$ --- number of entries in the array. I suspect that this is mainly because this paper is not very readable in the part where it describes the construction, so implementation of this approach is complicated. So a simpler description of a data structure with the same asymptotics is also very welcome.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ you should probably explain the acronyms. Is RMQ range-minimum and RSQ range-sum ? $\endgroup$ – Suresh Venkat Sep 30 '10 at 7:05
  • $\begingroup$ this is the kind of edit I had in mind. $\endgroup$ – Suresh Venkat Sep 30 '10 at 16:49
  • $\begingroup$ @Suresh Thanks for a comment, added the problem statement. $\endgroup$ – Grigory Yaroslavtsev Sep 30 '10 at 18:32
6
$\begingroup$

So, you are interested in range queries in the "dense case" (an array) as opposed to the case most frequently studied in theory (arbitrary points in space).

The RMQ problem is easier than the semigroup sum problem, and no $\alpha$ is needed. The most recent result I know is: Hao Yuan, Mikhail J. Atallah: Data Structures for Range Minimum Queries in Multidimensional Arrays, SODA 2010

The semigroup sum problem is mainly of theoretical interest, in my opinion (what is a natural semigroup beyond max?). This explains why the Chazelle-Rosenberg paper does not have a lot of citations.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ added a link to the paper. But Mihai, wasn't he asking about range max ? you can fix this for integers by flipping signs or subtracting, but without inverses can that be done ? $\endgroup$ – Suresh Venkat Sep 30 '10 at 17:12
  • 3
    $\begingroup$ "what is a natural semigroup beyond max?" There are tons. Free semigroups (list concatenation). Operator/matrix semigroups. Lattices wrt join/meet. Saturated semigroups other than min/max semigroups (e.g. Tony Morris's validation semigroup). Maybe not useful in the context of the semigroup sum problem, but definitely useful in general. $\endgroup$ – Per Vognsen Oct 1 '10 at 2:51
  • $\begingroup$ Accepted the answer, thank you! Really looks like there are no interesting semigroups beyond max to make RSQ problem very interesting. If somebody knows any examples, I would be interested to know. $\endgroup$ – Grigory Yaroslavtsev Oct 8 '10 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.