RSkycube: Efficient Skycube Computation by Reusing Principle 53
– We propose a set of rules named identical partitioning (IP) for constructing
a novel structure VSkyTree.
– we present the reusing principle, which utilizes both sharing strict space dom-
inance and sharing space incomparability by reusing VSkyTree on parent
cuboids to compute child cuboids.
– We design an efficient skycube computation algorithm RSkycube based on the
reusing principle.
– We evaluate our proposed algorithm RSkycube by comparing it with state-of-
the-art skycube algorithm in dimensionality and cardinality on both synthetic
and real datasets.
The rest of this paper is organized as follows. Section 2 introduces some defini-
tions about skycube. Section 3 proposes a set of rules named identical partitioning
(IP) for constructing a novel structure VSkyTree and present a reusing princi-
ple which utilizes both sharing strategies to compute child cuboids. Section 4
designs an efficient skycube algorithm RSkycube based on the reusing principle.
Section 5 evaluates experimentally our proposed algorithm with state-of-the-art
skycube algorithm on both real and synthetic datasets. Finally, our conclusion
is summarized in Sect. 6.
2 Preliminaries
For easy explanation, we present some notations used throughout this paper.
Given a dataset S with d dimensions, D represents the full dimension set. i.e.,
D = {D
0
, D
1
, ..., D
d−1
}. And the domain space for D is denoted by S
D
, where
S
D
i
is the domain on dimension D
i
. Actually, S is a subset of S
D
. For any point
p in S, we denote the value of point p on ith dimension by p(D
i
), abbreviated as
p(i), where i ∈ [0, d–1]. Without loss of generality, we assume that lower values
are better for all users on all dimensions.
Given two points p and q in the dataset S on D, p dominates q on dimension
subset U, where U⊆D, denoted by p
U
P
q iff ∀D
i
∈U, p(i) ≤ q(i)and∃D
i
∈U, p(i) <q(i). Otherwise p
U
P
q.Ifp
U
P
q and q
U
P
p, then p and q are
incomparable on U. The skyline query on U returns all the points that are not
dominated by any other points on U, denoted by SKY
U
(S)={p ∈ S |∀q ∈ S,
q
U
P
p}.
Definition 1 (Skycube and Cuboid). Given a dataset S on D, the skycube of
S consists of all skyline results on 2
d
− 1 non-empty dimension subsets, denoted
by SKYCUBE(S) = {SKY
U
(S) |U⊆D, U = ∅},whereSKY
U
(S) is cal led the
cuboid on U, abbreviated as cuboid U.
Actually, to meet users having different preferences, Skycube computes sky-
line results on all possible non-empty dimension subsets. Skycube can be visual-
ized as a lattice as shown in Fig. 1(b) for 3-dimensional datasets. For two cuboids
A on U and B on V,ifU⊂Vand |V − U| = 1, then A is a child of B and B is
aparentofA. For example, Fig. 1(c) gives the skycube computation result for
the dataset in Fig. 1(a).
剩余13页未读，继续阅读
weixin_38657115
- 粉丝: 5
- 资源: 905
我的内容管理
展开
最新资源
- 李兴华Java基础教程：从入门到精通
- U盘与硬盘启动安装教程：从菜鸟到专家
- C++面试宝典：动态内存管理与继承解析
- C++ STL源码深度解析：专家级剖析与关键技术
- C/C++调用DOS命令实战指南
- 神经网络补偿的多传感器航迹融合技术
- GIS中的大地坐标系与椭球体解析
- 海思Hi3515 H.264编解码处理器用户手册
- Oracle基础练习题与解答
- 谷歌地球3D建筑筛选新流程详解
- CFO与CIO携手：数据管理与企业增值的战略
- Eclipse IDE基础教程：从入门到精通
- Shell脚本专家宝典：全面学习与资源指南
- Tomcat安装指南：附带JDK配置步骤
- NA3003A电子水准仪数据格式解析与转换研究
- 自动化专业英语词汇精华：必备术语集锦
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
