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

Computer & Automation | Updated：2022-12-09

- PRISMO: predictive skyline query processing over moving objects
- PRISMO: predictive skyline query processing over moving objects
- Frontiers of Information Technology & Electronic Engineering Vol. 13, Issue 2, Pages: 99-117(2012)
- 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：
- DOI：10.1631/jzus.C10a0728
  CLC： TP391.4
- Received：31 July 2010，
  
  Revised：2012-;1-;7，
  
  Published：2012-02
- Accepted：
Scan QR Code
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：

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 . . . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Index and retrieve the skyline based on dominance relationship

Related Author

Chang XU

Gang CHEN

Yun-jun GAO

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰