Search NASA⌕ Search

DOE OSTI · 982896

Efficient Joins with Compressed Bitmap Indexes

Abstract

We present a new class of adaptive algorithms that use compressed bitmap indexes to speed up evaluation of the range join query in relational databases. We determine the best strategy to process a join query based on a fast sub-linear time computation of the join selectivity (the ratio of the number of tuples in the result to the total number of possible tuples). In addition, we use compressed bitmaps to represent the join output compactly: the space requirement for storing the tuples representing the join of two relations is asymptotically bounded by min(h; n . cb), where h is the number of tuple pairs in the result relation, n is the number of tuples in the smaller of the two relations, and cb is the cardinality of the larger column being joined. We present a theoretical analysis of our algorithms, as well as experimental results on large-scale synthetic and real data sets. Our implementations are efficient, and consistently outperform well-known approaches for a range of join selectivity factors. For instance, our count-only algorithm is up to three orders of magnitude faster than the sort-merge approach, and our best bitmap index-based algorithm is 1.2x-80x faster than the sort-merge algorithm, for various query instances. We achieve these speedups by exploiting several inherent performance advantages of compressed bitmap indexes for join processing: an implicit partitioning of the attributes, space-efficiency, and tolerance of high-cardinality relations.

Explore related subjects

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Madduri, Kamesh, Wu, Kesheng. 2009-08-19. Efficient Joins with Compressed Bitmap Indexes. https://www.osti.gov/biblio/982896

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related reports

TANTE: Time-adaptive operator learning via neural Taylor expansion

Operator learning for time-dependent partial differential equations (PDEs) has seen rapid progress in recent years, enabling efficient approximation of complex spatiotemporal dynamics. However, most existing methods rely on fixed time step sizes during rollout, which limits their ability to adapt to varying temporal complexity and often leads to error accumulation. In this work, we propose the Time-Adaptive Transformer with Neural Taylor Expansion (TANTE), a novel operator-learning framework that produces continuous-time predictions with adaptive step sizes. TANTE predicts future states by performing a Taylor expansion at the current state, where neural networks learn both the higher-order temporal derivatives and the local radius of convergence. This allows the model to dynamically adjust its rollout based on the local behavior of the solution, thereby reducing cumulative error and improving computational efficiency. We demonstrate the effectiveness of TANTE across a wide range of PDE benchmarks, achieving superior accuracy and adaptability compared to fixed-step baselines, delivering accuracy gains of 60-80 % and speed-ups of 30-40 % at inference time.

97 MATHEMATICS AND COMPUTING↗

Structured illumination for surface-resolved grazing-incidence X-ray scattering

Grazing-incidence (GI) scattering techniques are widely used to characterize thin films, offering high surface sensitivity and insight into morphology and structure. However, these approaches typically provide statistical averaged information due to elongated footprint or limited spatial resolution due to beam size. Here we introduce a method that combines structured illumination with GI X-ray scattering and leverages our computational imaging approach to resolve local structural details. We demonstrate that our method captures local features of an organic semiconductor thin film without the need for sample rotation as in tomography. The method expands GI techniques from statistical averaging to high-resolution imaging, thereby providing the capability for detailed analysis of local material properties, such as domain shape, orientation and polymorphism, which are critical for advancing material design towards more efficient and tailored materials.

97 MATHEMATICS AND COMPUTING↗