Database Reference
In-Depth Information
Figure 2. The TKSI Algorithm
The TKSI algorithm is presented in Figure 2. In the first step, TKSI initializes the set of Top-k Sky-
line objects ξ and the variable
cont
registers the number of top objects produced by the algorithm. In
step 2, TKSI identifies the Top-k objects in terms of SFM. In the step 2a-b), the next best object
o
t
from
the SFM metric is completely accessed. This object is a Top-k Skyline candidate because it has the fol-
lowing best skyline frequency value. However, TKSI must verify if
o
t
is incomparable. TKSI may select
sorted indices in a round-robin way in order to check if an object is incomparable. Nevertheless, based
on the properties of SFM, we have implemented a heuristic that guides TKSI in the space of possibly
good objects, and avoids excessive accesses of non-necessary objects. For simplicity, we suppose that
attributes of the multidimensional criteria are maximized. Since 2
q
- 1 subspaces are calculated to com-
pute the skyline frequency metric, TKSI computes a monotonic function ∑
∧
a
∧
m
s(a) / (2
q
- 1) with respect
to the last object seen in each source, in order to select the best one. Intuitively, while this function is
close to 1.0, it indicates that the object belongs to a large number of skylines. We are interested in this
kind of objects because they may discard quickly dominated objects. Because objects are sorted, it is
very likely that any object with the higher values in each index dominates the next objects in the other
indices. Thus, sources with the maximum value of the monotonic function will be selected, and scanned
for minimizing the number of accesses. Finally, if
o
t
is dominated by some seen intermediate object in
the selected index, then in step 2d) the object
o
t
is discarded. In case of
o
t
is non-dominated with respect
to the seen objects; then, in step 2e) the object
o
t
is a Top-k Skyline Frequency object and it is inserted
into ξ. Thus, the algorithm continues until
k
objects are found.
Finally, the Theorem 1 shows lower bound for TKSI algorithm.
