Document Open Access Logo

Predecessor on the Ultra-Wide Word RAM

Authors Philip Bille , Inge Li Gørtz , Tord Stordalen

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2022.18.pdf
  • Filesize: 0.75 MB
  • 15 pages

Document Identifiers

Author Details

Philip Bille
  • DTU Compute, Technical University of Denmark, Lyngby, Denmark
Inge Li Gørtz
  • DTU Compute, Technical University of Denmark, Lyngby, Denmark
Tord Stordalen
  • DTU Compute, Technical University of Denmark, Lyngby, Denmark

Funding

  • Bille, Philip: Danish Research Council grant DFF-8021-002498.
  • Gørtz, Inge Li: Danish Research Council grant DFF-8021-002498.

Acknowledgements

We thank the anonymous reviewers for their comments, which improved the presentation of the article.

Cite As Get BibTex

Philip Bille, Inge Li Gørtz, and Tord Stordalen. Predecessor on the Ultra-Wide Word RAM. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SWAT.2022.18

Abstract

We consider the predecessor problem on the ultra-wide word RAM model of computation, which extends the word RAM model with ultrawords consisting of w² bits [TAMC, 2015]. The model supports arithmetic and boolean operations on ultrawords, in addition to scattered memory operations that access or modify w (potentially non-contiguous) memory addresses simultaneously. The ultra-wide word RAM model captures (and idealizes) modern vector processor architectures.
Our main result is a simple, linear space data structure that supports predecessor in constant time and updates in amortized, expected constant time. This improves the space of the previous constant time solution that uses space in the order of the size of the universe. Our result is based on a new implementation of the classic x-fast trie data structure of Willard [Inform. Process. Lett. 17(2), 1983] combined with a new dictionary data structure that supports fast parallel lookups.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • Ultra-wide word RAM model
  • predecessor
  • word-level parallelism

Metrics

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

Related Versions

References

  1. Miklós Ajtai. A lower bound for finding predecessors in Yao’s cell probe model. Comb., 8(3):235-247, 1988. URL: https://doi.org/10.1007/BF02126797.
  2. Arne Andersson. Faster deterministic sorting and searching in linear space. In Proc. 37th FOCS, pages 135-141, 1996. URL: https://doi.org/10.1109/SFCS.1996.548472.
  3. Arne Andersson, Torben Hagerup, Stefan Nilsson, and Rajeev Raman. Sorting in linear time? J. Comput. Syst. Sci., 57(1):74-93, 1998. URL: https://doi.org/10.1006/jcss.1998.1580.
  4. Lars Arge, Paolo Ferragina, Roberto Grossi, and Jeffrey Scott Vitter. On sorting strings in external memory (extended abstract). In Proc. 29th STOC, pages 540-548, 1997. URL: https://doi.org/10.1145/258533.258647.
  5. Paul Beame and Faith E. Fich. Optimal bounds for the predecessor problem and related problems. J. Comput. Syst. Sci., 65(1):38-72, 2002. URL: https://doi.org/10.1006/jcss.2002.1822.
  6. Djamal Belazzougui. Worst-case efficient single and multiple string matching on packed texts in the word-RAM model. J. Discrete Algorithms, 14:91-106, 2012. URL: https://doi.org/10.1016/j.jda.2011.12.011.
  7. Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna. Monotone minimal perfect hashing: searching a sorted table with O(1) accesses. In Proc. 20th SODA, pages 785-794, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496856.
  8. Djamal Belazzougui, Paolo Boldi, and Sebastiano Vigna. Dynamic z-fast tries. In Proc. 17th SPIRE, pages 159-172, 2010. URL: https://doi.org/10.1007/978-3-642-16321-0_15.
  9. Michael A. Bender, Martin Farach-Colton, and Bradley C. Kuszmaul. Cache-oblivious string B-trees. In Proc. 25th PODS, pages 233-242, 2006. URL: https://doi.org/10.1145/1142351.1142385.
  10. Philip Bille, Mikko Berggren Ettienne, Inge Li Gørtz, and Hjalte Wedel Vildhøj. Time-space trade-offs for Lempel-Ziv compressed indexing. Theor. Comput. Sci., 713:66-77, 2018. URL: https://doi.org/10.1016/j.tcs.2017.12.021.
  11. Philip Bille, Inge Li Gørtz, and Frederik Rye Skjoldjensen. Deterministic indexing for packed strings. In Proc. 28th CPM, pages 6:1-6:11, 2017. URL: https://doi.org/10.4230/LIPIcs.CPM.2017.6.
  12. Philip Bille, Inge Li Gørtz, and Frederik Rye Skjoldjensen. Partial sums on the ultra-wide word RAM. Theor. Comput. Sci., 905:99-105, 2022. Announced at TAMC 2020. URL: https://doi.org/10.1016/j.tcs.2022.01.002.
  13. Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti, and Oren Weimann. Random access to grammar-compressed strings and trees. SIAM J. Comput., 44(3):513-539, 2015. URL: https://doi.org/10.1137/130936889.
  14. Andrej Brodnik, Svante Carlsson, Michael L. Fredman, Johan Karlsson, and J. Ian Munro. Worst case constant time priority queue. J. Syst. Softw., 78(3):249-256, 2005. URL: https://doi.org/10.1016/j.jss.2004.09.002.
  15. Thomas Chen, Ram Raghavan, Jason N. Dale, and Eiji Iwata. Cell Broadband engine architecture and its first implementation - A performance view. IBM J. Res. Dev., 51(5):559-572, 2007. URL: https://doi.org/10.1147/rd.515.0559.
  16. Intel Corporation. Intelregistered advanced vector extensions programming reference. Intel Corporation, 2011. Google Scholar
  17. Martin Dietzfelbinger and Friedhelm Meyer auf der Heide. A new universal class of hash functions and dynamic hashing in real time. In Proc. 17th ICALP, pages 6-19, 1990. URL: https://doi.org/10.1007/BFb0032018.
  18. Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen. A reliable randomized algorithm for the closest-pair problem. J. Algorithms, 25(1):19-51, 1997. URL: https://doi.org/10.1006/jagm.1997.0873.
  19. Martin Dietzfelbinger, Anna R. Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, and Robert Endre Tarjan. Dynamic perfect hashing: Upper and lower bounds. SIAM J. Comput., 23(4):738-761, 1994. URL: https://doi.org/10.1137/S0097539791194094.
  20. Martin Farach. Optimal suffix tree construction with large alphabets. In Proc. 38th FOCS, pages 137-143, 1997. URL: https://doi.org/10.1109/SFCS.1997.646102.
  21. Arash Farzan, Alejandro López-Ortiz, Patrick K. Nicholson, and Alejandro Salinger. Algorithms in the ultra-wide word model. In Proc. 12th TAMC, pages 335-346, 2015. URL: https://doi.org/10.1007/978-3-319-17142-5_29.
  22. Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table with O(1) worst case access time. J. ACM, 31(3):538-544, 1984. URL: https://doi.org/10.1145/828.1884.
  23. Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci., 47(3):424-436, 1993. URL: https://doi.org/10.1016/0022-0000(93)90040-4.
  24. Torben Hagerup. Sorting and searching on the word RAM. In Proc. 15th STACS, pages 366-398, 1998. URL: https://doi.org/10.1007/BFb0028575.
  25. Yijie Han. Deterministic sorting in O(nlog log n) time and linear space. J. Algorithms, 50(1):96-105, 2004. URL: https://doi.org/10.1016/j.jalgor.2003.09.001.
  26. Kasper Green Larsen and Rasmus Pagh. I/O-efficient data structures for colored range and prefix reporting. In Proc. 23rd SODA, pages 583-592, 2012. URL: https://doi.org/10.1137/1.9781611973099.49.
  27. R. Leben, M. Miletic, M. Spegel, A. Torst, A. Brodnik, and K. Karlsson. Design of high performance memory module on PC100. In Proc. Electrotechnical and Computer Science Conference (ERK), pages 75-78, 1999. Google Scholar
  28. Peter Bro Miltersen. Lower bounds for union-split-find related problems on random access machines. In Proc. 26th STOC, pages 625-634, 1994. URL: https://doi.org/10.1145/195058.195415.
  29. Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On data structures and asymmetric communication complexity. J. Comput. Syst. Sci., 57(1):37-49, 1998. URL: https://doi.org/10.1006/jcss.1998.1577.
  30. Gonzalo Navarro and Javiel Rojas-Ledesma. Predecessor search. ACM Comput. Surv., 53(5):105:1-105:35, 2020. URL: https://doi.org/10.1145/3409371.
  31. Mihai Pătraşcu and Mikkel Thorup. Time-space trade-offs for predecessor search. In Proc. 38th STOC, pages 232-240, 2006. URL: https://doi.org/10.1145/1132516.1132551.
  32. Mihai Pătraşcu and Mikkel Thorup. Randomization does not help searching predecessors. In Proc. 18th SODA, pages 555-564, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283443.
  33. Mihai Pătraşcu and Mikkel Thorup. Dynamic integer sets with optimal rank, select, and predecessor search. In Proc. 55th FOCS, pages 166-175, 2014. URL: https://doi.org/10.1109/FOCS.2014.26.
  34. James Reinders. Intelregistered AVX-512 instructions. Intelregistered Corporation, 2013. Google Scholar
  35. Pranab Sen and Srinivasan Venkatesh. Lower bounds for predecessor searching in the cell probe model. J. Comput. Syst. Sci., 74(3):364-385, 2008. URL: https://doi.org/10.1016/j.jcss.2007.06.016.
  36. Nigel Stephens, Stuart Biles, Matthias Boettcher, Jacob Eapen, Mbou Eyole, Giacomo Gabrielli, Matt Horsnell, Grigorios Magklis, Alejandro Martinez, Nathanaël Prémillieu, Alastair Reid, Alejandro Rico, and Paul Walker. The ARM scalable vector extension. IEEE Micro, 37(2):26-39, 2017. URL: https://doi.org/10.1109/MM.2017.35.
  37. Peter van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Inform. Process. Lett., 6(3):80-82, 1977. URL: https://doi.org/10.1016/0020-0190(77)90031-X.
  38. Peter van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Math. Syst. Theory, 10:99-127, 1977. URL: https://doi.org/10.1007/BF01683268.
  39. Dan E. Willard. Log-logarithmic worst-case range queries are possible in space Θ(N). Inform. Process. Lett., 17(2):81-84, 1983. URL: https://doi.org/10.1016/0020-0190(83)90075-3.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact