Cache-oblivious data structures for orthogonal range searching
| Autor: | Lars Arge, Pankaj K. Agarwal, Bryan Holland-Minkley, Andrew Danner |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2003 |
| Předmět: | |
| Zdroj: | Agarwal, P K, Arge, L A, Danner, A & Holland-Minkley, B 2003, Cache-oblivious data structures for orthogonal range searching . in Proceedings of the nineteenth annual symposium on Computational geometry . Association for Computing Machinery, pp. 237-245, San Diego, CA, United States, 08/06/2003 . https://doi.org/10.1145/777792.777828 Symposium on Computational Geometry |
| DOI: | 10.1145/777792.777828 |
| Popis: | We develop cache-oblivious data structures for orthogonal range searching, the problem of finding all T points in a set of N points in IRd lying in a query hyper-rectangle. Cache-oblivious data structures are designed to be efficient in arbitrary memory hierarchies.We describe a dynamic linear-size data structure that answers d-dimensional queries in O((N/B)1-1/d+T/B) memory transfers, where B is the block size of any two levels of a multilevel memory hierarchy. A point can be inserted into or deleted from this data structure in O(log2B N) memory transfers. We also develop a static structure for the two-dimensional case that answers queries in O(logB N+T/B) memory transfers using O(N log22 N) space. The analysis of the latter structure requires that B=22c for some non-negative integer constant c. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|