Top-k probabilistic prevalent co-location mining in spatially uncertain data sets

Abstract

A co-location pattern is a set of spatial features whose instances frequently appear in a spatial neighborhood. This paper efficiently mines the top-k probabilistic prevalent co-locations over spatially uncertain data sets and makes the following contributions: 1) the concept of the top-k probabilistic prevalent co-locations based on a possible world model is defined; 2) a framework for discovering the top-k probabilistic prevalent co-locations is set up; 3) a matrix method is proposed to improve the computation of the prevalence probability of a top-k candidate, and two pruning rules of the matrix block are given to accelerate the search for exact solutions; 4) a polynomial matrix is developed to further speed up the top-k candidate refinement process; 5) an approximate algorithm with compensation factor is introduced so that relatively large quantity of data can be processed quickly. The efficiency of our proposed algorithms as well as the accuracy of the approximation algorithms is evaluated with an extensive set of experiments using both synthetic and real uncertain data sets.

Keywords

spatial co-location mining / top-k probabilistic prevalent co-location mining / spatially uncertain data sets / matrix methods

References

[1] Huang Y, Shekhar S, Xiong H. Discovering co-location patterns from spatial data sets: a general approach. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(12): 1472–1485

[2] Yoo J S, Shekhar S, Smith J, Kumquat J P. A partial join approach for mining co-location patterns. In: Proceedings of the 12th ACM International Workshop on Geographic Information Systems. 2004, 241–249

[3] Yoo J S, Shekhar S. A joinless approach for mining spatial colocation patterns. IEEE Transactions on Knowledge and Data Engineering. 2006, 18(10): 1323–1337

[4] Wang L Z, Bao Y Z, Lu J, Yip J. A new join-less approach for colocation pattern mining, In: Proceedings of the 8th IEEE International Conference on Computer and Information Technology. 2008, 197–202

[5] Wang L Z, Zhou L, Lu J, Yip J. An order-clique-based approach for mining Maximal co-locations. Information Sciences, 2009, 179(19): 3370–3382

[6] Xiao X Y, Xie X, Luo Q, Ma W Y. Density based co-location pattern discovery. In: Proceedings of the 16th ACM International Conference on Advances in Geographic Information Systems. 2008, 11–20

[7] Celik M, Kang J M, Shekhar S. Zonal co-location pattern discovery with dynamic parameters. In: Proceedings of the 7th IEEE International Conference on Data Mining. 2007, 433–438

[8] Mohan P, Shekhar S, Shine J A, Rogers J P, Jiang Z, Wayant N. A neighborhood graph based approach to regional co-location pattern discovery: a summary of results. In: Proceedings of the 19th ACM International Conference on Advances in Geographic Information Systems. 2011, 122–131

[9] Sengstock C, Gertz M, Canh T V. Spatial interestingness measures for co-location pattern mining. In: Proceedings of the 12th IEEE International Conference on Data Mining. 2012, 821–826

[10] Huang Y, Pei J, Xiong H. Mining co-location patterns with rare events from spatial data sets. GeoInformatica, 2006, 10(3): 239–260

[11] Feng L,Wang L Z, Gao S J. A new approach of mining co-location patterns in spatial datasets with rare feature. Journal of Nanjing University (Natural Sciences), 2012, 48(1): 99–107

[12] Ouyang Z P, Wang L Z, Chen H M. Mining spatial co-location patterns for fuzzy objects. Jisuanji Xuebao (Chinese Journal of Computers), 2011, 34(10): 1947–1955

[13] Liu Z, Huang Y. Mining co-locations under uncertainty. In: Proceedings of International Symposium on Spatial and Temporal Databases. 2013, 429–446

[14] Lu Y,Wang L, Zhang X. Mining frequent co-location patterns from uncertain data. Journal of Frontiers of Computer Science and Technology, 2009, 3(6): 656–664

[15] Wang L Z, Wu P P, Chen H M. Finding probabilistic prevalent colocations in spatially uncertain data sets. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(4): 790–804

[16] Yi K, Li F F, Kollios G, Srivastava D. Efficient processing of top-k queries in uncertain databases with x-relations. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(12): 1669–1682

[17] Beskales G, Soliman M A, Ilyas I F. Efficient search for the top-k probable nearest neighbors in uncertain databases. In: Proceedings of International Conference on Very Large Data Bases. 2008, 326–339

[18] Hua M, Pei J, Zhang W J, Lin X M. Ranking queries on uncertain data: a probabilistic threshold approach. In: Proceedings of the 2008 ACM International Conference on Management of Data. 2008, 673–686

[19] Liu X J, Ye M, Xu J L, Tian Y, Lee W C. K-selection query over uncertain data. In: Proceedings of International Conference on Database Systems for Advanced Applications. 2010, 444–459

[20] Pietracaprina A, Riondato M, Upfla E, Vandin F. Mining top-k frequent itemsets through progressive sampling. Data Mining and Knowledge Discovery, 2010, 21(2): 310–326

[21] Wu C W, Shie B E, Tseng V S, Yu P S. Mining top-k high utility itemsets. In: Proceedings of the 18th ACM International Conference on Knowledge Discovery and Data Mining. 2012, 78–86

[22] Zhu F D, Qu Q, Lo D, Yan X F, Han J W, Yu P S. Mining top-k large structural patterns in a massive network. Proceedings of the VLDB Endowment, 2011, 4(11): 807–818

[23] Bartolini I, Ciaccia P, Patella M. Getting the best from uncertain data: the correlated case. In: Proceedings of the 20th Italian Symposium on Advanced Database Systems. 2012, 43–50

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg