{"action":"created","issue":{"url":"https://api.github.com/repos/tdunning/t-digest/issues/40","labels_url":"https://api.github.com/repos/tdunning/t-digest/issues/40/labels{/name}","comments_url":"https://api.github.com/repos/tdunning/t-digest/issues/40/comments","events_url":"https://api.github.com/repos/tdunning/t-digest/issues/40/events","html_url":"https://github.com/tdunning/t-digest/issues/40","id":55819295,"number":40,"title":"Improved constraint on centroid sizes","user":{"login":"oertl","id":9392465,"avatar_url":"https://avatars.githubusercontent.com/u/9392465?v=3","gravatar_id":"","url":"https://api.github.com/users/oertl","html_url":"https://github.com/oertl","followers_url":"https://api.github.com/users/oertl/followers","following_url":"https://api.github.com/users/oertl/following{/other_user}","gists_url":"https://api.github.com/users/oertl/gists{/gist_id}","starred_url":"https://api.github.com/users/oertl/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/oertl/subscriptions","organizations_url":"https://api.github.com/users/oertl/orgs","repos_url":"https://api.github.com/users/oertl/repos","events_url":"https://api.github.com/users/oertl/events{/privacy}","received_events_url":"https://api.github.com/users/oertl/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":8,"created_at":"2015-01-28T21:36:16Z","updated_at":"2015-02-05T22:13:33Z","closed_at":null,"body":"I propose an improved condition, whether neighboring centroids can be merged or not: Let `{(x_1, w_1), (x_2, w_2),...,(x_N, w_N)}` be the centroids in ascending order where `x_i` is the mean and `w_i` is the weight of the `i`-th centroid. Let `W` be the sum of all weights `W := w_1 + w_2 +...+ w_N`. \r\n\r\nThe original t-digest condition is equivalent to `w_i/W*f(q_i) <= 4*delta`, where `f(q):=1/(q*(1-q))` and `delta`is the reciprocal value of the compression. \r\n\r\nInstead, I propose to use the constraint `int_{z_i}^{z_{i+1}} f(q) dq <= 4*delta` with `z_i:=(sum_{j<i} w_i)/W`. Note, that this inequality is more strict than the original constraint due to Jensen's inequality and because `f(q)` is a convex function. The integral of `f(q)` from `z_i` to `z_{i+1}` can be solved analytically and the new constraint can be expressed as\r\n`ln(z_{i+1}/(1-z_{i+1})) - ln(z_{i}/(1-z_{i})) <= 4*delta` or equivalently as `(z_{i+1}-z_{i})<=(e^{4*delta}-1)*z_{i}*(1-z_{i+1})`. The last inequality can be evaluated very efficiently, if the constant first factor on the right hand side is precalculated. \r\n\r\nSince the integral of `f(q)` is indefinite at boundaries 0 and 1, the new constraint inhibits in a natural way merging with the first or the last centroid. This is not the case for the original constraint."},"comment":{"url":"https://api.github.com/repos/tdunning/t-digest/issues/comments/73141344","html_url":"https://github.com/tdunning/t-digest/issues/40#issuecomment-73141344","issue_url":"https://api.github.com/repos/tdunning/t-digest/issues/40","id":73141344,"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-02-05T22:13:33Z","updated_at":"2015-02-05T22:13:33Z","body":"Excellent.  I had derived exactly the same result for how many 1 there\nwere, but I like the extension which shows that there is no dependence on\nW.  The other way to attack this is to assume linearity in q at the\nperiphery.\n\n\n\nOn Wed, Feb 4, 2015 at 12:33 PM, Otmar Ertl <notifications@github.com>\nwrote:\n\n> Today I had time to analyze the asymptotic dependence of X on W. By\n> definition the (X+1)-th centroid is the first centroid that fulfills the\n> constraint: ln((X+1)/(W-X-1))-ln(X/(W-X)) < 4*delta or equivalently (X+1)*(W-X)/(X*(W-X-1))\n> < exp(4*delta)or W/(W*X-X*(X+1)) < exp(4*delta)-1. For W >> X the LHS\n> converges to 1/X which gives 1/X < exp(4*delta)-1 and finally X >\n> 1/(exp(4*delta)-1). Therefore, in case W >> X the smallest X fulfilling\n> the inequality is approximately 1/(exp(4*delta)-1) which is approximately\n> equal to 1/(4*delta) for delta<<1 and which is independent of W. As a\n> consequence, the number of centroids really increases logarithmically with\n> the number of points W for the q*(1-q) rule.\n>\n> —\n> Reply to this email directly or view it on GitHub\n> <https://github.com/tdunning/t-digest/issues/40#issuecomment-72933234>.\n>\n"}}