Fast local searches and updates in bounded universes

DOI10.1016/J.COMGEO.2012.01.002zbMATH Open1253.68111OpenAlexW2177407650MaRDI QIDQ691776FDOQ691776

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

Recommendations

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

zbMATH Keywords

range searchbounded universedistance sensitivitynearest neighbour searchpredecessor search

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Cross-document pattern matching
• LATIN 2004: Theoretical Informatics
• Biased predecessor search
• Data Structures with Local Update Operations
• Delta-fast tries: local searches in bounded universes with linear space
• Title not available (Why is that?)

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)