License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.54
URN: urn:nbn:de:0030-drops-129202
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12920/
Gao, Younan ;
He, Meng ;
Nekrich, Yakov
Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing
Abstract
Under the word RAM model, we design three data structures that can be constructed in O(n √{lg n}) time over n points in an n × n grid. The first data structure is an O(n lg^ε n)-word structure supporting orthogonal range reporting in O(lg lg n+k) time, where k denotes output size and ε 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^ε n)-word structure supporting sorted range reporting in O(lg lg n+k) 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 √{lg n}) construction time beats the previous bounds on preprocessing. Previously, among 2d range search structures, only the orthogonal range counting structure of Chan and Pǎtraşcu (SODA 2010) and the linear space, O(lg^ε n) query time structure for orthogonal range successor by Belazzougui and Puglisi (SODA 2016) can be built in the same O(n √{lg n}) time. Hence our work is the first that achieve the same preprocessing time for optimal orthogonal range reporting and range successor. We also apply our results to improve the construction time of text indexes.
BibTeX - Entry
@InProceedings{gao_et_al:LIPIcs:2020:12920,
author = {Younan Gao and Meng He and Yakov Nekrich},
title = {{Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {54:1--54:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-162-7},
ISSN = {1868-8969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12920},
URN = {urn:nbn:de:0030-drops-129202},
doi = {10.4230/LIPIcs.ESA.2020.54},
annote = {Keywords: orthogonal range search, geometric data structures, orthogonal range reporting, orthogonal range successor, sorted range reporting, text indexing, word RAM}
}
|
Keywords: |
|
orthogonal range search, geometric data structures, orthogonal range reporting, orthogonal range successor, sorted range reporting, text indexing, word RAM |
|
Collection: |
|
28th Annual European Symposium on Algorithms (ESA 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
26.08.2020 |
