Abstract
Increasingly, location-aware datasets are of a size, variety, and update rate that exceeds the capability of spatial computing technologies. This paper addresses the emerging challenges posed by such datasets, which we call Spatial Big Data (SBD). SBD examples include trajectories of cell-phones and GPS devices, vehicle engine measurements, temporally detailed road maps, etc. SBD has the potential to transform society via a number of new technologies including next-generation routing services. However, the envisaged SBD-based services pose several significant challenges for current spatial computing techniques. SBD magnifies the impact of partial information and ambiguity of traditional routing queries specified by a start location and an end location. In addition, SBD challenges the assumption that a single algorithm utilizing a specific dataset is appropriate for all situations. The tremendous diversity of SBD sources substantially increases the diversity of solution methods. Newer algorithms may emerge as new SBD becomes available, creating the need for a flexible architecture to rapidly integrate new datasets and associated algorithms. To quantify the performance of these new algorithms, new benchmarks are needed that focus on these spatial big datasets to ensure proper comparisons across techniques.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
American Transportation Research Institute (ATRI). Fpm congestion monitoring at 250 freight significant highway location: Final results of the 2010 performance assessment (2010), http://goo.gl/3cAjr
American Transportation Research Institute (ATRI). Atri and fhwa release bottleneck analysis of 100 freight significant highway locations (2010), http://goo.gl/C0NuD
Bauer, E., Adams, R., Eustace, D.: Beyond Redundancy: How Geographic Redundancy Can Improve Service Availability and Reliability of Computer-based Systems. Wiley-IEEE Press (2011)
Booth, J., Sistla, P., Wolfson, O., Cruz, I.: A data model for trip planning in multimodal transportation systems. In: Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, pp. 994–1005. ACM (2009)
Brown, A.: Transportation Energy Futures: Addressing Key Gaps and Providing Tools for Decision Makers. Technical report, National Renewable Energy Laboratory (2011)
Capps, G., Franzese, O., Knee, B., Lascurain, M., Otaduy, P.: Class-8 heavy truck duty cycle project final report. ORNL/TM-2008/122 (2008)
Chan, E.P.F., Zhang, J.: Efficient evaluation of static and dynamic optimal route queries. In: Mamoulis, N., Seidl, T., Pedersen, T.B., Torp, K., Assent, I. (eds.) SSTD 2009. LNCS, vol. 5644, pp. 386–391. Springer, Heidelberg (2009)
Chang, T.: Best routes selection in international intermodal networks. Computers & Operations Research 35(9), 2877–2891 (2008)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press (2001)
Davis, S.C., Diegel, S.W., Boundy, R.G.: Transportation energy data book: Edition 28. Technical report, Oak Ridge National Laboratory (2010)
Dobson, J., Fisher, P.: Geoslavery. IEEE Technology and Society Magazine 22(1), 47–52 (2003)
Federal Highway Administration. Highway Statistics. HM-63, HM-64 (2008)
Frigioni, D., Ioffreda, M., Nanni, U., Pasqualone, G.: Experimental analysis of dynamic algorithms for the single. ACM Journal of Experimental Algorithmics (JEA) 3, 5 (1998)
Frigioni, D., Marchetti-Spaccamela, A., Nanni, U.: Semidynamic algorithms for maintaining single-source shortest path trees. Algorithmica 22(3), 250–274 (1998)
Garmin, http://www.garmin.com/us/
George, B., Shekhar, S.: Road maps, digital. In: Encyclopedia of GIS, pp. 967–972. Springer (2008)
Google Maps, http://maps.google.com
Gray, J.: Benchmark handbook: for database and transaction processing systems, 2nd edn. Morgan Kaufmann Publishers Inc. (1993)
Hoel, E.G., Heng, W.-L., Honeycutt, D.: High performance multimodal networks. In: Medeiros, C.B., Egenhofer, M., Bertino, E. (eds.) SSTD 2005. LNCS, vol. 3633, pp. 308–327. Springer, Heidelberg (2005)
Jagadeesh, G., Srikanthan, T., Quek, K.: Heuristic techniques for accelerating hierarchical routing on road networks. IEEE Transactions on Intelligent Transportation Systems 3(4), 301–309 (2002)
Jing, N., Huang, Y.-W., Rundensteiner, E.A.: Hierarchical optimization of optimal path finding for transportation applications. In: Proceedings of the Fifth International Conference on Information and Knowledge Management (CIKM), pp. 261–268. ACM (1996)
Kargupta, H., Gama, J., Fan, W.: The next generation of transportation systems, greenhouse emissions, and data mining. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1209–1212. ACM (2010)
Kargupta, H., Puttagunta, V., Klein, M., Sarkar, K.: On-board vehicle data stream monitoring using minefleet and fast resource constrained monitoring of correlation matrices. New Generation Computing 25(1), 5–32 (2006)
Kleinberg, J., Tardos, E.: Algorithm Design. Pearson Education (2009)
Krumm, J.: A survey of computational location privacy. Personal and Ubiquitous Computing 13(6), 391–399 (2009)
Lovell, J.: Left-hand-turn elimination, December 9. New York Times (2007), http://goo.gl/3bkPb
Lynx GIS, http://www.lynxgis.com/
Mabrouk, M., Bychowski, T., Niedzwiadek, H., Bishr, Y., Gaillet, J., Crisp, N., Wilbrink, W., Horhammer, M., Roy, G., Margoulis, S.: Opengis location services (openls): Core services. OGC Implementation Specification 5, 016 (2005)
Manyika, J., et al.: Big data: The next frontier for innovation, competition and productivity. McKinsey Global Institute (May 2011)
MasterNaut. Green Solutions, http://www.masternaut.co.uk/carbon-calculator/
NAVTEQ, www.navteq.com
New York Times. Justices Say GPS Tracker Violated Privacy Rights (2011), http://www.nytimes.com/2012/01/24/us/police-use-of-gps-is-ruled-unconstitutional.html
OpenStreetMap, http://www.openstreetmap.org/
Potamias, M., Bonchi, F., Castillo, C., Gionis, A.: Fast shortest path distance estimation in large networks. In: Proceedings of the 18th ACM Conference on Information and Knowledge Management, CIKM 2009, pp. 867–876 (2009)
Pothole Info. Citizen pothole reporting via phone apps take off, but can street maintenance departments keep up? (2011), http://goo.gl/cGl3B
Ray, S., Simion, B., Brown, A.D.: Jackpine: A benchmark to evaluate spatial database performance. In: 2011 IEEE 27th International Conference on Data Engineering (ICDE), pp. 1139–1150. IEEE (2011)
SafeRoadMaps. Envisioning Safer Roads, http://saferoadmaps.org/
Samet, H., Sankaranarayanan, J., Alborzi, H.: Scalable network distance browsing in spatial databases. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, pp. 43–54 (2008)
Sanders, P., Schultes, D.: Engineering fast route planning algorithms. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol. 4525, pp. 23–36. Springer, Heidelberg (2007)
Sankaranarayanan, J., Samet, H.: Query processing using distance oracles for spatial networks. IEEE Transactions on Knowledge and Data Engineering 22(8), 1158–1175 (2010)
Schiller, J., Voisard, A.: Location-based services. Morgan Kaufmann (2004)
Shekhar, S., Evans, M.R., Kang, J.M., Mohan, P.: Identifying patterns in spatial information: A survey of methods. Wiley Interdisc. Rew.: Data Mining and Knowledge Discovery 1(3), 193–214 (2011)
Shekhar, S., Fetterer, A., Goyal, B.: Materialization trade-offs in hierarchical shortest path algorithms. In: Scholl, M., Voisard, A. (eds.) SSD 1997. LNCS, vol. 1262, pp. 94–111. Springer, Heidelberg (1997)
Shekhar, S., Kohli, A., Coyle, M.: Path computation algorithms for advanced traveller information system (atis). In: Proceedings of the Ninth International Conference on Data Engineering, Vienna, Austria, April 19-23, pp. 31–39. IEEE Computer Society (1993)
Shekhar, S., Vatsavai, R.R., Ma, X., Yoo, J.S.: Navigation systems: A spatial database perspective. In: Location-Based Services, pp. 41–82. Morgan Kaufmann (2004)
Shekhar, S., Xiong, H.: Encyclopedia of GIS. Springer Publishing Company, Incorporated (2007)
Shrank, D., Lomax, T., Eisele, B.: The 2011 urban mobility report. Texas Transportation Institute (2011)
Sperling, D., Gordon, D.: Two billion cars. Oxford University Press (2009)
Stonebraker, M., Frew, J., Gardels, K., Meredith, J.: The sequoia 2000 storage benchmark. ACM SIGMOD Record 22, 2–11 (1993)
TeleNav, http://www.telenav.com/
TeloGIS, http://www.telogis.com/
Tomlin, C.D.: Geographic information systems and cartographic modeling. Prentice Hall (1990)
TomTom. TomTom GPS Navigation (2011), http://www.tomtom.com/
U.S. Energy Information Adminstration. Monthly Energy Review (June 2011), http://www.eia.gov/totalenergy/data/monthly/
Ushahidi, http://www.ushahidi.com
Waze Mobile, http://www.waze.com/
Wikipedia. Usage-based insurance — wikipedia, the free encyclopedia (2011), http://goo.gl/NqJE5 (accessed December 15, 2011)
Zhou, C., Frankowski, D., Ludford, P., Shekhar, S., Terveen, L.: Discovering personal gazetteers: an interactive clustering approach. In: Proceedings of the 12th Annual ACM International Workshop on Geographic Information Systems, pp. 266–273. ACM (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shekhar, S., Evans, M.R., Gunturi, V., Yang, K., Cugler, D.C. (2014). Benchmarking Spatial Big Data. In: Rabl, T., Poess, M., Baru, C., Jacobsen, HA. (eds) Specifying Big Data Benchmarks. WBDB WBDB 2012 2012. Lecture Notes in Computer Science, vol 8163. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-53974-9_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-53974-9_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-53973-2
Online ISBN: 978-3-642-53974-9
eBook Packages: Computer ScienceComputer Science (R0)