# Fast Fractional Cascading and Its Applications

 dc.contributor.author Shi, Qingmin en_US dc.contributor.author JaJa, Joseph en_US dc.date.accessioned 2004-05-31T23:30:19Z dc.date.available 2004-05-31T23:30:19Z dc.date.created 2003-07 en_US dc.date.issued 2003-08-01 en_US dc.identifier.uri http://hdl.handle.net/1903/1296 dc.description.abstract Using the notions of Q-heaps and fusion trees developed by Fredman and en_US Willard, 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) dc.format.extent 335798 bytes dc.format.mimetype application/postscript dc.language.iso en_US dc.relation.ispartofseries UM Computer Science Department; CS-TR-4502 en_US dc.relation.ispartofseries UMIACS; UMIACS-TR-2003-71 en_US dc.title Fast Fractional Cascading and Its Applications en_US dc.type Technical Report 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
﻿