We consider the following autocompletion search scenario: imagine a user of a search engine typing a query; then with every keystroke display those completions of the last query word that would lead to the best hits, and also display the best such hits. The following problem is at the core of this feature: for a fixed document collection, given a set D of documents, and an alphabetical range W of words, compute the set of all word-in-document pairs ( w , d ) from the collection such that w ∈ W and d ∈ D . We present a new data structure with the help of which such autocompletion queries can be processed, on the average, in time linear in the input plus output size, independent of the size of the underlying document collection. At the same time, our data structure uses no more space than an inverted index. Actual query processing times on a large test collection correlate almost perfectly with our theoretical bound.

We show that there exists a constant $\omega < 1$ such that the fully dynamic d-dimensional orthogonal range reporting problem for any constant $d \ge 2$ can be solved in time $O(\log^{\omega+d-2} n)$ for updates and time $O((\log n / \log\log n)^{d-1} + r)$ for queries. Here n is the number of points stored and r is the number of points reported. The space usage is $O(n \log^{\omega+d-2} n)$. For $d=2$ our results are optimal in terms of time per operation, and this is the main contribution of this paper. Also for $d=2$, we give a new improved fully dynamic structure supporting 3-sided queries. The model of computation is a unit cost RAM@. We order the coordinates of points using list order as defined in the paper.

We consider the problem of maintaining a dynamic set of integers and answering queries of the form: report a point (equivalently, all points) in a given interval. Range searching is a natural and fundamental variant of integer search, and can be solved using predecessor search. However, for a RAM with w-bit words, we show how to perform updates in O(lg w) time and answer queries in O(lg lg w) time. The update time is identical to the van Emde Boas structure, but the query time is exponentially faster. Existing lower bounds show that achieving our query time for predecessor search requires doubly-exponentially slower updates. We present some arguments supporting the conjecture that our solution is optimal.Our solution is based on a new and interesting recursion idea which is "more extreme" that the van Emde Boas recursion. Whereas van Emde Boas uses a simple recursion (repeated halving) on each path in a trie, we use a nontrivial, van Emde Boas-like recursion on every such path. Despite this, our algorithm is quite clean when seen from the right angle. To achieve linear space for our data structure, we solve a problem which is of independent interest. We develop the first scheme for dynamic perfect hashing requiring sublinear space. This gives a dynamic Bloomier filter (a storage scheme for sparse vectors) which uses low space. We strengthen previous lower bounds to show that these results are optimal.