Encoding Two-Dimensional Range Top-k Queries Revisited

Authors Seungbum Jo , Srinivasa Rao Satti



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.69.pdf
  • Filesize: 495 kB
  • 13 pages

Document Identifiers

Author Details

Seungbum Jo
  • University of Siegen, Germany
Srinivasa Rao Satti
  • Seoul National University, South Korea

Cite AsGet BibTex

Seungbum Jo and Srinivasa Rao Satti. Encoding Two-Dimensional Range Top-k Queries Revisited. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 69:1-69:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.69

Abstract

We consider the problem of encoding two-dimensional arrays, whose elements come from a total order, for answering Top-k queries. The aim is to obtain encodings that use space close to the information-theoretic lower bound, which can be constructed efficiently. For 2 x n arrays, we first give upper and lower bounds on space for answering sorted and unsorted 3-sided Top-k queries. For m x n arrays, with m <=n and k <=mn, we obtain (m lg{(k+1)n choose n}+4nm(m-1)+o(n))-bit encoding for answering sorted 4-sided Top-k queries. This improves the min{(O(mn lg{n}),m^2 lg{(k+1)n choose n} + m lg{m}+o(n))}-bit encoding of Jo et al. [CPM, 2016] when m = o(lg{n}). This is a consequence of a new encoding that encodes a 2 x n array to support sorted 4-sided Top-k queries on it using an additional 4n bits, in addition to the encodings to support the Top-k queries on individual rows. This new encoding is a non-trivial generalization of the encoding of Jo et al. [CPM, 2016] that supports sorted 4-sided Top-2 queries on it using an additional 3n bits. We also give almost optimal space encodings for 3-sided Top-k queries, and show lower bounds on encodings for 3-sided and 4-sided Top-k queries.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data compression
Keywords
  • Encoding model
  • top-k query
  • range minimum query

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Omer Berkman and Uzi Vishkin. Recursive Star-Tree Parallel Data Structure. SIAM J. Comput., 22(2):221-242, 1993. URL: http://dx.doi.org/10.1137/0222017.
  2. Gerth Stølting Brodal, Andrej Brodnik, and Pooya Davoodi. The Encoding Complexity of Two Dimensional Range Minimum Data Structures. In Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, pages 229-240, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40450-4_20.
  3. Gerth Stølting 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.
  4. Pooya Davoodi, Gonzalo Navarro, Rajeev Raman, and S. Srinivasa Rao. Encoding range minima and range top-2 queries. Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 372(2016), 2014. URL: http://dx.doi.org/10.1098/rsta.2013.0131.
  5. Johannes Fischer and Volker Heun. Finding Range Minima in the Middle: Approximations and Applications. Mathematics in Computer Science, 3(1):17-30, 2010. URL: http://dx.doi.org/10.1007/s11786-009-0007-8.
  6. Pawel Gawrychowski and Patrick K. Nicholson. Encodings of Range Maximum-Sum Segment Queries and Applications. In Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 - July 1, 2015, Proceedings, pages 196-206, 2015. URL: http://dx.doi.org/10.1007/978-3-319-19929-0_17.
  7. Pawel Gawrychowski and Patrick K. Nicholson. Optimal Encodings for Range Top-k k , Selection, and Min-Max. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 593-604, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_48.
  8. Mordecai J. Golin, John Iacono, Danny Krizanc, Rajeev Raman, Srinivasa Rao Satti, and Sunil M. Shende. Encoding 2D range maximum queries. Theor. Comput. Sci., 609:316-327, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2015.10.012.
  9. Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter. High-order entropy-compressed text indexes. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA., pages 841-850, 2003. URL: http://dl.acm.org/citation.cfm?id=644108.644250.
  10. Roberto Grossi, John Iacono, Gonzalo Navarro, Rajeev Raman, and S. Srinivasa Rao. Asymptotically Optimal Encodings of Range Data Structures for Selection and Top-k Queries. ACM Trans. Algorithms, 13(2):28:1-28:31, 2017. URL: http://dx.doi.org/10.1145/3012939.
  11. 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, June 27-29, 2016, Tel Aviv, Israel, pages 3:1-3:11, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.CPM.2016.3.
  12. Seungbum Jo and Srinivasa Rao Satti. Encoding two-dimensional range top-k queries revisited. CoRR, abs/1809.07067, 2018. URL: http://arxiv.org/abs/1809.07067.
  13. N.D Kazarinoff. Geometric inequalities. New York: Random House, 1961. Google Scholar
  14. P. B. Miltersen. Cell probe complexity - a survey. FSTTCS, 1999. Google Scholar
  15. J. Ian Munro and Venkatesh Raman. Succinct Representation of Balanced Parentheses and Static Trees. SIAM J. Comput., 31(3):762-776, 2001. URL: http://dx.doi.org/10.1137/S0097539799364092.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail