PRISMO: predictive skyline query processing over moving objects

Nan CHEN; Li-dan SHOU; Gang CHEN; Yun-jun GAO; Jin-xiang DONG

doi:10.1631/jzus.C10a0728

Your Location：

Home >

Browse articles >

PRISMO: predictive skyline query processing over moving objects

计算机与自动化 | Updated：2022-12-09

- PRISMO: predictive skyline query processing over moving objects
- PRISMO: predictive skyline query processing over moving objects
- 信息与电子工程前沿（英文） 2012年13卷第2期页码：99-117
- Affiliations：
  
  1.School of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China
  2.China National Tobacco Corporation Zhejiang Province Corporation, Hangzhou 310001, China
- Author bio：
  
  [ "Nan CHEN, cnasd715@zju.edu.cn" ]
  Li-dan SHOU, should@zju.edu.cn
  [ "Gang CHEN, cg@zju.edu.cn" ]
  [ "Yun-jun GAO, gaoyj@zju.edu.cn" ]
  [ "Jin-xiang DONG, djx@zju.edu.cn" ]
- Funds：
  
  Project supported by the National Natural Science Foundation of China (Nos. 60603044 and 60803003) and the Program for Changjiang Scholars and Innovative Research Team in University (No. IRT0652)
- DOI：10.1631/jzus.C10a0728
  中图分类号： TP391.4
- 收稿：2010-07-31，
  
  修回：2012-;1-;7，
  
  纸质出版：2012-02
- Accepted：
Scan QR Code
PRISMO: predictive skyline query processing over moving objects[J]. 信息与电子工程前沿（英文）, 2012,13(2):99-117.

Nan CHEN, Li-dan SHOU, Gang CHEN, et al. PRISMO: predictive skyline query processing over moving objects[J]. Frontiers of Information Technology & Electronic Engineering, 2012, 13(2): 99-117.
PRISMO: predictive skyline query processing over moving objects[J]. 信息与电子工程前沿（英文）, 2012,13(2):99-117. DOI： 10.1631/jzus.C10a0728.

Nan CHEN, Li-dan SHOU, Gang CHEN, et al. PRISMO: predictive skyline query processing over moving objects[J]. Frontiers of Information Technology & Electronic Engineering, 2012, 13(2): 99-117. DOI： 10.1631/jzus.C10a0728.

摘要

Abstract

Skyline query is important in the circumstances that require the support of decision making. The existing work on skyline queries is based mainly on the assumption that the datasets are static. Querying skylines over moving objects

however

is also important and requires more attention. In this paper

we propose a framework

namely PRISMO

for processing predictive skyline queries over moving objects that not only contain spatio-temporal information

but also include non-spatial dimensions

such as other dynamic and static attributes. We present two schemes

RBBS (branch-and-bound skyline with rescanning and repacking) and TPBBS (time-parameterized branchand-bound skyline)

each with two alternative methods

to handle predictive skyline computation. The basic TPBBS is further extended to TPBBSE (TPBBS with expansion) to enhance the performance of memory space consumption and CPU time. Our schemes are flexible and thus can process point

range

and subspace predictive skyline queries. Extensive experiments show that our proposed schemes can handle predictive skyline queries effectively

and that TPBBS significantly outperforms RBBS.

关键词

Keywords

references

N. Beckmann , , , H.P. Kriegel , , , R. Schneider , , , B. Seeger . . The R * -Tree: an Efficient and Robust Access Method for Points and Rectangles . . SIGMOD , , 1990 . . p.322 - - 331 . . DOI: 10.1145/93597.98741 http://doi.org/10.1145/93597.98741 . .

R. Benetis , , , C.S. Jensen , , , G. Karciauskas , , , S. Saltenis . . Nearest neighbor and reverse nearest neighbor queries for moving objects . . VLDB J. , , 2006 . . 15 ( ( 3 ): ): 229 - - 249 . . DOI: 10.1007/s00778-005-0166-4 http://doi.org/10.1007/s00778-005-0166-4 . .

S. Borzsonyi , , , D. Kossmann , , , K. Stocker . . The Skyline Operator . . ICDE , , 2001 . . p.421 - - 430 . . DOI: 10.1109/ICDE.2001.914855 http://doi.org/10.1109/ICDE.2001.914855 . .

N. Chen , , , L.D. Shou , , , G. Chen , , , J.X. Dong . . Adaptive indexing of moving objects with highly variable update frequencies . . J. Comput. Sci. Technol. , , 2008 . . 23 ( ( 6 ): ): 998 - - 1014 . . DOI: 10.1007/s11390-008-9185-0 http://doi.org/10.1007/s11390-008-9185-0 . .

N. Chen , , , L.D. Shou , , , G. Chen , , , K. Chen , , , Y.J. Gao . . Bs-Tree: a Self-Tuning Index of Moving Objects . . DASFAA , , 2010 . . p.1 - - 16 . . . .

J. Chomicki , , , P. Godfrey , , , J. Gryz , , , D.M. Liang . . Skyline with Presorting . . ICDE , , 2003 . . p.717 - - 816 . . . .

B. Cui , , , L.J. Chen , , , L.H. Xu , , , H. Lu , , , G.J. Song , , , Q.Q. Xu . . Efficient skyline computation in structured peerto-peer systems . . IEEE Trans. Knowl. Data Eng. , , 2009 . . 21 ( ( 7 ): ): 1059 - - 1072 . . DOI: 10.1109/TKDE.2008.235 http://doi.org/10.1109/TKDE.2008.235 . .

Y.J. Gao , , , G.C. Chen , , , L. Chen , , , C. Chen . . An I/O Optimal and Scalable Skyline Query Algorithm . . BNCOD , , 2006 . . p.127 - - 139 . . . .

P. Godfrey , , , R. Shipley , , , J. Gryz . . Maximal Vector Computation in Large Data Sets . . VLDB , , 2005 . . p.229 - - 240 . . . .

A. Guttman . . R-Trees: a Dynamic Index Structure for Spatial Searching . . SIGMOD , , 1984 . . p.47 - - 57 . . DOI: 10.1145/602259.602266 http://doi.org/10.1145/602259.602266 . .

G.R. Hjaltason , , , H. Samet . . Distance browsing in spatial databases . . ACM Trans. Database Syst. , , 1999 . . 24 ( ( 2 ): ): 265 - - 318 . . DOI: 10.1145/320248.320255 http://doi.org/10.1145/320248.320255 . .

Z.Y. Huang , , , H. Lu , , , B.C. Ooi , , , A.K.H. Tung . . Continuous skyline queries for moving objects . . IEEE Trans. Knowl. Data Eng. , , 2006 . . 18 ( ( 12 ): ): 1645 - - 1658 . . DOI: 10.1109/TKDE.2006.185 http://doi.org/10.1109/TKDE.2006.185 . .

C.S. Jensen , , , D. Lin , , , B.C. Ooi . . Query and Update Efficient B+-Tree Based Indexing of Moving Objects . . VLDB , , 2004 . . p.768 - - 779 . . DOI: 10.1016/B978-012088469-8/50068-1 http://doi.org/10.1016/B978-012088469-8/50068-1 . .

I. Kamel , , , C. Faloutsos . . On Packing R-trees . . CIKM , , 1993 . . p.490 - - 499 . . DOI: 10.1145/170088.170403 http://doi.org/10.1145/170088.170403 . .

D. Kossmann , , , F. Ramsak , , , S. Rost . . Shooting Stars in the Sky: an Online Algorithm for Skyline Queries . . VLDB , , 2002 . . p.275 - - 286 . . . .

K.C.K. Lee , , , B.H. Zheng , , , H.J. Li , , , W.C. Lee . . Approaching the Skyline in Z Order . . VLDB , , 2007 . . p.279 - - 290 . . . .

S.T. Leutenegger , , , M.A. Lopez , , , J. Edgington . . STR: a Simple and Efficient Algorithm for R-Tree Packing . . ICDE , , 1997 . . p.497 - - 506 . . DOI: 10.1109/ICDE.1997.582015 http://doi.org/10.1109/ICDE.1997.582015 . .

B. Lin , , , H. Mokhtar , , , R. Pelaez-Aguilera , , , J.W. Su . . Querying Moving Objects with Uncertainty . . Vehicular Technology Conf. , , 2003 . . 4 2783 - - 2787 . . . .

D. Papadias , , , Y.F. Tao , , , G. Fu , , , B. Seeger . . Progressive skyline computation in database systems . . ACM Trans. Database Syst. , , 2005 . . 30 ( ( 1 ): ): 41 - - 82 . . DOI: 10.1145/1061318.1061320 http://doi.org/10.1145/1061318.1061320 . .

J. Pei , , , A.W.C. Fu , , , X.M. Lin , , , H.X. Wang . . Computing Compressed Multidimensional Skyline Cubes Efficiently . . ICDE , , 2007 . . p.96 - - 105 . . DOI: 10.1109/ICDE.2007.367855 http://doi.org/10.1109/ICDE.2007.367855 . .

S. Saltenis , , , C.S. Jensen . . Indexing of Moving Objects for Location-Based Services . . ICDE , , 2002 . . p.463 - - 472 . . DOI: 10.1109/ICDE.2002.994759 http://doi.org/10.1109/ICDE.2002.994759 . .

S. Saltenis , , , C.S. Jensen , , , S.T. Leutenegger , , , M.A. Lopez . . Indexing the Positions of Continuously Moving Objects . . SIGMOD , , 2000 . . p.331 - - 342 . . DOI: 10.1145/342009.335427 http://doi.org/10.1145/342009.335427 . .

K.L. Tan , , , P.K. Eng , , , B.C. Ooi . . Efficient Progressive Skyline Computation . . VLDB , , 2001 . . p.301 - - 310 . . . .

Y.F. Tao , , , D. Papadias , , , J.M. Sun . . The TPR * -Tree: an Optimized Spatio-Temporal Access Method for Predictive Queries . . VLDB , , 2003 . . p.790 - - 801 . . DOI: 10.1016/B978-012722442-8/50075-6 http://doi.org/10.1016/B978-012722442-8/50075-6 . .

Y.F. Tao , , , X.K. Xiao , , , J. Pei . . SUBSKY: Efficient Computation of Skylines in Subspaces . . ICDE , , 2006 . . p.65 DOI: 10.1109/ICDE.2006.149 http://doi.org/10.1109/ICDE.2006.149 . .

K. Tzoumas , , , M.L. Yiu , , , C.S. Jensen . . Workload-Aware Indexing of Continuously Moving Objects . . PVLDB , , 2009 . . p.1186 - - 1197 . . . .

A. Vlachou , , , C. Doulkeridis , , , Y. Kotidis . . AngleBased Space Partitioning for Efficient Parallel Skyline Computation . . SIGMOD , , 2008 . . p.227 - - 238 . . DOI: 10.1145/1376616.1376642 http://doi.org/10.1145/1376616.1376642 . .

S.Y. Wang , , , Q.H. Vu , , , B.C. Ooi , , , A.K.H. Tung , , , L.Z. Xu . . Skyframe: a framework for skyline query processing in peer-to-peer systems . . VLDB J. , , 2009 . . 18 ( ( 1 ): ): 345 - - 362 . . DOI: 10.1007/s00778-008-0104-3 http://doi.org/10.1007/s00778-008-0104-3 . .

Y.D. Yuan , , , X.M. Lin , , , Q. Liu , , , W. Wang , , , J.X. Yu , , , Q. Zhang . . Efficient Computation of the Skyline Cube . . VLDB , , 2005 . . p.241 - - 252 . . . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

Index and retrieve the skyline based on dominance relationship