# Algorithm for discarding geographically disgregate points

The context: I'm working on geocoded documents. This is, documents have latitude and longitude attributes, as well as some other geo attributes such as an address. Right now, I'm performing text search operations on the indexed docs and showing their geolocation on a map.

The problem: Most of search criterias include a location expressed by a name. But this name may appear in the document in fields other than those that express location. This usally gives irrelevan results on the map. In other cases, a doc within a resultset may be wrongly geocoded. I both cases, the consequence is that the map appears with some relevant results geographically grouped and a few irrelevant results scattered far away.

The required solution: I'm stuck trying to find an algorithm that processes the latitude/longitude of each doc in the results to determine which points are grouped and discard those that are not grouped.

-
by the way, discard calculating a weight based on the distance from each point to the rest of the points. The algorithm requires quick response and for results with 800 docs/points... this kind of solution can take too long – Daniel Cerecedo Dec 1 '10 at 22:11
Have looked at Cluster Analysis of graphs? en.wikipedia.org/wiki/Cluster_analysis – Timothy Wagner Dec 1 '10 at 22:55
I learned a new word by reading the title of this question. – Pete L. Clark Dec 2 '10 at 16:34
Clearly a clustering problem. Try this survey. – Emre May 2 '11 at 20:50

You can look, for each point, at the maximum distance among the $k$ nearest neighbors, and throw the point away if the maximum is too big (perhaps, relative to some average score on the specific map). You can determine $k$ by hand.

By the way, these points are known as outliers.

-

It sounds like you are marking all the pizza joints in an area on Google maps, or something similar. More like a programming problem than a math problem. I have two notions.

First, look under the covers of a Hash Table for ideas. Not my field, but I believe they have ways to group a set in one pass.

Or, second, use a statistical sampling approach. Find the median and quartiles of the lat/long of a subset and make your decisions based on that. A little research plus some experimentation will give an idea about how big the subset has to be.

-