Document Open Access Logo

Permuting and Batched Geometric Lower Bounds in the I/O Model

Authors Peyman Afshani, Ingo van Duijn

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.2.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Author Details

Peyman Afshani
Ingo van Duijn

Cite As Get BibTex

Peyman Afshani and Ingo van Duijn. Permuting and Batched Geometric Lower Bounds in the I/O Model. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.2

Abstract

We study permuting and batched orthogonal geometric reporting problems in the External Memory Model (EM), assuming indivisibility of the input records.
Our main results are twofold. First, we prove a general simulation result that essentially shows that any permutation algorithm (resp. duplicate removal algorithm) that does alpha*N/B I/Os (resp. to remove a fraction of the existing duplicates) can be simulated with an algorithm that does alpha phases where each phase reads and writes each element once, but using a factor alpha smaller block size. 

Second, we prove two lower bounds for batched rectangle stabbing and batched orthogonal range reporting queries. Assuming a short cache, we prove very high lower bounds that currently are not possible with the existing techniques under the tall cache assumption.

Subject Classification

Keywords
  • I/O Model
  • Batched Geometric Queries
  • Lower Bounds
  • Permuting

Metrics

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

References

  1. Peyman Afshani. Improved pointer machine and I/O lower bounds for simplex range reporting and related problems. In Symposium on Computational Geometry (SoCG), pages 339-346, 2012. Google Scholar
  2. Peyman Afshani, Lars Arge, and Kasper Dalgaard Larsen. Orthogonal range reporting in three and higher dimensions. In Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 149-158, 2009. Google Scholar
  3. Peyman Afshani, Lars Arge, and Kasper Dalgaard Larsen. Orthogonal range reporting: query lower bounds, optimal structures in 3-d, and higher-dimensional improvements. In Symposium on Computational Geometry (SoCG), pages 240-246, 2010. Google Scholar
  4. Peyman Afshani, Gerth Stolting Brodal, and Norbert Zeh. Ordered and unordered top-k range reporting in large data sets. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 390-400, 2011. Google Scholar
  5. Peyman Afshani and Nodari Sitchinava. I/O-efficient range minima queries. In Scandinavian Workshop on Algorithms Theory, pages 1-12, 2014. Google Scholar
  6. Peyman Afshani and Norbert Zeh. Lower bounds for sorted geometric queries in the I/O model. In ESA 12: Proceedings of the 20th Annual European Symposium, pages 48-59, 2012. Google Scholar
  7. Alok Aggarwal and Jeffrey Scott Vitter. The input/output complexity of sorting and related problems. Communications of the ACM (CACM), 31(9):1116-1127, 1988. Google Scholar
  8. L. Arge. External memory data structures. In J. Abello, P. M. Pardalos, and M. G. C. Resende, editors, Handbook of Massive Data Sets, pages 313-358. Kluwer Academic Publishers, 2002. Google Scholar
  9. Lars Arge. Efficient external-memory data structures and applications. PhD thesis, Aarhus University, 1996. Google Scholar
  10. Lars Arge. The buffer tree: A technique for designing batched external data structures. Algorithmica, 37(1):1-24, 2003. Google Scholar
  11. Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, and Jeffrey Scott Vitter. Theory and practice of I/O efficient algorithms for multidimensional batched searching problems. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 685-694, 1998. Google Scholar
  12. Lars Arge, Vasilis Samoladas, and Ke Yi. Optimal external-memory planar point enclosure. In Proceedings of European Symposium on Algorithms (ESA), pages 40-52, 2004. Google Scholar
  13. Lars Arge, Darren Erik Vengroff, and Jeffrey Scott Vitter. External-memory algorithms for processing line segments in geographic information systems. In Proceedings of European Symposium on Algorithms (ESA), pages 295-310. Springer, 1995. Google Scholar
  14. Bernard Chazelle. Lower bounds for orthogonal range searching: I. the reporting case. Journal of the ACM (JACM), 37(2):200-212, 1990. Google Scholar
  15. Yi-Jen Chiang, Michael T. Goodrich, Edward F. Grove, Roberto Tamassia, Darren Erik Vengroff, and Jeffrey Scott Vitter. External-memory graph algorithms. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 139-149, 1995. Google Scholar
  16. T. H. Cormen. Fast permuting on disk arrays. Journal of Parallel and Distributed Computing, 17(1):41-57, 1993. Google Scholar
  17. Andreas Crauser, Paolo Ferragina, Kurt Mehlhorn, Ulrich Meyer, and Edgar A Ramos. I/O-optimal computation of segment intersections. External Memory Algorithms and Visualization, pages 131-138, 1999. Google Scholar
  18. Andreas Crauser, Paolo Ferragina, Kurt Mehlhorn, Ulrich Meyer, and Edgar A. Ramos. Randomized external-memory algorithms for line segment intersection and other geometric problems. International Journal of Computational Geometry &Applications, 11(03):305-337, 2001. Google Scholar
  19. Robert W. Floyd. Permuting information in idealized two-level storage. In Complexity of computer computations, pages 105-109. Springer, 1972. Google Scholar
  20. Michael T. Goodrich, Jyh-Jong Tsay, Darren Erik Vengroff, and Jeffrey Scott Vitter. External-memory computational geometry. In Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 714-723, 1993. Google Scholar
  21. Gero Griener. Sparse Matrix Computations and their I/O Complexity. PhD thesis, Technische Universität München, 2012. Google Scholar
  22. Joseph M. Hellerstein, Elias Koutsoupias, Daniel P. Miranker, Christos H. Papadimitriou, and Vasilis Samoladas. On a model of indexability and its bounds for range queries. Journal of the ACM (JACM), 49(1):35-55, 2002. Google Scholar
  23. Hong T. Kung. Computational models for parallel computers. Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 326(1591):357-371, 1988. Google Scholar
  24. J. S. Vitter. Algorithms and data structures for external memory. Foundations and Trends in Theoretical Computer Science, 2(4):305-474, 2008. URL: http://dx.doi.org/10.1561/0400000014.
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