I/O-efficient structures for orthogonal range-max and stabbing-max queries
Publication
, Journal Article
Agarwal, PK; Arge, L; Yang, J; Yi, K
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
January 1, 2003
We develop several linear or near-linear space and I/O-efficient dynamic data structures for orthogonal range-max queries and stabbing-max queries. Given a set of N weighted points in ℝd, the range-max problem asks for the maximum-weight point in a query hyperrectangle. In the dual stabbing-max problem, we are given N weighted hyper-rectangles, and we wish to find the maximum-weight rectangle containing a query point. Our structures improve on previous structures in several important ways. © Springer-Verlag 2003.
Duke Scholars
Published In
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
Publication Date
January 1, 2003
Volume
2832
Start / End Page
7 / 18
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences
Citation
APA
Chicago
ICMJE
MLA
NLM
Agarwal, P. K., Arge, L., Yang, J., & Yi, K. (2003). I/O-efficient structures for orthogonal range-max and stabbing-max queries. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2832, 7–18. https://doi.org/10.1007/978-3-540-39658-1_4
Agarwal, P. K., L. Arge, J. Yang, and K. Yi. “I/O-efficient structures for orthogonal range-max and stabbing-max queries.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2832 (January 1, 2003): 7–18. https://doi.org/10.1007/978-3-540-39658-1_4.
Agarwal PK, Arge L, Yang J, Yi K. I/O-efficient structures for orthogonal range-max and stabbing-max queries. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2003 Jan 1;2832:7–18.
Agarwal, P. K., et al. “I/O-efficient structures for orthogonal range-max and stabbing-max queries.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2832, Jan. 2003, pp. 7–18. Scopus, doi:10.1007/978-3-540-39658-1_4.
Agarwal PK, Arge L, Yang J, Yi K. I/O-efficient structures for orthogonal range-max and stabbing-max queries. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2003 Jan 1;2832:7–18.
Published In
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
Publication Date
January 1, 2003
Volume
2832
Start / End Page
7 / 18
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences