Abstract
With the advent of the mobile era in the last decade and the evolution of the app economy in smartphones and other smart devices, there is an abundance of location data available. Traditional spatial analysis techniques are locked away in databases (such as DB2 Spatial, ESRI ArcGIS server, Oracle Spatial and Graph) that only enable basic analytics and do not scale very well to societal scale data. Moreover, these approaches tend to deal with only static objects, where time is not treated as a first class citizen. This paper introduces the idea of discretizing space-time as a first order primitive to significantly alter downstream algorithms ranging from simple spatial indexing to complex deep learning that operate on such space-time data. We coin the term space time box (STB) and propose this as a fundamental primitive of thinking about trajectories of moving objects. We substantiate and validate the concept of STB through various pieces of our past work. Finally, we show that 3D STBs can be used for efficiently tracking very fast moving objects (asteroids), which was never before been done.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bency, A.J., Rallapalli, S., Ganti, R.K, Srivatsa, M., Manjunath, B.S.: Beyond spatial auto-regressive models: predicting housing prices with satellite imagery. In: IEEE Winter Conference on Applications of Computer Vision (WACV), Santa Rosa, 24–31 March 2017. IEEE (2017). https://doi.org/10.1109/WACV.2017.42
Dubin, R., Pace, K., Thibodeau, T.: Spatial autoregression techniques for real estate data. J. Real Estate Lit. 7(1), 79–95 (1999)
Eubank, S., Guclu, H., Kumar, V., Marathe, M., Srinivasan, A., Toroczkai, Z., Wang, N.: Modelling disease outbreaks in realistic urban social networks. Nature 429(6988), 180–184 (2004)
Ganti, R., Srivatsa, M., Agrawal, D., Zerfos, P., Ortiz, J.: Mp-trie: fast spatial queries on moving objects. In: Proceedings of the Industrial Track of the 17th International Middleware Conference, Trento, 12–16 Dec 2016. https://doi.org/10.1145/3007646.3007653
Gonzalez, M., Hidalgo, C., Barbasi, A.-L.: Understanding individual human mobility patterns. Nature 453, 779–782 (2008)
Granvik, M., Virtanen, J., Oszkiewicz, D., Muinonen, K.: Openorb: Open-source asteroid orbit computation software including statistical ranging. Meteorit. Planet. Sci. 44(12), 1853–1861 (2009)
Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: Proceedings of ACM management of data (SIGMOD), Boston, 18–21 June 1984
Han, J., Kamber, M., Tung, A.K.H.: Spatial clustering methods in data mining: a survey. In: Miller, H.J., Han, J. (eds.) Geographic Data Mining and Knowledge Discovery, Research Monographs in GIS. Taylor and Francis (2001)
Kitamura, R., Chen, C., Pendyala, R., Narayanan, R.: Micro-simulation of daily activity-travel patterns for travel demand forecasting. Transportation 27(1), 25–51 (2000)
Lee, K., Ganti, R.K., Srivatsa, M., Liu, L.: Efficient spatial query processing for big data. In: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Dallas, 4–7 Nov 2014. https://doi.org/10.1145/2666310.2666481
Lee, D., Moussalli, R., Asaad, S., Srivatsa, M.: Spatial predicates evaluation in the geohash domain using reconfigurable hardware. In: IEEE 24th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), Washington, 1–3 May 2016. IEEE (2016). https://doi.org/10.1109/FCCM.2016.51
Li, S., Hu, S., Ganti, R., Srivatsa, M., Abdelzaher, T.: Pyro: a spatial-temporal big-data storage system. In: USENIX Annual Technical Conference, Santa Clara, 8–10 July 2015
Li, S., Amin, M.T., Ganti, R., Srivatsa, M., Hu, S., Zhao, Y., Abdelzaher, T.: Stark: Optimizing in-memory computing for dynamic dataset collections. In: IEEE 37th International Conference on Distributed Computing Systems (ICDCS), Atlanta, 5–8 June 2017. IEEE (2017). https://doi.org/10.1109/ICDCS.2017.143
Lilly, E., Jonas, J., Srivatsa, M., Ganti, R., Agrawal, D., Denneau, L., Kratky, M., Wainscoat, R.J.: Predicting close encounters between asteroids with the STB software. In: AAS/Division for Planetary Sciences Meeting Abstracts #47, vol. 47. American Astronomical Society (2015)
Morrison, D.: Patricia—practical algorithm to retrieve information coded in alphanumeric. J. ACM 15(4), 514–534 (1968)
Moussalli, R., Srivatsa, M., Assad, S.: Fast and flexible conversion of geohash codes to and from latitude/longitude coordinates. In: IEEE 23rd Annual International Symposium on Field-Programmable Custom Computing Machines, Vancouver, 2–6 May 2015. IEEE (2015). https://doi.org/10.1109/FCCM.2015.18
Niemeyer, G.: Geohash. http://en.wikipedia.org/wiki/Geohash (2008)
Nishimura, S., Das, S., Agrawal, D., Abbadi, A.E.: Md-hbase: A scalable multi-dimensional data infrastructure for location aware services. In: IEEE 12th International Conference on Mobile Data Management, Lulea, 6–9 June 2011. IEEE (2011). https://doi.org/10.1109/MDM.2011.41
Šidlauskas, D., Šaltenis, D., Christiansen, C.W., Johansen, J.M., Šaulys, D.: Trees or grids?: indexing moving objects in main memory. In: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, 4–6 Nov 2009, pp. 236–245. https://doi.org/10.1145/1653771.1653805
Srivatsa, M., Ganti, R., Mohapatra, P.: On the limits of subsampling of location traces. In: IEEE 37th International Conference on Distributed Computing Systems (ICDCS), Atlanta, 5–8 June 2017. IEEE (2017). https://doi.org/10.1109/ICDCS.2017.82
Acknowledgements
The authors would like to acknowledge all the co-authors of the previous body of work that utilized STBs and the derivative concepts, Sameh Asaad, Archit Bency, Manjunanth B. S., Larry Denneau, Dajung Lee, Kisung Lee, Eva Lilly-Schunova, Shen Li, Ling Liu, Roger Moussalli, Jorge Ortiz, Swati Rallapalli, and Petros Zerfos.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Agrawal, D., Ganti, R., Jonas, J. et al. STB: space time boxes. CCF Trans. Pervasive Comp. Interact. 1, 114–124 (2019). https://doi.org/10.1007/s42486-019-00006-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s42486-019-00006-1