Space-efficient data-analysis queries on grids

DOI10.1016/J.TCS.2012.11.031MaRDI QIDQ390915zbMATH OpenOpenAlexFDO

Authors Gonzalo Navarro, Yakov Nekrich, Luís M. S. Russo

Publication date 9 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.11.031

zbMATH Keywords

quantilemodedatabasessuccinct data structuresdynamic data structuresrange minimum queriesrange queriesalpha majorityorthogonal range queriespoint dominancerectangle visibilitystatistical database queriestop-\(k\)wavelet tree

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Database theory (68P15)

Recommendations

• Space-efficient data-analysis queries on grids
• Efficient data structures for range searching on a grid
• 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

Cites work

• scientific article; zbMATH DE number 4062572 (Why is no real title available?)
• scientific article; zbMATH DE number 3772902 (Why is no real title available?)
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 6146456 (Why is no real title available?)
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• An implicit data structure supporting insertion, deletion, and search in O( ^ 2\,n) time
• Colored range queries and document retrieval
• Compact rich-functional binary relation representations
• Data structures for range median queries
• Dynamic Planar Range Maxima Queries
• Dynamic entropy-compressed sequences and full-text indexes
• Efficient top-\(k\) queries for orthogonal ranges
• Fully-functional succinct trees
• Linear-space data structures for range mode query in arrays
• New Data Structures for Orthogonal Range Queries
• New algorithms on wavelet trees and applications to information retrieval
• On the Size of Succinct Indices
• Optimal succinctness for range minimum queries
• Orthogonal range searching in linear and almost-linear space
• Orthogonal range searching on the RAM, revisited
• Range Majority in Constant Time and Linear Space
• Rank and select revisited and extended
• Rank/select on dynamic compressed sequences and applications
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Time-optimal top-\(k\) document retrieval
• Time-space trade-offs for predecessor search
• Top-\(k\) ranked document search in general text databases
• Transposition invariant string matching
• Two-Dimensional Range Minimum Queries

Cited in

(17)

• Dualities in tree representations
• Fast construction of wavelet trees
• Time-optimal top-\(k\) document retrieval
• Document listing on repetitive collections with guaranteed performance
• Dynamic range majority data structures
• Practical compact indexes for top-\(k\) document retrieval
• New space/time tradeoffs for top-\(k\) document retrieval on sequences
• Space-efficient data-analysis queries on grids
• Compact binary relation representations with rich functionality
• The range 1 query (R1Q) problem
• Lempel-Ziv compressed structures for document retrieval
• Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
• Compact and succinct data structures for multidimensional orthogonal range searching
• scientific article; zbMATH DE number 1305015 (Why is no real title available?)
• Wavelet trees for all
• Improved range minimum queries
• Path queries on functions

This page was built for publication: Space-efficient data-analysis queries on grids

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