{"action":"opened","issue":{"url":"https://api.github.com/repos/uwescience/myria/issues/813","repository_url":"https://api.github.com/repos/uwescience/myria","labels_url":"https://api.github.com/repos/uwescience/myria/issues/813/labels{/name}","comments_url":"https://api.github.com/repos/uwescience/myria/issues/813/comments","events_url":"https://api.github.com/repos/uwescience/myria/issues/813/events","html_url":"https://github.com/uwescience/myria/issues/813","id":135594364,"number":813,"title":"Write balanced spatial partitioning query in MyriaL","user":{"login":"senderista","id":131425,"avatar_url":"https://avatars.githubusercontent.com/u/131425?v=3","gravatar_id":"","url":"https://api.github.com/users/senderista","html_url":"https://github.com/senderista","followers_url":"https://api.github.com/users/senderista/followers","following_url":"https://api.github.com/users/senderista/following{/other_user}","gists_url":"https://api.github.com/users/senderista/gists{/gist_id}","starred_url":"https://api.github.com/users/senderista/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/senderista/subscriptions","organizations_url":"https://api.github.com/users/senderista/orgs","repos_url":"https://api.github.com/users/senderista/repos","events_url":"https://api.github.com/users/senderista/events{/privacy}","received_events_url":"https://api.github.com/users/senderista/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/uwescience/myria/labels/Enhancement","name":"Enhancement","color":"84b6eb"},{"url":"https://api.github.com/repos/uwescience/myria/labels/Important","name":"Important","color":"eb6420"}],"state":"open","locked":false,"assignee":{"login":"jingjingwang","id":2280236,"avatar_url":"https://avatars.githubusercontent.com/u/2280236?v=3","gravatar_id":"","url":"https://api.github.com/users/jingjingwang","html_url":"https://github.com/jingjingwang","followers_url":"https://api.github.com/users/jingjingwang/followers","following_url":"https://api.github.com/users/jingjingwang/following{/other_user}","gists_url":"https://api.github.com/users/jingjingwang/gists{/gist_id}","starred_url":"https://api.github.com/users/jingjingwang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jingjingwang/subscriptions","organizations_url":"https://api.github.com/users/jingjingwang/orgs","repos_url":"https://api.github.com/users/jingjingwang/repos","events_url":"https://api.github.com/users/jingjingwang/events{/privacy}","received_events_url":"https://api.github.com/users/jingjingwang/received_events","type":"User","site_admin":false},"milestone":null,"comments":0,"created_at":"2016-02-23T01:03:28Z","updated_at":"2016-02-23T01:03:28Z","closed_at":null,"body":"We have a case (the `cosmo8` dataset) where a spatial dataset is extremely skewed (always hashes to a single partition), making queries very difficult. If we had a MyriaL query that applied a balanced spatial partitioning technique like kd-trees or octrees, we would be able to pre-partition the data to preserve locality while avoiding skew. (If necessary, this logic could later be implemented as a standalone operator.)\r\n\r\nWe should be able to implement this query as a `do...while` loop, with the termination condition expressed as point density or fraction of total points. We could initially implement the partitioning as repeated bisection of the space, cycling through each dimension as in kd-trees, but simply bisecting along the midpoint coordinates of each cell. Later we could turn this into a proper kd-tree, bisecting along the median coordinates in each dimension (possibly just using the median of a random sample of `k` points rather than trying to run an `O(n)` distributed median algorithm)."}}