Effective top-k

详细信息    查看全文

• 作者：Mingjie Zhu ; Shuming Shi ; Mingjing Li ; Ji-Rong Wen
• 关键词：Top-k ; Dynamic index pruning ; Term-proximity ; Document structure ; Proximity-Probe ; Non-linear ranking function ; Approximate top-k
• 刊名：Information Processing and Management
• 出版年：2009
• 出版时间：July 2009
• 年：2009
• 卷：45
• 期：4
• 页码：401-412
• 全文大小：413 K

文摘

Modern web search engines are expected to return the top-k results efficiently. Although many dynamic index pruning strategies have been proposed for efficient top-k computation, most of them are prone to ignoring some especially important factors in ranking functions, such as term-proximity (the distance relationship between query terms in a document). In our recent work [Zhu, M., Shi, S., Li, M., & Wen, J. (2007). Effective top-k computation in retrieving structured documents with term-proximity support. In Proceedings of 16th CIKM conference (pp. 771–780)], we demonstrated that, when term-proximity is incorporated into ranking functions, most existing index structures and top-k strategies become quite inefficient. To solve this problem, we built the inverted index based on web page structure and proposed the query processing strategies accordingly. The experimental results indicate that the proposed index structures and query processing strategies significantly improve the top-k efficiency. In this paper, we study the possibility of adopting additional techniques to further improve top-k computation efficiency. We propose a Proximity-Probe Heuristic to make our top-k algorithms more efficient. We also test the efficiency of our approaches on various settings (linear or non-linear ranking functions, exact or approximate top-k processing, etc.).