Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Approximate Data Structures with Applications   This paper explores the notion of approximate data structures, which return
approximately correct answers to queries, but run faster than their exact
counterparts. The paper describes approximate variants of the van Emde Boas
data structure, which support the same dynamic operations as the standard van
Emde Boas data structure (min, max, successor, predecessor, and existence
queries, as well as insertion and deletion), except that answers to queries are
approximate. The variants support all operations in constant time provided the
performance guarantee is 1+1/polylog(n), and in O(loglogn) time provided the
performance guarantee is 1+1/polynomial(n), for n elements in the data
structure.
  Applications described include Prim's minimum-spanning-tree algorithm,
Dijkstra's single-source shortest paths algorithm, and an on-line variant of
Graham's convex hull algorithm. To obtain output which approximates the desired
output with the performance guarantee tending to 1, Prim's algorithm requires
only linear time, Dijkstra's algorithm requires O(mloglogn) time, and the
on-line variant of Graham's algorithm requires constant amortized time per
operation.

2
The categories of this paper are: math
35
The categories of this paper are: mtrl-th
5
The categories of this paper are: gr-qc
23
The categories of this paper are: solv-int
18
The categories of this paper are: econ
30
The categories of this paper are: q-alg
9
The categories of this paper are: nlin
37
The categories of this paper are: supr-con
8
The categories of this paper are: hep-ex
3
The categories of this paper are: physics
34
The categories of this paper are: chem-ph
4
The categories of this paper are: cond-mat
33
The categories of this paper are: plasm-ph
14
The categories of this paper are: math-ph
13
The categories of this paper are: quant-ph
10
The categories of this paper are: q-bio