SCIENCE@home

Phrase Query Optimization on Inverted Indexes

Avishek Anand,I. Mele,Srikanta J. Bedathur,K. Berberich

Published 2014 in International Conference on Information and Knowledge Management

ABSTRACT

Phrase queries are a key functionality of modern search engines. Beyond that, they increasingly serve as an important building block for applications such as entity-oriented search, text analytics, and plagiarism detection. Processing phrase queries is costly, though, since positional information has to be kept in the index and all words, including stopwords, need to be considered. We consider an augmented inverted index that indexes selected variable-length multi-word sequences in addition to single words. We study how arbitrary phrase queries can be processed efficiently on such an augmented inverted index. We show that the underlying optimization problem is NP-hard in the general case and describe an exact exponential algorithm and an approximation algorithm to its solution. Experiments on ClueWeb09 and The New York Times with different real-world query workloads examine the practical performance of our methods.

PUBLICATION RECORD

  • Publication year

    2014

  • Venue

    International Conference on Information and Knowledge Management

  • Publication date

    2014-11-03

  • Fields of study

    Computer Science

  • Identifiers
    DOI 10.1145/2661829.2661928
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-27 of 27 references · Page 1 of 1

CITED BY