1

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)

1
  • 1
    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.
    – BradHards
    Jan 22 '14 at 8:46
2

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.