Database Reference
In-Depth Information
Figure 1. Lattice for the multidimensional criteria
BUS may be adapted to build the Top-k Skyline. First, BUS computes the lattice including the whole
Skyline; second, it calculates the SFM values for each Skyline object; and finally, it sorts the Skyline
by the SFM and returns the top-k objects. However, time complexity for Skyline queries is high and it
depends on the size of the input data set and the number of probes performed. In general, the problem
of identifying the Skyline is O(n
2
) (Godfrey et al., 2005); this is because all the input objects need to
be compared against themselves to probe the multidimensional criteria. Our goal is to minimize non-
necessary probes building the Skyline partially until the top-k objects are produced.
BUS requires the computation of the entire Skyline and executes probes of the multidimensional
function over the whole Skyline objects. Thus, we propose the use of Top-k Skyline Index (TKSI) to
efficiently solve this problem based on the Skyline Frequency Metric (SFM).
Consider Table 4 that shows a set of sorted indices I
1
, …, I
5
on each attribute of multidimensional
criteria and SFM values, and the first object
8846
characterized by the highest SFM value. I
1
, …, I
5
contain the objects sorted descendantly. We may observe that not exists an object above
8846
in all
indices I
1
, …, I
4
, and therefore
8846
is not dominated by any object and it is a Skyline object. Since
8846
is a Skyline and has the highest SFM value,
8846
is the Top-1 Skyline. Thus, it is not necessary
to completely build the Skyline whose size is five in order to produce the answer for our Top-1 Skyline
query. Next, we introduce the following property:
Table 4. Indices
I
1
I
2
I
3
I
4
I
5
Id
EDBT
Id
ICDE
Id
VLDB
Id
SIGMOD
Id
SFM
8846
10
19660
49
8846
35
23870
39
8846
12
19660
9
5932
37
20259
30
5932
32
23870
10
5932
6
23870
27
23870
26
20259
30
19660
8
23870
3
8846
23
5932
24
8846
28
5932
7
20259
2
20259
16
19660
21
19660
18
20259
4
