近年來，隨著人口流動率的增加，租屋已成為越來越多離家工作人的選擇，因為他的成本便宜且具有高度彈性。在這情況下，大量的租屋需求也使得許多提供租屋服務的平台被推出，例如：ForRent 與AirBnb。一般來說，一位使用者透過這些平台在尋找租屋地點時，會先以某個查詢點（例如使用者的工作地點或就讀的學校）開始，然後查詢此地點附近的居住區域。我們也發現使用者在評估一個居住區域是否合適時，也會連同它周遭的地點一併進行評估。評估時考慮的因素包括距離與個人的偏好。在距離因素方面，使用者會希望居住區域與周遭的地點都能夠靠近查詢點，因為未來居住在此區域裡時，可以節省交通上的時間。在個人偏好方面，使用者會希望居住區域周遭的設施能滿足自己生活上的習慣。當使用找到合適的居住區域後，才會從這個區域裡挑選租屋的地點。然而，大多數的租屋平台無法考慮使用者對租屋的個人化需求。這造成使用者必須進行多次查詢與比對查詢的結果，才能找出適合居住的區域。這樣的過程需要花費使用者大量時間。為了改善現有系統無法提供個人化租屋結果的問題，本篇論文提出了一種新型的查詢來幫助使用找尋找最適合的居住區域。本篇論文利用了適地性社群網路(location-based social network, LBSN)中的生活軌跡資料與時空資料庫查詢的技術來了解使用者的租屋需求，並計算使用者對於每一個區域的偏好程度。此外，本論文總共提出了三個可在道路網路上找出最佳解的演算法，包含了一個基礎演算法，以及兩個加速的演算法。最終，我們進行了一系列實驗來驗證了我們所提出方法的有效性，並得到了不錯的成果。

With more and more people migrating to other places for work or study in recent years, renting offers have been in greater demand because of its lower cost and greater flexibility. This phenomenon has given rise to a number of rental service platforms, such as ForRent and Airbnb. In general, users looking for rentals will first start from a query point (e.g., the user’s workplace or school) and then find the residential areas close to the point. Users will access the suitability of each residential area by evaluating its surrounding environments, where distance and personal preferences are two main factors put into consideration. In terms of the distance factor, users tend to choose a residential area nearest to the query point to shorten their daily commute. When it comes to the personal preferences, users usually hope that the facilities in the residential region can meet their needs. Therefore, it is more common that users will first determine the most suitable residential areas for them, and then select the best rental from the areas. However, the existing rental platforms do not provide the functions taking care of users’ individual needs. This causes the users to have to make multiple inquiries and to compare a number of results before the most suitable residential area is found, which is time-consuming. In order to optimize the search process for users, we propose a novel query method to help them find the most suitable residential area easier. In this thesis, we apply the spatio-temporal query and the trajectory data from the location-based social network (LBSN) to infer users’ needs and preferences for each area. In addition, we propose three algorithms employed for finding the best results in road networks, including a basic algorithm and two accelerated algorithms. Finally, we conduct a series of experiments to verify the proposed approach, which is proven to be effective.

[1] “Amap,” http://m.amap.com/
[2] “Airbnb,” https://www.airbnb.com/
[3] T. Brinkhoff, "A Framework for Generating Network-Based Moving Objects," GeoInformatica, journal article vol. 6, no. 2, pp. 153-180, June 01 2002.
[4] W. Bryc, “The normal distribution: characterizations with applications,”in SpringerScience & Business Media, vol. 100, 2012.
[5] X. Cao, G. Cong, C. S. Jensen, and M. L. Yiu, “Retrieving regions of interest for user exploration,” in Proceedings of the VLDB Endowment, vol. 7, no. 9, pp. 733-744, 2014.
[6] D.-W. Choi, C.-W. Chung, and Y. Tao, “A scalable algorithm for maximizing range sum in spatial databases,” in Proceedings of the VLDB Endowment, vol. 5, no. 11, pp. 1088-1099, 2012.
[7] Z. Chen, Y. Liu, R. C.-W. Wong, J. Xiong, G. Mai, and C. Long, “Efficient algorithms for optimal location queries in road networks,” in Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, pp. 123-134, 2014.
[8] Y.-C. Chung, I.-F. Su, and C. Lee, “k-most suitable locations selection,” in GeoInformatica, March 27 2018.
[9] Y. Du, D. Zhang, T. Xia, “The Optimal-Location Query,” in International Symposium on Spatial and Temporal Databases, pp. 163-180, 2005.
[10] K. Deng, X. Zhou, H. Shen, K. Xu, and X. Lin, “Surface k-NN Query Processing,” in 22nd International Conference on Data Engineering, pp. 78-78, 2006.
[11] E. W. Dijkstra, "A note on two problems in connexion with graphs," in Numerische Mathematik, vol. 1, no. 1, pp. 269-271, 1959.
[12] K. Feng, G. Cong, S. S. Bhowmick, W.-C. Peng, and C. Miao, “Towards Best Region Search for Data Exploration,” in Proceedings of the 2016 International Conference on Management of Data, 2016.
[13] P. Fan, G. Li, and L. Yuan, “Continuous K-Nearest Neighbor processing based on speed and direction of moving objects in a road network,” in Telecommunication systems, vol. 55 3, pp. 403-419, 2014.
[14] “ForRent,” https://www.forrent.com/
[15] “Facebook,” https://www.facebook.com/
[16] “GeoLife,” https://www.microsoft.com/en-us/download/details.aspx?id=52367
[17] “Ganji.com,” http://bj.ganji.com/fang1/
[18] A. Hinneburg, C. C. Aggarwal, D. A. Keim, “What Is the Nearest Neighbor in High Dimensional Spaces,” in Proceedings of the 26th International Conference on Very Large Data Bases, 2000.
[19] M. M.-u. Hussain, K. A. Islam, G. Trajcevski, and M. E. Ali, “Towards Efficient Maintenance of Continuous MaxRS Query for Trajectories,” in Proceedings of the 20th International Conference on Extending Database Technology, 2017.
[20] J. Huang, Z. Wen, J. Qi, R. Zhang, J. Chen, and Z. He. “Top-k most influential locations selection,” in Proceedings of the 20th Conference on Information and Knowledge Management, pages 2377–2380, 2011.
[21] H. Huang, “Who can be my joint promotion partners?,” Master thesis of National Cheng-Kung University, 2015.
[22] H. Imai and T. Asano, “Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane,” in Journal of algorithms, vol. 4, no. 4, pp. 310-323, Dec. 1983.
[23] C. S. Jensen, J. Kolářvr, T. B. Pedersen, and I. Timko, “Nearest neighbor queries in road networks,” in Proceedings of the 11th ACM international symposium on Advances in geographic information systems, 2003.
[24] Y. Liu and H. S. Seah, “Points of interest recommendation from GPS trajectories,” in International Journal of Geographical Information Science, vol. 29, no. 6, pp. 953-979, 2015.
[25] Y.-W. Lin, E-T. Wang, C.-F. Chiang, A.L.P. Chen, “Finding targets with the nearest favor neighbor and farthest disfavor neighbor by a skyline query,” in Proceedings of the 29th Annual ACM Symposium on Applied Computing, pp. 821-826, 2014.
[26] J. Liu, G. Yu, and H. Sun, “Subject-oriented top-k hot region queries in spatial dataset,” in Proceedings of the 20th ACM international conference on Information and knowledge management, pages 2409–2412, 2011
[27] K. Mouratidis, D. Papadias, and M. Hadjieleftheriou, “Conceptual partitioning: an efficient method for continuous nearest neighbor monitoring,” in Proceedings of the 2005 ACM SIGMOD international conference on Management of data, 2005.
[28] K. Mouratidis, M. L. Yiu, D. Papadias, and N. Mamoulis, “Continuous nearest neighbor monitoring in road networks,” in Proceedings of the 32nd international conference on Very large data bases, 2006.
[29] G. S. Njoo, X. W. Ruan, K. W. Hsu, and W. C. Peng, “A fusion-based approach for user activities recognition on smart phones,” in IEEE International Conference on Data Science and Advanced Analytics, pp. 1-10, 2015.
[30] S. Na, L. Xumin, and G. Yong, "Research on k-means Clustering Algorithm: An Improved k-means Clustering Algorithm," in International Symposium on Intelligent Information Technology and Security Informatics, pp. 63-67, 2010.
[31] S. Nutanong, R. Zhang, E. Tanin, and L. Kulik, “Analysis and evaluation of V*-knn: an efficient algorithm for moving knn queries,” in VLDB Journal, vol. 19, no. 3, pp. 307-332, 2010.
[32] “OpenStreetMap,” http://www.openstreetmap.org/
[33] A. Papadopoulos and Y. Manolopoulos, ”Multiple range query optimization in spatial databases,” in East European Symposium on Advances in Databases and Information Systems, pages 71-82, 1998.
[34] D. Papadias, Q. Shen, Y. Tao, and K. Mouratidis, “Group nearest neighbor queries,” in International Conference on Data Engineering, pp. 301-312, 2004.
[35] N. Roussopoulos, S. Kelley, and F. Vincent, "Nearest neighbor queries,” in ACM SIGMOD, vol. 24, no. 2, pp. 71-79, 1995.
[36] “Real datasets for spatial databases: Road networks and points of interest,” https://www.cs.utah.edu/~lifeifei/SpatialDataset.htm.
[37] D. Sacharidis and A. Deligiannakis, “Spatial cohesion queries,” in Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 1-10, 2015.
[38] S. Shang, D. Guo, J. Liu, K. Zheng, and J.-R. Wen, “Finding regions of interest using location based social media,” in Neurocomputing, vol. 173, pp. 118-123, 2016.
[39] C. Shahabi, M.R. Kolahdouzan, M. Sharifzadeh, “A Road Network Embedding Technique for k-Nearest Neighbor Search in Moving Object Databases,” in Proceedings of the 10th ACM Int'l Symp. Advances in Geographic Information Systems, pp. 94-100, 2002.
[40] Y. Tao, X. Hu, D.-W. Choi, and C.-W. Chung, “Approximate MaxRS in spatial databases,” in Proceedings of the VLDB Endowment, vol. 6, no. 13, pp. 1546-1557, 2013.
[41] Y. Tao, D. Papadias, and Q. Shen, “Continuous nearest neighbor search,” in Proceedings of the 28th international conference on Very Large Data Bases, 2002.
[42] D. Wu and C. S. Jensen, “A Density-Based Approach to the Retrieval of Top-K Spatial Textual Clusters,” in Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, 2016.
[43] X. Xiao, B. Yao, and F. Li, “Optimal location queries in road network databases,” in 2011 IEEE 27th International Conference on Data Engineering, pp. 804-815, 2011.
[44] M. L. Yiu, N. Mamoulis and D. Papadias, “Aggregate nearest neighbor queries in road networks,” in IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 6, pp. 820-833, June 2005.
[45] J. Yang, W. Zhang, Y. Zhang, X. Wang, and X. Lin, “Categorical top-k spatial influence query,” in World Wide Web, vol. 20, no. 2, pp. 175-203, 2017.
[46] J. Yuan, Y. Zheng, L. Zhang, X. Xie, and G. Sun, “Where to find my next passenger,” in Proceedings of the 13th international conference on Ubiquitous computing, 2011.
[47] C. Zhou, N. Bhatnagar, S. Shekhar, and L. Terveen, “Mining Personally Important Places from GPS Tracks,” in 2007 IEEE 23rd International Conference on Data Engineering Workshop, pp. 517-526, 2007.
[48] D. Zhang, C. Y. Chan and K. L. Tan, “Nearest group queries,” in International Conference on Scientific and Statistical Database Management, 2013.
[49] D. Zhang, Y. Du, T. Xia, and Y. Tao, “Progressive computation of the min-dist optimal-location query,” in Proceedings of the 32nd international conference on Very large data bases, 2006.
[50] L. Zhu, Y. Jing, W. Sun, D. Mao, and P. Liu, “Voronoi-based aggregate nearest neighbor query processing in road networks,” in Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2010.
[51] R. Zhong, G. Li, K. L. Tan, L. Zhou, and Z. Gong, “G-tree: An efficient and scalable index for spatial search on road networks,”in IEEE Transactions on Knowledge and Data Engineering, vol. 27, no. 8, pp. 2175-2189, 2015.
[52] W. Y. Zhu, Y. W. Wang, C. J. Chen, W. C. Peng, and P. R. Lei, “A Bayesian-Based Approach for Activity and Mobility Inference in Location-Based Social Networks,” in 17th IEEE International Conference on Mobile Data Management, vol. 1, pp. 152-157, 2016.
[53] Y. Zheng, L. Zhang, Z. Ma, X. Xie, and W.-Y. Ma, “Recommending friends and locations based on individual location history,” in ACM Transactions on the Web, vol. 5, no. 1, pp. 1-44, 2011.
[54] Y. Zheng, L. Zhang, X. Xie, and W.-Y. Ma, “Mining interesting locations and travel sequences from GPS trajectories,” in Proceedings of the 18th international conference on World wide web, 2009.
[55] L. Zhan, Y. Zhang, W. Zhang, X. Lin, “Finding top k most influential spatial facilities over uncertain objects,” in Proceedings of the 21st ACM international conference on Information and knowledge management, pp. 922-931, 2012.