{"action":"created","issue":{"url":"https://api.github.com/repos/ngageoint/hootenanny/issues/590","repository_url":"https://api.github.com/repos/ngageoint/hootenanny","labels_url":"https://api.github.com/repos/ngageoint/hootenanny/issues/590/labels{/name}","comments_url":"https://api.github.com/repos/ngageoint/hootenanny/issues/590/comments","events_url":"https://api.github.com/repos/ngageoint/hootenanny/issues/590/events","html_url":"https://github.com/ngageoint/hootenanny/issues/590","id":147770744,"number":590,"title":"Question:  Hoot road matching ","user":{"login":"ScottJohnson2718","id":2849375,"avatar_url":"https://avatars.githubusercontent.com/u/2849375?v=3","gravatar_id":"","url":"https://api.github.com/users/ScottJohnson2718","html_url":"https://github.com/ScottJohnson2718","followers_url":"https://api.github.com/users/ScottJohnson2718/followers","following_url":"https://api.github.com/users/ScottJohnson2718/following{/other_user}","gists_url":"https://api.github.com/users/ScottJohnson2718/gists{/gist_id}","starred_url":"https://api.github.com/users/ScottJohnson2718/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ScottJohnson2718/subscriptions","organizations_url":"https://api.github.com/users/ScottJohnson2718/orgs","repos_url":"https://api.github.com/users/ScottJohnson2718/repos","events_url":"https://api.github.com/users/ScottJohnson2718/events{/privacy}","received_events_url":"https://api.github.com/users/ScottJohnson2718/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/ngageoint/hootenanny/labels/Category:%20Algorithms","name":"Category: Algorithms","color":"d4c5f9"},{"url":"https://api.github.com/repos/ngageoint/hootenanny/labels/Question","name":"Question","color":"d3d3d3"}],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":3,"created_at":"2016-04-12T14:33:12Z","updated_at":"2016-04-18T14:27:58Z","closed_at":"2016-04-18T13:09:31Z","body":"I'm trying to follow along how the matching algorithm works because it is a beautiful problem and Hoot is my only example.  The Algorithms document references\r\n\r\nLinna Li, M. F. (2011). An optimisation model for linear feature matching in geographical data conflation.  International Journal of Image and Data Fusion , 2:4, 309-328\r\n\r\nThat paper specifies how the matching is formulated into an optimization problem that uses Hausdorff distance of matching pairs as the objective function.  The paper uses the GNU Linear Programming Kit but the only optimization I can find in Hoot code is the Nelder-Mead algorithm.  \r\n\r\nHow close is Hoot's implementation to the reference paper?  The paper claims 97% match rate on real data.  Did you find otherwise and select another method?  \r\n\r\nI'm part of a team to select a conflation solution and I think my co-workers are undervaluing the matching going on in Hoot.  But I must be sure.\r\n\r\nScott"},"comment":{"url":"https://api.github.com/repos/ngageoint/hootenanny/issues/comments/211403767","html_url":"https://github.com/ngageoint/hootenanny/issues/590#issuecomment-211403767","issue_url":"https://api.github.com/repos/ngageoint/hootenanny/issues/590","id":211403767,"user":{"login":"jasonsurratt","id":1638013,"avatar_url":"https://avatars.githubusercontent.com/u/1638013?v=3","gravatar_id":"","url":"https://api.github.com/users/jasonsurratt","html_url":"https://github.com/jasonsurratt","followers_url":"https://api.github.com/users/jasonsurratt/followers","following_url":"https://api.github.com/users/jasonsurratt/following{/other_user}","gists_url":"https://api.github.com/users/jasonsurratt/gists{/gist_id}","starred_url":"https://api.github.com/users/jasonsurratt/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jasonsurratt/subscriptions","organizations_url":"https://api.github.com/users/jasonsurratt/orgs","repos_url":"https://api.github.com/users/jasonsurratt/repos","events_url":"https://api.github.com/users/jasonsurratt/events{/privacy}","received_events_url":"https://api.github.com/users/jasonsurratt/received_events","type":"User","site_admin":false},"created_at":"2016-04-18T14:27:57Z","updated_at":"2016-04-18T14:27:57Z","body":"Hi Scott,\r\n\r\nWe are trying to solve a maximization problem with road matching. As you alluded to our first rough limitation is to only match up roads within a distance threshold. By default that is specified with the \"error:circular\" tag (95% CE in meters) or `search.radius.highway`. If that isn't available we assume 15m. Once match candidates are found we look a little further and determine if it is a subline that matches and then score the match using a Random Forest Classifier. If the match candidate isn't classified as a \"miss\" we keep it around for further consideration.\r\n\r\nOnce we have a collection of matches with associated scores we can then calculate which matches are conflicting (e.g. a road can't be merged with two other overlapping roads). With the list of conflicting matches we can now start the optimization phase. As you mentioned, finding an exact solution is slow. Integer programming in particular [is NP-Hard](https://en.wikipedia.org/wiki/Integer_programming). We have no intention of letting it run to completion -- if it succeeds in the time limit, great, otherwise we take the best solution generated. In the case of GLPK's _branch and cut_ algorithm it will give us the best solution found so far if it runs out of time (https://github.com/ngageoint/hootenanny/blob/2ef291df533d113a319625c2d13ea1c1a129c949/hoot-core/src/main/cpp/hoot/core/algorithms/IntegerProgrammingSolver.h#L174). In addition we also run a simple greedy algorithm. The greedy algorithm is incredibly fast (sort and keep the highest non-conflicting scores), however it doesn't always give the best result. We then keep the best solution between _greedy_ and _time bound branch and cut_. From the practical side, this will give a result in a reasonable amount of time. There are many other algorithms out there that give better approximations than greedy. We'd like the try them but it is just a matter of priorities.\r\n\r\nThe 200MB warning was requested by users quite a while ago just to give them a heads up that things may be slow or if you use the `max.memory.usage` parameter on shared servers that the conflation job may fail. It is a very coarse warning message, but creating more refined messages such as estimated time to execute and estimated memory usage are a bit more involved.\r\n"}}