High quantitative pattern searching using spatial indexing

Abstract

A computer searching technique identifies high quantitative patterns in data. A spatial indexing technique, such as an R-tree is used to represent the data. Then a pattern searching algorithm is used to identify anchor points that define the componentwise minimum patterns. High quantitative patterns are found responsive to the componentwise minimum patterns. The search strategy is demonstrated relevant to the problem of finding suitable locations for a retail business with reference to environments of prior successful retail businesses.

The invention claimed is: 
     
       1. A computer searching method, comprising carrying out operations in at least one data processing device, the operations comprising:
 applying a spatial indexing structure to a data set of quantitative patterns defined as vectors in a p-dimensional space; 
 specifying a frequency K, wherein 1≦K≦N, where N is a number of quantitative patterns,
 identifying at least one componentwise minimum pattern corresponding to the frequency K; and 
 outputting the at least one componentwise minimum pattern corresponding to the frequency and outputting quantitative patterns corresponding to said componentwise minimum pattern that satisfies a critical mass requirement defined by the componentwise minimum pattern at the frequency, said applying comprising creating an Minimum Bounding Rectangle (MBR) representation of the data set; and said identifying comprises:
 iterating through the MBR's; 
 pruning the MBR's responsive to a spatial frequency measurement; 
 deriving anchor points responsive to the spatial frequency measurement; and 
 providing the at least one componentwise minimum pattern responsive to the anchor points, 
 
 said outputting at least one componentwise minimum pattern comprising points on a top-right side of any component wise minimum pattern with frequency K, 
 the spatial frequency measurement comprising:
 selecting a lower left and upper right corner of each MBR; 
 counting a number of points in the data set above and to the right of each corner, the number being the spatial frequency measurement for that point; and 
 
 said deriving anchor points comprising:
 selecting using said specified frequency an anchor point responsive to the spatial frequency measurement of one of the corners equaling the frequency; and 
 pruning an MBR when one of its corners is selected as an anchor point; 
 pruning a given MBR when the spatial frequency measurement of the bottom left corner of the given MBR is less than the threshold; and 
 selecting a sub-rectangle within the MBR responsive to at least one pruning instance, wherein the at least one data processing device is programmed to perform said applying, said identifying and said outputting. 
 
 
 
     
     
       2. The method of  claim 1 , wherein the output identifies at least one portion of the data set that has a critical mass responsive to at least one search criterion. 
     
     
       3. The method of  claim 2 , wherein the search criterion seeks to locate suitable neighborhoods for establishing a business. 
     
     
       4. The method of  claim 1 , wherein each quantitative pattern in the pattern data set comprises data points relevant to prior fact instances and similar to at least one new fact instance corresponding to the search. 
     
     
       5. The method of  claim 4 , wherein the new fact instance is a type of business sought to be established and the quantitative pattern comprises instances of businesses neighboring prior instances of another business of that type. 
     
     
       6. The method of  claim 1 , wherein the spatial indexing structure is an R-tree. 
     
     
       7. The method of  claim 1 , comprising using a spatially based frequency measurement to identify componentwise minimum patterns. 
     
     
       8. The method of  claim 1 , wherein, for a p-dimensional hyperspace,
 considering point X (x 1 , x 2 , . . . , x p ), and point Y (y 1 , y 2 , . . . , y p ), where x i  are the i- th  axis value of point X and if x 1 <y 1 , x 2 <y 2 , . . . x p <y p , point X is considered to be on the left-bottom side of point Y, and if x 1 ≧y 1 , . . . x p ≧y p , X is considered to be on the right-top side of Y. 
 
     
     
       9. A computer program product for carrying out operations, the computer program product comprising:
 a tangible storage media, said storage media not a propagating signal, said storage media readable by a processing circuit and storing instructions to be run by the processing circuit for performing a method comprising: 
 applying a spatial indexing structure to a data set of quantitative patterns defined as vectors in a p-dimensional space; 
 specifying a frequency K, wherein 1≦K≦N, where N is a number of quantitative patterns, 
 identifying at least one componentwise minimum pattern corresponding to the frequency K; and 
 outputting the at least one componentwise minimum pattern corresponding to the frequency and outputting quantitative patterns corresponding to said componentwise minimum pattern that satisfies a critical mass requirement defined by the componentwise minimum pattern at the frequency, said applying comprising creating an Minimum Bounding Rectangle (MBR) representation of the data set; and said identifying comprises:
 iterating through the MBR's; 
 pruning the MBR's responsive to a spatial frequency measurement; 
 deriving anchor points responsive to the spatial frequency measurement; and 
 providing the at least one componentwise minimum pattern responsive to the anchor points, said outputting at least one componentwise minimum pattern comprising points on a top-right side of any component wise minimum pattern with frequency K, 
 
 the spatial frequency measurement comprising:
 selecting a lower left and upper right corner of each MBR; 
 counting a number of points in the data set above and to the right of each corner, the number being the spatial frequency measurement for that point; and 
 
 said deriving anchor points comprising:
 selecting using said specified frequency an anchor point responsive to the spatial frequency measurement of one of the corners equaling the frequency; and 
 pruning an MBR when one of its corners is selected as an anchor point; 
 pruning a given MBR when the spatial frequency measurement of the bottom left corner of the given MBR is less than the threshold; and 
 selecting a sub-rectangle within the MBR responsive to at least one pruning instance. 
 
 
     
     
       10. The computer program product of  claim 9 , wherein the pattern output identifies at least one portion of the data set that has a critical mass responsive to at least one search criterion. 
     
     
       11. The computer program product of  claim 10 , wherein the search criterion seeks to locate suitable neighborhoods for establishing a business. 
     
     
       12. The computer program product of  claim 9 , wherein each quantitative pattern in the pattern data set comprises data points relevant to prior fact instances and similar to at least one new fact instance corresponding to the search. 
     
     
       13. The computer program product of  claim 9 , wherein, for a p-dimensional hyperspace,
 considering point X (x 1 , x 2 , . . . , x p ), and point Y (y 1 , y 2 , . . . , y p ), where x i  are the i- th  axis value of point X and if x 1 <y 1 , x 2 <y 2 , . . . x p <y p , point X is considered to be on the left bottom side of point Y, and if x 1 ≧y 1 , . . . x p ≧y p , X is considered to be on the right-top side of Y. 
 
     
     
       14. A system comprising:
 at least one data processing device; 
 at least one tangible storage device readable by said data processing device, the device embodying data and/or computer program code for causing the data processing device to carry out operations, the operations comprising: 
 applying a spatial indexing structure to a data set of quantitative patterns defined as vectors in a p-dimensional space; 
 specifying a frequency K, wherein 1≦K≦N, where N is a number of quantitative patterns, 
 identifying at least one componentwise minimum pattern corresponding to the frequency K; and 
 outputting the at least one componentwise minimum pattern corresponding to the frequency and outputting quantitative patterns corresponding to said componentwise minimum pattern that satisfies a critical mass requirement defined by the componentwise minimum pattern at the frequency, said applying comprising creating an Minimum Bounding Rectangle (MBR) representation of the data set; and said identifying comprises:
 iterating through the MBR's; 
 pruning the MBR's responsive to a spatial frequency measurement; 
 deriving anchor points responsive to the spatial frequency measurement; and 
 providing the at least one componentwise minimum pattern responsive to the anchor points, said outputting at least one componentwise minimum pattern comprising points on a top-right side of any component wise minimum pattern with frequency K, 
 
 the spatial frequency measurement comprising:
 selecting a lower left and upper right corner of each MBR; 
 counting a number of points in the data set above and to the right of each corner, the number being the spatial frequency measurement for that point; and 
 
 said deriving anchor points comprising:
 selecting using said specified frequency an anchor point responsive to the spatial frequency measurement of one of the corners equaling the frequency; and 
 pruning an MBR when one of its corners is selected as an anchor point; 
 pruning a given MBR when the spatial frequency measurement of the bottom left corner of the given MBR is less than the threshold; and 
 selecting a sub-rectangle within the MBR responsive to at least one pruning instance, said at least one data processing device adapted to carry out the operations responsive to the medium. 
 
 
     
     
       15. The system of  claim 14 , wherein the pattern output identifies at least one portion of the data set that has a critical mass responsive to at least one search criterion. 
     
     
       16. The system of  claim 15 , wherein the search criterion seeks to locate suitable neighborhoods for establishing a business. 
     
     
       17. The system of  claim 14 , wherein each quantitative pattern in the pattern data set comprises data points relevant to prior fact instances and similar to at least one new fact instance corresponding to the search.