# Longest common prefix of geohashed points

I currently use Geohash to index some points and retrieve information faster by providing a geohash prefix for a given point for a given distance..

For example if I get a given point at '1600 Pennsylvania Ave, Washington, DC' with geohash dqcjqcpsr4t0 and I get all point that geohash starts with dqcjqc.

I would like to know if there is an algorithm and index solution to get the points ordered by the longest common segment without iterating through them all.

For example: I got a given point at '1600 Pennsylvania Ave, Washington, DC' with geohash dqcjqcpsr4t0 and I would like to get the nearest point first:

• point with geohash dqcjqfzg038b will be returned first (common prefix 'dqcjq'=>5 letters)
• point with geohash dqcjz4p344cu will be returned next (common prefix 'dqcj'=>4 letters)

The idea behind this is to get the nearest points first by providing the full (8 chars) geohash of a given point (in this case we don't use geohash to get points for a given box)

• How are you storing them? If you build some kind of tree structure (or perhaps even a simple ordered list), then the answer will vary from "full table scan", but the exact answer will probably depend on the exact structure. Commented Jan 22, 2014 at 8:46

You can measure similarity of strings using i.e. edit distance or Levenshtein distance or Jaro/Winkler distance. All are implemented in R in many packages (stringdist, RecordLinkage)

In case you are interested only in match of first n characters, I suggest programming your own function (in R, it would be).

``````matchStrings <- function(string1, string2){
split1 <- unlist(strsplit(string1,''))
split2 <- unlist(strsplit(string2,''))
match <- 0
for (i in 1:8){ # in case you are interested only in first 8 characters
if (split1[i]==split2[i]){match = match+1} else {break}
}
return(match)
}

matchStrings("abcdef134", 'abcdff134')
[1] 4
``````

To the second part: I think you have to iterate through all values (geohashes) to get the similarity and then you can sort them according to the similarity.