tag:blogger.com,1999:blog-786333285568106173.post8254514418257692011..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: A taxonomy of range query problemsMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-786333285568106173.post-54418076442689138142010-09-19T11:34:26.505-04:002010-09-19T11:34:26.505-04:00It's space O(n lglg n) and time O(k lglg n). I...It's space O(n lglg n) and time O(k lglg n). I strongly suspect a lower bound saying that O(k)-time reporting requires Omega(n lg^eps n) time -- but I don't have a formal proof yet.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-90751529350673312422010-09-19T10:05:16.513-04:002010-09-19T10:05:16.513-04:00In your MADALGO's summer school tutorial on or...In your MADALGO's summer school tutorial on orthogonal range queries you claim that you can do better 2D orthogonal range queries but you do not give the output sensitive term. Do you mean that you are able to get O(n log log n) space with O(log log n +k ) or O(log log n(1+k)) query time (the latter would be only a slight improvement over FOCS00 paper).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-80392015500420281612010-08-06T09:18:29.801-04:002010-08-06T09:18:29.801-04:00The colored version (especially counting) is only ...The colored version (especially counting) is only decomposable w.r.t. colors, causing a substantial gap between best-known colored/non-colored bounds.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-47967098797750987452010-08-05T15:42:24.133-04:002010-08-05T15:42:24.133-04:00Decomposability is a key property identified by Be...Decomposability is a key property identified by Bentley.Jackhttps://www.blogger.com/profile/02023530898615048685noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-73837572263047105482010-08-05T09:21:31.827-04:002010-08-05T09:21:31.827-04:00There are some variations for the weighted version...There are some variations for the weighted version based on what kind of sum is used. For example, if the sum is taken over a group, then static partial sums are trivial, but if you are in a commutative semigroup, then you cannot use subtraction and the problem gets much more complicated. Idempotence (x+x=x) is another property worth mentioning.<br /><br />Data structures may be exact or approximate. In the approximate version, you can approximate the count, the fraction of the points within the range, or allow points near the boundary to be misclassified.<br /><br />One may or may not consider problems where the objects are not points as range searching. For example, given a set of triangles, find the triangles intersected or contained in a rectangle.Guilhermehttp://www.uniriotec.br/~fonsecanoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-53667675063217794682010-08-05T08:31:58.309-04:002010-08-05T08:31:58.309-04:00You're right, David, that concept deserves a m...You're right, David, that concept deserves a mention. But it's more general than range queries. Eg, I can have records with 3D points and some string inside, and make range queries on the points and pattern matching queries on the string.<br /><br />By the way, do you think it would be useful to upload this list to Wikipedia? Perhaps here: http://en.wikipedia.org/wiki/Range_query<br /><br />What should one do about topics at the intersection of two fields (here, CG and databases), which nonetheless mean sufficiently different things inside those fields?Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-81754102303939081862010-08-04T21:48:54.253-04:002010-08-04T21:48:54.253-04:00Did you forget, or intentionally leave out, recurs...Did you forget, or intentionally leave out, recursive queries? Where what you want to do to the data within the range is apply some other range query on some unrelated dimension of the same data.<br /><br />Of course one can always flatten the recursion and get some kind of range space in which you're just doing a counting or reporting query or whatever. But the ranges for this flattened space might be harder to describe.D. Eppsteinhttp://11011110.livejournal.com/noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-41756223436123811212010-08-04T17:51:31.977-04:002010-08-04T17:51:31.977-04:00Thanks Jeff. I added the parametric/kinetic varian...Thanks Jeff. I added the parametric/kinetic variant.<br /><br />R^d is completely besides the point for orthogonal problems, since you should start by converting to rank space. (After that, what does the real model allow me to do?) For non-orthogonal queries, most data structures do use the Real RAM, since they don't want to worry about precision.<br /><br />I have a hard time seeing nearest neighbor as a range query. In any case there's enough material on it that it's now a separate topic. :)<br /><br />Orthogonal ray shooting is a range query -- I added a clarification. (Max segment intersection with priorities = y-coordinates.) But then I should probably not consider general ray shooting as a range query.<br /><br />Another hyper-generic view you can take is semigroup range sum. For instance, counting works in the (N,+) semigroup, range min works in the (N,min) semigroup, etc.<br /><br />About approximation, I have yet to be convinced about its value in range queries (as opposed to other things, like ANN). In any case, Sariel promised to do all approximation in the upcoming summer school :)Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-89730476374904105652010-08-04T16:03:18.748-04:002010-08-04T16:03:18.748-04:00Under dynamism, add parametric/kinetic. In its si...Under dynamism, add <em>parametric/kinetic</em>. In its simplest form, a kinetic data structure simply requires that the queries arrive in order along the 'time' coordinate, but the formulation allows for different interesting tradeoffs.<br /><br />Under universes, add R^d — you know, real geometry.<br /><br />Nearest neighbor and ray-shooting queries are special cases of range-min queries, where the weight of a point/object depends on the query.<br /><br />All the special types of queries are special cases of generic range spaces, which can be defined by a set of objects X, a set of queries Q, and a function over pairs in X × Q. For example: (points, rectangles, [p∈r]) is 2d orthogonal range searching; (rectangles, points, [p∈r]) is 2d rectangle stabbing; (points, points, |pq|) is nearest-neighbor searching; (strings, strings, [x is a substring of y]) is Google; (Turing machines, input strings, running time) is all of complexity theory; and so on.<br /><br />Finally, there are umpty-dozen kinds of approximation to consider.JeffEhttps://www.blogger.com/profile/17633745186684887140noreply@blogger.com