Full Text:   <1340>

CLC number: TP391.4

On-line Access: 2012-01-19

Received: 2010-07-31

Revision Accepted: 2011-01-05

Crosschecked: 2012-01-07

Cited: 0

Clicked: 2753

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2012 Vol.13 No.2 P.99-117


PRISMO: predictive skyline query processing over moving objects

Author(s):  Nan Chen, Li-dan Shou, Gang Chen, Yun-jun Gao, Jin-xiang Dong

Affiliation(s):  School of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China; more

Corresponding email(s):   cnasd715@zju.edu.cn, should@zju.edu.cn, cg@zju.edu.cn, gaoyj@zju.edu.cn, djx@zju.edu.cn

Key Words:  Spatio-temporal database, Moving object, Skyline

Nan Chen, Li-dan Shou, Gang Chen, Yun-jun Gao, Jin-xiang Dong. PRISMO: predictive skyline query processing over moving objects[J]. Journal of Zhejiang University Science C, 2012, 13(2): 99-117.

@article{title="PRISMO: predictive skyline query processing over moving objects",
author="Nan Chen, Li-dan Shou, Gang Chen, Yun-jun Gao, Jin-xiang Dong",
journal="Journal of Zhejiang University Science C",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T PRISMO: predictive skyline query processing over moving objects
%A Nan Chen
%A Li-dan Shou
%A Gang Chen
%A Yun-jun Gao
%A Jin-xiang Dong
%J Journal of Zhejiang University SCIENCE C
%V 13
%N 2
%P 99-117
%@ 1869-1951
%D 2012
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C10a0728

T1 - PRISMO: predictive skyline query processing over moving objects
A1 - Nan Chen
A1 - Li-dan Shou
A1 - Gang Chen
A1 - Yun-jun Gao
A1 - Jin-xiang Dong
J0 - Journal of Zhejiang University Science C
VL - 13
IS - 2
SP - 99
EP - 117
%@ 1869-1951
Y1 - 2012
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C10a0728

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

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1]Beckmann, N., Kriegel, H.P., Schneider, R., Seeger, B., 1990. The R*-Tree: an Efficient and Robust Access Method for Points and Rectangles. SIGMOD, p.322-331.

[2]Benetis, R., Jensen, C.S., Karciauskas, G., Saltenis, S., 2006. Nearest neighbor and reverse nearest neighbor queries for moving objects. VLDB J., 15(3):229-249.

[3]Borzsonyi, S., Kossmann, D., Stocker, K., 2001. The Skyline Operator. ICDE, p.421-430.

[4]Chen, N., Shou, L.D., Chen, G., Dong, J.X., 2008. Adaptive indexing of moving objects with highly variable update frequencies. J. Comput. Sci. Technol., 23(6):998-1014.

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

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

[7]Cui, B., Chen, L.J., Xu, L.H., Lu, H., Song, G.J., Xu, Q.Q., 2009. Efficient skyline computation in structured peer-to-peer systems. IEEE Trans. Knowl. Data Eng., 21(7):1059-1072.

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

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

[10]Guttman, A., 1984. R-Trees: a Dynamic Index Structure for Spatial Searching. SIGMOD, p.47-57.

[11]Hjaltason, G.R., Samet, H., 1999. Distance browsing in spatial databases. ACM Trans. Database Syst., 24(2):265-318.

[12]Huang, Z.Y., Lu, H., Ooi, B.C., Tung, A.K.H., 2006. Continuous skyline queries for moving objects. IEEE Trans. Knowl. Data Eng., 18(12):1645-1658.

[13]Jensen, C.S., Lin, D., Ooi, B.C., 2004. Query and Update Efficient B+-Tree Based Indexing of Moving Objects. VLDB, p.768-779.

[14]Kamel, I., Faloutsos, C., 1993. On Packing R-trees. CIKM, p.490-499.

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

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

[17]Leutenegger, S.T., Lopez, M.A., Edgington, J., 1997. STR: a Simple and Efficient Algorithm for R-Tree Packing. ICDE, p.497-506.

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

[19]Papadias, D., Tao, Y.F., Fu, G., Seeger, B., 2005. Progressive skyline computation in database systems. ACM Trans. Database Syst., 30(1):41-82.

[20]Pei, J., Fu, A.W.C., Lin, X.M., Wang, H.X., 2007. Computing Compressed Multidimensional Skyline Cubes Efficiently. ICDE, p.96-105.

[21]Saltenis, S., Jensen, C.S., 2002. Indexing of Moving Objects for Location-Based Services. ICDE, p.463-472.

[22]Saltenis, S., Jensen, C.S., Leutenegger, S.T., Lopez, M.A., 2000. Indexing the Positions of Continuously Moving Objects. SIGMOD, p.331-342.

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

[24]Tao, Y.F., Papadias, D., Sun, J.M., 2003. The TPR*-Tree: an Optimized Spatio-Temporal Access Method for Predictive Queries. VLDB, p.790-801.

[25]Tao, Y.F., Xiao, X.K., Pei, J., 2006. SUBSKY: Efficient Computation of Skylines in Subspaces. ICDE, p.65.

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

[27]Vlachou, A., Doulkeridis, C., Kotidis, Y., 2008. Angle-Based Space Partitioning for Efficient Parallel Skyline Computation.

[28]SIGMOD, p.227-238.

[29]Wang, S.Y., Vu, Q.H., Ooi, B.C., Tung, A.K.H., Xu, L.Z., 2009. Skyframe: a framework for skyline query processing in peer-to-peer systems. VLDB J., 18(1):345-362.

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

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE