Abstract
We consider the orthogonal range search problem: given a point set P in d-dimensional space and an orthogonal query region Q, return some information on \(P\cap Q\). We focus on the counting query to count the number of points of P contained in Q, and the reporting query to enumerate all points of P in Q.
For 2-dimensional case, Bose et al. proposed a space-efficient data structure supporting the counting query in \(\mathrm {O}\mathord {\left(\lg n/\lg \lg n\right)}\) time and the reporting query in \(\mathrm {O}\mathord {\left(k \lg n/\lg \lg n\right)}\) time, where \(n=|P|\) and \(k=|P\cap Q|\). For high-dimensional cases, the KDW-tree [Okajima, Maruyama, ALENEX 2015] and the data structure of [Ishiyama, Sadakane, DCC 2017] have been proposed. These are however not efficient for very large d.
This paper proposes practical space-efficient data structures for the problem. They run fast when the number of dimensions \(d'\) used in queries is smaller than the data dimension d. This kind of queries are typical in database queries.
This work was supported by JST CREST Grant Number JPMJCR1402, Japan.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Although we don’t store C in the root, we consider that the root corresponds to C.
- 2.
Here, we use zero-based indexing.
- 3.
As we mentioned before, we use zero-base indexing here.
- 4.
From now on we call the d dimensions as 0-th dimension to \((d-1)\)-st dimension.
References
Barbay, J., López-Ortiz, A., Lu, T., Salinger, A.: An experimental investigation of set intersection algorithms for text searching. ACM J. Exp. Algorithmics 14, 3.7–3.24 (2009)
Bentley, J.S.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509–517 (1975)
Bentley, J.S.: Decomposable searching problems. Inf. Process. Lett. 8(5), 244–251 (1979)
Bose, P., He, M., Maheshwari, A., Morin, P.: Succinct orthogonal range search structures on a grid with applications to text indexing. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 98–109. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03367-4_9
Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput. 17(3), 427–462 (1988)
Clark, D.: Compact pat trees. PhD thesis, University of Waterloo (1997)
Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pp. 135–143. ACM (1984)
Gagie, T., Navarro, G., Puglisi, S.J.: New algorithms on wavelet trees and applications to information retrieval. Theoret. Comput. Sci. 426, 25–41 (2012)
Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: plug and play with succinct data structures. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 326–337. Springer, Cham (2014). doi:10.1007/978-3-319-07959-2_28
Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 841–850. Society for Industrial and Applied Mathematics (2003)
Ishiyama, K., Sadakane, K.: A succinct data structure for multidimensional orthogonal range searching. In: Proceedings of Data Compression Conference 2017, pp. 270–279. IEEE (to be published, 2017)
Jacobson, G.J.: Succinct static data structures. PhD thesis, Carnegie Mellon University (1988)
Mäkinen, V., Navarro, G.: Position-restricted substring searching. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 703–714. Springer, Heidelberg (2006). doi:10.1007/11682462_64
Navarro, G.: Wavelet trees for all. J. Discrete Algorithms 25, 2–20 (2014)
Okajima, Y., Maruyama, K.: Faster linear-space orthogonal range searching in arbitrary dimensions. In: ALENEX, pp. 82–93. SIAM (2015)
O’Rourke, J., Goodman, J.E.: Handbook of Discrete and Computational Geometry. CRC Press (2004)
Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms (TALG) 3(4), 43 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Ishiyama, K., Sadakane, K. (2017). Practical Space-Efficient Data Structures for High-Dimensional Orthogonal Range Searching. In: Beecks, C., Borutta, F., Kröger, P., Seidl, T. (eds) Similarity Search and Applications. SISAP 2017. Lecture Notes in Computer Science(), vol 10609. Springer, Cham. https://doi.org/10.1007/978-3-319-68474-1_16
Download citation
DOI: https://doi.org/10.1007/978-3-319-68474-1_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-68473-4
Online ISBN: 978-3-319-68474-1
eBook Packages: Computer ScienceComputer Science (R0)