EUVIMEDEUVIMED entdecken
Crossref

Linear-Space Data Structures for Range Mode Query in Arrays

Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison, Bryan T. Wilkinson

Theory of Computing Systems · 2014-11 · 55 (4) · 719-741

DOI: 10.1007/s00224-013-9455-2 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Theory of Computing Systems, online erschienen am 08.03.2013. Verfasst von Timothy M. Chan und 4 weiteren Autor:innen. Die Arbeit wurde bisher 18-mal zitiert (Crossref) und nennt 62 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A mode of a multiset S is an element a∈S of maximum multiplicity; that is, a occurs at least as frequently as any other element in S. Given an array A[1:n] of n elements, we consider a basic problem: constructing a static data structure that efficiently answers range mode queries on A. Each query consists of an input pair of indices (i,j) for which a mode of A[i:j] must be returned. The best previous data structure with linear space, by Krizanc, Morin, and Smid (Proceedings of the International Symposium on Algorithms and Computation (ISAAC), pp. 517–526, 2003), requires \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\varTheta (\sqrt{n}\log\log n)$\end{document} query time in the worst case. We improve their result and present an O(n)-space data structure that supports range mode queries in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\sqrt{n/\log n})$\end{document} worst-case time. In the external memory model, we give a linear-space data structure that requires \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\sqrt{n/B})$\end{document} I/Os per query, where B denotes the block size. Furthermore, we present strong evidence that a query time significantly below \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\sqrt{n}$\end{document} cannot be achieved by purely combinatorial techniques; we show that boolean matrix multiplication of two \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\sqrt{n} \times \sqrt{n}$\end{document} matrices reduces to n range mode queries in an array of size O(n). Additionally, we give linear-space data structures for the dynamic problem (queries and updates in near O(n3/4) time), for orthogonal range mode in d dimensions (queries in near O(n1−1/2d) time) and for half-space range mode in d dimensions (queries in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(n^{1-1/d^{2}})$\end{document} time). Finally, we complement our dynamic data structure with a reduction from the multiphase problem, again supporting that we cannot hope for much more efficient data structures.

Zitieren

APA

Chan, T. M., Durocher, S., Larsen, K. G., Morrison, J., & Wilkinson, B. T. (2014). Linear-Space Data Structures for Range Mode Query in Arrays. Theory of Computing Systems, 55(4), 719-741. https://doi.org/10.1007/s00224-013-9455-2

Vancouver

Chan TM, Durocher S, Larsen KG, Morrison J, Wilkinson BT. Linear-Space Data Structures for Range Mode Query in Arrays. Theory of Computing Systems. 2014;55(4):719-741. doi:10.1007/s00224-013-9455-2

BibTeX
@article{Chan2014,
  author = {Chan, Timothy M. and Durocher, Stephane and Larsen, Kasper Green and Morrison, Jason and Wilkinson, Bryan T.},
  title = {Linear-Space Data Structures for Range Mode Query in Arrays},
  journal = {Theory of Computing Systems},
  year = {2014},
  volume = {55},
  number = {4},
  pages = {719--741},
  doi = {10.1007/s00224-013-9455-2}
}
Kostenlos starten →