{"action":"created","issue":{"url":"https://api.github.com/repos/tdunning/t-digest/issues/61","labels_url":"https://api.github.com/repos/tdunning/t-digest/issues/61/labels{/name}","comments_url":"https://api.github.com/repos/tdunning/t-digest/issues/61/comments","events_url":"https://api.github.com/repos/tdunning/t-digest/issues/61/events","html_url":"https://github.com/tdunning/t-digest/issues/61","id":112862348,"number":61,"title":"Possible improvement to the speed of the algorithm","user":{"login":"snaury","id":53117,"avatar_url":"https://avatars.githubusercontent.com/u/53117?v=3","gravatar_id":"","url":"https://api.github.com/users/snaury","html_url":"https://github.com/snaury","followers_url":"https://api.github.com/users/snaury/followers","following_url":"https://api.github.com/users/snaury/following{/other_user}","gists_url":"https://api.github.com/users/snaury/gists{/gist_id}","starred_url":"https://api.github.com/users/snaury/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/snaury/subscriptions","organizations_url":"https://api.github.com/users/snaury/orgs","repos_url":"https://api.github.com/users/snaury/repos","events_url":"https://api.github.com/users/snaury/events{/privacy}","received_events_url":"https://api.github.com/users/snaury/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":5,"created_at":"2015-10-22T18:27:16Z","updated_at":"2015-10-22T23:49:02Z","closed_at":null,"body":"Hi, I've recently learned about t-digest and really like the algorithm. I coded a very naive implementation in C++ using `std::multimap` for centroids and found 3µs per measurement way too expensive (I'm trying to use it in a fast map/reduce-like setting with up to 10 million measurements per chunk, and 3µs made response unacceptable).\r\n\r\nHowever in my search for improving the speed I found that too much time is spent in computing the head sum after finding closest centroids, which was possible to amortise: I first collect a big enough array of measurements (e.g. 8192), which when full is turned into centroids with weight 1 and sorted with the rest of the summary. Then I go over centroids from left to right compress it by checking if it is possible to merge two centroids by computing `q = sum + (l.count + r.count) / 2` (for the possibly merged centroid) and compute `k` based on it. If `l.count + r.count` is less than or equal to `k`, then I merge two centroids into one, which becomes the new `l`, otherwise I consider the next pair and so forth.\r\n\r\nIn my very simple checks on random data so far I found this seems to give less accurate results than the original t-digest, however the accuracy was still pretty good considering the final summary size, and the best part is that this variant gives me around 70ns per measurement. I considered other variants, like computing all head sums and then trying to merge closest or smallest centroids first, but this didn't give much accuracy improvement while slowing it down.\r\n\r\nI'm wondering what you might think about this extremely simplified version and what are fatal flaws with using it like this?"},"comment":{"url":"https://api.github.com/repos/tdunning/t-digest/issues/comments/150389609","html_url":"https://github.com/tdunning/t-digest/issues/61#issuecomment-150389609","issue_url":"https://api.github.com/repos/tdunning/t-digest/issues/61","id":150389609,"user":{"login":"tdunning","id":250490,"avatar_url":"https://avatars.githubusercontent.com/u/250490?v=3","gravatar_id":"","url":"https://api.github.com/users/tdunning","html_url":"https://github.com/tdunning","followers_url":"https://api.github.com/users/tdunning/followers","following_url":"https://api.github.com/users/tdunning/following{/other_user}","gists_url":"https://api.github.com/users/tdunning/gists{/gist_id}","starred_url":"https://api.github.com/users/tdunning/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tdunning/subscriptions","organizations_url":"https://api.github.com/users/tdunning/orgs","repos_url":"https://api.github.com/users/tdunning/repos","events_url":"https://api.github.com/users/tdunning/events{/privacy}","received_events_url":"https://api.github.com/users/tdunning/received_events","type":"User","site_admin":false},"created_at":"2015-10-22T23:49:02Z","updated_at":"2015-10-22T23:49:02Z","body":"Yes, the integrated location approach does give fewer centroids. In fact,\nit gives a bounded number while the other criteria tend to give an\nunbounded O(log(n)) result.\n\nBounds are good.\n\n\n\nOn Thu, Oct 22, 2015 at 4:29 PM, Alexey Borzenkov <notifications@github.com>\nwrote:\n\n> Hmm. I tried using merging condition of ∆integratedLocation <= 1 like in\n> MergingDigest, it causes a much smaller number of centroids in the end,\n> but accuracy is not as nice, and there are other differences like edge\n> centroids no longer stay at count 1, etc. However this:\n> https://github.com/snaury/t-digest-simple/blob/master/merging_tdigest.hpp\n> (sorry for C++, I'm not as comfortable with Java) gives a similar number of\n> final centroids to TreeDigest and is much faster (looks like asin is a\n> little slower than simple multiplications).\n>\n> —\n> Reply to this email directly or view it on GitHub\n> <https://github.com/tdunning/t-digest/issues/61#issuecomment-150383383>.\n>\n"}}