×

zbMATH — the first resource for mathematics

Low space data structures for geometric range mode query. (English) Zbl 1315.68113
Summary: Let \(\mathcal{S}\) be a set of \(n\) points in \(d\) dimensions such that each point is assigned a color. Given a query range \(\mathcal{Q} = [a_1, b_1] \times [a_2, b_2] \times \ldots \times [a_d, b_d]\), the geometric range mode query problem asks to report the most frequent color (i.e., a mode) of the multiset of colors corresponding to points in \(\mathcal{S} \cap \mathcal{Q}\). When \(d = 1\), T. M. Chan et al. [LIPICS – Leibniz Int. Proc. Inform. 14, 290–301 (2012; Zbl 1245.68071)] gave a data structure that requires \(O(n +(n / {\Delta})^2 / w)\) words and supports range mode queries in \(O({\Delta})\) time for any \({\Delta} \geq 1\), where \(w = {\Omega}(\log n)\) is the word size. Chan et al. also proposed a data structures for higher dimensions (i.e., \(d \geq 2\)) with \(O(s_n +(n / {\Delta})^{2 d})\) words and \(O({\Delta} \cdot t_n)\) query time, where \(s_n\) and \(t_n\) denote the space and query time of a data structure that supports orthogonal range counting queries on the set \(\mathcal{S}\). In this paper we show that the space can be improved without any increase to the query time, by presenting an \(O(s_n +(n/{\Delta})^{2 d} / w)\)-word data structure that supports orthogonal range mode queries on a set of \(n\) points in \(d\) dimensions in \(O({\Delta} \cdot t_n)\) time, for any \({\Delta} \geq 1\). When \(d = 1\), these space and query time costs match those achieved by the current best known one-dimensional data structure.

MSC:
68P05 Data structures
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chan, T. M.; Durocher, S.; Larsen, K. G.; Morrison, J.; Wilkinson, B. T., Linear-space data structures for range mode query in arrays, (Proc. STACS, Leibniz International Proceedings in Informatics, vol. 14, (2012)), 291-301 · Zbl 1245.68071
[2] Durocher, S.; El-Zein, H.; Munro, J. I.; Thankachan, S. V., Low space data structures for geometric range mode query, (Proc. CCCG, (2014), Springer Berlin), 212-215
[3] Chan, T. M.; Durocher, S.; Larsen, K. G.; Morrison, J.; Wilkinson, B. T., Linear-space data structures for range mode query in arrays, Theory Comput. Syst., 1-23, (2013)
[4] Krizanc, D.; Morin, P.; Smid, M., Range mode and range Median queries on lists and trees, Nordic J. Comput., 12, 1, 1-17, (2005) · Zbl 1083.68028
[5] Petersen, H.; Grabowski, S., Range mode and range Median queries in constant time and sub-quadratic space, Inform. Process. Lett., 109, 4, 225-228, (2009) · Zbl 1191.68343
[6] Petersen, H., Improved bounds for range mode and range Median queries, (Proc. SOFSEM, LNCS, vol. 4910, (2008), Springer), 418-423 · Zbl 1132.68426
[7] Greve, M.; Jørgensen, A. G.; Larsen, K. D.; Truelsen, J., Cell probe lower bounds and approximations for range mode, (Proc. ICALP, LNCS, vol. 6198, (2010), Springer), 605-616 · Zbl 1288.68046
[8] Bose, P.; Kranakis, E.; Morin, P.; Tang, Y., Approximate range mode and range Median queries, (Proc. STACS, LNCS, vol. 3404, (2005), Springer), 377-388 · Zbl 1118.68441
[9] Chan, T. M.; Durocher, S.; Skala, M.; Wilkinson, B. T., Linear-space data structures for range minority query in arrays, (Proc. SWAT, LNCS, vol. 7357, (2012), Springer), 295-306 · Zbl 1318.68068
[10] Durocher, S.; Shah, R.; Skala, M.; Thankachan, S. V., Linear-space data structures for range frequency queries on arrays and trees, (Proc. MFCS, LNCS, vol. 8087, (2013), Springer), 325-336 · Zbl 1400.68062
[11] Skala, M., Array range queries, (Proc. Space-Efficient Data Structures, Streams, and Algorithms, LNCS, vol. 8066, (2013), Springer), 333-350 · Zbl 1394.68103
[12] JáJá, J.; Mortensen, C. W.; Shi, Q., Space-efficient and fast algorithms for multidimensional dominance reporting and counting, (Proc. ISAAC, LNCS, vol. 3341, (2005), Springer), 558-568 · Zbl 1116.68629
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.