Abstract
We consider data structures and algorithms for preprocessing a labelled list of length n so that, for any given indices i and j we can answer queries of the form: What is the mode or median label in the sequence of labels between indices i and j. Our results are on approximate versions of this problem. Using \(O(\frac{n}{1-\alpha})\) space, our data structure can find in \(O({\rm log}{\rm log}_\frac{1}{\alpha} n)\) time an element whose number of occurrences is at least α times that of the mode, for some user-specified parameter 0 < α< 1. Data structures are proposed to achieve constant query time for α=1/2,1/3 and 1/4, using storage space of O(n log n), O(n log log n) and O(n), respectively. Finally, if the elements are comparable, we construct an \(O(\frac{n}{1-\alpha})\) space data structure that answers approximate range median queries. Specifically, given indices i and j, in O(1) time, an element whose rank is at least \(\alpha \times \lfloor|j-i+1|/2\rfloor\) and at most \((2-\alpha)\times\lfloor|j-i+1|/2\rfloor\) is returned for 0 < α< 1.
This work is supported in part by NSERC (Natural Sciences and Engineering Research Council of Canada) and MITACS (Mathematics of Information Technology and Complex Systems) grants.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alon, N., Schieber, B.: Optimal preprocessing for answering on-line product queries. Technical Report 71/87, Tel-Aviv University (1987)
Arasu, A., Manku, G.S.: Approximate counts and quantiles over sliding windows. In: Proceedings of the ACM Symposium on Principles of Database Systems, PODS (2004)
Battiato, S., Cantone, D., Catalano, D., Cincotti, G., Hofri, M.: An efficient algorithm for the approximate median selection problem. In: Proceedings of the Fourth Italian Conference (2000)
Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proceedings of the 15th annual ACM Symposium on the Theory of Computing, pp. 80–86 (1983)
Blum, M., Floyd, R.W., Pratt, V., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. Journal of Computer and System Sciences 7(4), 448–461 (1973)
Datar, M., Gionis, A., Indyk, P., Motwani, R.: Maintaining stream statistics over sliding windows. SIAM Journal of Computing 31(6), 1794–1813 (2002)
Demaine, E.D., Lópex-Ortiz, A., Munro, J.I.: Frequency estimation of internet packet streams with limited space. In: Proceedings of the 10th Annual European Symposium on Algorithms, pp. 348–360 (2002)
Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. Journal of Computer and System Sciences 38(1), 86–124 (1989)
Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences 30(2), 209–221 (1985)
Krizanc, D., Morin, P., Smid, M.: Range mode and range median queries on lists and trees. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 517–526. Springer, Heidelberg (2003)
Lin, X., Liu, H., Xu, J., Yu, J.X.: Continuously maintaining quantile summaries of the most recent n elements over a data stream. In: Proceedings of the 20th International Conference on Data Engineering (2004)
Manku, G.S., Rajagopalan, S., Lindsay, B.: Approximate median and other quantiles in one pass and with limited memory. In: Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, pp. 426–435 (1998)
Yao, A.C.: Space-time tradeoff for answering range queries. In: Proceedings of the 14th annual ACM Symposium on the Theory of Computing, pp. 128–136 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bose, P., Kranakis, E., Morin, P., Tang, Y. (2005). Approximate Range Mode and Range Median Queries. In: Diekert, V., Durand, B. (eds) STACS 2005. STACS 2005. Lecture Notes in Computer Science, vol 3404. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31856-9_31
Download citation
DOI: https://doi.org/10.1007/978-3-540-31856-9_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24998-6
Online ISBN: 978-3-540-31856-9
eBook Packages: Computer ScienceComputer Science (R0)