short-paper

Hybrid Dynamic Pruning for Efficient and Effective Query Processing

Authors:

Wenxiu Fang,

Trent G. Marbach,

Gang Wang,

Xiaoguang LiuAuthors Info & Claims

CIKM '20: Proceedings of the 29th ACM International Conference on Information & Knowledge Management

Pages 2013 - 2016

https://doi.org/10.1145/3340531.3412113

Published: 19 October 2020 Publication History

Get Access

Abstract

The performance of query processing has always been a concern in the field of information retrieval. Dynamic pruning algorithms have been proposed to improve query processing performance in terms of efficiency and effectiveness. However, a single pruning algorithm generally does not have both advantages. In this work, we investigate the performance of the main dynamic pruning algorithms in terms of average and tail latency as well as the accuracy of query results, and find that they are complementary. Inspired by these findings, we propose two types of hybrid dynamic pruning algorithms that choose different combinations of strategies according to the characteristics of each query. Experimental results demonstrate that our proposed methods yield a good balance between both efficiency and effectiveness.

Supplementary Material

MP4 File (3340531.3412113.mp4)

In this paper, we observe the pros and cons of some existing query processing algorithms and try to improve both average query processing time and tail latency by combining algorithms in DAAT family. And we exploit the stability of SAAT to make up for the tail latency of DAAT almost without loss of effectiveness.

Download
106.65 MB

References

[1]

Andrei Z Broder, David Carmel, Michael Herscovici, Aya Soffer, and Jason Zien. 2003. Efficient query evaluation using a two-level retrieval process. In Proc. CIKM. ACM, New Orleans, Louisiana, USA, 426--434.

Digital Library

Google Scholar

[2]

Matt Crane, J Shane Culpepper, Jimmy Lin, Joel Mackenzie, and Andrew Trotman. 2017. A comparison of Document-at-a-Time and Score-at-a-Time query evaluation. In Proc. WSDM. ACM, Cambridge, UK, 201--210.

Digital Library

Google Scholar

[3]

Shuai Ding and Torsten Suel. 2011. Faster top-k document retrieval using blockmax indexes. In Proc. SIGIR. ACM, Beijing, China, 993--1002.

Google Scholar

[4]

Myeongjae Jeon, Saehoon Kim, Seung-won Hwang, Yuxiong He, Sameh Elnikety, Alan L Cox, and Scott Rixner. 2014. Predictive parallelization: Taming tail latencies in web search. In Proc. SIGIR. ACM, Queensland, Australia, 253--262.

Digital Library

Google Scholar

[5]

Jimmy Lin and Andrew Trotman. 2015. Anytime ranking for impact-ordered indexes. In Proc. ICTIR. ACM, Northampton, MA, USA, 301--304.

Digital Library

Google Scholar

[6]

Joel Mackenzie, J Shane Culpepper, Roi Blanco, Matt Crane, Charles LA Clarke, and Jimmy Lin. 2018. Query driven algorithm selection in early stage retrieval. In Proc. WSDM. ACM, Los Angeles, California, USA, 396--404.

Digital Library

Google Scholar

[7]

Antonio Mallia, Giuseppe Ottaviano, Elia Porciani, Nicola Tonellotto, and Rossano Venturini. 2017. Faster BlockMax WAND with variable-sized blocks. In Proc. SIGIR. ACM, Shinjuku, Tokyo, Japan, 625--634.

Digital Library

Google Scholar

[8]

Stephen E Robertson and K Sparck Jones. 1976. Relevance weighting of search terms. J. Am. Soc. Inf. Sci. 27, 3 (1976), 129--146.

Crossref

Google Scholar

[9]

Nicola Tonellotto, Craig Macdonald, and Iadh Ounis. 2013. Efficient and effective retrieval using selective pruning. In Proc. WSDM. ACM, Rome, Italy, 63--72.

Digital Library

Google Scholar

[10]

Howard Turtle and James Flood. 1995. Query evaluation: strategies and optimizations. Inf. Process. Manag. 31, 6 (1995), 831--850.

Digital Library

Google Scholar

Cited By

View all

Liu XPan YLi YWang GLiu X(2022)An NVM SSD-Based High Performance Query Processing Framework for Search EnginesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.316055735:6(5612-5625)Online publication date: 18-Mar-2022
https://dl.acm.org/doi/10.1109/TKDE.2022.3160557

Index Terms

Hybrid Dynamic Pruning for Efficient and Effective Query Processing
1. Information systems
  1. Information retrieval
    1. Evaluation of retrieval results
      1. Retrieval effectiveness
      2. Retrieval efficiency
    2. Information retrieval query processing

Recommendations

On efficient reverse skyline query processing

We propose two efficient algorithms for exact RSQ processing.We use precomputation, reuse, and pruning techniques to boost query performance.We extend our techniques to tackle a natural variant of RSQ, i.e., CRSQ.Extensive experiments show that our ...
Query efficiency prediction for dynamic pruning
LSDS-IR '11: Proceedings of the 9th workshop on Large-scale and distributed informational retrieval

Dynamic pruning strategies are effective yet permit efficient retrieval by pruning - i.e. not fully scoring all postings of all documents matching a given query. However, the amount of pruning possible for a query can vary, resulting in queries with ...
Efficient skyline query processing in wireless sensor networks

How to process a skyline query efficiently has received considerable attention in recent years. A skyline query identifies a set of non-dominated data records in a multidimensional dataset. Whereas most previous studies have resolved this problem in a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CIKM '20: Proceedings of the 29th ACM International Conference on Information & Knowledge Management

October 2020

3619 pages

ISBN:9781450368599

DOI:10.1145/3340531

General Chairs:
Mathieu d'Aquin
DSI, Insight, NUI Galway, Ireland
,
Stefan Dietze
GESIS, Cologne, Germany, Heinrich-Heine-University Düsseldorf, Germany, L3S Research Center, Germany
,
Program Chairs:
Claudia Hauff
TU Delft, The Netherlands
,
Edward Curry
DSI, Insight, NUI Galway, Ireland
,
Philippe Cudre Mauroux
eXascale, University of Fribourg, Switzerland

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 October 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Conference

CIKM '20

Sponsor:

CIKM '20: The 29th ACM International Conference on Information and Knowledge Management

October 19 - 23, 2020

Virtual Event, Ireland

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
105
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liu XPan YLi YWang GLiu X(2022)An NVM SSD-Based High Performance Query Processing Framework for Search EnginesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.316055735:6(5612-5625)Online publication date: 18-Mar-2022
https://dl.acm.org/doi/10.1109/TKDE.2022.3160557

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

On efficient reverse skyline query processing

Query efficiency prediction for dynamic pruning

Efficient skyline query processing in wireless sensor networks