Self-organizing sequential search and Hilbert's inequalities
type: Item
instance of: scholarly article
title: Self-organizing sequential search and Hilbert's inequalities
zbMATH Open document ID: 0647.68059
DOI: 10.1016/0022-0000(88)90025-6
author: D. J. Hajela
author: Paul Seymour
author: Fan Chung
published in: Journal of Computer and System Sciences
publication date: 1988-01-01T00:00:00Z
review text: In this paper we describe a general technique which can be used to solve an old problem in analyzing self-organizing sequential search. We prove that the average time required for the move-to-front heuristic is no more than \(\pi\) /2 times that of the optimal order and this bound is the best possible. Hilbet's inequalities will be used to derive large classes of inequalities some of which can be applied to obtain tight worst-case bounds for several self-organizing heuristics.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 26D10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4057018
zbMATH Keywords: self-organizing sequential search
zbMATH Keywords: average time
zbMATH Keywords: move-to-front heuristic
zbMATH Keywords: Hilbet's inequalities
zbMATH Keywords: worst-case bounds
MaRDI profile type: Publication
full work available at URL: 0022-0000(88)90025-6
OpenAlex ID: W4240430811
cites work: A counterexample to a conjecture on optimal list ordering
cites work: Heuristics That Dynamically Organize Data Structures
cites work: On a model for storage and search
cites work: Exegesis of Self-Organizing Linear Search
cites work: Q4039929
cites work: An Account of Self-Organizing Systems
cites work: Optimal list order under partial memory constraints
cites work: Q5585020
cites work: On Serial Files with Relocatable Records
cites work: On self-organizing sequential search heuristics
description: scientific article; zbMATH DE number 4057018