Limited Bioweathering by Cyanobacteria in Cold, Nutrient-Limited Conditions: Implications for Microbe-Mineral Interactions and Aquatic Chemistry in Cold Environments
- Award ID(s):
- 2114225
- PAR ID:
- 10552506
- Publisher / Repository:
- Geomicrobiology
- Date Published:
- Journal Name:
- Geomicrobiology Journal
- Volume:
- 41
- Issue:
- 6
- ISSN:
- 0149-0451
- Page Range / eLocation ID:
- 672 to 690
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
We consider the (1+ϵ)-approximate nearest neighbor search problem: given a set X of n points in a d-dimensional space, build a data structure that, given any query point y, finds a point x∈X whose distance to y is at most (1+ϵ)minx∈X ‖x−y‖ for an accuracy parameter ϵ∈(0,1). Our main result is a data structure that occupies only O(ϵ^−2 n log(n)log(1/ϵ)) bits of space, assuming all point coordinates are integers in the range {−n^O(1)…n^O(1)}, i.e., the coordinates have O(logn) bits of precision. This improves over the best previously known space bound of O(ϵ^−2 n log(n)^2), obtained via the randomized dimensionality reduction method of Johnson and Lindenstrauss (1984). We also consider the more general problem of estimating all distances from a collection of query points to all data points X, and provide almost tight upper and lower bounds for the space complexity of this problem.more » « less
An official website of the United States government

