caa a22 4500 44580498X CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110201xx s 000 0 eng 10.1007/s00453-009-9297-0 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9297-0 Approximate Range Searching in External Memory [Elektronische Daten] [Micha Streppel, Ke Yi] In this paper, we present two linear-size external memory data structures for approximate range searching. Our first structure, the BAR-B-tree, stores a set of N points in ℝd and can report all points inside a query range Q by accessing O(log B N+ε γ+k ε/B) disk blocks, where B is the disk block size, γ=1−d for convex queries and γ=−d otherwise, and k ε is the number of points lying within a distance of ε⋅diam (Q) to the query rangeQ. Our second structure, the object-BAR-B-tree, is able to store objects of arbitrary shapes of constant complexity and provides similar query guarantees. In addition, both structures can support other types of range searching queries such as range aggregation and nearest-neighbor. Finally, we present I/O-efficient algorithms to build these structures. Springer Science+Business Media, LLC, 2009 Approximate range searching nationallicence External memory algorithms nationallicence Streppel Micha NCIM-Groep, Eindhoven, The Netherlands aut Yi Ke Department of Computer Science and Engineering, HKUST, Clear Water Bay, Kowloon, Hong Kong aut Algorithmica Springer-Verlag 59/2(2011-02-01), 115-128 0178-4617 59:2<115 2011 59 453 https://doi.org/10.1007/s00453-009-9297-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9297-0 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Streppel Micha NCIM-Groep, Eindhoven, The Netherlands aut NATIONALLICENCE 700 1- Yi Ke Department of Computer Science and Engineering, HKUST, Clear Water Bay, Kowloon, Hong Kong aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/2(2011-02-01), 115-128 0178-4617 59:2<115 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer