Improved bounds for finger search on a RAM
type: Item
instance of: scholarly article
title: Improved bounds for finger search on a RAM
zbMATH Open document ID: 1264.68070
author: Athanasios K. Tsakalidis
author: A. C. Kaporis
author: Christos Makris
author: Spyros Sioutas
author: Kostas Tsichlas
author: Christos Zaroliagis
published in: Algorithmica
publication date: 2013-05-13T00:00:00Z
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 6162393
zbMATH Keywords: data structures
zbMATH Keywords: dictionary problem
zbMATH Keywords: balls and bins problem
zbMATH Keywords: interpolation search
zbMATH Keywords: expected analysis
MaRDI profile type: Publication
full work available at URL: s00453-012-9636-4
OpenAlex ID: W2910834087
cites work: Q4091421
cites work: Tight(er) worst-case bounds on dynamic searching and priority queues
cites work: Dynamic ordered sets with exponential search trees
cites work: Optimal bounds for the predecessor problem and related problems
cites work: Optimal finger search trees in the pointer machine
cites work: Time bounded random access machines
cites work: On the Lambert \(w\) function
cites work: A constant update time finger search tree
cites work: Implicit Data Structures for the Dictionary Problem
cites work: Surpassing the information theoretic bound with fusion trees
cites work: Q3048278
cites work: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
cites work: Sorting jordan sequences in linear time using level-linked search trees
cites work: Algorithms - ESA 2003
cites work: Deletions That Preserve Randomness
cites work: Q4369384
cites work: Q4385511
cites work: Dynamic interpolation search
cites work: Worst-case optimal insertion and deletion methods for decomposable searching problems
cites work: Interpolation search—a log log N search
cites work: Understanding the complexity of interpolation search
cites work: Q3694703
cites work: Q4197343
cites work: Randomized search trees
cites work: Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching
cites work: Efficiency of a Good But Not Linear Set Union Algorithm
cites work: A class of algorithms which require nonlinear time to maintain disjoint sets
cites work: Q3707420
cites work: On RAM Priority Queues
cites work: Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time
cites work: Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree
DOI: 10.1007/S00453-012-9636-4
description: scientific article; zbMATH DE number 6162393