Abstract
A high utility co-location pattern (HUCP) is a set of spatial features, which is supported by groups of neighboring spatial instances, and the pattern utility ratios (PUR) of the spatial feature set are greater than a minimal utility threshold assigned by users, can reveal hidden relationships between spatial features in spatial datasets, is one of the most important branches of spatial data mining. The current algorithm for mining HUCPs adopts a level-wise search style. That is, it first generates candidates, then tests these candidates, and finally determines whether the candidates are HUCPs. It performs mining from the smallest size candidate and gradually expands until no more candidates are generated. However, in mining HUCPs, the UPR measurement scale does not hold the downward-closure property. If the level-wise search style is adopted, unnecessary candidates cannot be effectively pruned in advance, and the mining efficiency is extremely low, especially in large-scale and dense spatial datasets. To overcome this, this paper proposes a mining algorithm based on a query strategy. First, the neighboring spatial instances are obtained by enumerating maximal cliques, and then these maximal cliques are stored in a hash map structure. Neighboring spatial instances that support candidates can be quickly queried from the hash structure. Finally, the UPR of the candidate is calculated and a decision is made on it. A series of experiments are implemented on both synthetic and real datasets. Experimental results show that the proposed algorithm gives better mining performance than existing algorithms.
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
Similar content being viewed by others
Notes
References
Andrzejewski, W., Boinski, P.: Parallel GPU-based plane-sweep algorithm for construction of ICPI-trees. J. Database Manag. (JDM) 26(3), 1–20 (2015)
Bao, X., Wang, L.: A clique-based approach for co-location pattern mining. Inf. Sci. 490, 244–264 (2019)
Cheng, J., Ke, Y., Fu, A.W.C., Yu, J.X., Zhu, L.: Finding maximal cliques in massive networks. ACM Trans. Database Syst. (TODS) 36(4), 1–34 (2011)
Deng, M., Cai, J., Liu, Q., He, Z., Tang, J.: Multi-level method for discovery of regional co-location patterns. Int. J. Geogr. Inf. Sci. 31(9), 1846–1870 (2017)
Eppstein, D., Löffler, M., Strash, D.: Listing all maximal cliques in large sparse real-world graphs. J. Exp. Algorithmics (JEA) 18, 3-1 (2013)
He, Z., Deng, M., Xie, Z., Wu, L., Chen, Z., Pei, T.: Discovering the joint influence of urban facilities on crime occurrence using spatial co-location pattern mining. Cities 99, 102612 (2020)
Li, Y., Wang, L., Yang, P., Li, J.: EHUCM: an efficient algorithm for mining high utility co-location patterns from spatial datasets with feature-specific utilities. In: Strauss, C., Kotsis, G., Tjoa, A.M., Khalil, I. (eds.) DEXA 2021. LNCS, vol. 12923, pp. 185–191. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-86472-9_17
Liu, W., Liu, Q., Deng, M., Cai, J., Yang, J.: Discovery of statistically significant regional co-location patterns on urban road networks. Int. J. Geogr. Inf. Sci. 36(4), 749–772 (2022)
Shu, J., Wang, L., Yang, P., Tran, V.: Mining the potential relationships between cancer cases and industrial pollution based on high-influence ordered-pair patterns. In: Chen, W., Yao, L., Cai, T., Pan, S., Shen, T., Li, X. (eds.) ADMA 2022. LNCS, vol. 13725, pp. 27–40. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22064-7_3
Tran, V.: Meta-PCP: a concise representation of prevalent co-location patterns discovered from spatial data. Expert Syst. Appl. 213, 119255 (2023)
Tran, V., Wang, L., Chen, H., Xiao, Q.: MCHT: a maximal clique and hash table-based maximal prevalent co-location pattern mining algorithm. Expert Syst. Appl. 175, 114830 (2021)
Wu, Q., Hao, J.K.: A review on algorithms for maximum clique problems. Eur. J. Oper. Res. 242(3), 693–709 (2015)
Yang, S., Wang, L., Bao, X., Lu, J.: A framework for mining spatial high utility co-location patterns. In: 2015 12th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD), pp. 595–601. IEEE (2015)
Yoo, J.S., Shekhar, S.: A joinless approach for mining spatial colocation patterns. IEEE Trans. Knowl. Data Eng. 18(10), 1323–1337 (2006)
Yu, T., Liu, M.: A linear time algorithm for maximal clique enumeration in large sparse graphs. Inf. Process. Lett. 125, 35–40 (2017)
Acknowledgements
This work is supported by the National Natural Science Foundation of China (62276227, 61966036), the Project of Innovative Research Team of Yunnan Province (2018HC019), the Yunnan Fundamental Research Projects (202201AS070015), and Yunnan University of Finance and Economics Scientific Research Fund (2022B03).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Tran, V., Wang, L., Zhang, J., Do, T. (2023). Efficient Mining of High Utility Co-location Patterns Based on a Query Strategy. In: Yang, X., et al. Advanced Data Mining and Applications. ADMA 2023. Lecture Notes in Computer Science(), vol 14176. Springer, Cham. https://doi.org/10.1007/978-3-031-46661-8_27
Download citation
DOI: https://doi.org/10.1007/978-3-031-46661-8_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-46660-1
Online ISBN: 978-3-031-46661-8
eBook Packages: Computer ScienceComputer Science (R0)