时间依赖路网高效k最近邻查询混搭机制的研究
|
摘要
时空查询(如κ最近邻查询)被广泛地使用在基于位置服务(LBS)中,例如查找离我最近的五家饭店。尽管在路网中两点间的行驶时间非常重要,但已有时空查询的距离度量大部分都是基于物理距离,即欧几里得距离或网络距离,而这种距离度量并不能反映出行驶时间。但相对于物理距离,行驶时间具有高度动态性。路网中两点之间的行驶时间很难被实时而又准确预测。获取行驶时间最佳的方式是实时监控道路的交通状况,如部署摄像头、传感器以及收集车辆GPS信息等。然而,并不是每一个LBS提供者都有能力完成这种高代价的部署。
因此本文中,我们为LBS提供者设计出了一个服务器端的地图混搭机制。采用这种地图混搭机制,LBS提供者利用从互联网地图服务商(如谷歌地图、必应地图、雅虎地图和百度地图等)获取的行驶时间和路径信息并结合本地数据来有效地处理来自用户的各种基于行驶时间的时空查询请求。互联网地图服务商拥有足够的财力和实力,通过多渠道收集数据(如实时交通状况和历史交通数据等)以计算或估算路网中给定两点间的行驶时间和路径信息。但是由于从互联网地图服务商获取数据的高代价性以及局限性,本文提出了修剪、分组、方向共享和并行请求等优化算法并结合κ最近邻查询特点,来减少LBS提供者向互联网地图服务商发送数据请求的次数和响应用户的时间。本文的主要研究内容及贡献总结如下：
·为LBS提供者设计了一个服务器端的地图混搭机制。利用该机制,LBS提供者通过从互联网地图服务商获取行驶时间和路径信息,并结合本地数据,有效地处理路网中基于行驶时间的各项时空查询请求。
·利用修剪技术,即在算法执行过程中不断修剪不必要的查询对象,来减少LBS提供者向互联网地图服务商发送数据请求的次数,并结合网络扩展算法来处理k最近邻查询请求。
·设计出了分组优化策略,即把查询对象和用户分组到路网中交叉路口以实现共享执行,然后估算查询对象到其对应路口的行驶时间和路径信息。在保证查询结果高准确性的基础上,该分组算法能大大减少LBS提供者发送外部数据请求的次数。
·提出了方向共享策略以进一步减少外部数据请求次数。该策略试图让一条包含详细行驶时间和方向信息的路径能被多个起点和其对应的终点共享使用。为了最大化利用方向共享执行,本文中还设计了一个直方图方法用以估算一条路径的共享能力。
·研究了为相互独立路径并行发送数据请求到互联网地图服务商的策略,以降低LBS提供者响应查询用户的时间。此外,还充分挖掘了多用户查询间合作和增量执行以应对大规模用户查询请求,同时解决了增量执行中可能出现的饥饿问题。
·对于本文设计的每一个算法,我们都通过了大规模的实验或模拟仿真验证了其准确性、高效性以及可扩展性。
Spatio-temporal queries have been widely used in location-based services (LBS). Despite the importance of travel time in road networks, the distance measure of tra-ditional spatio-temporal queries for LBS, e.g., k-nearest-neighbor (k-NN), is mostly based on Euclidean or network distance between two locations, which can not reflect the real travel time. In this thesis, we focus on k-NN queries, in time-dependent road networks, where the travel time between two locations may vary significantly at dif-ferent time of the day. In practice, it is costly for an LBS provider to collect real-time traffic data from vehicles or roadside sensors to compute the best route from a user to a spatial object of interest in terms of the travel time. Thus, a server-side spatial mashup framework is designed that enables an LBS provider to efficiently evaluate spatio-temporal queries using the route information and travel time accessed from an external Web mapping service, e.g., Microsoft Bing Maps, Google Maps, MapQuest Maps, Yahoo! Maps, Baidu Maps and so on. Due to the expensive cost and limita-tions of retrieving such external information, we propose pruning, grouping, direction sharing and parallel requesting optimizations to reduce the number of external Web mapping requests and user query response time, and integrate them into k-NN queries using spatial mashups. In summary, the main contribution of this thesis as follows:
· A new framework is proposed, which uses a server-side spatial mashup paradigm for an LBS provider, by accessing travel time and direction information from Web mapping services, to process spatio-temporal queries in a time-dependent road network.
· We have utilized pruning techniques to reduce the number of external requests by pruning objects that are definitely not be part of query answers, and designed an algorithm to processing k-NN queries by combining pruning techniques with network expansion algorithm.
· Grouping optimizations are designed by grouping objects and users to intersec- tions based on the road network topology and user moving directions to achieve shared execution, which is a first attempt to do this kind of grouping as far as we know. This kind of grouping optimization can heavily reduce the number of external request while keeps the high accuracy of travel time and query answers.
· To further reduce the number of external requests, another shared execution op-timization called direction sharing is proposed, which try to make the route be-tween a source to a destination be shared used by other sources and their corre-sponding destinations. A histogram approach is also employed to estimate the sharing ability for a route to make full utilization of the direction sharing opti-mization.
· We have presented a totally new parallel requesting approach to reduce response time for a single user query, exploited inter-query cooperation and incremental processing for a system with high workload (e.g., a large number of user queries arrived concurrently or in succession), brought forth and solved the starvation problem during incremental processing.
因此本文中,我们为LBS提供者设计出了一个服务器端的地图混搭机制。采用这种地图混搭机制,LBS提供者利用从互联网地图服务商(如谷歌地图、必应地图、雅虎地图和百度地图等)获取的行驶时间和路径信息并结合本地数据来有效地处理来自用户的各种基于行驶时间的时空查询请求。互联网地图服务商拥有足够的财力和实力,通过多渠道收集数据(如实时交通状况和历史交通数据等)以计算或估算路网中给定两点间的行驶时间和路径信息。但是由于从互联网地图服务商获取数据的高代价性以及局限性,本文提出了修剪、分组、方向共享和并行请求等优化算法并结合κ最近邻查询特点,来减少LBS提供者向互联网地图服务商发送数据请求的次数和响应用户的时间。本文的主要研究内容及贡献总结如下：
·为LBS提供者设计了一个服务器端的地图混搭机制。利用该机制,LBS提供者通过从互联网地图服务商获取行驶时间和路径信息,并结合本地数据,有效地处理路网中基于行驶时间的各项时空查询请求。
·利用修剪技术,即在算法执行过程中不断修剪不必要的查询对象,来减少LBS提供者向互联网地图服务商发送数据请求的次数,并结合网络扩展算法来处理k最近邻查询请求。
·设计出了分组优化策略,即把查询对象和用户分组到路网中交叉路口以实现共享执行,然后估算查询对象到其对应路口的行驶时间和路径信息。在保证查询结果高准确性的基础上,该分组算法能大大减少LBS提供者发送外部数据请求的次数。
·提出了方向共享策略以进一步减少外部数据请求次数。该策略试图让一条包含详细行驶时间和方向信息的路径能被多个起点和其对应的终点共享使用。为了最大化利用方向共享执行,本文中还设计了一个直方图方法用以估算一条路径的共享能力。
·研究了为相互独立路径并行发送数据请求到互联网地图服务商的策略,以降低LBS提供者响应查询用户的时间。此外,还充分挖掘了多用户查询间合作和增量执行以应对大规模用户查询请求,同时解决了增量执行中可能出现的饥饿问题。
·对于本文设计的每一个算法,我们都通过了大规模的实验或模拟仿真验证了其准确性、高效性以及可扩展性。
Spatio-temporal queries have been widely used in location-based services (LBS). Despite the importance of travel time in road networks, the distance measure of tra-ditional spatio-temporal queries for LBS, e.g., k-nearest-neighbor (k-NN), is mostly based on Euclidean or network distance between two locations, which can not reflect the real travel time. In this thesis, we focus on k-NN queries, in time-dependent road networks, where the travel time between two locations may vary significantly at dif-ferent time of the day. In practice, it is costly for an LBS provider to collect real-time traffic data from vehicles or roadside sensors to compute the best route from a user to a spatial object of interest in terms of the travel time. Thus, a server-side spatial mashup framework is designed that enables an LBS provider to efficiently evaluate spatio-temporal queries using the route information and travel time accessed from an external Web mapping service, e.g., Microsoft Bing Maps, Google Maps, MapQuest Maps, Yahoo! Maps, Baidu Maps and so on. Due to the expensive cost and limita-tions of retrieving such external information, we propose pruning, grouping, direction sharing and parallel requesting optimizations to reduce the number of external Web mapping requests and user query response time, and integrate them into k-NN queries using spatial mashups. In summary, the main contribution of this thesis as follows:
· A new framework is proposed, which uses a server-side spatial mashup paradigm for an LBS provider, by accessing travel time and direction information from Web mapping services, to process spatio-temporal queries in a time-dependent road network.
· We have utilized pruning techniques to reduce the number of external requests by pruning objects that are definitely not be part of query answers, and designed an algorithm to processing k-NN queries by combining pruning techniques with network expansion algorithm.
· Grouping optimizations are designed by grouping objects and users to intersec- tions based on the road network topology and user moving directions to achieve shared execution, which is a first attempt to do this kind of grouping as far as we know. This kind of grouping optimization can heavily reduce the number of external request while keeps the high accuracy of travel time and query answers.
· To further reduce the number of external requests, another shared execution op-timization called direction sharing is proposed, which try to make the route be-tween a source to a destination be shared used by other sources and their corre-sponding destinations. A histogram approach is also employed to estimate the sharing ability for a route to make full utilization of the direction sharing opti-mization.
· We have presented a totally new parallel requesting approach to reduce response time for a single user query, exploited inter-query cooperation and incremental processing for a system with high workload (e.g., a large number of user queries arrived concurrently or in succession), brought forth and solved the starvation problem during incremental processing.
引文
[1]Christian S. Jensen. Database aspects of location-based services. In Location-Based Services, pages 115-148. Morgan Kaufmann,2004.
[2]Dik Lun Lee, Manli Zhu, and Haibo Hu. When location-based services meet databases. Mobile Information Systems,1(2):81-90,2005.
[3]Bugra Gedik and Ling Liu. Mobieyes:A distributed location monitoring service using moving location queries. IEEE Transactions on Mobile Computing,5(10): 1384-1402,2006.
[4]Mohamed F. Mokbel, Xiaopeng Xiong, and Walid G. Aref. SINA:scalable in-cremental processing of continuous queries in spatio-temporal databases. In Pro-ceedings of the ACM Conference on Management of Data,2004.
[5]Dimitris Papadias, Jun Zhang, Nikos Mamoulis, and Yufei Tao. Query processing in spatial network databases. In Proceedings of the International Conference on Very Large Data Bases,2003.
[6]Bijit Hore, Sharad Mehrotra, and Gene Tsudik. A privacy-preserving index for range queries. In Proceedings of the International Conference on Very Large Data Bases,2004.
[7]Dimitrios Gunopulos, George Kollios, Vassilis J. Tsotras, and Carlotta Domeni-coni. Approximating multi-dimensional aggregate range queries over real at-tributes. In Proceedings of the ACM Conference on Management of Data,2000.
[8]J. Jin, Ning An, and Anand Sivasubramaniam. Analyzing range queries on spatial data. In Proceedings of the IEEE International Conference on Data Engineering, 2000.
[9]Xin Li, Young Jin Kim, Ramesh Govindan, and Wei Hong. Multi-dimensional range queries in sensor networks. In Proceedings of the International Conference on Embedded Networked Sensor Systems,2003.
[10]Haibo Hu, Jianliang Xu, and Dik Lun Lee. A generic framework for monitor-ing continuous spatial queries over moving objects. In Proceedings of the ACM Conference on Management of Data,2005.
[11]Kyriakos Mouratidis, Dimitris Papadias, and Marios Hadjieleftheriou. Concep-tual partitioning:An efficient method for continuous nearest neighbor monitor-ing. In Proceedings of the ACM Conference on Management of Data,2005.
[12]Yufei Tao, Dimitris Papadias, and Qiongmao Shen. Continuous nearest neighbor search. In Proceedings of the International Conference on Very Large Data Bases, 2002.
[13]Hae Don Chon, Divyakant Agrawal, and Amr El Abbadi. Range and knn query processing for moving objects in grid model. Mobile Networks and Applications, 8(4):401^12,2003.
[14]Xiaohui Yu, Ken Q Pu, and Nick Koudas. Monitoring k-nearest neighbor queries over moving objects. In Proceedings of the IEEE International Conference on Data Engineering,2005.
[15]Glenn S Iwerks, Hanan Samet, and Ken Smith. Continuous k-nearest neighbor queries for continuously moving points with updates. In Proceedings of the In-ternational Conference on Very Large Data Bases,2003.
[16]Mohammad Kolahdouzan and Cyrus Shahabi. Voronoi-based k nearest neighbor search for spatial network databases. In Proceedings of the International Confer-ence on Very Large Data Bases,2004.
[17]Congjun Yang and King-Ip Lin. An index structure for efficient reverse nearest neighbor queries. In Proceedings of the IEEE International Conference on Data Engineering,2001.
[18]Amit Singh, Hakan Ferhatosmanoglu, and Ali Saman Tosun. High dimensional reverse nearest neighbor queries. In Proceedings of the International Conference on Information and Knowledge Management,2003.
[19]Rimantas Benetis, Christian Jensen, Gytis Karciauskas, and Simonas Saltenis. Nearest and Reverse Nearest Neighbor Queries for Moving Objects. The Inter- national Journal on Very Large Data Bases,15(3):229-249,2006.
[20]Muhammad Aamir Cheema, Xuemin Lin, Wei Wang, Wenjie Zhang, and Jian Pei. Probabilistic reverse nearest neighbor queries on uncertain data. IEEE Transac-tions on Knowledge and Data Engineering,22(4):550-564,2010.
[21]Xiang Lian and Lei Chen. Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data. The International Journal on Very Large Data Bases,18(3):787-808,2009.
[22]Xiaopeng Xiong, Mohamed F Mokbel, and Walid G Aref. Sea-cnn:Scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases. In Proceedings of the IEEE International Conference on Data Engineering,2005.
[23]Kyriakos Mouratidis, Man Lung Yiu, Dimitris Papadias, and Nikos Mamoulis. Continuous nearest neighbor monitoring in road networks. In Proceedings of the 32nd international conference on Very large data bases,2006.
[24]Muhammad Aamir Cheema, Wenjie Zhang, Xuemin Lin, Ying Zhang, and Xuefei Li. Continuous reverse k nearest neighbors queries in euclidean space and in spatial networks. The International Journal on Very Large Data Bases,21(1): 69-95,2012.
[25]Hicham G Elmongui, Mohamed F Mokbel, and Walid G Aref. Continuous ag-gregate nearest neighbor queries. Geolnformatica,17(1):63-95,2013.
[26]Hakan Ferhatosmanoglu, Ioanna Stanoi, Divyakant Agrawal, and Amr El Ab-badi. Constrained nearest neighbor queries. In Proceedings of the International Symposium on Spatial and Temporal Databases,2001.
[27]Ugur Demiryurek, Farnoush Banaei-Kashani, and Cyrus Shahabi. Efficient k-nearest neighbor search in time-dependent spatial networks. In Proceedings of the International Conference on Database and Expert Systems Applications,2010.
[28]Betsy George, Sangho Kim, and Shashi Shekhar. Spatio-temporal network databases and routing algorithms:A summary of results. In Proceedings of the International Symposium on Spatial and Temporal Databases,2007.
[29]Ugur Demiryurek, Famoush Banaei-Kashani, and Cyrus Shahabi. Towards k-nearest neighbor search in time-dependent spatial network databases. In Interna-tional Workshop on Databases in Networked Systems,2010.
[30]Steven I-Jy Chien and Chandra Mouly Kuchipudi. Dynamic travel time prediction with real-time and historic data. Journal of transportation engineering,129(6): 608-616,2003.
[31]Shuo Shang, Hua Lu, Torben Bach Pedersen, and Xike Xie. Modeling of traffic-aware travel time in spatial networks. In Proceedings of the International Con-ference on Mobile Data Management,2013.
[32]Luca Foschini, John Hershberger, and Subhash Suri. On the complexity of time-dependent shortest paths. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms,2011.
[33]Andrei Vancea, Michael Grossniklaus, and Moira C. Norrie. Database-driven web mashups. In Proceedings of the International Conference on Web Engineering, 2008.
[34]HousingMaps. http://www.housingmaps.com.
[35]Yahoo! Pipes, http://pipes.yahoo.com/pipes.
[36]DUI Map. http://duimap.org/.
[37]Vataware. http://www.vataware.com/.
[38]DJ Earworm. http://djearworm.com/.
[39]Qunar. http://www.qunar.com/.
[40]Soufun. http://www.soufun.cn/.
[41]Jin Yu, Boualem Benatallah, Fabio Casati, and Florian Daniel. Understanding mashup development. IEEE Internet Computing,12(5):44-52,2008.
[42]Soudip Roy Chowdhury, Carlos Rodriguez, Florian Daniel, and Fabio Casati. Baya:Assisted mashup development as a service. In Proceedings of the Interna-tional Conference on World Wide Web,2012.
[43]S. Endrullis, A. Thor, and E. Rahm. Entity search strategies for mashup applica-tions. In Proceedings of the IEEE International Conference on Data Engineering, 2012.
[44]Keman Huang, Yushun Fan, and Wei Tan. An empirical study of programmable web:A network analysis on a service-mashup system. In Proceedings of the IEEE International Conference on Web Services,2012.
[45]Djamal Benslimane, Schahram Dustdar, and Amit Sheth. Services mashups:The new generation of web applications. IEEE Internet Computing,12(5):13-15, 2008.
[46]Anant Jhingran. Enterprise information mashups:integrating information, sim-ply. In Proceedings of the International Conference on Very Large Data Bases, 2006.
[47]Jeffrey Wong and Jason I Hong. Making mashups with marmite:towards end-user programming for the web. In Proceedings of the SIGCH1 conference on Human factors in computing systems,2007.
[48]Robert J Ennals and Minos N Garofalakis. Mashmaker:mashups for the masses. In Proceedings of the ACM Conference on Management of Data,2007.
[49]Hendrik Gebhardt, Martin Gaedke, Florian Daniel, Stefano Soi, Fabio Casati, Carlos A Iglesias, and Scott Wilson. From mashups to telco mashups:a survey. IEEE Internet Computing,16(3):70-76,2012.
[50]Cinzia Cappiello, Maristella Matera, Matteo Picozzi, Alessandro Caio, and Mar-iano Tomas Guevara. Mobimash:end user development for mobile mashups. In Proceedings of the international conference companion on World Wide Web, 2012.
[51]V. Stirbu, Yu You, K. Roimela, and V. Mattila. A lightweight platform for web mashups in immersive mirror worlds. IEEE Pervasive Computing,12(1):34-41, 2013.
[52]Programmable Web. http://www.programmableweb.com.
[53]Google Maps. http://maps.google.com.
[54]MapQuest Maps. http://www.mapquestapi.com.
[55]Microsoft Bing Maps. http://www.bing.com/maps.
[56]Yahoo! Maps. http://maps.yahoo.com.
[57]Baidu Maps. http://map.baidu.com/.
[58]Justin J. Levandoski, Mohamed F. Mokbel, and Mohamed E. Khalefa. Preference query evaluation over expensive attributes. In Proceedings of the International Conference on Information and Knowledge Management,2010.
[59]Google Maps/Google Earth APIs Terms of Service. http://code.google.com/apis/maps/terms.html.
[60]Micha Sharir. Intersection and closest-pair problems for a set of planar discs. SIAM Journal on Computing,14(2).448-468,1985.
[61]Antonio Corral, Yannis Manolopoulos, Yannis Theodoridis, and Michael Vassi-lakopoulos. Closest pair queries in spatial databases. ACM SIGMOD Record,29 (2):189-200,2000.
[62]Antonio Corral, Yannis Manolopoulos, Yannis Theodoridis, and Michael Vassi-lakopoulos. Algorithms for processing k-closest-pair queries in spatial databases. Data& Knowledge Engineering,49(1):67-104,2004.
[63]Hanan Samet, Jagan Sankaranarayanan, and Houman Alborzi. Scalable network distance browsing in spatial databases. In Proceedings of the ACM Conference on Management of Data,2008.
[64]Xuegang Huang, Christian S. Jensen, and Simonas Saltenis. The islands approach to nearest neighbor querying in spatial networks. In Proceedings of the Interna-tional Symposium on Spatial and Temporal Databases,2005.
[65]Bolin Ding, Jeffrey Xu Yu, and Lu Qin. Finding time-dependent shortest paths over large graphs. In Proceedings of the International Conference on Extending Database Technology,2008.
[66]Rimma V. Nehmel and Elke A. Rundensteiner. SCUBA:Scalable cluster-based algorithm for evaluating continuous spatio-temporal queries on moving objects. Proceedings of the International Conference on Extending Database Technology, 2006.
[67]Egemen Tanin, Aaron Harwood, and Hanan Samet. Using a distributed quadtree index in peer-to-peer networks. The International Journal on Very Large Data Bases,16(2):165-178,2007.
[68]Chi-Yin Chow, Mohamed F. Mokbel, and Hong Va Leong. On efficient and scal-able support of continuous queries in mobile peer-to-peer environments. IEEE Transactions on Mobile Computing,10(10):1473-1487,2011.
[69]Qijun Zhu, Dik Lun Lee, and Wang-Chien Lee. Collaborative caching for spa-tial queries in mobile P2P networks. In Proceedings of the IEEE International Conference on Data Engineering,2011.
[70]Tao-Yang Fu, Wen-Chih Peng, and Wang-Chien Lee. Parallelizing itinerary-based KNN query processing in wireless sensor networks. IEEE Transactions on Knowledge and Data Engineering,22(5):711-729,2010.
[71]Shan-Hung Wu, Kun-Ta Chuang, Chung-Min Chen, and Ming-Syan Chen. DIKNN:An itinerary-based KNN query processing algorithm for mobile sen-sor networks. In Proceedings of the IEEE International Conference on Data Engineering,2007.
[72]Mohamed F. Mokbel, Xiaopeng Xiong, Moustafa A. Hammad, and Walid G. Aref. Continuous query processing of spatio-temporal data streams in PLACE. Geoinformatica,9(4):343-365,2005.
[73]Jaime Ballesteros, Ariel Cary, and Naphtali Rishe. SpSJoin:Parallel spatial sim-ilarity joins. In Proceedings of the ACM Symposium on Advances in Geographic Information Systems,2011.
[74]Xiaofang Zhou, David J. Abel, and David Truffet. Data partitioning for parallel spatial join processing. GeoInformatica,2:175-204,1998.
[75]Gang Luo, J.F. Naughton, and C.J. Ellmann. A non-blocking parallel spatial join algorithm. In Proceedings of the IEEE International Conference on Data Engineering,2002.
[76]Nicolas Bruno, Luis Gravano, and Amelie Marian. Evaluating top-k queries over web-accessible databases. In Proceedings of the IEEE International Conference on Data Engineering,2002.
[77]Kevin Chen-Chuan Chang and Seung-Won Hwang. Minimal probing:Supporting expensive predicates for top-k queries. In Proceedings of the ACM Conference on Management of Data,2002.
[78]The Google Directions API. https://developers. google.com/maps/documenta-tion/directions.
[79]MapQuest Directions Web Service. http://www.mapquestapi.com/directions.
[80]The Google Distance Matrix API. https://developers. google.com/maps/docu-mentation/distancematrix.
[81]MapQuest Directions Web Service-Route Matrix. http://www.mapquestapi.com/directions/#matrix.
[82]TIGER/Line Shapefiles 2009 for:Hennepin County, Minnesota. http://www2.census.gov/cgi-bin/shapefiles2009/county-files?county=27053.
[83]Evangelos Kanoulas, Yang Du, Tian Xia, and Donghui Zhang. Finding fastest paths on a road network with speed patterns. In Proceedings of the IEEE Inter-national Conference on Data Engineering,2006.
[84]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. The MIT Press,2001.
[85]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3. ed.). MIT Press,2009.
[86]The Google Places API. https://developers.google.com/places/.
[87]Chi-Yin Chow, Mohamed F. Mokbel, Jie Bao, and Xuan Liu. Query-aware loca-tion anonymization for road networks. Geolnformatica,15(3):571-607,2011.
[2]Dik Lun Lee, Manli Zhu, and Haibo Hu. When location-based services meet databases. Mobile Information Systems,1(2):81-90,2005.
[3]Bugra Gedik and Ling Liu. Mobieyes:A distributed location monitoring service using moving location queries. IEEE Transactions on Mobile Computing,5(10): 1384-1402,2006.
[4]Mohamed F. Mokbel, Xiaopeng Xiong, and Walid G. Aref. SINA:scalable in-cremental processing of continuous queries in spatio-temporal databases. In Pro-ceedings of the ACM Conference on Management of Data,2004.
[5]Dimitris Papadias, Jun Zhang, Nikos Mamoulis, and Yufei Tao. Query processing in spatial network databases. In Proceedings of the International Conference on Very Large Data Bases,2003.
[6]Bijit Hore, Sharad Mehrotra, and Gene Tsudik. A privacy-preserving index for range queries. In Proceedings of the International Conference on Very Large Data Bases,2004.
[7]Dimitrios Gunopulos, George Kollios, Vassilis J. Tsotras, and Carlotta Domeni-coni. Approximating multi-dimensional aggregate range queries over real at-tributes. In Proceedings of the ACM Conference on Management of Data,2000.
[8]J. Jin, Ning An, and Anand Sivasubramaniam. Analyzing range queries on spatial data. In Proceedings of the IEEE International Conference on Data Engineering, 2000.
[9]Xin Li, Young Jin Kim, Ramesh Govindan, and Wei Hong. Multi-dimensional range queries in sensor networks. In Proceedings of the International Conference on Embedded Networked Sensor Systems,2003.
[10]Haibo Hu, Jianliang Xu, and Dik Lun Lee. A generic framework for monitor-ing continuous spatial queries over moving objects. In Proceedings of the ACM Conference on Management of Data,2005.
[11]Kyriakos Mouratidis, Dimitris Papadias, and Marios Hadjieleftheriou. Concep-tual partitioning:An efficient method for continuous nearest neighbor monitor-ing. In Proceedings of the ACM Conference on Management of Data,2005.
[12]Yufei Tao, Dimitris Papadias, and Qiongmao Shen. Continuous nearest neighbor search. In Proceedings of the International Conference on Very Large Data Bases, 2002.
[13]Hae Don Chon, Divyakant Agrawal, and Amr El Abbadi. Range and knn query processing for moving objects in grid model. Mobile Networks and Applications, 8(4):401^12,2003.
[14]Xiaohui Yu, Ken Q Pu, and Nick Koudas. Monitoring k-nearest neighbor queries over moving objects. In Proceedings of the IEEE International Conference on Data Engineering,2005.
[15]Glenn S Iwerks, Hanan Samet, and Ken Smith. Continuous k-nearest neighbor queries for continuously moving points with updates. In Proceedings of the In-ternational Conference on Very Large Data Bases,2003.
[16]Mohammad Kolahdouzan and Cyrus Shahabi. Voronoi-based k nearest neighbor search for spatial network databases. In Proceedings of the International Confer-ence on Very Large Data Bases,2004.
[17]Congjun Yang and King-Ip Lin. An index structure for efficient reverse nearest neighbor queries. In Proceedings of the IEEE International Conference on Data Engineering,2001.
[18]Amit Singh, Hakan Ferhatosmanoglu, and Ali Saman Tosun. High dimensional reverse nearest neighbor queries. In Proceedings of the International Conference on Information and Knowledge Management,2003.
[19]Rimantas Benetis, Christian Jensen, Gytis Karciauskas, and Simonas Saltenis. Nearest and Reverse Nearest Neighbor Queries for Moving Objects. The Inter- national Journal on Very Large Data Bases,15(3):229-249,2006.
[20]Muhammad Aamir Cheema, Xuemin Lin, Wei Wang, Wenjie Zhang, and Jian Pei. Probabilistic reverse nearest neighbor queries on uncertain data. IEEE Transac-tions on Knowledge and Data Engineering,22(4):550-564,2010.
[21]Xiang Lian and Lei Chen. Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data. The International Journal on Very Large Data Bases,18(3):787-808,2009.
[22]Xiaopeng Xiong, Mohamed F Mokbel, and Walid G Aref. Sea-cnn:Scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases. In Proceedings of the IEEE International Conference on Data Engineering,2005.
[23]Kyriakos Mouratidis, Man Lung Yiu, Dimitris Papadias, and Nikos Mamoulis. Continuous nearest neighbor monitoring in road networks. In Proceedings of the 32nd international conference on Very large data bases,2006.
[24]Muhammad Aamir Cheema, Wenjie Zhang, Xuemin Lin, Ying Zhang, and Xuefei Li. Continuous reverse k nearest neighbors queries in euclidean space and in spatial networks. The International Journal on Very Large Data Bases,21(1): 69-95,2012.
[25]Hicham G Elmongui, Mohamed F Mokbel, and Walid G Aref. Continuous ag-gregate nearest neighbor queries. Geolnformatica,17(1):63-95,2013.
[26]Hakan Ferhatosmanoglu, Ioanna Stanoi, Divyakant Agrawal, and Amr El Ab-badi. Constrained nearest neighbor queries. In Proceedings of the International Symposium on Spatial and Temporal Databases,2001.
[27]Ugur Demiryurek, Farnoush Banaei-Kashani, and Cyrus Shahabi. Efficient k-nearest neighbor search in time-dependent spatial networks. In Proceedings of the International Conference on Database and Expert Systems Applications,2010.
[28]Betsy George, Sangho Kim, and Shashi Shekhar. Spatio-temporal network databases and routing algorithms:A summary of results. In Proceedings of the International Symposium on Spatial and Temporal Databases,2007.
[29]Ugur Demiryurek, Famoush Banaei-Kashani, and Cyrus Shahabi. Towards k-nearest neighbor search in time-dependent spatial network databases. In Interna-tional Workshop on Databases in Networked Systems,2010.
[30]Steven I-Jy Chien and Chandra Mouly Kuchipudi. Dynamic travel time prediction with real-time and historic data. Journal of transportation engineering,129(6): 608-616,2003.
[31]Shuo Shang, Hua Lu, Torben Bach Pedersen, and Xike Xie. Modeling of traffic-aware travel time in spatial networks. In Proceedings of the International Con-ference on Mobile Data Management,2013.
[32]Luca Foschini, John Hershberger, and Subhash Suri. On the complexity of time-dependent shortest paths. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms,2011.
[33]Andrei Vancea, Michael Grossniklaus, and Moira C. Norrie. Database-driven web mashups. In Proceedings of the International Conference on Web Engineering, 2008.
[34]HousingMaps. http://www.housingmaps.com.
[35]Yahoo! Pipes, http://pipes.yahoo.com/pipes.
[36]DUI Map. http://duimap.org/.
[37]Vataware. http://www.vataware.com/.
[38]DJ Earworm. http://djearworm.com/.
[39]Qunar. http://www.qunar.com/.
[40]Soufun. http://www.soufun.cn/.
[41]Jin Yu, Boualem Benatallah, Fabio Casati, and Florian Daniel. Understanding mashup development. IEEE Internet Computing,12(5):44-52,2008.
[42]Soudip Roy Chowdhury, Carlos Rodriguez, Florian Daniel, and Fabio Casati. Baya:Assisted mashup development as a service. In Proceedings of the Interna-tional Conference on World Wide Web,2012.
[43]S. Endrullis, A. Thor, and E. Rahm. Entity search strategies for mashup applica-tions. In Proceedings of the IEEE International Conference on Data Engineering, 2012.
[44]Keman Huang, Yushun Fan, and Wei Tan. An empirical study of programmable web:A network analysis on a service-mashup system. In Proceedings of the IEEE International Conference on Web Services,2012.
[45]Djamal Benslimane, Schahram Dustdar, and Amit Sheth. Services mashups:The new generation of web applications. IEEE Internet Computing,12(5):13-15, 2008.
[46]Anant Jhingran. Enterprise information mashups:integrating information, sim-ply. In Proceedings of the International Conference on Very Large Data Bases, 2006.
[47]Jeffrey Wong and Jason I Hong. Making mashups with marmite:towards end-user programming for the web. In Proceedings of the SIGCH1 conference on Human factors in computing systems,2007.
[48]Robert J Ennals and Minos N Garofalakis. Mashmaker:mashups for the masses. In Proceedings of the ACM Conference on Management of Data,2007.
[49]Hendrik Gebhardt, Martin Gaedke, Florian Daniel, Stefano Soi, Fabio Casati, Carlos A Iglesias, and Scott Wilson. From mashups to telco mashups:a survey. IEEE Internet Computing,16(3):70-76,2012.
[50]Cinzia Cappiello, Maristella Matera, Matteo Picozzi, Alessandro Caio, and Mar-iano Tomas Guevara. Mobimash:end user development for mobile mashups. In Proceedings of the international conference companion on World Wide Web, 2012.
[51]V. Stirbu, Yu You, K. Roimela, and V. Mattila. A lightweight platform for web mashups in immersive mirror worlds. IEEE Pervasive Computing,12(1):34-41, 2013.
[52]Programmable Web. http://www.programmableweb.com.
[53]Google Maps. http://maps.google.com.
[54]MapQuest Maps. http://www.mapquestapi.com.
[55]Microsoft Bing Maps. http://www.bing.com/maps.
[56]Yahoo! Maps. http://maps.yahoo.com.
[57]Baidu Maps. http://map.baidu.com/.
[58]Justin J. Levandoski, Mohamed F. Mokbel, and Mohamed E. Khalefa. Preference query evaluation over expensive attributes. In Proceedings of the International Conference on Information and Knowledge Management,2010.
[59]Google Maps/Google Earth APIs Terms of Service. http://code.google.com/apis/maps/terms.html.
[60]Micha Sharir. Intersection and closest-pair problems for a set of planar discs. SIAM Journal on Computing,14(2).448-468,1985.
[61]Antonio Corral, Yannis Manolopoulos, Yannis Theodoridis, and Michael Vassi-lakopoulos. Closest pair queries in spatial databases. ACM SIGMOD Record,29 (2):189-200,2000.
[62]Antonio Corral, Yannis Manolopoulos, Yannis Theodoridis, and Michael Vassi-lakopoulos. Algorithms for processing k-closest-pair queries in spatial databases. Data& Knowledge Engineering,49(1):67-104,2004.
[63]Hanan Samet, Jagan Sankaranarayanan, and Houman Alborzi. Scalable network distance browsing in spatial databases. In Proceedings of the ACM Conference on Management of Data,2008.
[64]Xuegang Huang, Christian S. Jensen, and Simonas Saltenis. The islands approach to nearest neighbor querying in spatial networks. In Proceedings of the Interna-tional Symposium on Spatial and Temporal Databases,2005.
[65]Bolin Ding, Jeffrey Xu Yu, and Lu Qin. Finding time-dependent shortest paths over large graphs. In Proceedings of the International Conference on Extending Database Technology,2008.
[66]Rimma V. Nehmel and Elke A. Rundensteiner. SCUBA:Scalable cluster-based algorithm for evaluating continuous spatio-temporal queries on moving objects. Proceedings of the International Conference on Extending Database Technology, 2006.
[67]Egemen Tanin, Aaron Harwood, and Hanan Samet. Using a distributed quadtree index in peer-to-peer networks. The International Journal on Very Large Data Bases,16(2):165-178,2007.
[68]Chi-Yin Chow, Mohamed F. Mokbel, and Hong Va Leong. On efficient and scal-able support of continuous queries in mobile peer-to-peer environments. IEEE Transactions on Mobile Computing,10(10):1473-1487,2011.
[69]Qijun Zhu, Dik Lun Lee, and Wang-Chien Lee. Collaborative caching for spa-tial queries in mobile P2P networks. In Proceedings of the IEEE International Conference on Data Engineering,2011.
[70]Tao-Yang Fu, Wen-Chih Peng, and Wang-Chien Lee. Parallelizing itinerary-based KNN query processing in wireless sensor networks. IEEE Transactions on Knowledge and Data Engineering,22(5):711-729,2010.
[71]Shan-Hung Wu, Kun-Ta Chuang, Chung-Min Chen, and Ming-Syan Chen. DIKNN:An itinerary-based KNN query processing algorithm for mobile sen-sor networks. In Proceedings of the IEEE International Conference on Data Engineering,2007.
[72]Mohamed F. Mokbel, Xiaopeng Xiong, Moustafa A. Hammad, and Walid G. Aref. Continuous query processing of spatio-temporal data streams in PLACE. Geoinformatica,9(4):343-365,2005.
[73]Jaime Ballesteros, Ariel Cary, and Naphtali Rishe. SpSJoin:Parallel spatial sim-ilarity joins. In Proceedings of the ACM Symposium on Advances in Geographic Information Systems,2011.
[74]Xiaofang Zhou, David J. Abel, and David Truffet. Data partitioning for parallel spatial join processing. GeoInformatica,2:175-204,1998.
[75]Gang Luo, J.F. Naughton, and C.J. Ellmann. A non-blocking parallel spatial join algorithm. In Proceedings of the IEEE International Conference on Data Engineering,2002.
[76]Nicolas Bruno, Luis Gravano, and Amelie Marian. Evaluating top-k queries over web-accessible databases. In Proceedings of the IEEE International Conference on Data Engineering,2002.
[77]Kevin Chen-Chuan Chang and Seung-Won Hwang. Minimal probing:Supporting expensive predicates for top-k queries. In Proceedings of the ACM Conference on Management of Data,2002.
[78]The Google Directions API. https://developers. google.com/maps/documenta-tion/directions.
[79]MapQuest Directions Web Service. http://www.mapquestapi.com/directions.
[80]The Google Distance Matrix API. https://developers. google.com/maps/docu-mentation/distancematrix.
[81]MapQuest Directions Web Service-Route Matrix. http://www.mapquestapi.com/directions/#matrix.
[82]TIGER/Line Shapefiles 2009 for:Hennepin County, Minnesota. http://www2.census.gov/cgi-bin/shapefiles2009/county-files?county=27053.
[83]Evangelos Kanoulas, Yang Du, Tian Xia, and Donghui Zhang. Finding fastest paths on a road network with speed patterns. In Proceedings of the IEEE Inter-national Conference on Data Engineering,2006.
[84]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. The MIT Press,2001.
[85]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3. ed.). MIT Press,2009.
[86]The Google Places API. https://developers.google.com/places/.
[87]Chi-Yin Chow, Mohamed F. Mokbel, Jie Bao, and Xuan Liu. Query-aware loca-tion anonymization for road networks. Geolnformatica,15(3):571-607,2011.