Title: | A tree-based inverted file for fast ranked-document retrieval |
Authors: | Shieh, WY Chen, TF Chung, CP 資訊工程學系 Department of Computer Science |
Keywords: | information retrieval;inverted file;Boolean query;ranked document;posting tree |
Issue Date: | 2003 |
Abstract: | Inverted files are widely used to index documents in large-scale information retrieval systems. An inverted file consists of posting lists, which can be stored in either a document-identifier ascending order or a document-weight descending order. For an identfier-ascending-order posting list, retrieving ranked documents necessitates traversal of all postings, whereas for the weight-descending-order posting list, performing Boolean queries involves very complex processing. In this paper, we transform a posting list to a tree-based structure, called the n-key-heap posting tree, to speedup ranked-document retrieval for Boolean queries. In this structure, the orders of document identfiers and document weights are preserved simultaneously. To preserve the identifier order, the edge pointers are designed to maintain numerical order in the posting tree. To preserve the weight order, greater-weight postings are stored in higher tree nodes by the heap property. We model these criteria to a tree-construction problem and propose an efficient algorithm to construct an optimal posting tree having the minimal access time. |
URI: | http://hdl.handle.net/11536/18625 |
ISBN: | 1-932415-09-2 |
Journal: | IKE'03: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON INFORMATION AND KNOWLEDGE ENGINEERING, VOLS 1 AND 2 |
Begin Page: | 64 |
End Page: | 69 |
Appears in Collections: | Conferences Paper |