×

zbMATH — the first resource for mathematics

Succinct orthogonal range search structures on a grid with applications to text indexing. (English) Zbl 1253.68103
Dehne, Frank (ed.) et al., Algorithms and data structures. 11th international symposium, WADS 2009, Banff, Canada, August 21–23, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03366-7/pbk). Lecture Notes in Computer Science 5664, 98-109 (2009).
Summary: We present a succinct representation of a set of \(n\) points on an \(n\times n\) grid using \(n\lg n + o(n\lg n)\) bits to support orthogonal range counting in \(O(\lg n /\lg\lg n)\) time, and range reporting in \(O(k\lg n/\lg\lg n)\) time, where \(k\) is the size of the output. This achieves an improvement on query time by a factor of \(\lg\lg n\) upon the previous result of G. Navarro and V. Mäkinen [Theor. Comput. Sci. 387, No. 3, 332–347 (2007; Zbl 1144.68023)], while using essentially the information-theoretic minimum space. Our data structure not only can be used as a key component in solutions to the general orthogonal range search problem to save storage cost, but also has applications in text indexing. In particular, we apply it to improve two previous space-efficient text indexes that support substring search [Y. F. Chien et al., “Geometric Burrows-Wheeler transform: linking range searching and text indexing”, in: Proceedings of the 2008 IEEE data compression conference, DCC 2008. Los Alamitos: IEEE. 252–261 (2008), http://kuscholarworks.ku.edu/dspace/bitstream/1808/7231/1/CHS08.geometricbw.pdf] and position-restricted substring search [Navarro and Mäkinen, loc. cit.]. We also use it to extend previous results on succinct representations of sequences of small integers, and to design succinct data structures supporting certain types of orthogonal range query in the plane.
For the entire collection see [Zbl 1173.68007].

MSC:
68P05 Data structures
68P10 Searching and sorting
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Mäkinen, V., Navarro, G.: Rank and select revisited and extended. Theor. Comput. Sci. 387, 332–347 (2007) · Zbl 1144.68023 · doi:10.1016/j.tcs.2007.07.013
[2] Chien, Y.F., Hon, W.K., Shah, R., Vitter, J.S.: Geometric burrows-wheeler transform: Linking range searching and text indexing. In: DCC, pp. 252–261 (2008)
[3] Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: STOC, pp. 135–143 (1984) · doi:10.1145/800057.808675
[4] Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM Journal on Computing 17(3), 427–462 (1988) · Zbl 0679.68074 · doi:10.1137/0217026
[5] Overmars, M.H.: Efficient data structures for range searching on a grid. Journal of Algorithms 9(2), 254–275 (1988) · Zbl 0637.68067 · doi:10.1016/0196-6774(88)90041-7
[6] Alstrup, S., Brodal, G.S., Rauhe, T.: New data structures for orthogonal range searching. In: FOCS, pp. 198–207 (2000) · doi:10.1109/SFCS.2000.892088
[7] Nekrich, Y.: Orthogonal range searching in linear and almost-linear space. Computational Geometry: Theory and Applications 42(4), 342–351 (2009) · Zbl 1170.68012 · doi:10.1016/j.comgeo.2008.09.001
[8] Jacobson, G.: Space-efficient static trees and graphs. In: FOCS, pp. 549–554 (1989) · doi:10.1109/SFCS.1989.63533
[9] Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms 3(4), 43 (2007) · Zbl 1446.68046 · doi:10.1145/1290672.1290680
[10] Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: SODA, pp. 841–850 (2003) · Zbl 1092.68584
[11] Barbay, J., Golynski, A., Munro, J.I., Rao, S.S.: Adaptive searching in succinctly encoded binary relations and tree-structured documents. Theoretical Computer Science 387(3), 284–297 (2007) · Zbl 1144.68014 · doi:10.1016/j.tcs.2007.07.015
[12] Barbay, J., He, M., Munro, J.I., Rao, S.S.: Succinct indexes for strings, binary relations and multi-labeled trees. In: SODA, pp. 680–689 (2007) · Zbl 1302.68097
[13] Geary, R.F., Raman, R., Raman, V.: Succinct ordinal trees with level-ancestor queries. ACM Transactions on Algorithms 2(4), 510–534 (2006) · Zbl 1321.68223 · doi:10.1145/1198513.1198516
[14] Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Structuring labeled trees for optimal succinctness, and beyond. In: FOCS, pp. 184–196 (2005) · doi:10.1109/SFCS.2005.69
[15] Ferragina, P., Manzini, G., Mäkinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Trans. Alg. 3(2), 20 (2007) · Zbl 1321.68263 · doi:10.1145/1240233.1240243
[16] Bauernöppel, F., Kranakis, E., Krizanc, D., Maheshwari, A., Sack, J.R., Urrutia, J.: Planar stage graphs: Characterizations and applications. Theoretical Computer Science 175(2), 239–255 (1997) · Zbl 0903.68140 · doi:10.1016/S0304-3975(96)00201-0
[17] Clark, D.R., Munro, J.I.: Efficient suffix trees on secondary storage. In: SODA, pp. 383–391 (1996) · Zbl 0847.68030
[18] Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88–94. Springer, Heidelberg (2000) · Zbl 0959.68133 · doi:10.1007/10719839_9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.