Database Reference
In-Depth Information
5
5
15%
10%
5%
15%
10%
5%
4
4
3
3
2
2
1
1
0
0
5
10
15
20
25
5
10
15
20
25
Parameter k
Parameter k
(a) Top-
k
simple typicality queries.
(b) Top-
k
discriminative typicality queries.
5
15%
10%
5%
4
3
2
1
0
5
10
15
20
25
Parameter k
(c) Top-
k
representative typicality queries.
Fig. 4.9
The error rates of having different amount of noises with respect to
k
.
300
400
DTLA
LT-tree construction
LT3
Exact
DLTA
LT-tree construction
LT3
RT
250
350
300
200
250
150
200
150
100
100
50
50
0
0
2
2.5
3
3.5
4
5
10
15
20
25
Neighborhood threshold
Parameter k
(a) Runtime vs. neighborhood.
(b) Runtime vs.
k
.
3000
Exact
DLTA
LT-tree construction
LT3
RT
Exact
DLTA
LT-tree
c
onstruction
LT3
RT
1400
2500
1200
2000
1000
800
1500
600
1000
400
500
200
0
0
5
10
15
20
25
20000 40000 60000 80000 100000
Number of attributes
Number of tuples
(c) Runtime vs. dimensionality.
(d) Runtime vs. cardinality.
Fig. 4.10
Efficiency and scalability of answering top-
k
simple typicality queries.
The error rate of the exact algorithm is always 0.
We compare three approximation techniques: the randomized tournament method
(RT, Algorithm 4.2), the direct local typicality approximation method (DLTA, Sec-
tion 4.2.2), and the LT-tree tournament method (LT3, Section 4.2.3). By default, we
set the number of instances to 10
000, the dimensionality to 5 attributes, and con-
duct top-10 simple typicality queries. When local typicality is computed, by default
,
