LIPIcs.CPM.2016.3.pdf
- Filesize: 0.57 MB
- 11 pages
Document
Encoding Two-Dimensional Range Top-k Queries
Authors
-
Part of:
Volume:
27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Annual Symposium on Combinatorial Pattern Matching (CPM) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-06-27
Cite As Get BibTex
Seungbum Jo, Rahul Lingala, and Srinivasa Rao Satti. Encoding Two-Dimensional Range Top-k Queries. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 3:1-3:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.CPM.2016.3
Abstract
We consider various encodings that support range top-k queries on a two-dimensional array containing elements from a total order. For an m x n array, we first propose an almost optimal encoding for answering one-sided top-k queries, whose query range is restricted to [1 ... m][1 .. a], for 1 <= a <= n. Next, we propose an encoding for the general top-k queries that takes m^2 * lg(binom((k+1)n)(n)) + m * lg(m) + o(n) bits. This generalizes the one-dimensional top-k encoding of Gawrychowski and Nicholson [ICALP, 2015]. Finally, for a 2 x n array, we obtain a 2 lg(binom(3n)(n)) + 3n + o(n)-bit encoding for answering top-2 queries.
Subject Classification
Keywords
- Encoding model
- top-k query
- range minimum query
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Gerth S. Brodal, Pooya Davoodi, and S. Srinivasa Rao. On space efficient two dimensional range minimum data structures. Algorithmica, 63(4):815-830, 2012. URL: http://dx.doi.org/10.1007/s00453-011-9499-0.
-
Gerth Stølting Brodal, Andrej Brodnik, and Pooya Davoodi. The encoding complexity of two dimensional range minimum data structures. In ESA 2013, 2013. Proceedings, pages 229-240, 2013.
- Gerth Stølting Brodal, Rolf Fagerberg, Mark Greve, and Alejandro López-Ortiz. Online sorted range reporting. In ISAAC 2009, Proceedings, pages 173-182, 2009. URL: http://dx.doi.org/10.1007/978-3-642-10631-6_19.
-
Timothy M. Chan and Bryan T. Wilkinson. Adaptive and approximate orthogonal range counting. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013,2013, pages 241-251, 2013.
-
Greg N. Frederickson. An optimal algorithm for selection in a min-heap. Inf. Comput., 104(2):197-214, 1993.
- Pawel Gawrychowski and Patrick K. Nicholson. Optimal encodings for range top- k k , selection, and min-max. In ICALP 2015, Proceedings, Part I, pages 593-604, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_48.
- Mordecai J. Golin, John Iacono, Danny Krizanc, Rajeev Raman, and S. Srinivasa Rao. Encoding 2d range maximum queries. In ISAAC, pages 180-189, 2011. URL: http://dx.doi.org/10.1007/978-3-642-25591-5_20.
-
Roberto Grossi, John Iacono, Gonzalo Navarro, Rajeev Raman, and Srinivasa Rao Satti. Encodings for range selection and top-k queries. In ESA 2013, pages 553-564, 2013.
-
P. B. Miltersen. Cell probe complexity - a survey. FSTTCS, 1999.
-
Gonzalo Navarro, Rajeev Raman, and Srinivasa Rao Satti. Asymptotically optimal encodings for range selection. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014,2014, pages 291-301, 2014.
-
Rajeev Raman, Venkatesh Raman, and Srinivasa Rao Satti. Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms, 3(4):Article 43, 2007.