Time-optimal domain-specific querying on enhanced meshes

Abstract

Query processing is a crucial component of various application domains including information retrieval, database design and management, pattern recognition, robotics, and VLSI. Many of these applications involve data stored in a matrix satisfying a number of properties. One property that occurs time and again specifies that the rows and the columns of the matrix are independently sorted. It is customary to refer to such a matrix as sorted. An instance of the batched searching and ranking problem (BSR) involves a sorted matrix A of items from a totally ordered universe, along with a collection Q of queries. Q is an arbitrary mix of the following query types: for a search query q/sub j/, one is interested in an item of A that is closest to q/sub j/; for a rank query q/sub j/ one is interested in the number of items of A that are strictly smaller than q/sub j/. The BSR problem asks for solving all queries in Q. The authors consider the BSR problem in the following context: the matrix A is pretiled, one item per processor, onto an enhanced mesh of size /spl radic/n/spl times//spl radic/n; the m queries are stored, one per processor, in the first m//spl radic/n~ columns of the platform. Their main contribution is twofold. First, they show that any algorithm that solves the BSR problem must take at least /spl Omega/(max{logn, /spl radic/m}) time in the worst case. Second, they show that this time lower bound is tight on meshes of size /spl radic/n/spl times//spl radic/n enhanced with multiple broadcasting, by exhibiting an algorithm solving the BSR problem in /spl Theta/(max{logn, /spl radic/m}) time on such a platform.