Databases Reference
In-Depth Information
2222222
2222222
2211122
221
C
122
2211122
2222222
2222222
Figure 12.7
Grids in the CELL method.
Let
a
be the number of objects in cell
C
,
b
1
be the total number of objects in the
level-1 cells, and
b
2
be the total number of objects in the level-2 cells. We can apply the
following rules.
Level-1 cell pruning rule
: Based on the level-1 cell property, if
a
C
b
1
>d
n
e, then
every object
o
in
C
is not a
DB
-outlier because all those objects in
C
and
the level-1 cells are in the
r
-neighborhood of
o
, and there are at least d
.
r
,
/
n
e such
neighbors.
Level-2 cell pruning rule
: Based on the level-2 cell property, if
a
C
b
1
C
b
2
<
d
n
eC1, then all objects in
C
are
DB
.
r
,
/
-outliers because each of their
r
-
neighborhoods has less than d
n
e other objects.
Using the preceding two rules, the CELL method organizes objects into groups using
a grid—all objects in a cell form a group. For groups satisfying one of the two rules, we
can determine that either all objects in a cell are outliers or nonoutliers, and thus do not
need to check those objects one by one. Moreover, to apply the two rules, we need only
check a limited number of cells close to a target cell instead of the whole data set.
Using the previous two rules, many objects can be determined as being either
nonoutliers or outliers. We only need to check the objects that cannot be pruned using
the two rules. Even for such an object,
o
, we need only compute the distance between
o
and the objects in the level-2 cells with respect to
o
. This is because all objects in the
level-1 cells have a distance of at most
r
to
o
, and all objects not in a level-1 or level-2
cell must have a distance of more than
r
from
o
, and thus cannot be in the
r
-neighbor-
hood of
o
.
When the data set is very large so that most of the data are stored on disk, the CELL
method may incur many random accesses to disk, which is costly. An alternative method
was proposed, which uses a very small amount of main memory (around 1% of the data
