Optimal information retrieval when queries are not random
type: Item
instance of: scholarly article
title: Optimal information retrieval when queries are not random
zbMATH Open document ID: 0571.68081
DOI: 10.1016/0020-0255(84)90049-5
published in: Information Sciences
publication date: 1984-01-01T00:00:00Z
review text: Given query probabilities attached to attributes, a general formula for the average number of buckets to be accessed using the multiple key hashing (MKH) scheme is derived. It is shown that the problem of arranging multiattribute records optimally in a fixed number of buckets is NP-hard and that the optimal integer solution for hashing function ranges can be reduced to finding minimal N-tuples. Based on the general formula, a good and efficient heuristic algorithm for MKH design is proposed and simulation results are presented.
Mathematics Subject Classification ID: 68P20
zbMATH DE Number: 3911756
zbMATH Keywords: queries with probability
zbMATH Keywords: multiattribute file
zbMATH Keywords: average number of buckets
zbMATH Keywords: multiple key hashing
zbMATH Keywords: NP-hard
zbMATH Keywords: hashing function ranges
zbMATH Keywords: heuristic algorithm
author: Chin-Chen Chang
MaRDI profile type: Publication
full work available at URL: 0020-0255(84)90049-5
OpenAlex ID: W2072772767
cites work: Algorithmic approach to the consecutive retrieval property
cites work: Optimality Properties of Multiple-Key Hashing Functions
cites work: Performance Analyses of Cartesian Product Files and Random Files
cites work: The hierarchical ordering in multiattribute files
cites work: Symbolic Gray Code as a Perfect Multiattribute Hashing Scheme for Partial Match Queries
cites work: Q4198056
cites work: Q3051421
cites work: Reducing block accesses in inverted files by partial clustering
cites work: Common Properties of Some Multiattribute File Systems
cites work: Multi-dimensional clustering for data base organizations
cites work: Riemann's hypothesis and tests for primality
cites work: Every Prime Has a Succinct Certificate
cites work: Partial-Match Retrieval Algorithms
description: scientific article; zbMATH DE number 3911756