Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/25637
Title: Scalable, statistical storage allocation for extensible inverted file construction
Authors: Luk, RWP 
Keywords: Inverted file
Optimization
Storage allocation
Issue Date: 2011
Publisher: Elsevier
Source: Journal of systems and software, 2011, v. 84, no. 7, p. 1082-1088 How to cite?
Journal: Journal of systems and software 
Abstract: An Inverted file is a commonly used index for both archival databases and free text where no updates are expected. Applications like information filtering and dynamic environments like the Internet require inverted files to be updated efficiently. Recently, extensible inverted files are proposed which can be used for fast online indexing. The effective storage allocation scheme for such inverted files uses the arrival rate to preallocate storage. In this article, this storage allocation scheme is improved by using information about both the arrival rates and their variability to predict the storage needed, as well as scaling the storage allocation by a logarithmic factor. The resultant, final storage utilization rate can be as high as 97-98% after indexing about 1.6 million documents. This compares favorably with the storage utilization rate of the original arrival rate storage allocation scheme. Our evaluation shows that the retrieval time for extensible inverted file on solid state disk is on average similar to the retrieval time for in-memory extensible inverted file. When file seek time is not an issue, our scalable storage allocation enables extensible inverted files to be used as the main index on disk. Our statistical storage allocation may be applicable to novel situations where the arrival of items follows a binomial, Poisson or normal distribution.
URI: http://hdl.handle.net/10397/25637
ISSN: 0164-1212
DOI: 10.1016/j.jss.2011.01.049
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

1
Last Week
0
Last month
0
Citations as of Aug 19, 2017

WEB OF SCIENCETM
Citations

1
Last Week
0
Last month
0
Citations as of Aug 20, 2017

Page view(s)

37
Last Week
0
Last month
Checked on Aug 20, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.