Skip to main content
Springer Nature Link
Log in

Space-Efficient Data Structure for Next/Previous Larger/Smaller Value Queries

  • Conference paper
  • First Online:
LATIN 2022: Theoretical Informatics (LATIN 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13568))

Included in the following conference series:

  • 852 Accesses

  • 1 Citation

Abstract

Given an array of size n from a total order, we consider the problem of constructing a data structure that supports various queries (range minimum/maximum queries with their variants and next/previous larger/smaller queries) efficiently. In the encoding model (i.e., the queries can be answered without the input array), we propose a \((3.701n + o(n))\)-bit data structure, which supports all these queries in \(O(\log ^{(\ell )}n)\) time, for any positive integer \(\ell \) (here, \(\log ^{(1)} n = \log n\), and for \(\ell > 1\), \(\log ^{(\ell )} n = \log ({\log ^{(\ell -1)}} n)\)). The space of our data structure matches the current best upper bound of Tsur (Inf. Process. Lett., 2019), which does not support the queries efficiently. Also, we show that at least \(3.16n-\Theta (\log n)\) bits are necessary for answering all the queries. Our result is obtained by generalizing Gawrychowski and Nicholson’s \((3n - \Theta (\log n))\)-bit lower bound (ICALP, 15) for answering range minimum and maximum queries on a permutation of size n.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
€34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 74.89
Price includes VAT (Germany)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 96.29
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

') var buybox = document.querySelector("[data-id=id_"+ timestamp +"]").parentNode var buyingOptions = buybox.querySelectorAll(".buying-option") ;[].slice.call(buyingOptions).forEach(initCollapsibles) var buyboxMaxSingleColumnWidth = 480 function initCollapsibles(subscription, index) { var toggle = subscription.querySelector(".buying-option-price") subscription.classList.remove("expanded") var form = subscription.querySelector(".buying-option-form") var priceInfo = subscription.querySelector(".price-info") var buyingOption = toggle.parentElement if (toggle && form && priceInfo) { toggle.setAttribute("role", "button") toggle.setAttribute("tabindex", "0") toggle.addEventListener("click", function (event) { var expandedBuyingOptions = buybox.querySelectorAll(".buying-option.expanded") var buyboxWidth = buybox.offsetWidth ;[].slice.call(expandedBuyingOptions).forEach(function(option) { if (buyboxWidth buyboxMaxSingleColumnWidth) { toggle.click() } else { if (index === 0) { toggle.click() } else { toggle.setAttribute("aria-expanded", "false") form.hidden = "hidden" priceInfo.hidden = "hidden" } } }) } initialStateOpen() if (window.buyboxInitialised) return window.buyboxInitialised = true initKeyControls() })()

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Throughout the paper, we denote \(\log n\) as the logarithm to the base 2.

  2. 2.

    refer to Table 1 in [13] for detailed definitions of the queries.

References

  1. Baxter, G.: On fixed points of the composite of commuting functions. Proc. Am. Math. Soc. 15(6), 851–855 (1964)

    Article  MathSciNet  MATH  Google Scholar 

  2. Benoit, D., Demaine, E.D., Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Representing trees of higher degree. Algorithmica 43(4), 275–292 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  3. Berkman, O., Schieber, B., Vishkin, U.: Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values. J. Algorithms 14(3), 344–370 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  4. Dodis, Y., Patrascu, M., Thorup, M.: Changing base without losing space. In: STOC 2010, pp. 593–602. ACM (2010)

    Google Scholar 

  5. Ferrada, H., Navarro, G.: Improved range minimum queries. In: 2016 Data Compression Conference, DCC 2016, pp. 516–525. IEEE (2016)

    Google Scholar 

  6. Fischer, J.: Combined data structure for previous- and next-smaller-values. Theor. Comput. Sci. 412(22), 2451–2456 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  7. Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465–492 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  8. Gawrychowski, P., Nicholson, P.K.: Optimal encodings for range top-\(k\), selection, and min-max. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 593–604. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47672-7_48

    Chapter  MATH  Google Scholar 

  9. Jo, S., Satti, S.R.: Simultaneous encodings for range and next/previous larger/smaller value queries. Theor. Comput. Sci. 654, 80–91 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  10. Merlini, D., Sprugnoli, R., Verri, M.C.: Waiting patterns for a printer. Discret. Appl. Math. 144(3), 359–373 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  11. Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762–776 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  12. Munro, J.I., Raman, V., Rao, S.S.: Space efficient suffix trees. J. Algorithms 39(2), 205–222 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  13. Navarro, G., Sadakane, K.: Fully functional static and dynamic succinct trees. ACM Trans. Algorithms 10(3), 16:1–16:39 (2014)

    Google Scholar 

  14. Ohlebusch, E., Fischer, J., Gog, S.: CST++. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol. 6393, pp. 322–333. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16321-0_34

    Chapter  Google Scholar 

  15. Raman, R.: Encoding data structures. In: Rahman, M.S., Tomita, E. (eds.) WALCOM 2015. LNCS, vol. 8973, pp. 1–7. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-15612-5_1

    Chapter  Google Scholar 

  16. Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), 43 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  17. Sadakane, K.: Succinct data structures for flexible text retrieval systems. J. Discrete Algorithms 5(1), 12–22 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  18. Tsur, D.: The effective entropy of next/previous larger/smaller value queries. Inf. Process. Lett. 145, 39–43 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  19. Vuillemin, J.: A unifying look at data structures. Commun. ACM 23(4), 229–239 (1980)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. NRF-2020R1G1A1101477). We would like to thank to Srinivasa Rao Satti for helpful discussions.

Author information

Authors and Affiliations

  1. Chungnam National University, Daejeon, South Korea

    Seungbum Jo

  2. Chungbuk National University, Cheongju, South Korea

    Geunho Kim

Authors
  1. Seungbum Jo
    View author publications

    Search author on:PubMed Google Scholar

  2. Geunho Kim
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Seungbum Jo .

Editor information

Editors and Affiliations

  1. Universidad Nacional Autónoma de México, Mexico City, Mexico

    Armando Castañeda

  2. Centro de investigación y de Estudios Avanzados, Mexico City, Mexico

    Francisco Rodríguez-Henríquez

Rights and permissions

Reprints and permissions

Copyright information

© 2022 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Jo, S., Kim, G. (2022). Space-Efficient Data Structure for Next/Previous Larger/Smaller Value Queries. In: Castañeda, A., Rodríguez-Henríquez, F. (eds) LATIN 2022: Theoretical Informatics. LATIN 2022. Lecture Notes in Computer Science, vol 13568. Springer, Cham. https://doi.org/10.1007/978-3-031-20624-5_5

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-20624-5_5

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-20623-8

  • Online ISBN: 978-3-031-20624-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics