Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Sub-O(log n) Out-of-Order Sliding-Window Aggregation   Sliding-window aggregation summarizes the most recent information in a data
stream. Users specify how that summary is computed, usually as an associative
binary operator because this is the most general known form for which it is
possible to avoid naively scanning every window. For strictly in-order
arrivals, there are algorithms with $O(1)$ time per window change assuming
associative operators. Meanwhile, it is common in practice for streams to have
data arriving slightly out of order, for instance, due to clock drifts or
communication delays. Unfortunately, for out-of-order streams, one has to
resort to latency-prone buffering or pay $O(\log n)$ time per insert or evict,
where $n$ is the window size.
  This paper presents the design, analysis, and implementation of FiBA, a novel
sliding-window aggregation algorithm with an amortized upper bound of $O(\log
d)$ time per insert or evict, where $d$ is the distance of the inserted or
evicted value to the closer end of the window. This means $O(1)$ time for
in-order arrivals and nearly $O(1)$ time for slightly out-of-order arrivals,
with a smooth transition towards $O(\log n)$ as $d$ approaches $n$. We also
prove a matching lower bound on running time, showing optimality. Our algorithm
is as general as the prior state-of-the-art: it requires associativity, but not
invertibility nor commutativity. At the heart of the algorithm is a careful
combination of finger-searching techniques, lazy rebalancing, and
position-aware partial aggregates. We further show how to answer range queries
that aggregate subwindows for window sharing. Finally, our experimental
evaluation shows that FiBA performs well in practice and supports the
theoretical findings.

21
The categories of this paper are: adap-org
17
The categories of this paper are: q-fin
16
The categories of this paper are: stat
6
The categories of this paper are: astro-ph
36
The categories of this paper are: cmp-lg
33
The categories of this paper are: plasm-ph
28
The categories of this paper are: alg-geom
0
The categories of this paper are: hep-ph
9
The categories of this paper are: nlin
31
The categories of this paper are: ao-sci
2
The categories of this paper are: math
24
The categories of this paper are: dg-ga
8
The categories of this paper are: hep-ex
18
The categories of this paper are: econ
22
The categories of this paper are: chao-dyn
25
The categories of this paper are: patt-sol