Kasper Green Larsen

In this paper, we study the cell probe complexity of evaluating an n-degree polynomial P over a finite field F of size at least n^1+Ω(1). More specifically, we show that any static data structure for evaluating P(x), where x∈F, must use Ω(lg|F|/lg(Sw/nlg|F|)) cell probes to answer a query, where S denotes the space of the data structure in number of cells and w the cell size in bits. This bound holds in expectation for randomized data structures with any constant error probability δ<1/2. Our lower bound not only improves over the Ω(lg|F|/lgS) lower bound of Miltersen [TCS'95], but is in fact the highest static cell probe lower bound to date: For linear space (i.e. S=O(nlg|F|/w)), our query time lower bound simplifies to Ω(lg|F|), whereas the highest previous lower bound for any static data structure problem having U different queries is Ω(lgU/lglgU), which was first achieved by Pătraşcu and Thorup [SICOMP'10].
We also use the recent technique of Larsen [STOC'12] to show a lower bound of t_q=Ω(lg|F|lgn/lg(wt_u/lg|F|)lg(wt_u)) for dynamic data structures for polynomial evaluation over a finite field F of size Ω(n²). Here t_q denotes the expected query time and t_u the worst case update time. This lower bound holds for randomized data structures with any constant error probability δ<1/2. This is only the second time a lower bound beyond max{t_u,t_q}=Ω(max{lgn,lgU/lglgU}) has been achieved for dynamic data structures, where U denotes the number of different queries and updates to the problem. Furthermore, it is the first such lower bound that holds also for randomized data structures with a constant probability of error.

In this paper we present a number of improved lower bounds for range searching in the pointer machine and the group model. In the pointer machine, we prove lower bounds for the approximate simplex range reporting problem. In approximate simplex range reporting, points that lie within a distance of ε·diam(s) from the border of a query simplex s, are free to be included or excluded from the output, where ε≥0 is an input parameter to the range searching problem. We prove our lower bounds by constructing a hard input set and query set, and then invoking Chazelle and Rosenberg's [CGTA'96] general theorem on the complexity of navigation in the pointer machine.
For the group model, we show that input sets and query sets that are hard for range reporting in the pointer machine (i.e. by Chazelle and Rosenberg's theorem), are also hard for dynamic range searching in the group model. This theorem allows us to reuse decades of research on range reporting lower bounds to immediately obtain a range of new group model lower bounds. Amongst others, this includes an improved lower bound for the fundamental problem of dynamic d-dimensional orthogonal range searching, stating that t_qt_u=Ω((lgn/lglgn)^d-1). Here t_q denotes the query time and t_u the update time of the data structure. This is an improvement of a lg^1-δn factor over the recent lower bound of Larsen [FOCS'11], where δ>0 is a small constant depending on the dimension.

In this paper, we consider two fundamental problems in the pointer machine model of computation, namely orthogonal range reporting and rectangle stabbing. Orthogonal range reporting is the problem of storing a set of n points in d-dimensional space in a data structure, such that the t points in an axis-aligned query rectangle can be reported efficiently. Rectangle stabbing is the ``dual'' problem where a set of n axis-aligned rectangles should be stored in a data structure, such that the t rectangles that contain a query point can be reported efficiently. Very recently an optimal O(lgn+t) query time pointer machine data structure was developed for the three-dimensional version of the orthogonal range reporting problem. However, in four dimensions the best known query bound of O(lg²n/lglgn+t) has not been improved for decades.
We describe an orthogonal range reporting data structure that is the first structure to achieve significantly less than O(lg²n+t) query time in four dimensions. More precisely, we develop a structure that uses O(n(lgn/lglgn)^d) space and can answer d-dimensional orthogonal range reporting queries (for d≥4) in O(lgn(lgn/lglgn)^d-4+1/(d-2)+t) time. Ignoring lglgn factors, this speeds up the best previous query time by a lg^1-1/(d-2)n factor. For the rectangle stabbing problem, we show that any data structure that uses nh space must use Ω(lgn(lgn/lgh)^d-2+t) time to answer a query. This improves the previous results by a lgh factor, and is the first lower bound that is optimal for a large range of h, namely for h≥lg^d-2+εn where ε>0 is an arbitrarily small constant. By a simple geometric transformation, our result also implies an improved query lower bound for orthogonal range reporting.

In this paper we develop a new technique for proving lower bounds on the update time and query time of dynamic data structures in the cell probe model. With this technique, we prove the highest lower bound to date for any explicit problem, namely a lower bound of t_q=Ω((lgn/lg(wt_u))²). Here n is the number of update operations, w the cell size, t_q the query time and t_u the update time. In the most natural setting of cell size w=Θ(lgn), this gives a lower bound of t_q=Ω((lgn/lglgn)²) for any polylogarithmic update time. This bound is almost a quadratic improvement over the highest previous lower bound of Ω(lgn), due to Pătraşcu and Demaine [SICOMP'06].
We prove our lower bound for the fundamental problem of weighted orthogonal range counting. In this problem, we are to support insertions of two-dimensional points, each assigned a Θ(lgn)-bit integer weight. A query to this problem is specified by a point q=(x,y), and the goal is to report the sum of the weights assigned to the points dominated by q, where a point (x',y') is dominated by q if x'≤x and y'≤y. In addition to being the highest cell probe lower bound to date, our lower bound is also tight for data structures with update time t_u=Ω(lg^2+εn), where ε>0 is an arbitrarily small constant.

A mode of a multiset S is an element a∈S of maximum multiplicity; that is, a occurs at least as frequently as any other element in S. Given an array A[1 : n] of n elements, we consider a basic problem: constructing a static data structure that efficiently answers range mode queries on A. Each query consists of an input pair of indices (i,j) for which a mode of A[i : j] must be returned. The best previous data structure with linear space, by Krizanc, Morin, and Smid (ISAAC 2003), requires O(n^1/2lglgn) query time. We improve their result, by not only eliminating the lglgn factor, but also achieving o(n^1/2) time: specifically, we present an O(n)-space data structure that supports range mode queries in O((n/lgn)^1/2) worst-case time. Furthermore, we present strong evidence that a query time significantly below n^1/2 cannot be achieved by purely combinatorial techniques. We show that boolean matrix multiplication of two n^1/2×n^1/2 matrices reduces to n range mode queries in an array of size O(n). Since the current best combinatorial algorithm for boolean matrix multiplication has cubic running time (ignoring polylogarithmic factors), this reduction shows that achieving preprocessing time significantly less than n^3/2 and query time significantly less than n^1/2 simultaneously would be a major breakthrough. Additionally, we give linear-space data structures for the dynamic problem (queries and updates in near O(n^3/4) time), for orthogonal range mode in higher dimensions (queries in near O(n^1-1/2d) time), and for halfspace range mode in higher dimensions (queries in O(n^1-1/d²) time).

Motivated by information retrieval applications, we consider the one-dimensional colored range reporting problem in rank space. The goal is to build a static data structure for sets C₁,...,C_m ⊆ {1,...,σ} that supports queries of the kind: Given indices a,b, report the set ∪_a≤i≤bC_i.
We study the problem in the I/O model, and show that there exists an optimal linear-space data structure that answers queries in O(1+k/B) I/Os, where k denotes the output size and B the disk block size in words. In fact, we obtain the same bound for the harder problem of three-sided orthogonal range reporting. In this problem, we are to preprocess a set of n two-dimensional points in rank space, such that all points inside a query rectangle of the form [x₁,x₂]×(-∞,y] can be reported. The best previous bounds for this problem is either O(nlg
2
B
n) space and O(1+k/B) query I/Os, or O(n) space and O(lg
(h)
B
n+k/B) query I/Os, where lg
(h)
B
n is the base B logarithm iterated h times, for any constant integer h. The previous bounds are both achieved under the indivisibility assumption, while our solution exploits the full capabilities of the underlying machine. Breaking the indivisibility assumption thus provides us with cleaner and optimal bounds.
Our results also imply an optimal solution to the following colored prefix reporting problem. Given a set S of strings, each O(1) disk blocks in length, and a function c : S→2^{1,...,σ}, support queries of the kind: Given a string p, report the set ∪_x∈S∩p*c(x), where p* denotes the set of strings with prefix p. Finally, we consider the possibility of top-k extensions of this result, and present a simple solution in a model that allows non-blocked I/O.

In this paper we establish an intimate connection between dynamic range searching in the group model and combinatorial discrepancy. Our result states that, for a broad class of range searching data structures (including all known upper bounds), it must hold that t_ut_q=Ω(disc²/lgn) where t_u is the worst case update time, t_q the worst case query time and disc is the combinatorial discrepancy of the range searching problem in question. This relation immediately implies a whole range of exceptionally high and near-tight lower bounds for all of the basic range searching problems. We list a few of them in the following:

For halfspace range searching in d-dimensional space, we get a lower bound of t_ut_q=Ω(n^1-1/d/lgn). This comes within a lgnlglgn factor of the best known upper bound.
For orthogonal range searching in d-dimensional space, we get a lower bound of t_ut_q=Ω(lg^d-2+μ(d)n), where μ(d)>0 is some small but strictly positive function of d.
For ball range searching in d-dimensional space, we get a lower bound of t_ut_q=Ω(n^1-1/d/lgn).

We note that the previous highest lower bound for any explicit problem, due to Pătraşcu [STOC'07], states that t_q=Ω((lgn/lg(lgn+t_u))²), which does however hold for a less restrictive class of data structures.
Our result also has implications for the field of combinatorial discrepancy. Using textbook range searching solutions, we improve on the best known discrepancy upper bound for axis-aligned rectangles in dimensions d≥3.

We present a number of new results on one of the most extensively studied topics in computational geometry, orthogonal range searching. All our results are in the standard word RAM model:

We present two data structures for 2-d orthogonal range emptiness. The first achieves O(nlglgn) space and O(lglgn) query time, assuming that the n given points are in rank space. This improves the previous results by Alstrup, Brodal, and Rauhe (FOCS'00), with O(nlg^εn) space and O(lglgn) query time, or with O(nlglgn) space and O(lg²lgn) query time. Our second data structure uses O(n) space and answers queries in O(lg^εn) time. The best previous O(n)-space data structure, due to Nekrich (WADS'07), answers queries in O(lgn/lglgn) time.
We give a data structure for 3-d orthogonal range reporting with O(nlg^1+εn) space and O(lglgn+k) query time for points in rank space, for any constant ε>0. This improves the previous results by Afshani (ESA'08), Karpinski and Nekrich (COCOON'09), and Chan (SODA'11), with O(nlg³n) space and O(lglgn+k) query time, or with O(nlg^1+εn) space and O(lg²lgn+k) query time. Consequently, we obtain improved upper bounds for orthogonal range reporting in all constant dimensions above 3.
Our approach also leads to a new data structure for 2-d orthogonal range minimum queries with O(nlg^εn) space and O(lglgn) query time for points in rank space.
We give a randomized algorithm for 4-d offline dominance range reporting/emptiness with running time O(nlgn) plus the output size. This resolves two open problems (both appeared in Preparata and Shamos' seminal book):
1. given a set of n axis-aligned rectangles in the plane, we can report all k enclosure pairs (i.e., pairs (r₁,r₂) where rectangle r₁ completely encloses rectangle r₂) in O(nlgn+k) expected time;
2. given a set of n points in 4-d, we can find all maximal points (points not dominated by any other points) in O(nlgn) expected time.
The most recent previous development on (a) was reported back in SoCG'95 by Gupta, Janardan, Smid, and Dasgupta, whose main result was an O([nlgn+k]lglgn) algorithm. The best previous result on (b) was an O(nlgnlglgn) algorithm due to Gabow, Bentley, and Tarjan---from STOC'84! As a consequence, we also obtain the current-record time bound for the maxima problem in all constant dimensions above 4.

Given a set of points with uncertain locations, we consider the problem of computing the probability of each point lying on the skyline, that is, the probability that it is not dominated by any other input point. If each point's uncertainty is described as a probability distribution over a discrete set of locations, we improve the best known exact solution. We also suggest why we believe our solution might be optimal. Next, we describe simple, near-linear time approximation algorithms for computing the probability of each point lying on the skyline. In addition, some of our methods can be adapted to construct data structures that can efficiently determine the probability of a query point lying on the skyline.

Range selection is the problem of preprocessing an input array A of n unique integers, such that given a query (i,j,k), one can report the k'th smallest integer in the subarray A[i],A[i+1],...,A[j]. In this paper we consider static data structures in the word-RAM for range selection and several natural special cases thereof.
The first special case is known as range median, which arises when k is fixed to ⌊(j-i+1)/2⌋. The second case, denoted prefix selection, arises when i is fixed to 0. Finally, we also consider the bounded rank prefix selection problem and the fixed rank range selection problem. In the former, data structures must support prefix selection queries under the assumption that k≤κ for some value κ≤n given at construction time, while in the latter, data structures must support range selection queries where k is fixed beforehand for all queries. We prove cell probe lower bounds for range selection, prefix selection and range median, stating that any data structure that uses S words of space needs Ω(lgn/lg(Sw/n)) time to answer a query. In particular, any data structure that uses nlg^O(1)n space needs Ω(lgn/lglgn) time to answer a query, and any data structure that supports queries in constant time, needs n^1+Ω(1) space. For data structures that uses nlg^O(1)n space this matches the best known upper bound.
Additionally, we present a linear space data structure that supports range selection queries in O(lgk/lglgn+lglgn) time. Finally, we prove that any data structure that uses S space, needs Ω(lgκ/lg(Sw/n)) time to answer a bounded rank prefix selection query and Ω(lgk/lg(Sw/n)) time to answer a fixed rank range selection query. This shows that our data structure is optimal except for small values of k.

We consider the problem of automatically cleaning massive sonar data point clouds, that is, the problem of automatically removing noisy points that for example appear as a result of scans of (shoals of) fish, multiple reflections, scanner self-reflections, refraction in gas bubbles, and so on.
We describe a new algorithm that avoids the problems of previous local-neighbourhood based algorithms. Our algorithm is theoretically I/O-efficient, that is, it is capable of efficiently processing massive sonar point clouds that do not fit in internal memory but must reside on disk. The algorithm is also relatively simple and thus practically efficient, partly due to the development of a new simple algorithm for computing the connected components of a graph embedded in the plane. A version of our cleaning algorithm has already been incorporated in a commercial product.

The mode of a multiset of labels, is a label that occurs at least as often as any other label. The input to the range mode problem is an array A of size n. A range query [i,j] must return the mode of the subarray A[i],A[i+1],...,A[j]. We prove that any data structure that uses S memory cells of w bits needs Ω(lgn/lg(Sw/n)) time to answer a range mode query. Secondly, we consider the related range k-frequency problem. The input to this problem is an array A of size n, and a query [i,j] must return whether there exists a label that occurs precisely k times in the subarray A[i],A[i+1],...,A[j]. We show that for any constant k>1, this problem is equivalent to 2D orthogonal rectangle stabbing, and that for k=1 this is no harder than four-sided 3D orthogonal range emptiness. Finally, we consider approximate range mode queries. A c-approximate range mode query must return a label that occurs at least 1/c times that of the mode. We describe a linear space data structure that supports 3-approximate range mode queries in constant time, and a data structure that uses O(n/ε) space and supports (1+ε)-approximation queries in O(lg1/ε) time.

Orthogonal range reporting is the problem of storing a set of n points in d-dimensional space, such that the k points in an axis-orthogonal query box can be reported efficiently. While the 2-d version of the problem was completely characterized in the pointer machine model more than two decades ago, this is not the case in higher dimensions.
    In this paper we provide a space optimal pointer machine data structure for 3-d orthogonal range reporting that answers queries in O(lgn+k) time. Thus we settle the complexity of the problem in 3-d. We use this result to obtain improved structures in higher dimensions, namely structures with a lgn/lglgn factor increase in space and query time per dimension. Thus for d≥3 we obtain a structure that both uses optimal O(n(lgn/lglgn)^d-1) space and answers queries in the best known query bound O(lgn(lgn/lglgn)^d-3+k).
    Furthermore, we show that any data structure for the d-dimensional orthogonal range reporting problem in the pointer machine model of computation that uses S(n) space must spend Ω((lgn/lg(S(n)/n))^⌊d/2⌋-1) time to answer queries. Thus, if S(n)/n is poly-logarithmic, then the query time is at least Ω((lgn/lglgn)^⌊d/2⌋-1). This is the first known non-trivial higher dimensional orthogonal range reporting query lower bound and it has two important implications. First, it shows that the query bound increases with dimension. Second, in combination with our upper bounds it shows that the optimal query bound increases from Θ(lgn+k) to Ω((lgn/lglgn)²+k) somewhere between three and six dimensions.
    Finally, we show that our techniques also lead to improved structures for point location in rectilinear subdivisions, that is, the problem of storing a set of n disjoint d-dimensional axis-orthogonal rectangles, such that the rectangle containing a query point q can be found efficiently.

In orthogonal range reporting we are to preprocess N points in d dimensions such that the points inside an axis-aligned query box can be found efficiently. This is a fundamental problem in various fields, including spatial databases and computational geometry.
In this paper we provide a number of improvements for three and higher dimensional orthogonal range reporting: In the pointer machine model, we improve all the best previous results available, some of which have not seen any improvements in almost two decades. In the I/O-model, we improve the previously known three-dimensional structures and provide the first (non-trivial) structures for four and higher dimensions.

Predicting the success of students participating in introductory programming courses has been an active research area for more than 25 years. Until recently, no variables or tests have had any significant predictive power. However, Dehnadi and Bornat claim to have found a simple test for programming aptitude to cleanly separate programming sheep from non-programming goats. We briefly present their theory and test instruments.
We have repeated their test in our local context in order to verify and perhaps generalise their findings, but we could not show that the test predicts students' success in our introductory programming course.
Based on this failure of the test instrument, we discuss various explanations for our differing results and suggest a research method from which it may be possible to generalise local results in this area. Furthermore, we discuss and criticize Dehnadi and Bornat's programming aptitude test and devise alternative test instruments.

	Kasper Green Larsen
	Ph.D. student
	August 2008 - (expected) July 2013
	MADALGO (Center for Massive Data Algorithmics)
	Department of Computer Science
	Aarhus University

	Contact Information
	Mail: larsen@cs.au.dk

Awards:

Publications: