{"controller"=>"catalog", "action"=>"show", "id"=>"8759631"}
  • EN
  • DA

Danish NationalResearch Database

  • Search Publications & Researchers
  • Open Access Indicator
  • Publications
  • Researchers
Example Finds records
water{} containing the word "water".
water supplies"{}" containing the phrase "water supplies".
author:"Doe, John"author:"{}" containing the prase "Doe, John" in the author field.
title:IEEEtitle:{} containing the word "IEEE" in the title field.
Need more help? Advanced search tutorial
  • Selected (0)
  • History

Cache-Oblivious Planar Orthogonal Range Searching and Counting

    • Save to Mendeley
    • Export to BibTeX
    • Export to RIS
    • Email citation
Authors:
  • Arge, L. ;
    Close
    unknown
  • Brodal, G.S. ;
    Close
    unknown
  • Fagerberg, Rolf ;
    Close
    Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU
  • Laustsen, M.
    Close
    unknown
Editor:
Mitchell, J., Rote, G.
DOI:
10.1145/1064092.1064119
Abstract:
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.
Type:
Conference paper
Language:
English
Published in:
Proceedings of the 21st Annual Acm Symposium on Computational Geometry, 2005, p. 160-169
Main Research Area:
Science/technology
Publication Status:
Published
Review type:
Peer Review
Conference:
The 21st Annual ACM Symposium on Computational Geometry, 2005
Publisher:
Association for Computing Machinery
Submission year:
2005
Scientific Level:
Scientific
ID:
8759631

Full text access

  • Doi Get publisher edition via DOI resolver
Checking for on-site access...

On-site access

At institutions

  • University southern denmark
  • Aarhus university.en
Feedback

Sitemap

  • Search
    • Statistics
    • Tutorial
    • Data
    • FAQ
    • Contact
  • Open Access
    • Overview
    • Development
    • FAQ
    • Contact
  • About
    • Institutions
    • Release History
    • Cookies and privacy policy

Copyright © 1998–2018.

Fivu en