Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports from UMIACS
    • View Item
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports from UMIACS
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Fast Fractional Cascading and Its Applications

    Thumbnail
    View/Open
    CS-TR-4502.ps (327.9Kb)
    No. of downloads: 286

    Auto-generated copy of CS-TR-4502.ps (261.3Kb)
    No. of downloads: 645

    Date
    2003-08-01
    Author
    Shi, Qingmin
    JaJa, Joseph
    Metadata
    Show full item record
    Abstract
    Using the notions of Q-heaps and fusion trees developed by Fredman and 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)
    URI
    http://hdl.handle.net/1903/1296
    Collections
    • Technical Reports from UMIACS
    • Technical Reports of the Computer Science Department

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility