Space-efficient data-analysis queries on grids

DOI10.1016/j.tcs.2012.11.031zbMath1291.68155OpenAlexW2080990114MaRDI QIDQ390915

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

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

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

Related Items (15)

Fast construction of wavelet trees ⋮ Dynamic range majority data structures ⋮ Document listing on repetitive collections with guaranteed performance ⋮ Improved range minimum queries ⋮ The range 1 query (R1Q) problem ⋮ Compact binary relation representations with rich functionality ⋮ Time-Optimal Top-$k$ Document Retrieval ⋮ Wavelet trees for all ⋮ Path queries on functions ⋮ Spaces, Trees, and Colors ⋮ New space/time tradeoffs for top-\(k\) document retrieval on sequences ⋮ Lempel-Ziv compressed structures for document retrieval ⋮ Unnamed Item ⋮ Compact and succinct data structures for multidimensional orthogonal range searching ⋮ Practical Compact Indexes for Top-kDocument Retrieval

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Colored range queries and document retrieval
• New algorithms on wavelet trees and applications to information retrieval
• An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
• Rank/select on dynamic compressed sequences and applications
• Orthogonal range searching in linear and almost-linear space
• Rank and select revisited and extended
• Time-space trade-offs for predecessor search
• Time-Optimal Top-$k$ Document Retrieval
• Range Majority in Constant Time and Linear Space
• Dynamic Planar Range Maxima Queries
• Efficient Top-k Queries for Orthogonal Ranges
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Two-Dimensional Range Minimum Queries
• On the Size of Succinct Indices
• Optimal Succinctness for Range Minimum Queries
• Compact Rich-Functional Binary Relation Representations
• Top-k Ranked Document Search in General Text Databases
• Data Structures for Range Median Queries
• New Data Structures for Orthogonal Range Queries
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Dynamic entropy-compressed sequences and full-text indexes
• Orthogonal range searching on the RAM, revisited
• Transposition invariant string matching

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