List Intersection for Web Search: Algorithms, Cost Models, and Optimizations
Summary: Cost-based optimization over a space of list-intersection algorithms and combinations for web-search postings. Hardware-aware cost model selects low-cost plans, often mixing 2-way strategies to beat 2-way and k-way baselines, outperforming state-of-the-art alternatives; validated on two CPUs with real and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Sunghwan Kim (Pohang University of Science and Technology)
- 2. Taesung Lee (IBM)
- 3. Seung-won Hwang (Yonsei University)
- 4. Sameh Elnikety (Microsoft)
BibTeX Citation
@article{kim_vldb19,
title = {{List Intersection for Web Search: Algorithms, Cost Models, and Optimizations}},
author = {Kim, Sunghwan and Lee, Taesung and Hwang, Seung-won and Elnikety, Sameh},
journal = {PVLDB},
series = {{VLDB} '19},
volume = {12},
number = {1},
pages = {1--13},
doi = {10.14778/3275536.3275537},
url = {https://doi.org/10.14778/3275536.3275537},
year = {2019}
}Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,440 | In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework | 2024 | SIGMOD | 5.2680376e-05 |
| 10,612 | Index Intersection for High-Dimensional Range Queries | 2026 | VLDB | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 6 of 6 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 290 | An Overview of Query Optimization in Relational Systems | 1998 | PODS | 0.0002227038 |
| 1,717 | Improving the Performance of List Intersection | 2009 | VLDB | 9.9327227e-05 |
| 2,245 | Fast Set Intersection in Memory | 2011 | VLDB | 8.8734284e-05 |
| 3,212 | Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions | 2015 | VLDB | 7.6328776e-05 |
| 4,703 | Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers | 2014 | VLDB | 6.5549049e-05 |
| 7,842 | Processing and Optimizing Main Memory Spatial-Keyword Queries | 2016 | VLDB | 5.5333985e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 5,230 | Optimizing Result Prefetching in Web Search Engines with Segmented Indices | 2002 | VLDB |
| 2 | 7,629 | Bitlist: New Full-text Index for Low Space Cost and Efficient Keyword Search | 2013 | VLDB |
| 3 | 2,948 | Optimized Query Execution in Large Search Engines with Global Page Ordering | 2003 | VLDB |
| 4 | 6,329 | An Eight-Dimensional Systematic Evaluation of Optimized Search Algorithms on Modern Processors | 2018 | VLDB |
| 5 | 11,790 | Minimization of Classifier Construction Cost for Search Queries | 2020 | SIGMOD |
| 6 | 1,989 | Incremental Updates of Inverted Lists for Text Document Retrieval | 1994 | SIGMOD |
| 7 | 2,245 | Fast Set Intersection in Memory | 2011 | VLDB |
| 8 | 1,655 | Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units | 2011 | VLDB |
| 9 | 1,717 | Improving the Performance of List Intersection | 2009 | VLDB |
| 10 | 11,888 | Document Reordering for Faster Intersection | 2019 | VLDB |