Space Efficient Two-Dimensional Orthogonal Colored Range Counting
Bibliographic record
Abstract
In the two-dimensional orthogonal colored range counting problem, we preprocess a set, P, of n colored points on the plane, such that given an orthogonal query rectangle, the number of distinct colors of the points contained in this rectangle can be computed efficiently. For this problem, we design three new solutions, and the bounds of each can be expressed in some form of time-space tradeoff. By setting appropriate parameter values for these solutions, we can achieve new specific results with (the space costs are in words and ε is an arbitrary constant in (0,1)): - O(nlg³ n) space and O(√nlg^{5/2} n lg lg n) query time; - O(nlg² n) space and O(√nlg^{4+ε} n) query time; - O(n (lg² n)/(lg lg n)) space and O(√nlg^{5+ε} n) query time; - O(nlg n) space and O(n^{1/2+ε}) query time. A known conditional lower bound to this problem based on Boolean matrix multiplication gives some evidence on the difficulty of achieving near-linear space solutions with query time better than √n by more than a polylogarithmic factor using purely combinatorial approaches. Thus the time and space bounds in all these results are efficient. Previously, among solutions with similar query times, the most space-efficient solution uses O(nlg⁴ n) space to answer queries in O(√nlg⁸ n) time (SIAM. J. Comp. 2008). Thus the new results listed above all achieve improvements in space efficiency, while all but the last result achieve speed-up in query time as well.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.002 | 0.010 |
| Meta-epidemiology (narrow) | 0.001 | 0.000 |
| Meta-epidemiology (broad) | 0.002 | 0.001 |
| Bibliometrics | 0.001 | 0.004 |
| Science and technology studies | 0.001 | 0.001 |
| Scholarly communication | 0.003 | 0.006 |
| Open science | 0.004 | 0.005 |
| Research integrity | 0.002 | 0.002 |
| Insufficient payload (model declined to judge) | 0.009 | 0.002 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".