Optimal information retrieval when queries are not random

DOI10.1016/0020-0255(84)90049-5MaRDI QIDQ1061507zbMATH OpenOpenAlexFDO

Authors Chin-Chen Chang

Publication date 1984

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0255(84)90049-5

zbMATH Keywords

average number of bucketshashing function rangesheuristic algorithmmultiattribute filemultiple key hashingNP-hardqueries with probability

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20)

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.

Recommendations

• On the complexity of designing optimal partial-match retrieval systems
• Optimal multiple key hashing files for orthogonal range queries
• Optimal Partial-Match Hashing Design
• Optimal dynamic multi-attribute hashing for range queries
• On the File Design Problem for Partial Match Retrieval

Cites work

• Algorithmic approach to the consecutive retrieval property
• Common Properties of Some Multiattribute File Systems
• Every Prime Has a Succinct Certificate
• scientific article; zbMATH DE number 3646329 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Multi-dimensional clustering for data base organizations
• Optimality Properties of Multiple-Key Hashing Functions
• Partial-Match Retrieval Algorithms
• Performance Analyses of Cartesian Product Files and Random Files
• Reducing block accesses in inverted files by partial clustering
• Riemann's hypothesis and tests for primality
• Symbolic Gray Code as a Perfect Multiattribute Hashing Scheme for Partial Match Queries
• The hierarchical ordering in multiattribute files

Cited in

(16)

• Data base design with the constrained multiple attribute tree
• Multidisk partial match file design with known access pattern
• Optimal dynamic multi-attribute hashing for range queries
• Optimal multiple key hashing files for orthogonal range queries
• Some properties of optimal cartesian product files for orthogonal range queries
• A note on allocating k-ary multiple key hashing files among multiple disks
• Fundamental limits for information retrieval
• Everywhere-Tight Information Cost Tradeoffs for Augmented Index
• Concatenated hash code selection
• On the complexity of designing optimal partial-match retrieval systems
• scientific article; zbMATH DE number 3972242 (Why is no real title available?)
• scientific article; zbMATH DE number 4104389 (Why is no real title available?)
• Optimal Partial-Match Hashing Design
• Dimensioning a multiple hashing scheme
• On partial information retrieval: the unconstrained 100 prisoner problem
• Optimization of descriptor information retrieval systems with zone- hierarchical organization of the retrieval set

This page was built for publication: Optimal information retrieval when queries are not random

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