Improved techniques for processing queries in full-text systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved techniques for processing queries in full-text systems

Full text

Pdf (933 KB)

Source

Annual ACM Conference on Research and Development in Information Retrieval archive
Proceedings of the 10th annual international ACM SIGIR conference on Research and development in information retrieval table of contents

New Orleans, Louisiana, United States

Pages: 306 - 315

Year of Publication: 1987

ISBN:0-89791-232-2

Authors

Y. Choueka	Inst. for Information Retrieval and Computational Linguistics (IRCOL) -- The Responsa Project and Department of Mathematics and Computer Science, Bar-Ilan University, Ramat Gan, Israel and On sabbatical leave at Bell Communications Research, Morristown, New Jersey, USA
A. Fraenkel	Department of Applied Mathematics, The Weizmann Institute of Science, Rehovot 76100, Israel
S. Klein	Department of Applied Mathematics, The Weizmann Institute of Science, Rehovot 76100, Israel
E. Segal	Inst. for Information Retrieval and Computational Linguistics (IRCOL) -- The Responsa Project

Sponsor

SIGIR: ACM Special Interest Group on Information Retrieval

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 14, Citation Count: 8

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/42005.42039 What is a DOI?

ABSTRACT

In static full-text retrieval systems, which accommodate metrical as well as Boolean operators, the traditional approach to query processing uses a “concordance”, from which large sets of coordinates are retrieved and then merged and/or collated. Alternatively, in a system with l documents, the concordance can be replaced by a set of bit-maps of fixed length l, which are constructed for every different word of the database and serve as occurrence maps. We propose to combine the concordance and bit-map approaches, and show how this can speed up the processing of queries: fast ANDing and ORing of the maps in a preprocessing stage, lead to large I/O savings in collating coordinates of keywords needed to satisfy the metrical and Boolean constraints. Moreover, the bit-maps give partial information on the distribution of the coordinates of the keywords, which can be used when queries must be processed by stages, due to their complexity and the sizes of the involved sets of coordinates. The new techniques are partially implemented at the Responsa Retrieval Project.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	R. Attar , Y. Choueka , Nachum Dershowitz , A. S. Fraenkel, KEDMA—Linguistic Tools for Retrieval Systems, Journal of the ACM (JACM), v.25 n.1, p.52-66, Jan. 1978 [doi>10.1145/322047.322052]
	2	Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
	3	Bratley P., Choueka Y., Processing truncated terms in document retrieval systems, Inf. Processing ~ Management 18 (1982) 257-266.
	4	Choueka Y., Full text systems and research in the humanities, Computers and the Humanities XIV (1980) 153-169.
	5	A. S. Fraenkel , S. T. Klein , Y. Choueka , E. Segal, Improved hierarchical bit-vector compression in document retrieval systems, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.88-96, September 1986, Palazzo dei Congressi, Pisa, Italy [doi>10.1145/253168.253190]
	6	D. R. Davis , A. D. Lin, Secondary key retrieval using an IBM 7090-1301 system, Communications of the ACM, v.8 n.4, p.243-246, April 1965 [doi>10.1145/363831.364908]
	7	Fraenkel A.S., All about the Responsa Retrieval Project you always wanted to know but were afraid to ask, Expanded Summary, Jurimetrics J. 16 (1976) 149- 156.
	8	Fraenkel A.S., Klein S.T., Novel compression of sparse bit-strings ~ preliminary report, Combinatorial Algo. rithms on Words, NATO ASI Series Vol. F12, Springer Verlag, Berlin (1985) 169-183.
	9	H. S. Heaps, Information Retrieval: Computational and Theoretical Aspects, Academic Press, Inc., Orlando, FL, 1978
	10	Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977

CITED BY 8

	S. T. Klein , A. Bookstein , S. Deerwester, Storing text retrieval systems on CD-ROM: compression and encryption considerations, ACM SIGIR Forum, v.23 n.SI, p.160-167, June 1989
	A. Bookstein , S. T. Klein, Construction of optimal graphs for bit-vector compression, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.327-342, September 05-07, 1990, Brussels, Belgium
	Shmuel T. Klein, Processing queries with metrical constraints in XML-based IR systems, Journal of the American Society for Information Science and Technology, v.59 n.1, p.86-97, January 2008
	Alistair Moffat , Justin Zobel, Self-indexing inverted files for fast text retrieval, ACM Transactions on Information Systems (TOIS), v.14 n.4, p.349-379, Oct. 1996
	A. Bookstein , St Klein , T. Raita, Simple Bayesian Model for Bitmap Compression, Information Retrieval, v.1 n.4, p.315-328, January 2000
	A. Bookstein , S. T. Klein , T. Raita, Detecting content-bearing words by serial clustering—extended abstract, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.319-327, July 09-13, 1995, Seattle, Washington, United States
	Shmuel T. Klein , Abraham Bookstein , Scott Deerwester, Storing text retrieval systems on CD-ROM: compression and encryption considerations, ACM Transactions on Information Systems (TOIS), v.7 n.3, p.230-245, July 1989
	Justin Zobel , Alistair Moffat, Inverted files for text search engines, ACM Computing Surveys (CSUR), v.38 n.2, p.6-es, 2006

INDEX TERMS

Primary Classification:
H. Information Systems
H.2 DATABASE MANAGEMENT
H.2.4 Systems
Subjects: Query processing

Additional Classification:
H. Information Systems
H.3 INFORMATION STORAGE AND RETRIEVAL
H.3.3 Information Search and Retrieval
Subjects: Retrieval models
H.3.4 Systems and Software
Subjects: Question-answering (fact retrieval) systems**

I. Computing Methodologies
I.7 DOCUMENT AND TEXT PROCESSING

General Terms:
Algorithms, Human Factors, Performance

Collaborative Colleagues:

Y. Choueka: colleagues

A. Fraenkel: colleagues

S. Klein: colleagues

E. Segal: colleagues

Peer to Peer - Readers of this Article have also read:

M⁴: a metamodel for data preprocessing Proceedings of the 4th ACM international workshop on Data warehousing and OLAP
Anca Vaduva , Jörg-Uwe Kietz , Regina Zücker
Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein
Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM 34, 12
Ellen Francik , Susan Ehrlich Rudman , Donna Cooper , Stephen Levine

Adobe Acrobat

QuickTime

Windows Media Player

Real Player