Processing long queries against short text: Top-k advertisement matching in news stream applications

• Main Authors: ZHANG, Dongxiang, LI, Yuchen, FAN, Ju, GAO, Lianli, SHEN, Fumin, SHEN, Heng Tao
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2017
• Subjects: Long queries; short text; top-k retrieval; inverted index; rank-aware partitioning; Databases and Information Systems; Software Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/3995; https://ink.library.smu.edu.sg/context/sis_research/article/4997/viewcontent/a28_zhang__1_.pdf
• Institution: Singapore Management University

Many real applications in real-time news stream advertising call for efficient processing of long queriesagainst short text. In such applications, dynamic news feeds are regarded as queries to match against anadvertisement (ad) database for retrieving the k most relevant ads. The existing approaches to keywordretrieval cannot work well in this search scenario when queries are triggered at a very high frequency.To address the problem, we introduce new techniques to significantly improve search performance. First,we devise a two-level partitioning for tight upper bound estimation and a lazy evaluation scheme to delayfull evaluation of unpromising candidates, which can bring three to four times performance boosting in adatabase with 7 million ads. Second, we propose a novel rank-aware block-oriented inverted index to furtherimprove performance. In this index scheme, each entry in an inverted list is assigned a rank according toits importance in the ad. Then, we introduce a block-at-a-time search strategy based on the index scheme tosupport a much tighter upper bound estimation and a very early termination. We have conducted experimentswith real datasets, and the results show that the rank-aware method can further improve performance byan order of magnitude.