Efficient Data Structures for Range Selections Problem

Abstract:

Building an efficient data structure for range selection problems is considered. While there are several theoretical solutions to the problem, only a few have been tried out, and there is little idea on how the others would perform. The computation model used in this paper is the RAM model with word-size . Our data structure is a practical linear space data structure that supports range selection queries in time with preprocessing time.

• Periodical: Advanced Materials Research (Volumes 756-759)
• Pages: 1387-1391
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.756-759.1387
• Online since: September 2013
• Authors: Xiao Dong Wang, Jun Tian
• Keywords: Data Structure, RAM Model, Range Selection

References

[1] M. J. Atallah and H. Yuan, Data structures for range minimum queries in multidimensional arrays, In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 150-160, (2010).

DOI: 10.1137/1.9781611973075.14

[2] G. S. Brodal and A. G. Jorgensen, Data structures for range median queries, In Proceedings of the 20th International Symposium on Algorithms and Computation, 822-831, (2009).

DOI: 10.1007/978-3-642-10631-6_83

[3] M. Chan, Persistent predecessor search and orthogonal point location in the word RAM, In Proceedings of the 22nd ACM/SIAM Symposium on Discrete Algorithms (SODA), 1131-1145, (2011).

DOI: 10.1137/1.9781611973082.85

[4] B. Gfeller and P. Sanders. Towards optimal range medians. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming, 475-486, (2009).

DOI: 10.1007/978-3-642-02927-1_40

[5] D. Krizanc, P. Morin, and M. H. M. Smid, Range mode and range median queries on lists and trees. Nordic Journal of Computing, 12(1): 1-17, (2005).

DOI: 10.1007/978-3-540-24587-2_53

[6] Kasper Green Larsen, The cell probe complexity of dynamic range counting, In Proceedings 44th ACM Symposium on Theory of Computing (STOC), (2012).

[7] H. Petersen, Improved bounds for range mode and range median queries, In Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science , 418-423, (2008).

DOI: 10.1007/978-3-540-77566-9_36

[8] H. Petersen and S. Grabowski, Range mode and range median queries in constant time and sub-quadratic space, Information Processing Letters, 109(4): 225-228, (2008).

DOI: 10.1016/j.ipl.2008.10.007

[9] D. E. Willard, Log-logarithmic worst-case range queries are possible in space Theta(n), Information Processing Letters, 17(2): 81-84, (1983).

DOI: 10.1016/0020-0190(83)90075-3