Density-based co-location pattern discovery
Described is using density to efficiently mine co-location patterns, such as closely located businesses frequently found together in business listing databases, geographic search logs, and/or GPS-based data. A data space of such information is geographically partitioned into a grid of cells, with dense cells scanned first. A dynamic upper bound of prevalence measure of co-location patterns is maintained during the scanning process. If the current upper bound is smaller than a threshold, the scanning is stopped, thereby significantly reducing the computation cost for processing many cells, while providing suitable results.
1. A method of mining co-location patterns, the method comprising:
partitioning, by a computer, a set of spatial data into a grid of cells, wherein the spatial data comprises a plurality of instances of a plurality of classes, and wherein the grid represents a non-uniform distribution of the instances in geographic space, and wherein any cell of the grid is a neighboring cell to itself and to any other cell of the grid given a common side or a common vertex; and
processing the cells of the grid in a dense space first order where a cell that comprises more of the spatial data is processed before a cell that comprises less of the spatial data, wherein the processing comprises:
initializing, by the computer, k≧2, where k is a variable, and
step 1 : generating, by the computer and in response to the partitioning and the initializing, size k candidate patterns C k based on size k- 1 patterns P k-1 .
2. The method of claim 1 , the processing further comprising step 2 : generating, in response to step 1 , instance-cell-sets R k of the size k candidate patterns C k based on the size k candidate patterns C k and instance-cell-sets of size k- 1 patterns R k-1 .
3. The method of claim 2 , the processing further comprising step 3 : generating, in response to step 2 , instances of each size k candidate cl of the size k candidate patterns C k in the dense space first order.
4. The method of claim 3 , the processing further comprising:
incrementing, in response to step 3 , k by one, and
repeating, in response to the incrementing, step 1 and then step 2 and then step 3 until a number of size k patterns in P k is one, where P k is a set of size k co-location patterns, at which point the processing stops.
5. The method of claim 1 , the processing further comprising pruning a false candidate pattern of the size k candidate patterns C k .
6. The method of claim 1 wherein each of the cells are of equal size.
7. The method of claim 1 wherein any two of the instances that are neighbors are located in neighboring cells.
8. At least one computer storage medium storing computer-executable instructions that, when executed by a computer, cause the computer to perform a method of mining co-location patterns, the method comprising:
partitioning a set of spatial data into a grid of cells, wherein the spatial data comprises and a plurality of instances of a plurality of classes, and wherein the grid represents a non-uniform distribution of the instances in geographic space, and wherein any cell of the grid is a neighboring cell to itself and to any other cell of the grid given a common side or a common vertex; and
processing the cells of the grid in a dense space first order where a cell that comprises more of the spatial data is processed before a cell that comprises less of the spatial data, wherein the processing comprises:
initializing k≧2, where k is a variable, and
step 1 : generating, in response to the partitioning and the initializing, size k candidate patterns C k based on size k- 1 patterns P k-1 .
9. The at least one computer storage medium of claim 8 , the processing further comprising step 2 : generating, in response to step 1 , instance-cell-sets R k of the size k candidate patterns C k based on the size k candidate patterns C k and instance-cell-sets of size k- 1 patterns R k-1 .
10. The at least one computer storage medium of claim 9 , the processing further comprising step 3 : generating, in response to step 2 , instances of each size k candidate cl of the size k candidate patterns C k in the dense space first order.
11. The at least one computer storage medium of claim 10 , the processing further comprising:
incrementing, in response to step 3 , k by one, and
repeating, in response to the incrementing, step 1 and then step 2 and then step 3 until a number of size k patterns in P k is one, where P k is a set of size k co-location patterns, at which point the processing stops.
12. The at least one computer storage medium of claim 8 , the processing further comprising pruning a false candidate pattern of the size k candidate patterns C k .
13. The at least one computer storage medium of claim 8 wherein each of the cells are of equal size.
14. The at least one computer storage medium of claim 8 wherein any two of the instances are that neighbors are located in neighboring cells.
15. A system comprising:
a computer;
a co-location pattern processing mechanism implemented by the computer and configured for partitioning a set of spatial data into a grid of cells, wherein the spatial data comprises and a plurality of instances of a plurality of classes, and wherein the grid represents a non-uniform distribution of the instances in geographic space, and wherein any cell of the grid is a neighboring cell to itself and to any other cell of the grid given a common side or a common vertex; and
the co-location pattern processing mechanism further configured for processing the cells of the grid in a dense space first order where a cell that comprises more of the spatial data is processed before a cell that comprises less of the spatial data, wherein the processing comprises:
initializing k≧2, where k is a variable, and
step 1 : generating, in response to the partitioning and the initializing, size k candidate patterns C k based on size k- 1 patterns P k-1 .
16. The system of claim 15 , the processing further comprising performing step 2 : generating, in response to step 1 , instance-cell-sets R k of the size k candidate patterns C k based on the size k candidate patterns C k and instance-cell-sets of size k- 1 patterns R k-1 .
17. The system of claim 16 , the processing further comprising performing step 3 : generating, in response to step 2 , instances of each size k candidate cl of the size k candidate patterns C k in the dense space first order.
18. The system of claim 17 , the processing further comprising:
incrementing, in response to step 3 , k by one and
repeating, in response to the incrementing, step 1 and then step 2 and then step 3 until a number of size k patterns in P k is one, where P k is a set of size k co-location patterns, at which point the processing stops.
19. The system of claim 15 , the processing further comprising for pruning a false candidate pattern of the size k candidate patterns C k .
20. The system of claim 15 wherein any two of the instances that are neighbors are located in neighboring cells.