TY - RPRT
T1 - Fast Fractional Cascading and Its Applications
Y1 - 2003
A1 - Shi,Qingmin
A1 - JaJa, Joseph F.
KW - Technical Report
AB - Using the notions of Q-heaps and fusion trees developed by Fredman andWillard, we develop a faster version of the fractional cascading technique while maintaining the linear space structure. The new version enables sublogarithmic iterative search in the case when we have a search tree and the degree of each node is bounded by $O(\log^{\epsilon}n)$, for some constant $\epsilon >0$, where $n$ is the total size of all the lists stored in the tree. The fast fractional cascading technique is used in combination with other techniques to derive sublogarithmic time algorithms for the geometric retrieval problems: orthogonal segment intersection and rectangular point enclosure. The new algorithms use $O(n)$ space and achieve a query time of $O(\log n/\log\log n + f)$, where $f$ is the number of objects satisfying the query. All our algorithms assume the version of the RAM model used by Fredman and Willard. (UMIACS-TR-2003-71)
PB - Instititue for Advanced Computer Studies, Univ of Maryland, College Park
VL - UMIACS-TR-2003-71
UR - http://drum.lib.umd.edu/handle/1903/1296
ER -