Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Range Counting
| dc.contributor.author | Shi, Qingmin | en_US |
| dc.contributor.author | JaJa, Joseph | en_US |
| dc.contributor.author | Mortensen, Christian | en_US |
| dc.date.accessioned | 2004-05-31T23:33:07Z | |
| dc.date.available | 2004-05-31T23:33:07Z | |
| dc.date.created | 2003-10 | en_US |
| dc.date.issued | 2003-11-25 | en_US |
| dc.description.abstract | We present linear-space sublogarithmic algorithms for handling the {\em three-dimensional dominance reporting problem} and the {\em two-dimensional range counting problem}. Under the RAM model as described in~[M.~L. Fredman and D.~E. Willard. ``Surpassing the information theoretic bound with fusion trees'', {\em Journal of Computer and System Sciences}, 47:424--436, 1993], our algorithms achieve $O(\log n/\log\log n+f)$ query time for 3-D dominance reporting, where $f$ is the number of points reported, and $O(\log n/\log\log n)$ query time for 2-D range counting case. We extend these results to any constant dimension $d$ achieving $O(n(\log n/\log\log n)^{d-3})$-space and $O((\log n/\log\log )^{d-2}+f)$-query time for the reporting case and $O(n(\log n/\log\log n)^{d-2})$-space and $O((\log n/\log\log n)^{d-1})$ query time for the counting case. (UMIACS-TR-2003-101) | en_US |
| dc.format.extent | 271107 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/1318 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-4533 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-2003-101 | en_US |
| dc.title | Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Range Counting | en_US |
| dc.type | Technical Report | en_US |