NDLI: On the complexity of designing optimal partial-match retrieval systems

Content Provider	ACM Digital Library
Author	Moran, Shlomo
Copyright Year	1983
Abstract	We consider the problem of designing an information retrieval system on which partial match queries have to be answered. Each record in the system consists of a list of $\textit{attributes},$ and a partial match query specifies the values of some of the attributes. The records are stored in $\textit{buckets}$ in a secondary memory, and in order to answer a partial match query all the buckets that may contain a record satisfying the specifications of that query must be retrieved. The bucket in which a given record is stored is found by a multiple key hashing function, which maps each attribute to a string of a fixed number of bits. The address of that bucket is then represented by the string obtained by concatenating the strings on which the various attributes were mapped. A partial match query may specify only part of the bits in the string representing the address, and the larger the number of bits specified, the smaller the number of buckets that have to be retrieved in order to answer the query.The optimization problem considered in this paper is that of deciding to how many bits each attribute should be mapped by the bashing function above, so that the expected number of buckets retrieved per query is minimized. Efficient solutions for special cases of this problem have been obtained in [1], [12], and [14]. It is shown that in general the problem is NP-hard, and that if $\textit{P}$ ≠ NP, it is also not fully approximable. Two heuristic algorithms for the problem are also given and compared.
Starting Page	543
Ending Page	551
Page Count	9
File Format	PDF
ISSN	03625915
e-ISSN	15574644
DOI	10.1145/319996.320004
Volume Number	8
Issue Number	4
Journal	ACM Transactions on Database Systems (TODS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1983-12-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	NP-hard problems Approximation algorithms File organization Hashing Partial match retrieval Searching
Content Type	Text
Resource Type	Article
Subject	Information Systems

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Optimal partial-match retrieval when fields are independently specified

On the File Design Problem for Partial Match Retrieval

Hashing and trie algorithms for partial match retrieval

Partial-match retrieval using hashing and descriptors

Optimal bucket allocation design of k-ary MKH files for partial match retrieval

Optimal file distribution for partial match retrieval

New file organization based on dynamic hashing

Symbolic Gray Code as a Perfect Multiattribute Hashing Scheme for Partial Match Queries

Approximation Algorithms for NP-Hard Problems

On the complexity of designing optimal partial-match retrieval systems

Similar Documents

Optimal partial-match retrieval when fields are independently specified

On the File Design Problem for Partial Match Retrieval

Hashing and trie algorithms for partial match retrieval

Partial-match retrieval using hashing and descriptors

Optimal bucket allocation design of k-ary MKH files for partial match retrieval

Optimal file distribution for partial match retrieval

New file organization based on dynamic hashing

Symbolic Gray Code as a Perfect Multiattribute Hashing Scheme for Partial Match Queries

Approximation Algorithms for NP-Hard Problems

On the complexity of designing optimal partial-match retrieval systems