Abstract
We consider range queries in arrays that search for low-frequency elements: least frequent elements and α-minorities. An α-minority of a query range has multiplicity no greater than an α fraction of the elements in the range. Our data structure for the least frequent element range query problem requires O(n) space, O(n 3/2) preprocessing time, and \(O(\sqrt{n})\) query time. A reduction from boolean matrix multiplication to this problem shows the hardness of simultaneous improvements in both preprocessing time and query time. Our data structure for the α-minority range query problem requires O(n) space, supports queries in O(1/α) time, and allows α to be specified at query time.
Work supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC).
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
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)
Bose, P., An, H.-C., Morin, P., Tang, Y.: Approximate Range Mode and Range Median Queries. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 377–388. Springer, Heidelberg (2005)
Brodal, G.S., Gfeller, B., Jørgensen, A.G., Sanders, P.: Towards optimal range medians. Theor. Comp. Sci. 412(24), 2588–2601 (2011)
Chan, T.M.: Persistent predecessor search and orthogonal point location on the word RAM. In: Proc. ACM-SIAM SODA, pp. 1131–1145 (2011)
Chan, T.M., Durocher, S., Larsen, K.G., Morrison, J., Wilkinson, B.T.: Linear-space data structures for range mode query in arrays. In: Proc. STACS, vol. 14, pp. 291–301 (2012)
Chazelle, B.: Filtering search: A new approach to query-answering. SIAM J. Comp. 15(3), 703–724 (1986)
Demaine, E.D., Landau, G.M., Weimann, O.: On Cartesian Trees and Range Minimum Queries. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 341–353. Springer, Heidelberg (2009)
Durocher, S.: A simple linear-space data structure for constant-time range minimum query. CoRR, abs/1109.4460 (2011)
Durocher, S., He, M., Munro, J.I., Nicholson, P.K., Skala, M.: Range Majority in Constant Time and Linear Space. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 244–255. Springer, Heidelberg (2011)
Elmasry, A., He, M., Munro, J.I., Nicholson, P.K.: Dynamic Range Majority Data Structures. In: Asano, T., Nakano, S.-I., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 150–159. Springer, Heidelberg (2011)
Gagie, T., He, M., Munro, J.I., Nicholson, P.K.: Finding Frequent Elements in Compressed 2D Arrays and Strings. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds.) SPIRE 2011. LNCS, vol. 7024, pp. 295–300. Springer, Heidelberg (2011)
Gagie, T., Puglisi, S.J., Turpin, A.: Range Quantile Queries: Another Virtue of Wavelet Trees. In: Karlgren, J., Tarhio, J., Hyyrö, H. (eds.) SPIRE 2009. LNCS, vol. 5721, pp. 1–6. Springer, Heidelberg (2009)
Greve, M., Jørgensen, A.G., Larsen, K.D., Truelsen, J.: Cell Probe Lower Bounds and Approximations for Range Mode. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part I. LNCS, vol. 6198, pp. 605–616. Springer, Heidelberg (2010)
Jørgensen, A.G., Larsen, K.D.: Range selection and median: Tight cell probe lower bounds and adaptive data structures. In: Proc. ACM-SIAM SODA, pp. 805–813 (2011)
Karpinski, M., Nekrich, Y.: Searching for frequent colors in rectangles. In: Proc. CCCG, pp. 11–14 (2008)
Krizanc, D., Morin, P., Smid, M.: Range mode and range median queries on lists and trees. Nordic J. Computing 12, 1–17 (2005)
Petersen, H.: Improved Bounds for Range Mode and Range Median Queries. In: Geffert, V., Karhumäki, J., Bertoni, A., Preneel, B., Návrat, P., Bieliková, M. (eds.) SOFSEM 2008. LNCS, vol. 4910, pp. 418–423. Springer, Heidelberg (2008)
Petersen, H., Grabowski, S.: Range mode and range median queries in constant time and sub-quadratic space. Inf. Proc. Let. 109, 225–228 (2009)
Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: Proc. ACM-SIAM SODA, pp. 134–149 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chan, T.M., Durocher, S., Skala, M., Wilkinson, B.T. (2012). Linear-Space Data Structures for Range Minority Query in Arrays. In: Fomin, F.V., Kaski, P. (eds) Algorithm Theory – SWAT 2012. SWAT 2012. Lecture Notes in Computer Science, vol 7357. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31155-0_26
Download citation
DOI: https://doi.org/10.1007/978-3-642-31155-0_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31154-3
Online ISBN: 978-3-642-31155-0
eBook Packages: Computer ScienceComputer Science (R0)