基於位置的服務(Location-based service)越來越進步，成為許多人生活中不可或缺的一部分。
過去大部分的研究都著重於單一種類物體的查詢，但它們存在許多限制。
所以近年來越來越多使用者對多種類物體的查詢感到興趣。
這些不同種類的物體稱為異種物體(Heterogeneous objects, HOs)。
多種類物體的查詢最主要的目的是要找到滿足使用者需求的異種物體組合。
本文我們同時考量了異種物體的組合、距離、物體品質和物體價格等因素。
根據這些因素，我們提出了三個查詢distance-based spatial skyline query (DSSQ)、budget-based spatial skyline query (BSSQ)和lowest-cost spatial skyline query (LCSSQ)。
這三個查詢可以為使用者找到滿足下列兩個條件的組合。
(1)組合中任兩物體之間的距離不遠。
(2)組合中每一個物體的品質都很好。
三個查詢的差別如下:
DSSQ會找到離使用者最近的組合。
BSSQ找到的組合除了離使用者近，組合的總花費也會小於使用者的預算。
LCSSQ則會找到總花費最小的組合。
為了有效解決這些問題，我們提出了三個方法spatial skyline-first algorithm (SF)、combination-first algorithm with dominating tables (CFWDT)和combination -first algorithm with spatial skyline lists (CFWSSL)。
三個演算法都可以有效解決上述的三個問題。
此外，如果運用在各自適合的環境就可以達到更好的效果。
最後我們在實驗用合成資料和真實資料來證明演算法的效率。

Location-based service has become more and more advanced, which has resulted in their becoming an integral part of people's lives.
In the past, most studies focused on spatial queries on a single data type.
However, users may be interested in the relationship among multiple types of objects.
This different types of objects are called {em heterogeneous objects}(HOs).
The goal of spatial queries on multiple data types is to find a group of HOs that fulfills the requirements of users.
In this thesis, we simultaneously consider the combination of HOs, distance, the quality of HOs, and the costs of HOs.
Based on the above factors, we propose three queries: the {em distance-based spatial skyline query} (DSSQ), the {em budget-based spatial skyline query} (BSSQ), and the {em lowest cost spatial skyline query} (LCSSQ).
The three queries return a combination that fulfills the following two requirements:
(1)The distances between the HOs in the combination are short, and
(2)the quality of HOs in the combination is good.
In addition, the differences between the three queries are as follows:
The combination returned by the DSSQ has the shortest average distance to the user.
The combination returned by the BSSQ has the shortest average distance to the user, and the sum cost of the combination is not greater than the user's budget.
The sum cost of the combination returned by the LCSSQ is the lowest.
To solve these problems effectively, we propose three algorithms as follows: the spatial skyline-first algorithm (SF), the combination-first algorithm with dominating tables (CFWDT), and the combination-first algorithm with spatial skyline lists (CFWSSL).
The three algorithms can effectively solve the three problems.
In addition, they achieve a better effect in a suitable environment, respectively.
Finally, we conduct comprehensive experiments to demonstrate the efficiency of these algorithms.

[1] R. Benetis, C. S. Jensen, G. Karciauskas, and S. Saltenis, ”Nearest and reverse nearest neighbor queries for moving objects,” The VLDB Journal, vol. 15, no. 3, pp. 229-249, 2006.
[2] T. Bernecker, T. Emrich, H. Kriegel, M. Renz, S. Zankl, and A. Zu¨fle, ”Efficient probabilistic reverse nearest neighbor query processing on uncertain data,” Proc. VLDB Endow., vol. 4, no. 10, pp. 669-680, 2011.
[3] G. Beskales, M. A. Soliman, and I. F. Ilyas, ”Efficient search for the top-k probable nearest neighbors in uncertain databases,” Proc. VLDB Endow., vol. 1, no. 1, pp. 326-339, 2008.
[4] X. Cao, G. Cong, C. S. Jensen, and B. C. Ooi, ”Collective spatial keyword query- ing,” presented at the Proceedings of the 2011 ACM SIGMOD International Con- ference on Management of data, Athens, Greece, 2011.
[5] M. A. Cheema, X. Lin, W. Wang, W. Zhang, and J. Pei, ”Probabilistic Reverse Nearest Neighbor Queries on Uncertain Data,” IEEE Trans. on Knowl. and Data Eng., vol. 22, no. 4, pp. 550-564, 2010.
[6] J. Chen and R. Cheng, ”Efficient Evaluation of Imprecise Location-Dependent Queries,” in 2007 IEEE 23rd International Conference on Data Engineering, 2007, pp. 586-595.
[7] R. Cheng, L. Chen, J. Chen, and X. Xie, ”Evaluating probability threshold k-

nearest-neighbor queries over uncertain data,” presented at the Proceedings of the

12th International Conference on Extending Database Technology: Advances in Database Technology, Saint Petersburg, Russia, 2009.
[8] R. Cheng, D. V. Kalashnikov, and S. Prabhakar, ”Querying imprecise data in mov- ing object environments,” IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 9, pp. 1112-1127, 2004.
[9] D. W. Choi and C. W. Chung, ”Nearest neighborhood search in spatial databases,” in 2015 IEEE 31st International Conference on Data Engineering, 2015, pp. 699-710.
[10] B. S. E. Chung, W.-C. Lee, and A. L. P. Chen, ”Processing probabilistic spatio- temporal range queries over moving objects with uncertainty,” presented at the Proceedings of the 12th International Conference on Extending Database Technol- ogy: Advances in Database Technology, Saint Petersburg, Russia, 2009.
[11] A. Corral, Y. Manolopoulos, Y. Theodoridis, and M. Vassilakopoulos, ”Algorithms for processing K-closest-pair queries in spatial databases,” Data Knowl. Eng., vol. 49, no. 1, pp. 67-104, 2004.
[12] K. Deng, X. Li, J. Lu, and X. Zhou, ”Best Keyword Cover Search,” IEEE Trans- actions on Knowledge and Data Engineering, vol. 27, no. 1, pp. 61-73, 2015.
[13] I. D. Felipe, V. Hristidis, and N. Rishe, ”Keyword Search on Spatial Databases,” in 2008 IEEE 24th International Conference on Data Engineering, 2008, pp. 656-665.
[14] X. Fu, X. Miao, J. Xu, and Y. Gao, ”Continuous range-based skyline queries in road networks,” World Wide Web, vol. 20, no. 6, pp. 1443-1467, 2017.
[15] F. Gao, R. Jain, S. Prabhakar, and L. Si, ”ProbKS: Keyword Search on Probabilistic Spatial Data,” Berlin, Heidelberg, 2014, pp. 388-402: Springer Berlin Heidelberg.
[16] T. Guo, X. Cao, and G. Cong, ”Efficient Algorithms for Answering the m-Closest Keywords Query,” presented at the Proceedings of the 2015 ACM SIGMOD In- ternational Conference on Management of Data, Melbourne, Victoria, Australia,
2015.

[17] H. Gupta, B. Chawda, S. Negi, T. A. Faruquie, L. V. Subramaniam, and M. Mo- hania, ”Processing multi-way spatial joins on map-reduce,” presented at the Pro- ceedings of the 16th International Conference on Extending Database Technology, Genoa, Italy, 2013.
[18] A. Guttman, ”R-trees: a dynamic index structure for spatial searching,” presented at the Proceedings of the 1984 ACM SIGMOD international conference on Man- agement of data, Boston, Massachusetts, 1984.
[19] G. R. Hjaltason and H. Samet, ”Incremental distance join algorithms for spatial databases,” in ACM SIGMOD Record, 1998, vol. 27, no. 2, pp. 237-248: ACM.
[20] C.-C. Huang, J.-L. Huang, T.-C. Liang, J.-Z. Wang, W.-Y. Shih, and W.-C. Lee, ”Nearest Window Cluster Queries,” in EDBT, 2016.
[21] G. S. Iwerks, H. Samet, and K. Smith, ”Continuous K-nearest neighbor queries for continuously moving points with updates,” presented at the Proceedings of the 29th international conference on Very large data bases - Volume 29, Berlin, Germany, 2003.
[22] J. B. Rocha-Junior, O. Gkorgkas, S. Jonassen, and K. Nørv˚ag, ”Efficient processing of top-k spatial keyword queries,” presented at the Proceedings of the 12th inter- national conference on Advances in spatial and temporal databases, Minneapolis, MN, 2011.
[23] F. Korn and S. Muthukrishnan, ”Influence sets based on reverse nearest neighbor queries,” presented at the Proceedings of the 2000 ACM SIGMOD international conference on Management of data, Dallas, Texas, USA, 2000.
[24] H.-P. Kriegel, P. Kunath, and M. Renz, ”Probabilistic nearest-neighbor query on uncertain objects,” presented at the Proceedings of the 12th international confer- ence on Database systems for advanced applications, Bangkok, Thailand, 2007.

[25] H. T. Kung, F. Luccio, and F. P. Preparata, ”On Finding the Maxima of a Set of Vectors,” J. ACM, vol. 22, pp. 469-476, 1975.
[26] G. Li, J. Feng, and J. Xu, ”DESKS: Direction-Aware Spatial Keyword Search,” presented at the Proceedings of the 2012 IEEE 28th International Conference on Data Engineering, 2012.
[27] J. Li, B. Wang, and G. Wang, ”Efficient Probabilistic Reverse k-Nearest Neigh- bors Query Processing on Uncertain Data,” Berlin, Heidelberg, 2013, pp. 456-471: Springer Berlin Heidelberg.
[28] Z. Li, K. C. K. Lee, B. Zheng, W.-C. Lee, D. Lee, and X. Wang, ”IR-Tree: An Efficient Index for Geographic Document Search,” IEEE Trans. on Knowl. and Data Eng., vol. 23, no. 4, pp. 585-599, 2011.
[29] X. Lian and L. Chen, ”Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data,” The VLDB Journal, vol. 18, no. 3, pp. 787-808, 2009.
[30] C. Long, R. C.-W. Wong, K. Wang, and A. W.-C. Fu, ”Collective spatial keyword queries: a distance owner-driven approach,” in SIGMOD Conference, 2013.
[31] N. Mamoulis and D. Papadias, ”Multiway spatial joins,” ACM Trans. Database Syst., vol. 26, no. 4, pp. 424-475, 2001.
[32] D. Papadias and D. Arkoumanis, ”Approximate Processing of Multiway Spatial Joins in Very Large Databases,” Berlin, Heidelberg, 2002, pp. 179-196: Springer Berlin Heidelberg.
[33] D. Papadias, Y. Tao, K. Mouratidis, and C. K. Hui, ”Aggregate nearest neighbor queries in spatial databases,” ACM Trans. Database Syst., vol. 30, no. 2, pp. 529- 576, 2005.
[34] A. N. Papadopoulos and Y. Manolopoulos, ”Multiple range query optimization in spatial databases,” Berlin, Heidelberg, 1998, pp. 71-82: Springer Berlin Heidelberg.

[35] Y. Qiu, T. Ohmori, T. Shintani, and H. Fujita, ”A new algorithm for m-closest keywords query over spatial Web with grid partitioning,” in 2015 IEEE/ACIS 16th International Conference on Software Engineering, Artificial Intelligence, Network- ing and Parallel/Distributed Computing (SNPD), 2015, pp. 1-8.
[36] N. Roussopoulos, S. Kelley, F. Vincent, ”Nearest neighbor queries,” presented at the Proceedings of the 1995 ACM SIGMOD international conference on Management of data, San Jose, California, USA, 1995.
[37] M. Sharifzadeh and C. Shahabi, ”The spatial skyline queries,” presented at the Proceedings of the 32nd international conference on Very large data bases, Seoul,
Korea, 2006.

[38] Y. Sun, J. Qi, Y. Zheng, and R. Zhang, ”K-Nearest Neighbor Temporal Aggregate Queries,” presented at the Proceedings of the 18th International Conference on Extending Database Technology, 2015.
[39] Y. Tao and C. Sheng, ”Fast Nearest Neighbor Search with Keywords,” IEEE Trans. on Knowl. and Data Eng., vol. 26, no. 4, pp. 878-888, 2014.
[40] Z. J. Wang, D. H. Wang, B. Yao, and M. Guo, ”Probabilistic Range Query over Uncertain Moving Objects in Constrained Two-Dimensional Space,” IEEE Trans- actions on Knowledge and Data Engineering, vol. 27, no. 3, pp. 866-879, 2015.
[41] C. Yang and K.-I. Lin, ”An Index Structure for Efficient Reverse Nearest Neighbor Queries,” presented at the Proceedings of the 17th International Conference on Data Engineering, 2001.
[42] C. Zhang, Y. Zhang, W. Zhang, and X. Lin, ”Inverted linear quadtree: Efficient top k spatial keyword search,” in 2013 IEEE 29th International Conference on Data Engineering (ICDE), 2013, pp. 901-912.

[43] D. Zhang, C.-Y. Chan, and K.-L. Tan, ”Nearest group queries,” presented at the Proceedings of the 25th International Conference on Scientific and Statistical Database Management, Baltimore, Maryland, USA, 2013.
[44] D. Zhang, K.-L. Tan, and A. K. H. Tung, ”Scalable top-k spatial keyword search,” presented at the Proceedings of the 16th International Conference on Extending Database Technology, Genoa, Italy, 2013.
[45] S. Zhao, X. Cheng, S. Su, and K. Shuang, ”Popularity-aware collective keyword queries in road networks,” Geoinformatica, vol. 21, no. 3, pp. 485-518, 2017.