Speaker: Pramod Ganapathi and Samuel McCauley
Title: The Range 1 Query (R1Q) Problem
Abstract: We define the "range 1 query" (R1Q) problem as follows.
Given a d-dimensional (d >= 1) input bit matrix A, preprocess A
so that for any given region R of A, one can efficiently answer
queries asking if R contains a 1 or not. We consider both orthogonal
and non-orthogonal shapes for R including rectangles, axis-parallel
right-triangles, certain types of polygons, and spheres. We provide
space-efficient deterministic and randomized algorithms with constant
query times (in constant dimensions) for solving the problem in the
word RAM model. The space usage in bits is sublinear, linear, or
near linear in the size of A, depending on the algorithm. The R1Q
problem for both orthogonal and non-orthogonal ranges arises during
the generation of optimized kernels in the Pochoir stencil compiler.
This is joint work with Michael Bender, Rezaul Chowdhury and Yuan Tang.