Fast local searches and updates in bounded universes

DOI10.1016/J.COMGEO.2012.01.002MaRDI QIDQ691776zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Karim Douïeb, Vida Dujmović, John Howat, Pat Morin

Publication date 4 December 2012

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2012.01.002

zbMATH Keywords

range searchbounded universedistance sensitivitynearest neighbour searchpredecessor search

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10)

Recommendations

• Delta-fast tries: local searches in bounded universes with linear space
• Time-space trade-offs for predecessor search
• Algorithms – ESA 2005

Cites work

• scientific article; zbMATH DE number 2119699 (Why is no real title available?)
• A priority queue in which initialization and queue operations takeO(loglogD) time
• Data Structures with Local Update Operations
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Dynamic ordered sets with exponential search trees
• Efficient data structures for range searching on a grid
• Efficient regular data structures and algorithms for dilation, location, and proximity problems
• Geometric approximation algorithms
• Improved bounds for finger search on a RAM
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Optimal bounds for the predecessor problem and related problems
• Optimal finger search trees in the pointer machine
• Orthogonal range searching on the RAM, revisited
• Preserving order in a forest in less than logarithmic time and linear space
• Priority Search Trees

Cited in

(5)

• Data Structures with Local Update Operations
• Delta-fast tries: local searches in bounded universes with linear space
• scientific article; zbMATH DE number 7271257 (Why is no real title available?)
• Cross-document pattern matching
• LATIN 2004: Theoretical Informatics

This page was built for publication: Fast local searches and updates in bounded universes

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