Continuous k nearest neighbor-skyline query (CkNN-SQ) 為一類重要的時間-空間查詢。
給定一段查詢時間區段 [ts, te] 和一個移動查詢物體 q，CkNN-SQ 可取得時間區段 [ts, te] 內每個時間點，查詢物體 q 的 k 個最近鄰居天際線點 (k-nearest neighbor skyline points， kNN-SP)。
不同於先前的研究，我們的研究致力於克服過去研究提出的假設，即每個物體為靜止不動且具有確定的維度值，並位在道路網路 (road networks) 上。
本篇論文中，我們是針對在歐幾里得空間 (Euclidean space) 上具有不確定維度值的移動物體，且每個物體 (包含查詢物體) 的速度皆在已知範圍內變動，去處理 CkNN-SQ。
我們稱此種查詢為 continuous possible-kNN-skyline query (CPkNN-SQ)。
我們首先會討論物體具有不確定性所引發的困難，接著提出 CPkNN-SQ 演算法。
CPkNN-SQ 演算法結合了名為 uncertain TPR-tree (UTPR-tree) 的資料分割索引，用來有效率地回答 CPkNN-SQ。
大量的實驗被用來驗證所提出的方法之有效性與效能。

Continuous k nearest neighbor-skyline query (CkNN-SQ) is an important type of spatio-temporal queries. Given a query time interval [ts, te] and a moving query object q, a CkNN-SQ is to retrieve the k-nearest neighbor skyline points (kNN-SP) of q at each time instant within [ts, te]. Different from the previous works, our work devotes to overcoming the past assumption that each object is static with certain dimensional values and located in road networks. In this paper, we focus on processing the CkNN-SQ over moving objects with uncertain dimensional values in Euclidean space and the velocity of each object (including the query object) varies within a known range. Such a query is called the continuous possible-kNN-skyline query (CPkNN-SQ). We first discuss the difficulties raised by the uncertainty of object and then propose the CPkNN-SQ algorithm operated with a data-partitioning index, called the uncertain TPR-tree (UTPR-tree), to efficiently answer the CPkNN-SQ. Comprehensive experiments are performed to demonstrate the effectiveness and the efficiency of the proposed approach.

[1] S. Borzsonyi, D. Kossmann, and K. Stocker, “The skyline operator,” in 17th International Conference on Data Engineering, pp. 421–430, 2001.
[2] K. Deng, X. Zhou, and H. T. Shen, “Multi-source skyline query processing in road networks,” in 23rd International Conference on Data Engineering, pp. 796–805, 2007.
[3] S. M. Jang and J. S. Yoo, “Processing continuous skyline queries in road networks,” in International Symposium on Computer Science and Its Applications, pp. 353–356, 2008.
[4] K. Mouratidis, Y. Lin, and M. L. Yiu, “Preference queries in large multi-cost transportation networks,” in International Conference on Data Engineering, pp. 533–544, 2010.
[5] H.-P. Kriegel, M. Renz, and M. Schubert, “Route skyline queries: a multi-preference path planning approach,” in 26th IEEE International Conference on Data Engineering, pp. 261–272, 2010.
[6] L. Zou, L. Chen, M. T. Ozsu, and D. Zhao, “Dynamic skyline queries in large graphs,” in Database Systems for Advanced Applications, pp. 62–78, 2010.
[7] Y.-K. Huang, C.-H. Chang, and C. Lee, “Continuous distance-based skyline queries in road networks,” in Information Systems, 2012.
[8] M. E. Khalefa, M. F. Mokbel, and J. J. Levandoski, “Skyline query processing for incomplete data,” in International Conference on Data Engineering, pp. 556–565, 2008.
[9] J. Chomicki, P. Godfrey, J. Gryz, and D. Liang, “Skyline with presorting,” in Nineteenth International Conference on Data Ingineering, pp. 717–719, 2003.
[10] I. Bartolini, P. Ciaccia, and M. Patella, “Efficient sort-based skyline evaluation,” ACM Transactions on Database Systems, vol. 33, no. 4, pp. 1–45, November 2008.
[11] K.-L. Tan, P.-K. Eng, and B. C. Ooi, “Efficient progressive skyline computation,” in International Conference on Very Large Data Bases, pp. 301–310, 2001.
[12] D. Kossmann, F. Ramsak, and S. Rost, “Shooting stars in the sky: an online algorithm for skyline queries,” in Proceedings of the VLDB Conference, 2002.
[13] D. Papadias, Y. Tao, G. Fu, and B. Seeger, “An optimal and progressive algorithm for skyline queries,” in ACM SIGMOD, pp. 467–478, 2003.
[14] J. Pei, B. Jiang, X. Lin, and Y. Yuan, “Probabilistic skylines on uncertain data,” in Proceedings of the VLDB Conference, 2007.
[15] M. E. Khalefa, M. F. Mokbel, and J. J. Levandoski, “Skyline query processing for uncertain data,” in 19th International Conference on Information and Knowledge
Management and Co-located Workshops, pp. 1293–1296, 2010.
[16] Y.-K. Huang, C.-C. Chen, and C. Lee, “Continuous k-nearest neighbor query for moving objects with uncertain velocity,” in Geoinformatica, pp. 1–25, 2009.
[17] Y.-K. Huang and C. Lee, “Efficient evaluation of continuous spatio-temporal queries on moving objects with uncertain velocity,” in Geoinformatica, pp. 163–200, 2010.
[18] P. Fan, G. Li, L. Yuan, and Y. Li, “Vague continuous k-nearest neighbor queries over moving objects with uncertain velocity in road networks,” in Information Systems, vol. 37, pp. 13–32, 2012.
[19] Z. Huang, H. Lu, B. C. Ooi, and A. K. Tung, “Continuous skyline queries for moving objects,” in IEEE Transactions on Knowledge and Data Engineering, vol. 18, no. 12, pp. 1645–1658, December 2006.
[20] B. Zheng, K. C. K. Lee, and W.-C. Lee, “Location-dependent skyline query,” in IEEE International Conference on Mobile Data Management, pp. 148–155, 2008.
[21] M.-W. Lee and S. won Hwang, “Continuous skylining on volatile moving data,” in 25th IEEE International Conference on Data Engineering, pp. 1568–1575, 2009.
[22] S. Simonas, J. C. S, L. S. T, and L. M. A, “Indexing the positions of continuously moving objects,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 331–342, 2000.