Document Open Access Logo

Synergistic Solutions on MultiSets

Authors Jérémy Barbay, Carlos Ochoa, Srinivasa Rao Satti

PDF
Thumbnail PDF

File

LIPIcs.CPM.2017.31.pdf
  • Filesize: 0.61 MB
  • 14 pages

Document Identifiers

Author Details

Jérémy Barbay
Carlos Ochoa
Srinivasa Rao Satti

Cite As Get BibTex

Jérémy Barbay, Carlos Ochoa, and Srinivasa Rao Satti. Synergistic Solutions on MultiSets. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CPM.2017.31

Abstract

Karp et al. (1988) described Deferred Data Structures for Multisets as "lazy" data structures which partially sort data to support online rank and select queries, with the minimum amount of work in the worst case over instances of size n and number of queries q fixed. Barbay et al. (2016) refined this approach to take advantage of the gaps between the positions hit by the queries (i.e., the structure in the queries). We develop new techniques in order to further refine this approach and take advantage all at once of the structure (i.e., the multiplicities of the elements), some notions of local order (i.e., the number and sizes of runs) and global order (i.e., the number and positions of existing pivots) in the input; and of the structure and order in the sequence of queries. Our main result is a synergistic deferred data structure which outperforms all solutions in the comparison model that take advantage of only a subset of these features. As intermediate results, we describe two new synergistic sorting algorithms, which take advantage of some notions of structure and order (local and global) in the input, improving upon previous results which take advantage only of the structure (Munro and Spira 1979) or of the local order (Takaoka 1997) in the input; and one new multiselection algorithm which takes advantage of not only the order and structure in the input, but also of the structure in the queries.

Subject Classification

Keywords
  • deferred data structure
  • multivariate analysis
  • quick sort
  • select

Metrics

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

References

  1. Peyman Afshani, Jérémy Barbay, and Timothy M. Chan. Instance-optimal geometric algorithms. J. ACM, 64(1):3:1-3:38, March 2017. URL: http://dx.doi.org/10.1145/3046673.
  2. Jérémy Barbay, Ankur Gupta, Srinivasa Rao Satti, and Jonathan Sorenson. Near-optimal online multiselection in internal and external memory. J. Discrete Algorithms, 36:3-17, 2016. URL: http://dx.doi.org/10.1016/j.jda.2015.11.001.
  3. Jérémy Barbay and Gonzalo Navarro. On compressing permutations and adaptive sorting. Theor. Comput. Sci., 513:109-123, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2013.10.019.
  4. Jérémy Barbay and Carlos Ochoa. Synergistic computation of planar maxima and convex hull, 2017. URL: http://arxiv.org/abs/1702.08545.
  5. Jérémy Barbay, Carlos Ochoa, and Srinivasa Rao Satti. Synergistic sorting and deferred data structures on multisets, August 2016. URL: http://arxiv.org/abs/1608.06666.
  6. Jon Louis Bentley and Andrew Chi-Chih Yao. An almost optimal algorithm for unbounded searching. Inf. Process. Lett., 5(3):82-87, 1976. URL: http://dx.doi.org/10.1016/0020-0190(76)90071-5.
  7. Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, and Robert E. Tarjan. Time bounds for selection. J. Comput. Syst. Sci., 7(4):448-461, 1973. URL: http://dx.doi.org/10.1016/S0022-0000(73)80033-9.
  8. Gerth S. Brodal. Finger search trees with constant insertion time. In Howard J. Karloff, editor, Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998), pages 540-549. ACM/SIAM, 1998. URL: http://dl.acm.org/citation.cfm?id=314613.314842.
  9. Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro. Adaptive set intersections, unions, and differences. In David B. Shmoys, editor, Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pages 743-752. ACM/SIAM, 2000. URL: http://dl.acm.org/citation.cfm?id=338219.338634.
  10. David P. Dobkin and J. Ian Munro. Optimal time minimal space selection algorithms. J. ACM, 28(3):454-461, 1981. URL: http://dx.doi.org/10.1145/322261.322264.
  11. Vladimir Estivill-Castro and Derick Wood. A survey of adaptive sorting algorithms. ACM Comput. Surv., 24(4):441-476, 1992. URL: http://dx.doi.org/10.1145/146370.146381.
  12. Charles A. R. Hoare. Algorithm 65: Find. Commun. ACM, 4(7):321-322, 1961. URL: http://dx.doi.org/10.1145/366622.366647.
  13. Kenneth E. Iverson. A Programming Language. John Wiley &Sons, Inc., New York, NY, USA, 1962. URL: http://www.softwarepreservation.org/projects/apl/Books/APROGRAMMING%20LANGUAGE.
  14. Kanela Kaligosi, Kurt Mehlhorn, J. Ian Munro, and Peter Sanders. Towards optimal multiple selection. In Luís Caires, Giuseppe F. Italiano, Luís Monteiro, Catuscia Palamidessi, and Moti Yung, editors, Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming (ICALP 2005), volume 3580 of LNCS, pages 103-114. Springer, 2005. URL: http://dx.doi.org/10.1007/11523468_9.
  15. Richard Karp, Rajeev Motwani, and Prabhakar Raghavan. Deferred data structuring. SIAM J. Comput., 17(5):883-902, 1988. URL: http://dx.doi.org/10.1137/0217055.
  16. Donald E. Knuth. Art of Computer Programming, Volume 3: Sorting and Searching (2nd Edition). Addison-Wesley Professional, April 1998. Google Scholar
  17. Veli Mäkinen and Gonzalo Navarro. Rank and select revisited and extended. Theor. Comput. Sci., 387(3):332-347, 2007. URL: http://dx.doi.org/10.1016/j.tcs.2007.07.013.
  18. Alistair Moffat and Ola Petersson. An overview of adaptive sorting. Aust. Comput. J., 24(2):70-77, 1992. URL: http://50years.acs.org.au/__data/assets/pdf_file/0017/111464/ACJ-V24-N02-199205.pdf.
  19. J. Ian Munro and Philip M. Spira. Sorting and searching in multisets. SIAM J. Comput., 5(1):1-8, 1976. URL: http://dx.doi.org/10.1137/0205001.
  20. Tadao Takaoka. Partial solution and entropy. In Rastislav Královic and Damian Niwiński, editors, Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS 2009), volume 5734 of LNCS, pages 700-711. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-03816-7_59.
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