research-article

Logic and Computational Complexity for Boolean Information Retrieval

Authors:

Manolis Koubarakis,

Spiros Skiadopoulos,

Christos TryfonopoulosAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 18, Issue 12

Pages 1659 - 1666

https://doi.org/10.1109/TKDE.2006.193

Published: 01 December 2006 Publication History

Abstract

We study the complexity of query satisfiability and entailment for the Boolean Information Retrieval models {\cal WP} and {\cal AWP} using techniques from propositional logic and computational complexity. {\cal WP} and {\cal AWP} can be used to represent and query textual information under the Boolean model using the concept of attribute with values of type text, the concept of word, and word proximity constraints. Variations of {\cal WP} and {\cal AWP} are in use in most deployed digital libraries using the Boolean model, text extenders for relational database systems (e.g., Oracle 10g), search engines, and P2P systems for information retrieval and filtering.

References

[1]

S. Amer-Yahia, C. Botev, and J. Shanmugasundaram, “TeXQuery: A Full-Text Search Extension to Query,” Proc. 13th Int'l World Wide Web Conf., pp.583-594, 2004.

Digital Library

[2]

R. Baeza-Yates and B. Ribeiro-Neto, Modern Information Retrieval. Addison Wesley, 1999.

Digital Library

[3]

Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris, Ion Stoica, Looking up data in P2P systems, Communications of the ACM, v.46 n.2, February 2003

Digital Library

[4]

Michael Benedikt, Leonid Libkin, Thomas Schwentick, Luc Segoufin, Definable relations and first-order query languages over strings, Journal of the ACM (JACM), v.50 n.5, p.694-751, September 2003

Digital Library

[5]

J. Callan, W. Croft, and S. Harding, “The INQUERY Retrieval System,” Proc. Third Int'l Conf. Database and Expert Systems Applications, pp. 78-83, 1992.

[6]

Proc. 23rd Int'l Conf. Software Eng. (ICSE '01), pp. 443-452, May 2001.

[7]

A. Carzaniga, D.S. Rosenblum, and A.L. Wolf, “Achieving Scalability and Expressiveness in an Internet-Scale Event Notification Service,” Proc. 19th ACM Symp. Principles of Distributed Computing (PODC '00), pp. 219-227, 2000.

Digital Library

[8]

K.C.-C. Chang, “Query and Data Mapping across Heterogeneous Information Sources,” PhD thesis, Stanford Univ., Jan. 2001.

[9]

IEEE Trans. Knowledge and Data Eng., vol. 8, no. 4, pp. 515-521, 1996.

Digital Library

[10]

Chen-Chuan K. Chang, Héctor Garcia-Molina, Andreas Paepcke, Predicate rewriting for translating Boolean queries in a heterogeneous information system, ACM Transactions on Information Systems (TOIS), v.17 n.1, p.1-39, Jan. 1999

Digital Library

[11]

S. Chaudhuri, R. Ramakrishnan, and G. Weikum, “Integrating DB and IR Technologies: What is the Sound of One Hand Clapping?” Proc. Second Biennial Conf. Innovative Data Systems Research, pp. 1-12, 2005.

[12]

T. Chinenyanga and N. Kushmerick, “Expressive Retrieval from XML Documents,” Proc. ACM SIGIR '01, Sept. 2001.

Digital Library

[13]

Artificial Intelligence, vol. 118, nos. 1-2, pp.163-196, 2000.

[14]

R. Dechter, Constraint Processing. Morgan Kaufmann, 2003.

Digital Library

[15]

Artificial Intelligence, special volume on knowledge representation, vol. 49, nos. 1-3, pp. 61-95, 1991.

[16]

N. Fuhr and K. Großjohann, “XIRQL: An XML Query Language Based on Information Retrieval Concepts,” ACM Trans. Information Systems, vol. 22, no. 2, pp. 313-356, Apr. 2004.

Digital Library

[17]

S. Idreos, C. Tryfonopoulos, M. Koubarakis, and Y. Drougas, “Query Processing in Super-Peer Networks with Languages Based on Information Retrieval: the P2P-DIET Approach,” Proc. Int'l Workshop Peer-to-Peer Computing and Databases (P2P&DB), Mar. 2004.

Digital Library

[18]

Theoretical Computer Science, L.V.S. Lakshmanan, ed., special issue on uncertainty in databases and deductive systems, vol. 171, pp. 25-60, Jan. 1997.

Digital Library

[19]

M. Koubarakis, T. Koutris, C. Tryfonopoulos, and P. Raftopoulou, “Information Alert in Distributed Digital Libraries: The Models, Languages, and Architecture of DIAS,” Proc. Sixth European Conf. Research and Advanced Technology for Digital Libraries (ECDL), pp.527-542, Sept. 2002.

Digital Library

[20]

M. Koubarakis, C. Tryfonopoulos, S. Idreos, and Y. Drougas, “Selective Information Dissemination in P2P Networks: Problems and Solutions,” SIGMOD Record, special issue on peer-to-peer data management, vol. 32, no. 3, pp. 71-76, 2003.

Digital Library

[21]

M. Koubarakis, C. Tryfonopoulos, P. Raftopoulou, and T. Koutris, “Data Models and Languages for Agent-Based Textual Information Dissemination,” Proc. Sixth Int'l Workshop Cooperative Information Agents (CIA), pp. 179-193, Sept. 2002.

Digital Library

[22]

Gonzalo Navarro, Ricardo Baeza-Yates, Proximal nodes: a model to query document databases by content and structure, ACM Transactions on Information Systems (TOIS), v.15 n.4, p.400-435, Oct. 1997

Digital Library

[23]

Computer Networks and ISDN Systems, vol. 27, no. 6, pp. 1027-1036, 1995.

Digital Library

[24]

Theoretical Computer Science, vol. 116, no. 1, pp. 117-149, 1993.

[25]

P. Revesz, Introduction to Constraint Databases. Springer, 2002.

[26]

S. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases. Addison Wesley, 1995.

Digital Library

[27]

A. Theobald and G. Weikum, “Adding Relevance to XML,” WebDB (Selected Papers), pp. 105-124, 2000.

Digital Library

[28]

C. Tryfonopoulos, S. Idreos, and M. Koubarakis, “LibraRing: An Architecture for Distributed Digital Libraries Based on DHTs,” Proc. Ninth European Conf. Research and Advanced Technology for Digital Libraries (ECDL), pp. 25-36, Sept. 2005.

Digital Library

[29]

Christos Tryfonopoulos, Stratos Idreos, Manolis Koubarakis, Publish/subscribe functionality in IR environments using structured overlay networks, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil

Digital Library

[30]

C. Tryfonopoulos, M. Koubarakis, and Y. Drougas, “Filtering Algorithms for Information Retrieval Models with Named Attributes and Proximity Operators,” Proc. 27th Ann. Int'l ACM SIGIR Conf., pp. 313-320, July 2004.

Digital Library

Cited By

Zervakis LTryfonopoulos CSkiadopoulos SKoubarakis M(2017)Query Reorganization Algorithms for Efficient Boolean Information FilteringIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2016.262014029:2(418-432)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1109/TKDE.2016.2620140
Tryfonopoulos CKoubarakis MDrougas Y(2009)Information filtering and query indexing for an information retrieval modelACM Transactions on Information Systems10.1145/1462198.146220227:2(1-47)Online publication date: 9-Mar-2009
https://dl.acm.org/doi/10.1145/1462198.1462202
Klein S(2009)On the use of negation in Boolean IR queriesInformation Processing and Management: an International Journal10.1016/j.ipm.2008.12.00345:2(298-311)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1016/j.ipm.2008.12.003

Index Terms

Logic and Computational Complexity for Boolean Information Retrieval
1. Information systems
  1. Data management systems
    1. Database design and models
    2. Query languages
2. Theory of computation
  1. Design and analysis of algorithms
  2. Theory and algorithms for application domains
    1. Database theory
      1. Database query languages (principles)

Recommendations

Some Computational Aspects of distance-sat

In many AI fields, one must face the problem of finding a solution that is as close as possible to a given configuration. This paper addresses this problem in a propositional framework. We introduce the decision problem distance-sat , which consists in ...
A satisfiability procedure for quantified boolean formulae
The renesse issue on satisfiability

We present a satisfiability tester QSAT for quantified Boolean formulae and a restriction QSAT_CNF of QSAT to unquantified conjunctive normal form formulae. QSAT makes use of procedures which replace subformulae of a formula by equivalent formulae. By a ...
Descriptional and computational complexity of finite automata---A survey

Finite automata are probably best known for being equivalent to right-linear context-free grammars and, thus, for capturing the lowest level of the Chomsky-hierarchy, the family of regular languages. Over the last half century, a vast literature ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 18, Issue 12

December 2006

141 pages

ISSN:1041-4347

Issue’s Table of Contents

Copyright © 2006.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 December 2006

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zervakis LTryfonopoulos CSkiadopoulos SKoubarakis M(2017)Query Reorganization Algorithms for Efficient Boolean Information FilteringIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2016.262014029:2(418-432)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1109/TKDE.2016.2620140
Tryfonopoulos CKoubarakis MDrougas Y(2009)Information filtering and query indexing for an information retrieval modelACM Transactions on Information Systems10.1145/1462198.146220227:2(1-47)Online publication date: 9-Mar-2009
https://dl.acm.org/doi/10.1145/1462198.1462202
Klein S(2009)On the use of negation in Boolean IR queriesInformation Processing and Management: an International Journal10.1016/j.ipm.2008.12.00345:2(298-311)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1016/j.ipm.2008.12.003

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents