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.
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
