In this paper, we study two spatial knowledge discovery problems involving proximity
relationships between clusters and features. The first problem is: Given a cluster of points,
how can we efficiently find features (represented as polygons) that are closest to the
majority of points in the cluster? We measure proximity in an aggregate sense due to the
non-uniform distribution of points in a cluster (e.g., houses on a map), and the different
shapes and sizes of features (e.g., natural or man-made geographic features). The second
problem is: Given n clusters of points, how can we extract the aggregate proximity
commonalities (i.e., features) that apply to most, if not all, of the n clusters? Regarding
the first problem, the main contribution of the paper is the development of Algorithm CRH
which uses geometric approximations (i.e., circles, rectangles, and convex hulls) to filter
and select features. Highly scalable and incremental, Algorithm CRH can examine over 50,000
features and their spatial relationships with a given cluster in approximately one second of
CPU time. Regarding the second problem, the key contribution is the development of
Algorithm GenCom that makes use of concept generalization to effectively derive many
meaningful commonalities that cannot be found otherwise.