On Tue, Jun 26, 2012 at 11:52:15PM -0700, khris wrote: > Hi Petr, > > Appreciate your feedback and sorry for the delay in responding. The > following is the description of problem from start:- > > We have a set of sensors in XY plane arranged in more or less a rectangular > grid and we know their (x,y) co-ordinate. Now these sensors send data and > from that data using Data mining techniques I can find out the relative > distance between Sensors. So the question was using the relative distance > matrix obtained from Database can we figure out (x,y) position of sensors in > DB.
Hi Khris: If i understand the problem correctly, you have a list of (x,y) coordinates, where some sensor is located, but you do not know, which sensor is there. The database contains data for each sensor identified in some way, but you do not know the mapping between sensor identifiers from the database and the (x,y) coordinates. Is this correct? > So I modelled the problem as inexact match between 2 Graphs. Since the best > package on Graphs i.e. iGraph does not have any function for Graph matching I think, the problem is close to http://en.wikipedia.org/wiki/Graph_isomorphism You have estimates of the distances between the sensors using identifiers from the database. So, you know, which pairs of sensors are close. This is one graph. The other graph is the graph of closeness between the known (x,y) coordinates. You want to find a mapping between the vertices of these two graphs, which preserves edges. > I converted the Inexact graph matching problem to Binary Quadratic Opt > Problem. Since there is no specialized package for Binary Quadratic Opt, > based on your input I converted it into Binary Linear Opt problem. The problem of graph isomorphism is hard in general, but if one of the graphs is a rectangular grid, which does not have too many automorphisms, the problem is not too hard. Try, for example, the following approach. Look for small groups of the sensors, which form connected subgraphs, which have the form of small pieces of the rectangular grid. If you have such a small subgraph, look for nodes, which can be add to the subgraph to make it a larger piece of the grid. To start, the algorithm can choose any sensor, say S_0. Find all its neighbours. There should be at most 4 neighbours (in an ideal grid). Call the group of these neighbours S_1. Then, find sensors, which are neighbours to at least two members of S_1. Call them group S_2. The connections between S_0, S_1 and S_2 should form a pattern like 2 - 1 - 2 | | | 1 - 0 - 1 | | | 2 - 1 - 2 The digits 0, 1, 2 distinguish elements of S_0, S_1, S_2. Continue this in order to enlarge this recognised pattern. If the grid is not ideal, the process may require to maintain several candidate connected patterns and choose those, which can be extended with further sensors and discard those, which cannot. Another approach is as follows. Choose a random mapping between the sensors and (x,y). Define a measure of the quality of the mapping. For example, the number of matching edges minus the number of non-matching edges. Then, use local search to maximize the quality. For example, in each step, exchange two sensors in a way, which increases the quality. Do you think that some of these approaches is applicable to your situation? Petr. ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
