Internati
o
nal
Journal of Ele
c
trical
and Computer
Engineering
(IJE
CE)
V
o
l.
5, N
o
. 5
,
O
c
tob
e
r
201
5, p
p
. 1
188
~119
3
I
S
SN
: 208
8-8
7
0
8
1
188
Jo
urn
a
l
h
o
me
pa
ge
: h
ttp
://iaesjo
u
r
na
l.com/
o
n
lin
e/ind
e
x.ph
p
/
IJECE
Computing Subspace Skylines without Dominance Tests using
Set Interaction Approaches
T. Vijaya S
a
r
a
dhi
*
,
Dr. K. Subr
ahm
a
n
y
am**
,
Dr. Ch. V
.
Phani
Krishna***
*Departm
ent
of
Com
puter s
c
ien
c
e and
Eng
i
neer
in
g, K.
L Univ
ers
i
t
y
,
**Departm
ent
of
Com
puter s
c
i
e
n
ce
and
Engineering, K.L Univ
ersity
***Department
of Computer science
and
Engin
e
ering, K.L Univ
ersity
Article Info
A
B
STRAC
T
Article histo
r
y:
Received Feb 21, 2015
Rev
i
sed
Ju
l 4
,
2
015
Accepte
d
J
u
l 20, 2015
Now a da
y’s
prefer
enc
e
an
s
w
ering pla
y
s
m
a
jor role
in
all
cru
c
ia
l
applications. If
user wants
to
find top
k–ob
jects from a s
e
t of h
i
gh
dimensional data based on
an
y
monotonic function r
e
q
u
ires huge
computation
.
One of th
e promising me
thods to compute pref
er
ence set is
Skyline Techno
logy.
Sk
y lin
e co
m
putation re
turn
s the set obj
ec
ts that
are no
t
overruled b
y
an
y other obj
ec
ts in n a m
u
lti dim
e
nsional space
. If data is high
dimensional, different
use
r
s re
que
sts sky
line
set based
on differ
e
n
t
dimensions. It
requires subspace sk
y
lin
e com
putation
.
If ob
j
ects
ar
e d-
dim
e
nsional we
need to
com
pute
sk
y
lin
e sets in 2
d
different s
ubs
p
aces
,
ca
lled
as
S
KYLINE CUBE com
putat
i
on, which in
cur
s
lot of
computation cost. In
this
paper we ad
dres
s
the proble
m
of finding s
u
bs
pace s
k
yline
c
o
m
putation
with minimum e
ffort b
y
using simple se
t interaction methods. B
y
that we
can
decre
a
s
e
th
e nu
m
b
er of s
ubs
pace s
k
y
l
ines
ne
ed t
o
be s
earch
ed to
find full s
k
y
cube. In this pap
e
r we developed
one
algorithm which uses Boolean alg
e
bra
rules to
redu
ce d
o
minance
test fo
r preparing sub s
p
ace sk
y
lines
.
Keyword:
Hi
g
h
di
m
e
nsi
onal
dat
a
Sky
l
i
n
e c
o
m
put
at
i
on
Sk
ylin
e cu
b
e
Copyright ©
201
5 Institut
e
o
f
Ad
vanced
Engin
eer
ing and S
c
i
e
nce.
All rights re
se
rve
d
.
Co
rresp
ond
i
ng
Autho
r
:
T. Vi
jay
a
Sa
ra
dhi
Depa
rt
m
e
nt
of
C
o
m
put
er sci
e
nce a
n
d
E
ngi
n
eeri
n
g,
K
.
L.
Un
iv
e
r
s
i
ty
,
V
a
d
d
e
s
w
ar
am.
e-m
a
il
:
saradhi
14
4
0
@
k
l
u
ni
ve
rsi
t
y
.i
n
1.
INTRODUCTION
Now day’s pe
ople
are expecting
accurate pre
d
ictions
from
available applic
ations
base
d
on e
n
orm
ous
pre
v
ious
data
and curre
nt
dat
a
[1]. So
for e
x
act pre
d
iction, pe
ople
need to c
o
ns
ider eac
h a
n
d e
v
ery
pi
ece of
data. If
data
is
high dim
e
nsional
data
we
ne
ed to c
onsi
d
er
each a
n
d e
v
ery
dim
e
nsion
[2]. So the
r
e is
ne
ed
of
m
u
lti criteria decision m
a
king system
.
In
s
e
lection, Player A dom
inates
pl
ay
er B
i
f
a
n
d
onl
y
i
f
pl
ay
e
r
A i
s
bet
t
e
r t
h
a
n
pl
a
y
er B
i
n
m
i
nim
u
m
one di
m
e
nsi
o
n an
d
pl
ay
er A i
s
n
o
t
w
o
rst
t
h
a
n
pl
ay
e
r
B
i
n
al
l
dim
e
nsi
o
n[
3]
.
For instance as
sum
e
franchise
wants to
select players. Fra
n
chise X wa
nt
s t
o
con
s
i
d
er
onl
y
fi
el
di
ng
_eco
nom
y
and
bo
wl
i
n
g
econ
o
m
y
of pl
ay
ers f
o
r s
e
l
ect
i
on. S
o
A.fi
el
di
n
g_ec
o
nom
y
<=B
. fi
el
di
ng
_ec
o
n
o
m
y
and
A.
bo
wl
i
n
g_ec
o
nom
y
<=B
.bo
w
l
i
n
g
_
ec
on
om
y
.
one
o
f
t
h
e
ef
fi
ci
ent
com
put
at
i
on t
o
fi
n
d
t
h
e re
q
u
i
r
e
d
s
u
bset
o
f
o
b
j
ect no
t d
o
min
a
ted
m
y
a
n
y o
t
h
e
r rem
a
in
in
g
o
b
j
ect is sk
ylin
e co
mp
u
t
ation
[3
]. In
trad
ition
a
l sk
ylin
e
com
put
at
i
on t
h
ey
are co
nsi
d
eri
n
g fi
xe
d di
m
e
nsi
ons
of
o
b
ject
s [
4
]
.
I
n
sel
ect
i
on Di
f
f
e
r
ent
f
r
anc
h
i
s
e
req
u
i
r
e
r
e
su
lts
b
a
sed
on
d
i
f
f
e
r
e
n
t
cr
iter
i
a.
O
t
h
e
r fr
an
ch
ise m
a
y co
n
s
id
er
catch_dr
op
s and
d
u
c
k_
ou
ts.
So r
ecen
tly sub
space s
k
yline
becam
e
m
o
re crucial in
sk
yl
ine
com
putation. If player
is ha
vi
ng D
dimensions t
o
ans
w
er all
user
que
ri
es w
e
need t
o
c
onsi
d
er
2
D
-1 s
ub s
p
ace dim
e
nsions. Fi
ndi
ng s
kyline of proble
m space by finding all
su
b sp
ace sk
ylin
es is called sk
ylin
e cu
b
e
[
5
]. Ev
en
thoug
h ex
isting
meth
od
s seem
s to
b
e
ov
er
co
me th
e
p
r
ob
lem
o
f
unn
ecessary co
m
p
u
t
ation
o
f
domin
an
ce tests
lik
e prun
ing
t
h
rou
g
h
sp
atial relatio
n
s
, sk
y
cub
e
co
m
p
u
t
atio
n
has still its u
n
i
q
u
e
ch
allen
g
e
s
[5
,
1
]
. In
sk
y cu
b
e
we
will com
p
u
t
e sk
ylin
e sets in
all d
i
fferen
t
sub
spaces. In e
x
isting
studies to
build Sky c
u
be t
h
ey ha
ve t
o
find a
n
d sear
c
h
s
k
y lines i
n
all a
v
ailable s
u
bs
paces,
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE Vo
l. 5
,
N
o
. 5
,
O
c
tob
e
r
20
15
:
118
8
–
11
93
1
189
wh
ich
m
a
y le
ad
to
p
itiab
l
e p
e
rform
a
n
ce in
h
i
g
h
d
i
m
e
n
s
io
n
a
l data sets.
Stella
r,
a s
k
y
cube c
o
m
p
u
t
at
i
on
m
e
thod
pre
v
e
n
ts com
puting e
v
ery s
u
bspace
skyline [3,
5].
It
starts fi
ndi
ng
seed
skylines from
that it
builds
full space s
k
yline with the
help
of decisive s
ubs
paces c
onc
epts .In this
, problem
is
determine num
ber of see
d
skyline groups
and
we nee
d
t
o
com
p
ar
e ev
e
r
y
ob
ject
o
f
se
ed sky
l
i
n
e
gr
o
up
wi
t
h
ob
ject
s not
bel
o
ng
s t
o
f
u
l
l
space skyline
.
This will be the sour
ce
of
deprive
d
pe
rform
a
nce [5]. St
ellar algorithm
won’t consi
d
er the
relations
hips between propert
i
es
am
ong
skyl
ine points yet to be
de
rive
d
on di
ffe
rent s
ubspaces
[6, 1].
We ca
n
t
a
ke ad
va
nt
age
o
f
t
h
ese
rel
a
t
i
ons
hi
ps t
o
de
ri
ve s
k
y
l
i
n
es
of
ot
he
r s
u
b
s
pace
s f
o
r
fast
c
o
m
put
at
i
on
o
f
s
k
y
cube
.
t
h
i
s
wo
rk co
n
s
i
s
t
s
of t
w
o i
m
port
a
nt
aspe
ct
s fi
rst
one i
s
reduci
n
g do
m
i
nance t
e
st
to com
put
e sky
cube i
n
a subs
pace by ide
n
tifying the sub s
p
aces from
which we can derive s
k
ylines without dom
i
nance
t
e
st
s. Seco
nd
one i
s
we ca
n
red
u
ce ef
f
o
rt
by
res
u
l
t
shari
ng i
n
s
k
y
cu
b
e
com
put
at
i
on.
W
e
can
di
vi
d
e
t
h
e
subspace
s as
2 groups.
Firs
t
group is known as
CATE
GORY-
I s
u
bsp
a
c
e
. Skyline of t
h
ese types
of s
p
aces
can be
fo
u
nd
wi
t
h
si
m
p
l
e
deduct
i
o
n
rul
e
s.
Ot
he
r g
r
o
u
p
,
C
A
TE
GOR
Y-
II, s
u
bspa
ce s
k
y
l
i
n
es can
be
fo
un
d
usi
n
g s
p
eci
al
d
e
ri
vat
i
o
n f
o
rm
ul
as
or
p
o
ssi
bl
y
by
pe
rf
o
r
m
i
n
g
dom
i
n
ance t
e
st
s
Th
is
p
a
p
e
r is
stru
ctured
as
fo
llo
ws: Section
2
is
related
to
prelimin
aries and
th
e previo
u
s
wo
rk
related
to
th
is
work. Section
3
states th
e
p
r
o
b
l
em
in
formal way and
it will b
e
ex
ecu
t
ed
with
sm
al
l
ex
am
p
l
e
Section
4 cont
ain the propos
ed algo
rithm
for s
u
bspace
s
k
yline com
puta
tion. In
Section 5 pape
r
wi
ll
be
concl
ude
d wi
t
h
t
h
e di
rect
i
o
ns of
f
u
t
u
re wo
rk
2.
RELATED WORK
2
.
1
Preliminaries
Skyline Com
putati
o
n:
we
start d
e
fin
i
ng
sk
ylin
e co
m
p
u
t
atio
n
with th
e assu
m
p
tio
n
t
h
at sm
a
ller v
a
lues are
bet
t
e
r. S
k
y
l
i
n
e com
put
at
i
on r
e
t
r
i
e
ves su
bset
of el
em
ent
s
fr
om
t
h
e gi
ven s
e
t
of el
em
ent
s
, t
h
at
subset
i
s
cal
l
e
d
sk
ylin
e set
[7
]
.
Fo
rm
ally ass
u
m
e
th
at d
-
di
m
e
n
s
io
n
a
l
reco
rd
set
with card
i
n
ality n
is av
ailab
l
e. Skylin
e
com
put
at
i
on re
t
r
i
e
ves m
dat
a
poi
nt
s
whi
c
h
are n
o
t
dom
i
n
at
ed by
any
ot
her
poi
nt
s [8
,
9]
. To s
p
eci
fy
t
h
at
a
poi
nt
X
d
o
m
i
nat
e
s an
ot
he
r
p
o
i
n
t
Y can
be
r
e
prese
n
t
e
d
as
X
Y i
ff
X[i]
<
=
Y[i]
∀
1<=i<
=
d a
n
d
k s
u
c
h
t
h
at
X
[
k
]
<Y
[k
] [10
]
.
H
e
r
e
i
th
di
m
e
nsi
on
of t
h
e
X o
b
j
ect
i
s
de
not
e
d
as
X[
i].
We can
re
pres
ent the facts t
h
at X not
dom
i
n
at
i
ng Y
usi
n
g X
Y. X
≈
Y to indicate that X and Y a
r
e incom
p
arabl
e
(
m
eans X
Y
and Y
X) a
n
d
x
y
to indicate that
either
x
y
or
x=
y
h
o
l
d
s
. If
D is t
h
e
d
a
ta set th
en
sk
ylin
e set o
f
D
i
s
defi
n
e
d
as
{
X
∈
D
| Y
X,
∀
y
∈
D
}
Initial sky line algorit
hm
s ar
e BNL
(Bloc
k
Nested loop)
whic
h com
p
ares each point
with all othe
r
p
o
i
n
t
s an
d qu
alifies o
n
l
y
when
it is
n
o
t
domin
ated
b
y
al
l
o
t
h
e
rs
[1
0
]
.
SFS (Sort Filter Sk
ylin
e) is same as
BNL
b
u
t
it sorts th
e
d
a
ta b
y
th
is it will b
e
ad
v
a
n
t
ag
eou
s
t
h
an
B
N
L
[9
]. DC (Di
v
id
e
and
Co
nqu
er)
d
i
v
i
des th
e
gi
ve
n s
p
ace
i
n
t
o
regi
on
s a
n
d
f
i
nds
t
h
e
sky
l
i
n
e i
n
e
v
e
r
y
re
gi
on
by
t
h
at
i
t
pr
od
uces
t
h
e
fi
na
l
sky
l
i
n
e
[3]
.
L
E
SS
(Lin
ear Elim
in
atio
n
Sort sk
yl
in
e) is
h
a
v
i
ng
attractiv
e
wors
t case pe
rform
a
nce
[7].
In
all abo
v
e
algo
rithm
s
we
m
u
st
read t
h
e
d
a
t
a
base at
l
east
o
n
ce. B
u
t
I
n
de
x
base
d m
e
t
hods
nee
d
t
o
vi
si
t
o
n
l
y
a p
o
r
t
i
o
n
of
dat
a
base
[
8
]
.
3.
PROP
OSE
D
FRAMEW
O
R
K
We will take n-dim
e
nsional s
p
ace D = {d1, d2, d3, ...
dn}
. Ass
u
m
e
a
set
of points S in space D.If
yo
u
co
n
s
i
d
er an
y po
in
t P in
set S, we can refer P(d
i
) as
d
th
di
m
e
nsi
on val
u
e
of
poi
nt
P. T
o
t
a
l
p
o
ssi
bl
e
num
bers
of s
u
bspaces (M
) of full space
D a
r
e 2
D
. i.e
.
M
⊆
2
D
. Conside
r
a
U-dim
e
nsiona
l subs
pace
of t
h
e full
space D.If we want
to declare
M
as
m
a
xima
l subs
pace i
n
M there s
h
oul
d
not exist,
V
∈
M su
ch
th
at
U
⊂
V
[3]
. In
a s
ubs
pace, U
⊆
D.
Le
t
p,
q a
r
e
p
o
i
n
t
s
. I
f
p i
s
sai
d
t
o
be
do
mina
t
e
a
n
o
t
h
e
r
p
o
i
n
t
q,
de
n
o
t
e
d
by
p
Uq
,
if
∀
di
∈
U
, p(
di)
≤
q(
di
)
a
n
d
∃
dj
∈
U
,
p(
dj)
<
q
(
dj
)[
10
].w
e
use th
e
n
o
t
ation
p
≈
U
q
t
o
re
pr
esent
t
h
at
p a
n
d
q are
unique
. It
m
e
an p i
s
not
d
o
m
i
nat
i
ng q an
d q i
s
not
dom
i
n
at
i
ng p. i
f
al
l
respect
i
v
e di
m
e
nsi
o
n val
u
es of
any
two
poi
nts of
any sub s
p
ace
skyline set are
e
qual T
h
e
n
those two
poi
nts are known a
s
indistinct sky
line
points.
We can re
prese
n
t indistinct
poi
nt
s
p
,
q o
f
su
bs
pace
U as
p =U
q
if
∀
x
i
∈
U
, p(
x
i
)=q
(
x
i
). Poi
n
t p
can be
in
d
i
cated
as
ind
i
sstin
ct
po
in
t
u
s
ing
no
tatio
n
#
p
.
Definiti
on 1:
Point
‘O’ of c
e
rtain set X
wants to
be qual
ified
as s
k
yline poi
nt in ce
rtain subs
pace S of
full
space D
iff
∀
q
∈
S
, O
Sq. Sub s
p
ace s
k
yline set consists a
ll skyline
point
s
in that
subs
p
ace. If you c
onsider
full space
with D
dim
e
nsions then s
k
y
cube of S c
a
n
be
considere
d
as
m
u
lti set of all sub
space
skyline sets
{SKY
(S) |S
∈
2
D
}
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
C
o
m
put
i
n
g
S
u
b
sp
ace
Skyl
i
n
e
s
w
i
t
h
o
u
t
D
o
mi
na
nce
Test
s
usi
n
g
Set
I
n
t
e
ract
i
on
Ap
pr
oac
he
s
(T. Vija
ya
S
a
ra
dh
i)
1
190
Collection
of
all sub space s
k
yline sets of
a full space
is
known as Sky
c
ube
.T
his conc
ept is sim
ilar a
s
data
cube c
once
p
t
i
n
dat
a
ware
h
o
u
se. I
f
ful
l
spa
ce i
s
havi
ng
d di
m
e
nsi
ons t
h
e
n
we can f
o
rm
sky
cube by
fi
ndi
ng
sk
ylin
e sets in
2
d
su
bspace
s.
W
i
t
h
sky
cu
be conce
p
t
su
bs
pa
ce sk
yline que
ries can be ans
w
ere
d
effectively.W
e
can fi
nd
sky
l
i
n
e set
s
i
n
t
w
o a
p
p
r
oaches
nam
e
l
y
B
U
S (
bot
t
o
m
up s
k
y
l
i
n
e)
and
TD
S (t
op
do
w
n
s
k
y
l
i
n
e).
w
e ar
e
f
o
llow
i
ng
BU
S [3
].
Definiti
on 2
(I
ndistinc
t
/uniq
u
e
sk
yline)
If we want to qualify on
e p
o
int p
∈
SKL
(
U) as indistinct skyline in
a specified s
u
bspace U the
r
e exist
anot
her p
o
i
n
t
q
∈
SKL(U) with
p
r
op
erties p
≠
q
an
d p=
U
q
.i
f
w
e
wa
nt
t
o
den
o
t
e
a su
bset
,
X a
s
indistinct sky
line
Grou
p
in subspace
U if a
n
d only if it satisfies
the bel
o
w
3 c
o
nditions.
(1) Set siz
e
of
X
≥
2.
(
2
) Al
l
dim
e
nsional va
lues of any two skyline
point
s
of
X s
h
ould
be sam
e
with re
spect to s
u
bs
pace U. (3)
Ta
ke any
sk
ylin
e po
in
t p
∈
X, q
′
∈
S
K
L (U
)
−
X
,
p
≈
Uq
′
.We ca
n declare a sk
yline point ‘p’ of
an
y subspace
U if it it
is n
o
t
m
e
m
b
er o
f
an
y
o
f
the in
d
i
stin
ct skylin
e g
r
o
u
p
.
It
m
ean
s P is un
iqu
e
to th
e
oth
e
r Sk
ylin
e
group
me
m
b
ers
of
the
subs
pace U. We denote p by
≈
p.
In t
h
i
s
w
o
rk t
w
o i
m
port
a
nt
c
o
ncept
s
a
r
e i
ndi
st
i
n
ct
sky
lin
e
gr
oup
s an
d
un
iqu
e
sk
ylin
e grou
p
s
.
W
i
t
h
th
e help
of
i
ndi
st
i
n
ct
s
k
y
l
i
n
e
gr
o
ups
we
use
d
t
o
el
im
i
n
at
e un
necessa
r
y
i
n
f
o
rm
at
i
on fr
om
subs
pace
. B
o
t
h
i
m
port
a
nt
an
d
no
n
re
du
n
d
ant
i
n
f
o
rm
at
i
on wi
l
l
be cha
r
act
eri
zed
by
I
n
di
st
i
n
ct
and
u
n
i
q
ue
s
k
y
l
i
n
e g
r
ou
ps.
R
u
nning Example
:
In
t
h
is
p
a
p
e
r,
we
will co
n
s
i
d
er data set of
6
p
l
ayers,
each
with
4
d
i
m
e
n
s
i
o
n
s
as runn
ing
ex
am
p
l
e.
Th
e p
o
s
sib
l
e
subspace
s are
2
4
-1.In our exa
m
ple to re
pre
s
ent s
k
y cube
we
n
eed to find the
s
k
yline s
e
ts of 15 subs
paces
listed
lik
e Tab
l
e 2
.
Th
ere are
2
ind
i
stin
ct skylin
e p
o
i
n
t
s,
p
1
(BOE
)
and p
2
(BO
E
)
with
v
a
lu
e
3
in th
e subsp
ace
{A}.we will use two
d
i
fferen
t
sy
m
b
o
l
s to id
en
tify un
iq
u
e
and
ind
i
stin
ct sk
ylin
e poin
t
s.
W
ith
th
e
h
e
lp
o
f
th
o
s
e sym
b
o
l
s we can
sp
ecify
th
e SKL ({A,
D})
as m
u
lti set: {{
≈
o
3
},{
≈
o
4
},{#o
1,
#o
2
}}
Tabl
e 1. Sam
p
le
dat
a
set
OBJECTS
BO_(A)
FL_E(B)
ICCBAT_R(C)
ICCBOL_R(D)
P1 3
5
8
10
P2
3
5
7
10
P3
4
6
7
9
P4
6
6
6
8
P5
5
7
11
9
P6
7
10
9
9
Table 2. Subs
paces
and Skyline
Sets
SUB SPAC
E
SKYL
INE
SE
TS
SUB SPAC
E
SKYL
INE
SE
TS
{A} {#P
1,
#
,
P
2
}
{B,D}
{
#P
1,
#P
2
,
≈
P
4
}
{B} {#P
1,
#P
2
} {
C
,D
}
{
≈
P
4
}
{C} {
≈
P
4
} {A,B,C}
{
≈
P
2,
≈
P
4
}
{D} {
≈
P
4
} {A,C,D}
{
≈
P
2,
≈
P
3,
≈
P
4
}
{A,B}
{#P
1,
#P
2
} {B,C,D}
{
≈
P
2,
≈
P
4
}
{A,C}
{
≈
P
2,
≈
P
4
} {A,B,D}
{#P
1,
#P
2
≈
P
3 ,
P
4
}
{A,D}
{#P
1,
#P
2,
≈
P
3,
≈
P
4
} {A,B,C,D}
{
≈
P
2,
≈
P
3,
≈
P
4
}
{B,C} {#P
1,
#P
2
}
Theorem 1
: (
Skyline union derivation
). We can ap
pl
y
uni
on r
u
l
e
t
o
fi
nd s
k
y
l
i
n
e set
s
and o
b
ject
s i
n
sky
l
i
n
e
set. Take a
n
y two s
ub
space
s U and
V of
full space
D.
If
any poi
n
t p
belongs to th
e
skyline sets of bot
h
su
bsp
aces th
en p
will also
b
e
l
o
ng
s t
o
sk
yline set of
u
n
i
o
n
set .i.e if
p
∈
S
K
L
(X
) a
n
d
p
∈
SKL (Y), t
h
en
p
∈
SKL (X
∪
Y)
C
o
ro
lla
ry
1
.
∀
X, Y subs
pace
s, S
K
L
(X)
∩
SKL (Y)
⊆
SKL
(X
∪
Y)
In
o
u
r a
b
ove
e
x
am
pl
e (Tabl
e
1)
, P
1
i
s
a s
k
y
l
i
n
e
poi
nt
i
n
bot
h s
ub
space
s {
A
} a
nd {B
}
.
B
y
t
h
eorem
1,
we can say tha
t
P1 is a skyline in
subs
pace {
A
, B}. M
o
re
over, poi
n
t P
2
is a sk
ylin
e po
in
t
in
bo
th
su
bsp
a
ce o
f
{A, C
}
an
d {B
}. Usi
n
g C
o
r
o
l
l
a
ry
-1
, we h
a
ve can de
ri
ve
t
h
at
poi
nt
{P
2
}
⊂
SKY
({A, B, C}).By th
e ab
ov
e
Deri
vation
we can c
oncl
u
de that it is possible to
de
ri
ve som
e
subs
pace skyline
points using simple set
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE Vo
l. 5
,
N
o
. 5
,
O
c
tob
e
r
20
15
:
118
8
–
11
93
1
191
ope
rat
i
o
ns wi
t
h
o
u
t
pe
rf
orm
i
ng
any
d
o
m
i
nance
t
e
st
s.
Our aim is d
e
riv
i
ng
co
m
p
lete
sk
ylin
e set with
ou
t do
m
i
n
a
n
ce tests. To
ach
i
e
v
e
th
is we sho
u
l
d
inv
e
stig
ate and
defi
ne m
o
re r
u
l
e
s.
Definiti
on 4
:
(
Ca
te
gori
e
s o
f
subsp
a
ces
).
If
all points i
n
a s
u
bspace
s
k
yline ar
e
indi
stinct with eac
h
othe
r t
h
en
we
can rec
o
gnize that subspace as
CAT-1 s
u
bspa
ce. i.e
∀
p;
q
∈
SKL
(U), p=
Uq.If sub space i
s
not CA
T-1 then it will be C
A
T-2 sub spac
e.
Theorem 2
:
T
a
ke any two s
ubs
paces
of C
A
T-1 if there
is
any comm
o
n
skyline po
int between s
u
bspace
skylines then
we can conclude that
subspa
ce skyline intersection is equi
valent to subs
pace skyline union[4]
.
∀
X,
Y
∈
C
A
T
-
1 s
u
b
s
pace
i
f
S
K
L(
X)
∩
SKL(Y)
≠
, then
SK
L(X
)
∩
SK
L (Y
)
= SK
L
(
X
∪
Y
).
Using the
o
rem-2
we ca
n
derive skyline set
with sim
p
le set ope
ration i
n
a CAT-I s
u
bspaces effectively.
Obviously, eve
r
y subspace
wi
th singl
e
dim
e
nsion is a CAT-I Sub space
. We will fallow bottom
up fashion t
o
deri
ve skyline
s
with single
scan in t
h
e single
di
m
e
nsional subs
pace
without an
y dom
i
nance
test. W
e
can
deri
ve s
k
ylines
in C
A
T-II sub spaces
using
unique s
k
ylines.
Theorem 3
:
For any
2 s
u
bs
paces U,
V a
n
d
U
⊆
V, i
f
p i
s
a
uni
que
s
k
y
l
i
n
e
poi
nt
i
n
U t
h
en
p
∈
SK
L (V
) also
.
The
o
rem
3 ca
n
be c
o
nsi
d
e
r
e
d
as
a
deri
vat
i
o
n
o
f
The
o
re
m
-
1.
W
i
t
h
t
h
e
hel
p
of
The
o
r
e
m
-
3
we ca
n
di
rect
l
y
deri
ve s
k
yline
poi
nts in CAT
-
II s
u
bs
paces.
In
o
u
r e
x
i
s
t
i
n
g
exam
pl
e P2,
P
4
bel
o
ngs
t
o
S
K
L {
A
, C
}
wi
t
h
t
h
e
hel
p
o
f
t
h
eo
rem
-
3 we
c
a
n c
oncl
ude
that P2, P4 als
o
bel
o
ngs t
o
t
h
e s
k
yline sets
of
su
persets of {A, C}.
We
speci
fied categories a
n
d subs
pace
sk
ylin
e po
in
ts
in
Tab
l
e 2. Apart fro
m
d
e
riv
e
d
sk
ylin
es
we
n
eed
t
o
find
o
n
ly a s
m
a
ll n
u
m
b
e
r
o
f
sk
ylin
es u
s
ing
tech
n
i
qu
es o
t
her th
an
t
h
e two th
eorem
s
to
form
fu
ll sk
ylin
e
set.
F
i
n
d
i
ng
S
k
y
l
in
es
by
D
o
mina
t
i
o
n
Test
s
Indistinc
t
sk
yl
ines
Whe
n
we try to de
rive skyline points from
s
ubs
pace s
k
ylines indistinct skylines (i.e.
∃
p,q
∈
SK
L(
U)
p
=
Uq
)
in
su
bsp
aces
p
r
even
ts th
e app
licab
ility o
f
u
n
i
qu
e
ru
le.
If
th
at is
th
e
case we can
ap
p
l
y fo
llowing
ru
le
Theorem 4
. For any
su
bs
pac
e
s U,
W
an
d U
⊂
W,i
f
we wa
n
t
t
o
say a poi
nt
p
∈
SKY(U) is
a sk
ylin
e in
su
b
s
pace
W if and
o
n
l
y
if th
ere sh
ou
l
d
no
t ex
ist q
su
ch
t
h
at q
=
U
p, q
W
−
U
p.To d
e
ri
ve s
k
y
l
i
n
e u
s
i
ng
dom
i
n
anc
e
t
e
st
u
s
ing
th
erorem
-4
it req
u
i
res an
ap
pro
ach lik
e BNL
(Blo
ck Nested L
o
op).
In
t
h
is
approach we need t
o
com
p
are the i
n
distinct skyline
s
of U
in
the subspace W-U. T
h
is
rule reduce
s
th
e e
f
fort
[4].
N
e
w u
n
i
qu
e Sk
y
lin
es
:
Up to now we
use
d
to deri
ve sky
line of a space from
its
subspaces. From
exam
ples we c
a
n conclude that all
skylines
of a s
p
ace
not
neces
sarily th
e m
e
mbers
of its s
ubsp
ace s
k
ylines. In
our c
u
rr
e
n
t exam
ple all skyline
poi
nts in s
u
bs
pace {A,
D} a
r
e not s
k
ylines in either
{
A
}
or {
D
}.It m
e
ans a
poi
nt ca
n be
a m
e
m
b
e
r
of a
skyline
s
p
ace
e
v
en though it is not a s
ubs
pac
e
skyline. To derive these type
s of skylines
we nee
d
to do
m
o
re
ex
ercise.
We will d
o
it wit
h
the h
e
lp of en
com
p
ass can
d
i
d
a
t
e
ru
le.
Definiti
on 5
(Enc
om
pass candi
date).
If we wa
nt to
declare
a
poi
nt p as
encom
p
ass
poi
nt in a
n
y subs
pace X,
every
di
m
e
nsion
val
u
e
of t
h
a
t
poi
nt
p sh
o
u
l
d
l
i
e
s bet
w
ee
n
t
h
e m
a
xim
u
m
and m
i
nim
u
m
val
u
es
of t
h
e s
k
y
l
i
n
e
set po
in
ts
with
resp
ect t
o
that
d
i
m
e
n
s
io
n
.
∀
d
i
∈
X,m
i
n
SKL(X)
(d
i
)
≤
p(
d
i
)
≤
ma
x
SKL(X)
(d
i
).
Theorem 5
.
I
f
a poi
nt
p i
s
n
o
t
deri
ve
d by
sky
l
i
n
e de
ri
vat
i
on r
u
l
e
o
r
i
n
d
i
st
i
n
ct
rul
e
o
r
i
t
’
s not
s
k
y
l
i
n
e by
en
co
m
p
ass cand
id
ate
ru
le t
h
en
d
e
fi
n
itely it i
s
no
t a sk
ylin
e.
W
i
t
h
h
e
lp
o
f
t
h
eorem
-5
we can
find
th
e full sk
ylin
e set
i
n
th
e sub
s
p
ace. Th
is th
eorem -5
will b
e
consid
ered
as pr
un
ing
techn
i
qu
e
[
6
].
E
xam
pl
e 5:
In a a
b
ove e
x
a
m
ple skyline set for
subs
pa
ce W
=
{
A
,
D
} can be de
ri
ve
d
as
f
o
l
l
o
ws.
{o
4
}
∈
SKL
(
{D}
)
so i
t
belongs to {
A
,D}.o
1,
o
2
∈
A
s
o
o
1,
o
2
∈W
.From
Encom
p
ass candi
date rule
o
3,
o
5
∈W
because
3
≤
p(
A)
≤
6
and 8
≤
p(
D)
≤
10
.
bu
t
o
3
≺
U
o
5
s
o
fi
nal S
K
L(
W)
={
#o
1
, #o
2,
≈
o
3
,
≈
o
4
}.
SubS
ky
(S:
Data Set, D:
Dimen
s
ion
a
l Sp
ace)
{
While
(X<
-
Ge
narates
u
bs
pace
(D)
≠
)
{
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
C
o
m
put
i
n
g
S
u
b
sp
ace
Skyl
i
n
e
s
w
i
t
h
o
u
t
D
o
mi
na
nce
Test
s
usi
n
g
Set
I
n
t
e
ract
i
on
Ap
pr
oac
he
s
(T. Vija
ya
S
a
ra
dh
i)
1
192
For ea
ch s
u
bspace
W
∈
X do
W.pare
nt is CAT-1 Subspace the
n
sel
ects any
E
q
ual 2 subs
paces
U,
V
W
If
( S
K
L
(
U
)
SKL
(V)
≠
) then
{
S
K
L
(
W) =
SK
L (
U
)
SK
L
(
V
)
W is
a CAT
-I
Subs
pace.
}
Else
{
W is a
CAT
-
II Subspace.
If
(W is
a CAT
-
II
Subs
pace) the
n
F
o
r e
ach s
u
bspace
U
∈
W
D
o
{
Ap
pl
y
t
h
eo
rem
-
3 (
u
ni
que
s
k
y
l
i
n
e r
u
l
e
) a
n
d
C
opy al
l uni
que
s
k
ylines f
r
om
U.P
r
oc
ess
the
indistinct skylines
and use e
n
c
o
m
p
ass rule .
Usi
n
g B
N
L t
o
fi
nd full
space s
k
yline.
}
}
Retu
r
n
(SK
L
(W
))
;
}
4.
CO
NCL
USI
O
N
The
pa
per
w
o
r
k
st
udi
es
sky
l
i
n
e c
o
m
put
at
i
on
of
hi
gh
di
m
e
nsi
o
nal
dat
a
.
We s
h
ow
t
h
at
d
o
m
i
nance
t
e
st
s can be
h
i
ghl
y
re
duce
d
by
fi
n
d
i
n
g
uni
que a
n
d i
n
di
st
i
n
ct
sky
l
i
n
e g
r
ou
ps t
h
an B
N
L an
d I
n
d
e
x
base
d
al
go
ri
t
h
m
s
. B
y
usi
n
g t
h
i
s
m
e
t
hod
di
f
f
ere
n
t
s
k
y
l
i
n
e q
u
e
r
i
e
s can
be
ea
si
l
y
answe
r
ed
by
fi
ndi
ng
sk
y
cube
effectively.
We can also dec
r
ease subs
pace
s searches
.
W
e
have exe
r
ci
se
d ab
ove t
ech
ni
que
s wi
t
h
n
u
m
b
er o
f
exam
pl
e dat
a
set
s
t
o
p
r
o
v
e ef
fect
i
v
e s
k
y
l
i
n
e com
put
at
i
on.
In
o
u
r
fut
u
re
wo
rk
,
devel
opi
ng
ne
w al
g
o
ri
t
h
m
s
t
o
fi
n
d
c
o
m
p
act
sky
cu
be
base
d
on
a
f
orem
ent
i
one
d
st
rat
e
g
i
es.
REFERE
NC
ES
[1]
J. Pei,
A. W
.
C.
Fu, X. L
i
n,
and
H. W
a
ng. “
C
om
puting com
p
ressed m
u
ltidim
ensi
onal sk
ylin
e cub
e
s effi
cien
tl
y”
. I
n
ICDE
, pag
e
s 96
–105. IEEE, 200
7.
[2]
A. Vlachou
, C
.
Doulkeridis, Y.
Kotid
is,
and M.
Vazirgiannis, “Sk
y
peer: E
ffi
ci
en
t S
ubs
pace
S
k
y
l
ine Computation
over Distrib-u
t
ed Data”,
Proc. I
EEE 23rd Int’
l
Conf. Data
Eng
.
(ICDE ’07), pp.
416-425, 2007
.
[3]
Y.
Yuan,
X.
Lin,
Q.
Liu,
W.
Wang,
J.
X.
Yu,
and Q.
Zhang. “Efficien
t computatio
n of the sky
lin
e cube”. In
VL
DB
2005.
[4]
C. Ra
¨
ı
ssi,
J. Pe
i,
a
n
d T.
Kiste
r
. “Computing closed sk
y
c
ubes”
.
PVLDB
,
3(1):838–
847, 2010
.
[5]
J
.
P
e
i
,
W
.
J
i
n
,
M
.
E
s
t
e
r
,
a
n
d
Y
.
T
a
o. “Catch
ing the best views of sky
lin
e:
A semantic approach based on decis
i
v
e
s
ubs
paces
”.
In
VLDB
2005
0
5
10
15
20
25
30
Time
required
to
compute
Skyline
set
stellar
approach
set
approach
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE Vo
l. 5
,
N
o
. 5
,
O
c
tob
e
r
20
15
:
118
8
–
11
93
1
193
[6]
X. Li
an and
L
.
Chen, “
P
robabil
i
s
tic Rank
ed Que
r
ies
in Un
cert
a
in
Datab
a
s
e
s
”
,
P
r
oc.
In
t’l Con
f
.
Extending Database
Technology (
E
DBT ’08
), pp. 511
-522, 2008
[7]
P. Godfre
y
,
R
.
Shiple
y, and J.
Gr
y
z
, “
M
axim
al
Vector Com
p
utation in L
a
rge
Data Sets”,
Pro
c
. Int’l Conf
. Ve
ry
Large
Data Bas
e
s (VLDB
), pp. 2
29-240, 2005
.
[8]
X.
Lin,
Y.
Yuan,
Q.
Zhang,
and Y.
Zhang, “
S
ele
c
ting S
t
ars
:
Th
e K M
o
s
t
Repres
entativ
e S
k
yline
Operator”
,
P
r
oc
.
IEEE 23rd Int’
l
Conf. Data
Eng
.
(
I
CDE ’07
), pp.
86-95, 2007
.
[9]
D. Papadias, Y
.
Tao
,
G. Fu,
an
d B.
Seeger
, “An optimal and P
r
ogressive
Algor
ithm
for Sk
ylin
e
Queries”
, Proc
.
ACM SIGMOD I
n
t’l Conf.
Mana
gement o
f
Data
,
pp. 467-478
, 20
03.
[10]
S.
Borz
sony
i, D. Kossma
nn,
and
K. S
t
ocker
,
“
T
h
e
S
k
y
l
ine Op
erato
r
”, P
r
oc
.
17
th Int’l Conf. Data
En
g.
(ICDE ’01
)
,
pp.421-430, 200
1.
BIOGRAP
HI
ES OF
AUTH
ORS
T.
Vijay
a
Sar
a
dhi
working as
Assistant profes
sor in th
e dep
a
r
t
ment of CSE,
KL university
.
Pursuing Ph.D.
He is hav
i
ng more th
an 10
y
e
ars
e
xperience in
bo
th academics an
d industr
y
.
His
area
of
inte
rest
i
s
Data m
i
ning
.
Dr
.
K.
Subr
ah
many
am
working as Assoc Dean R&D, professor in the d
e
par
tment of CSE, K
L
universit
y
.
He i
s
having m
o
re t
h
an 20
y
ears ex
perien
ce in bo
th
acad
em
ics and
industr
y
.
He
published and coauthored more than 50 research
publicatiobns
.His research in
terests includ
e
Software Eng
i
neering, Data Mining, and
Cloud
C
o
mputing. He is
a senior
me
mbe
r
of t
h
e
CSI.
D
r
. C
h
.V
. Ph
a
n
i Kris
h
n
a
, working as Assoc professor in
the dep
a
rtment of CSE, KL
universit
y
.
H
e
is
having m
o
re th
an 10
y
ears
exp
e
rien
ce in
both
acad
em
ics. He
published and
coauthor
ed more than 20 research publicatio
bns
. His research inter
e
sts include Software
Engineering, Data Min
i
ng. He is
a senior
member of th
e CSI.
Evaluation Warning : The document was created with Spire.PDF for Python.