Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing
dc.contributor.author | Gao, Younan | |
dc.contributor.copyright-release | No | en_US |
dc.contributor.degree | Master of Computer Science | en_US |
dc.contributor.department | Faculty of Computer Science | en_US |
dc.contributor.ethics-approval | Not Applicable | en_US |
dc.contributor.external-examiner | n/a | en_US |
dc.contributor.graduate-coordinator | Michael McAllister | en_US |
dc.contributor.manuscripts | Not Applicable | en_US |
dc.contributor.thesis-reader | Travis Gagie | en_US |
dc.contributor.thesis-reader | Norbert Zeh | en_US |
dc.contributor.thesis-supervisor | Meng He | en_US |
dc.date.accessioned | 2020-08-28T13:30:44Z | |
dc.date.available | 2020-08-28T13:30:44Z | |
dc.date.defence | 2020-08-10 | |
dc.date.issued | 2020-08-28T13:30:44Z | |
dc.description.abstract | Under 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.uri | http://hdl.handle.net/10222/79749 | |
dc.language.iso | en | en_US |
dc.subject | orthogonal range search | en_US |
dc.subject | geometric data structures | en_US |
dc.subject | orthogonal range reporting | en_US |
dc.subject | orthogonal range successor | en_US |
dc.subject | sorted range reporting | en_US |
dc.subject | text indexing | en_US |
dc.subject | word RAM | en_US |
dc.title | Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing | en_US |
dc.type | Thesis | en_US |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Gao-Younan-MCS-CSCI-August-2020.pdf
- Size:
- 767.23 KB
- Format:
- Adobe Portable Document Format
- Description:
- The master thesis
License bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- license.txt
- Size:
- 1.71 KB
- Format:
- Item-specific license agreed upon to submission
- Description: