Database Reference
In-Depth Information
Figure 3. Skyline size
some object from I
i
dominates
o
or none of the objects better than
o
in the attribute
i
dominates to
o
. If
o
is incomparable, then
o
is a Top-k Skyline object and it is added in the set of answers. This process
continues until computing the top k objects.
DBLP data were stored in relational tables on Oracle 9i, and sorted based on each dimension. The
experiments were evaluated on a SunFire V440 machine equipped with 2 processors Sparcv9 of 1.281
MHZ, 16 GB of memory and 4 disks Ultra320 SCSI of 73 GB running on SunOS 5.10 (Solaris 10).
Quality and Performance of the Top-Skyline Technique
We studied the quality of the TKSI, and we compare its performance with respect to the BUS algorithm.
We ran 25 queries on subset of 13,029 objects.
In Figure 3, we report the ratio of the skyline size based on the multidimensional criteria. In general,
we observe that the skyline size is larger for high dimensional queries. In the studied queries, the skyline
size ranges from 6% to 43% of the total number of objects that satisfy the multidimensional criteria.
Figure 4 reports on the number of probes performed by TKSI and BUS (logarithmic scale). We can
observe that TKSI reduces the number of probes by at least three and half orders of magnitude with
respect to the bottom-up solution implemented by the BUS algorithm. This is because TKSI does not
build the skyline completely.
Additionally, the quality of the Top-k Skyline objects identified by the ranking engine is shown in
Figure 5. NSF values are between 0.37 and 0.75, i.e., the retrieved objects dominate in at most 75% of
the subspaces of the multidimensional criteria and they may be of good quality. For Top-k Skyline que-
ries for six and seven dimensions, NSF is near to 0.5; this indicates that selected objects dominate in
almost 50% of the subspaces of the multidimensional criteria. For Top-k Skyline queries with five di-
mensions, NSF is between 0.6 and 0.75; thus, selected objects are more dominators.
