{"action":"created","issue":{"url":"https://api.github.com/repos/OpenMS/OpenMS/issues/1610","labels_url":"https://api.github.com/repos/OpenMS/OpenMS/issues/1610/labels{/name}","comments_url":"https://api.github.com/repos/OpenMS/OpenMS/issues/1610/comments","events_url":"https://api.github.com/repos/OpenMS/OpenMS/issues/1610/events","html_url":"https://github.com/OpenMS/OpenMS/pull/1610","id":107660993,"number":1610,"title":"FeatureLinkerUnlabeledQT improvements","user":{"login":"hroest","id":464014,"avatar_url":"https://avatars.githubusercontent.com/u/464014?v=3","gravatar_id":"","url":"https://api.github.com/users/hroest","html_url":"https://github.com/hroest","followers_url":"https://api.github.com/users/hroest/followers","following_url":"https://api.github.com/users/hroest/following{/other_user}","gists_url":"https://api.github.com/users/hroest/gists{/gist_id}","starred_url":"https://api.github.com/users/hroest/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hroest/subscriptions","organizations_url":"https://api.github.com/users/hroest/orgs","repos_url":"https://api.github.com/users/hroest/repos","events_url":"https://api.github.com/users/hroest/events{/privacy}","received_events_url":"https://api.github.com/users/hroest/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/OpenMS/OpenMS/labels/enhancement","name":"enhancement","color":"f7c6c7"},{"url":"https://api.github.com/repos/OpenMS/OpenMS/labels/Performance","name":"Performance","color":"eb6420"}],"state":"open","locked":false,"assignee":{"login":"hroest","id":464014,"avatar_url":"https://avatars.githubusercontent.com/u/464014?v=3","gravatar_id":"","url":"https://api.github.com/users/hroest","html_url":"https://github.com/hroest","followers_url":"https://api.github.com/users/hroest/followers","following_url":"https://api.github.com/users/hroest/following{/other_user}","gists_url":"https://api.github.com/users/hroest/gists{/gist_id}","starred_url":"https://api.github.com/users/hroest/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hroest/subscriptions","organizations_url":"https://api.github.com/users/hroest/orgs","repos_url":"https://api.github.com/users/hroest/repos","events_url":"https://api.github.com/users/hroest/events{/privacy}","received_events_url":"https://api.github.com/users/hroest/received_events","type":"User","site_admin":false},"milestone":{"url":"https://api.github.com/repos/OpenMS/OpenMS/milestones/10","html_url":"https://github.com/OpenMS/OpenMS/milestones/Release%202.1","labels_url":"https://api.github.com/repos/OpenMS/OpenMS/milestones/10/labels","id":946633,"number":10,"title":"Release 2.1","description":null,"creator":{"login":"hroest","id":464014,"avatar_url":"https://avatars.githubusercontent.com/u/464014?v=3","gravatar_id":"","url":"https://api.github.com/users/hroest","html_url":"https://github.com/hroest","followers_url":"https://api.github.com/users/hroest/followers","following_url":"https://api.github.com/users/hroest/following{/other_user}","gists_url":"https://api.github.com/users/hroest/gists{/gist_id}","starred_url":"https://api.github.com/users/hroest/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hroest/subscriptions","organizations_url":"https://api.github.com/users/hroest/orgs","repos_url":"https://api.github.com/users/hroest/repos","events_url":"https://api.github.com/users/hroest/events{/privacy}","received_events_url":"https://api.github.com/users/hroest/received_events","type":"User","site_admin":false},"open_issues":5,"closed_issues":31,"state":"open","created_at":"2015-01-22T09:15:39Z","updated_at":"2015-09-22T20:49:44Z","due_on":null,"closed_at":null},"comments":2,"created_at":"2015-09-22T07:39:11Z","updated_at":"2015-09-24T13:16:31Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/OpenMS/OpenMS/pulls/1610","html_url":"https://github.com/OpenMS/OpenMS/pull/1610","diff_url":"https://github.com/OpenMS/OpenMS/pull/1610.diff","patch_url":"https://github.com/OpenMS/OpenMS/pull/1610.patch"},"body":"This PR contains a major improvement to the FeatureLinkerUnlabeledQT which I have found to perform rather slow and consume huge amounts of memory when I tried to run it. These problems are addressed in this PR.\r\n\r\nThe main problem with FeatureLinkerUnlabeledQT was that the algorithm basically kept around a lot of data structures that grew quadratically with the number of input features. Specifically, `distances_` was basically a hash of all distances between all features that were ever needed in the past which is `O(n^2 * k^2)` where *n* is the number of features per map and *k* is the number of maps (thus total number of features `m = n* k`). Similarly, `QTCluster` was a data structure created for each feature in each map (a total of `m` instances) and each instance held a list of *all* its neighbors in *all* the other maps, so this would grow with `O(c * m^2) = O( n^2 * k^2)` where `c` is a constant. Note that of course not every cluster node has a list of every other cluster node but only the immediate neighbours, so the constant factor `c` is quite small but the growth is of course still `O( n^2 * k^2)`.\r\n\r\nI have modified these two data structures, eliminated `distances_` completely and modified `QTCluster` such that it only stores the *best* feature from every map, thus reducing memory complexity to `O(n * k^2)` which showed big improvements on my machine. Unfortunately, memory is still going to grow quadratically with the number of input maps. Even doing this change turned out to be non-trivial as there is one corner-case when using identifications where the correct cluster depends on *all* neighbors. For this case, I now temporary store all neighbors and delete the map again after computing the correct cluster.\r\n\r\nAdditionally I have introduced an optional partitioning by *m/z* as often the distance between features in m/z domain can be quite large and way larger than the maximal distance to be considered for a cluster. This means that the problem can be partitioned and each partition can be solved independently.\r\n\r\nUsing the partitioning, even runtime goes down. With one partition, runtime is constant or somewhat larger. This is despite the fact that I remove some speed-optimization and some work now needs to be done multiple times (e.g. now every time a neighbor gets removed from a cluster, all potential neighbors need to be re-investigated and everything needs to be recomputed).\r\n\r\nSome data on a dataset of 7 feature maps with  about 10k features each that were re-used multiple times:\r\n\r\nDataset of 7 maps:\r\n- before: 616 MB memory usage and 112 seconds runtime\r\n- after (1 partition): 88 MB of memory and 64 seconds runtime\r\n- after (30 partitions): 43 MB of memory and 9.5 seconds runtime\r\n\r\nso this is an 10x improvement in runtime and a 14x improvement in memory usage\r\n\r\nDataset of 28 maps (re-using the same maps 4 times)\r\n- before: 2.4 GB / 5:26 min\r\n- after (45 partitions): 127 MB memory usage / 65 seconds runtime\r\n\r\n\r\nNow memory usage seems to scale (almost) linearly with the number of maps and the good thing is that the algorithm now seems to scale to dozens of maps, if not hundreds (it starts to get slow at some point). This is all computed using 30 partitions:\r\n\r\n- 7 maps: 43 MB of memory\r\n- 28 maps: 127 MB of memory\r\n- 56 maps: 276.5 MB of memory\r\n- 112 maps: 666.5 MB of memory\r\n\r\n\r\ncaveats: this is now only tested on raw maps without any id data (currently I do not have any such data) and -- surprise surprise -- there has not been a test with the `use_identifications` enabled. I have tried to manage this case also carefully but I would be very glad if somebody could test this on a larger dataset and confirm that  the results are the same. I have also created a test data where `use_identifications` produces different results and this is now tested in a toy example."},"comment":{"url":"https://api.github.com/repos/OpenMS/OpenMS/issues/comments/142924008","html_url":"https://github.com/OpenMS/OpenMS/pull/1610#issuecomment-142924008","issue_url":"https://api.github.com/repos/OpenMS/OpenMS/issues/1610","id":142924008,"user":{"login":"timosachsenberg","id":5803621,"avatar_url":"https://avatars.githubusercontent.com/u/5803621?v=3","gravatar_id":"","url":"https://api.github.com/users/timosachsenberg","html_url":"https://github.com/timosachsenberg","followers_url":"https://api.github.com/users/timosachsenberg/followers","following_url":"https://api.github.com/users/timosachsenberg/following{/other_user}","gists_url":"https://api.github.com/users/timosachsenberg/gists{/gist_id}","starred_url":"https://api.github.com/users/timosachsenberg/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/timosachsenberg/subscriptions","organizations_url":"https://api.github.com/users/timosachsenberg/orgs","repos_url":"https://api.github.com/users/timosachsenberg/repos","events_url":"https://api.github.com/users/timosachsenberg/events{/privacy}","received_events_url":"https://api.github.com/users/timosachsenberg/received_events","type":"User","site_admin":false},"created_at":"2015-09-24T13:16:31Z","updated_at":"2015-09-24T13:16:31Z","body":"Sounds great. I like the partitioning - the next extension would be to do a DBScan clustering first and then use the resulting clusters as an initial partitioning (and also to resolve all clusters within the QT) ;)\r\n"}}