Abstract
A novel algorithm is presented for discovering areas having locally maximized confidence of an association rule on a collection of location data. Although location data obtained from GPS-equipped devices have promising applications, those GPS points are usually not uniformly distributed in two-dimensional space. As a result, substantial insights might be missed by using data mining algorithms that discover admissible or rectangular areas under the assumption that the GPS data points are distributed uniformly. The proposed algorithm composes transitively connected groups of irregular meshes that have locally maximized confidence. There is thus no need to assume the uniformity, which enables the discovery of areas not limited to a certain class of shapes. Iterative removal of the meshes in accordance with the local maximum property enables the algorithm to perform 50 times faster than state-of-the-art ones.
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
de Berg, M., Chong, O., van Kreveld, M., Overmars, M.: Computational Geometry - Algorithms and Applications, 3rd edn. Springer (2008)
Derekenaris, G., Garofalakis, J., Makris, C., Prentzas, J., Sioutas, S., Tsakalidis, A.: Integrating GIS, GPS and GSM Technologies for the Effective Management of Ambulances. Computers, Environment and Urban Systems 25(3), 267–278 (2001)
Dobkin, D.: Computing the Maximum Bichromatic Discrepancy, with Applications to Computer Graphics and Machine Learning. Journal of Computer and System Sciences 52(3), 453–470 (1996)
Fukuda, T., Morimoto, Y., Morishita, S., Tokuyama, T.: Data Mining with Optimized Two-Dimensional Association Rules. ACM Transactions on Database Systems 26(2), 179–213 (2001)
Fukuda, T., Morimoto, Y., Morishita, S., Tokuyama, T.: Mining Optimized Association Rules for Numeric Attributes. Journal of Computer and System Sciences 58(1), 1–12 (1999)
Giannotti, F., Nanni, M., Pinelli, F., Pedreschi, D.: Trajectory Pattern Mining. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2007, pp. 330–339. ACM Press, New York (2007)
Mamei, M., Rosi, A., Zambonelli, F.: Automatic Analysis of Geotagged Photos for Intelligent Tourist Services. In: 2010 Sixth International Conference on Intelligent Environments, pp. 146–151. IEEE (2010)
Panahi, S., Delavar, M.R.: Dynamic Shortest Path in Ambulance Routing Based on GIS. International Journal of Geoinformatics 5(1), 13–19 (2009)
Rastogi, R., Shim, K.: Mining Optimized Association Rules with Categorical and Numeric Attributes. IEEE Transactions on Knowledge and Data Engineering 14(1), 29–50 (2002)
Teerayut, H., Witayangkurn, A., Shibasaki, R.: The Challenge of Geospatial Big Data Analysis. In: Open Source Geospatial Research & Education Symposium (2012)
Yoshida, D., Song, X., Raghavan, V.: Development of Track Log and Point of Interest Management System Using Free and Open Source Software. Applied Geomatics 2(3), 123–135 (2010)
Zheng, V.W., Zheng, Y., Xie, X., Yang, Q.: Collaborative Location and Activity Recommendations with GPS History Data. In: Proceedings of the 19th International Conference on World Wide Web - WWW 2010, pp. 1029–1038. ACM Press, New York (2010)
Zheng, Y., Zhang, L., Xie, X., Ma, W.Y.: Mining Interesting Locations and Travel Sequences from GPS Trajectories. In: Proceedings of the 18th International Conference on World Wide Web, WWW 2009, pp. 791–800. ACM Press, New York (2009)
Zheng, Y., Zhou, X. (eds.): Computing with Spatial Trajectories. Springer (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Inakoshi, H., Morikawa, H., Asai, T., Yugami, N., Okamoto, S. (2014). Discovery of Areas with Locally Maximal Confidence from Location Data. In: Bhowmick, S.S., Dyreson, C.E., Jensen, C.S., Lee, M.L., Muliantara, A., Thalheim, B. (eds) Database Systems for Advanced Applications. DASFAA 2014. Lecture Notes in Computer Science, vol 8421. Springer, Cham. https://doi.org/10.1007/978-3-319-05810-8_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-05810-8_4
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-05809-2
Online ISBN: 978-3-319-05810-8
eBook Packages: Computer ScienceComputer Science (R0)