Compact and succinct data structures for multidimensional orthogonal range searching

DOI10.1016/J.IC.2020.104519MaRDI QIDQ776842zbMATH OpenOpenAlexWikidataFDO

Authors Kazuki Ishiyama, Kunihiko Sadakane

Publication date 13 July 2020

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2020.104519

zbMATH Keywords

databasesuccinct data structureorthogonal range searching

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Database theory (68P15)

Recommendations

• On the average performance of orthogonal range search in multidimensional data structures
• scientific article; zbMATH DE number 2086648
• Faster Linear-space Orthogonal Range Searching in Arbitrary Dimensions
• New Data Structures for Orthogonal Range Queries
• Cache-oblivious data structures for orthogonal range searching
• Orthogonal range searching in linear and almost-linear space
• Orthogonal Range Searching in Linear and Almost-Linear Space
• Space-Time Trade-Offs for Orthogonal Range Queries
• Efficient Data Structures for the Orthogonal Range Successor Problem
• Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back

Cites work

• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 2107521 (Why is no real title available?)
• An experimental investigation of set intersection algorithms for text searching
• Decomposable searching problems
• Entropy-bounded representation of point grids
• Faster Linear-space Orthogonal Range Searching in Arbitrary Dimensions
• Multidimensional binary search trees used for associative searching
• New algorithms on wavelet trees and applications to information retrieval
• Optimal succinctness for range minimum queries
• Practical entropy-compressed rank/select dictionary
• Rank and select revisited and extended
• Space-efficient data-analysis queries on grids
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets

Cited in

(18)

• The \(n\)-dimensional \(k\)-vector and its application to orthogonal range searching
• Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
• Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back
• Multidimensional range selection
• Efficient Data Structures for the Orthogonal Range Successor Problem
• Compressed data structures for range searching
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Orthogonal range searching on the RAM, revisited
• Faster Linear-space Orthogonal Range Searching in Arbitrary Dimensions
• scientific article; zbMATH DE number 194610 (Why is no real title available?)
• Algorithms - ESA 2003
• Some properties of optimal cartesian product files for orthogonal range queries
• Discrete range searching primitive for the GPU and its applications
• Entropy-bounded representation of point grids
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Space Efficient Data Structures for Dynamic Orthogonal Range Counting
• Cache-oblivious data structures for orthogonal range searching
• Entropy-bounded representation of point grids

This page was built for publication: Compact and succinct data structures for multidimensional orthogonal range searching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q776842)