Searching Monotone Multidimensional Arrays.pdfVIP

Searching Monotone Multi-dimensional Arrays Yongxi Cheng a Xiaoming Sun b Yiqun Lisa Yin c 6 0 0 2 g u aDepartment of Computer Science, Tsinghua University, Beijing 100084, China A Email: cyx@mails.tsinghua.edu.cn 1 b Center for Advanced Study, Tsinghua University, Beijing 100084, China 2 Email: xiaomings@tsinghua.edu.cn ] cIndependent security consultant, Greenwich CT, USA S D Email: yiqun@alum.mit.edu . s c [ 2 v 6 2 0 4 0 5 0 / s c : v i X r a Preprint submitted to Elsevier Science 1 February 2008 Abstract In this paper we investigate the problem of searching monotone multi-dimensional arrays. We generalize Linial and Saks’ search algorithm [2] for monotone 3-dimensional arrays to d-dimensions with d ≥ 4. Our new search algorithm is asymptotically op- timal for d = 4. Key words: search algorithm, complexity, multi-dimensional array, partial order 1 Introduction In this paper, we investigate the problem of searching monotone multi-dimensional arrays. Suppose we are given a d-dimensional array with n entries along each dimension An,d = {ai ,i ,...,i |i , i , . . . , i = 1, 2, . . . , n}. 1 2 d 1 2 d We say that the array An,d is monotone if its entries are real numbers that are increasing along each dimension. More precisely, if i ≤ j , i ≤ j ,. . . , 1 1 2 2 id ≤ jd then ai ,i ,...,i ≤ aj ,j ,...,j . In other words, if P = [n]d is the product 1 2 d 1 2 d of d totally ordered sets {