Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Dynamic Indexability: The Query-Update Tradeoff for One-Dimensional
  Range Queries   The B-tree is a fundamental secondary index structure that is widely used for
answering one-dimensional range reporting queries. Given a set of $N$ keys, a
range query can be answered in $O(\log_B \nm + \frac{K}{B})$ I/Os, where $B$ is
the disk block size, $K$ the output size, and $M$ the size of the main memory
buffer. When keys are inserted or deleted, the B-tree is updated in $O(\log_B
N)$ I/Os, if we require the resulting changes to be committed to disk right
away. Otherwise, the memory buffer can be used to buffer the recent updates,
and changes can be written to disk in batches, which significantly lowers the
amortized update cost. A systematic way of batching up updates is to use the
logarithmic method, combined with fractional cascading, resulting in a dynamic
B-tree that supports insertions in $O(\frac{1}{B}\log\nm)$ I/Os and queries in
$O(\log\nm + \frac{K}{B})$ I/Os. Such bounds have also been matched by several
known dynamic B-tree variants in the database literature.
  In this paper, we prove that for any dynamic one-dimensional range query
index structure with query cost $O(q+\frac{K}{B})$ and amortized insertion cost
$O(u/B)$, the tradeoff $q\cdot \log(u/q) = \Omega(\log B)$ must hold if
$q=O(\log B)$. For most reasonable values of the parameters, we have $\nm =
B^{O(1)}$, in which case our query-insertion tradeoff implies that the bounds
mentioned above are already optimal. Our lower bounds hold in a dynamic version
of the {\em indexability model}, which is of independent interests.

16
The categories of this paper are: stat
10
The categories of this paper are: q-bio
7
The categories of this paper are: hep-th
32
The categories of this paper are: atom-ph
31
The categories of this paper are: ao-sci
11
The categories of this paper are: hep-lat
19
The categories of this paper are: eess
4
The categories of this paper are: cond-mat
6
The categories of this paper are: astro-ph
35
The categories of this paper are: mtrl-th
28
The categories of this paper are: alg-geom
29
The categories of this paper are: funct-an
9
The categories of this paper are: nlin
33
The categories of this paper are: plasm-ph
18
The categories of this paper are: econ
0
The categories of this paper are: hep-ph