Cache-Oblivious Planar Orthogonal Range Searching and Counting

Lars Arge, Gerth Stølting Brodal, Rolf Fagerberg, and Morten Laustsen

In Proc. 21st Annual ACM Symposium on Computational Geometry, pages 160-169, 2005.

Abstract

We present the first cache-oblivious data structure for planar orthogonal range counting, and improve on previous results for cache-oblivious planar orthogonal range searching.

Our range counting structure uses O(Nlog2 N) space and answers queries using O(logB N) memory transfers, where B is the block size of any memory level in a multilevel memory hierarchy. Using bit manipulation techniques, the space can be further reduced to O(N). The structure can also be modified to support more general semigroup range sum queries in O(logB N) memory transfers, using O(Nlog2 N) space for three-sided queries and O(Nlog22 N/log2log2 N) space for four-sided queries.

Based on the O(Nlog N) space range counting structure, we develop a data structure that uses O(Nlog2 N) space and answers three-sided range queries in O(logB N+T/B) memory transfers, where T is the number of reported points. Based on this structure, we present a general four-sided range searching structure that uses O(Nlog22 N/log2log2 N) space and answers queries in O(logB N + T/B) memory transfers.

Copyright notice

Copyright © 2005 by the Association for Computer Machinery, Inc.

Online version

socg05.pdf (210 Kb)

DOI

10.1145/1064092.1064119

BIBTEX entry

@inproceedings{socg05,
  author = "Lars Arge and Gerth St{\o}lting Brodal and Rolf Fagerberg and Morten Laustsen",
  booktitle = "Proc. 21st Annual ACM Symposium on Computational Geometry",
  doi = "10.1145/1064092.1064119",
  isbn = "1-58113-991-8",
  pages = "160-169",
  title = "Cache-Oblivious Planar Orthogonal Range Searching and Counting",
  year = "2005"
}