Repository logo
 

Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing

dc.contributor.authorGao, Younan
dc.contributor.copyright-releaseNoen_US
dc.contributor.degreeMaster of Computer Scienceen_US
dc.contributor.departmentFaculty of Computer Scienceen_US
dc.contributor.ethics-approvalNot Applicableen_US
dc.contributor.external-examinern/aen_US
dc.contributor.graduate-coordinatorMichael McAllisteren_US
dc.contributor.manuscriptsNot Applicableen_US
dc.contributor.thesis-readerTravis Gagieen_US
dc.contributor.thesis-reader‪Norbert Zehen_US
dc.contributor.thesis-supervisorMeng Heen_US
dc.date.accessioned2020-08-28T13:30:44Z
dc.date.available2020-08-28T13:30:44Z
dc.date.defence2020-08-10
dc.date.issued2020-08-28T13:30:44Z
dc.description.abstractUnder the word RAM model, we design three data structures that can be constructed in $O(n\sqrt{\lg n})$ time over $n$ points in an $n \times n$ grid. The first data structure is an $O(n\lg^{\epsilon} n)$-word structure supporting orthogonal range reporting in $O(\lg\lg n+\occ)$ time, where $\occ$ denotes output size and $\epsilon$ is an arbitrarily small constant. The second is an $O(n\lg\lg n)$-word structure supporting orthogonal range successor in $O(\lg\lg n)$ time, while the third is an $O(n\lg^{\epsilon} n)$-word structure supporting sorted range reporting in $O(\lg\lg n+\occ)$ time. The query times of these data structures are optimal when the space costs must be within $O(n\polylog n)$ words. Their exact space bounds match those of the best known results achieving the same query times, and the $O(n\sqrt{\lg n})$ construction time beats the previous bounds on preprocessing. We also apply our results to improve the construction time of text indexes.en_US
dc.identifier.urihttp://hdl.handle.net/10222/79749
dc.language.isoenen_US
dc.subjectorthogonal range searchen_US
dc.subjectgeometric data structuresen_US
dc.subjectorthogonal range reportingen_US
dc.subjectorthogonal range successoren_US
dc.subjectsorted range reportingen_US
dc.subjecttext indexingen_US
dc.subjectword RAMen_US
dc.titleFast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexingen_US
dc.typeThesisen_US

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Gao-Younan-MCS-CSCI-August-2020.pdf
Size:
767.23 KB
Format:
Adobe Portable Document Format
Description:
The master thesis

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description: