|
|
Journal of Zhejiang University SCIENCE C
ISSN 1869-1951(Print), 1869-196x(Online), Monthly
2012 Vol.13 No.2 P.99-117
PRISMO: predictive skyline query processing over moving objects
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 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.
Key words: Spatio-temporal database, Moving object, Skyline
References:
[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
<1>
DOI:
10.1631/jzus.C10a0728
CLC number:
TP391.4
Download Full Text:
Downloaded:
2963
Clicked:
7197
Cited:
0
On-line Access:
2012-01-19
Received:
2010-07-31
Revision Accepted:
2011-01-05
Crosschecked:
2012-01-07
Tel: +86-571-87952276; Fax: +86-571-87952331; E-mail: jzus@zju.edu.cn
Copyright © 2000~ Journal of Zhejiang University-SCIENCE