The DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
Self-indexing inverted files for fast text retrieval
Open accessAbstract
Query-processing costs on large text databases are dominated by the need to retrieve and scan the inverted list of each query term. Retrieval time for inverted lists can be greatly reduced by the use of compression, but this adds to the CPU time required. Here we show that the CPU component of query response time for conjunctive Boolean queries and for informal ranked queries can be similarly reduced, at little cost in terms of storage, by the inclusion of an internal index in each compressed inverted list. This method has been applied in a retrieval system for a collection of nearly two million short documents. Our experimental results show that the self-indexing strategy adds less than 20% to the size of the compressed inverted file, which itself occupies less than 10% of the indexed text, yet can reduce processing time for Boolean queries of 5-10 terms to under one fifth of the previous cost. Similarly, ranked queries of 40-50 terms can be evaluated in as little as 25% of the previous time, with little or no loss of retrieval effectiveness.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
Introduction to Modern Information Retrieval
Salton, G., & McGill, M. J. (1983) · Virtual Defense Library (Ministerio de Defensa) · Cited by 11,392
Grossman, P. (2009) · Discrete Mathematics for Computing · doi:10.1007/978-0-230-37405-8_1 · Cited by 8,834
Introduction to modern information retrieval
Dillon, M. (1983) · Information Processing & Management · doi:10.1016/0306-4573(83)90062-6 · Cited by 5,909
Automatic text processing: the transformation, analysis, and retrieval of information by computer
(1989) · Choice Reviews Online · doi:10.5860/choice.27-0351 · Cited by 3,188
Fundamentals of Database Systems
Elmasri, R. A., & Navathe, S. B. (1989) · Cited by 3,141
Information Retrieval: Data Structures and Algorithms
Frakes, W. B., & Baeza-Yates, R. A. (1992) · Cited by 2,757
Universal codeword sets and representations of the integers
Elias, P. (1975) · IEEE Transactions on Information Theory · doi:10.1109/tit.1975.1055349 · Cited by 1,165
Development of a Stemming Algorithm
Lovins, J. B. (1968) · Mech. Transl. Comput. Linguistics · Cited by 1,115
Run-length encodings (Corresp.)
Golomb, S. (1966) · IEEE Transactions on Information Theory · doi:10.1109/tit.1966.1053907 · Cited by 988
Managing Gigabytes: Compressing and Indexing Documents and Images
Witten, I. H., Moffat, A., & Bell, T. C. (1995) · IEEE Transactions on Information Theory · doi:10.1109/tit.1995.476344 · Cited by 726
Self-citationOptimization of inverted vector searches
Buckley, C., & Lewit, A. F. (1985) · Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval - SIGIR '85 · doi:10.1145/253495.253515 · Cited by 216
A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets
Hwang, F. K., & Lin, S. (1972) · SIAM Journal on Computing · doi:10.1137/0201004 · Cited by 148
Retrieving records from a gigabyte of text on a minicomputer using statistical ranking
Harman, D. K., & Candela, G. T. (1990) · Journal of the American Society for Information Science · doi:10.1002/(sici)1097-4571(199012)41:8<581::aid-asi4>3.0.co;2-u · Cited by 129
Implementing ranking strategies using text signatures
Croft, W. B., & Savino, P. (1988) · ACM Transactions on Information Systems · doi:10.1145/42279.45947 · Cited by 58
Efficient retrieval of partial documents
Zobel, J., Moffat, A., Wilkinson, R. G., & Sacks‐Davis, R. (1995) · Information Processing & Management · doi:10.1016/0306-4573(94)00052-5 · Cited by 55
Self-citationAn inverted index implementation
McDonell, K. J. (1977) · The Computer Journal · doi:10.1093/comjnl/20.2.116 · Cited by 10
(1990)
Cited by
Inverted files for text search engines
Zobel, J., & Moffat, A. (2006) · ACM Computing Surveys · doi:10.1145/1132956.1132959 · Cited by 1,081
Self-citationScaling up all pairs similarity search
Bayardo, R. J., Ma, Y., & Srikant, R. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242591 · Cited by 673
High-order entropy-compressed text indexes
Grossi, R., Gupta, A. K., & Vitter, J. S. (2003) · doi:10.5555/644108.644250 · Cited by 648
Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
Grossi, R., & Vitter, J. S. (2005) · SIAM Journal on Computing · doi:10.1137/s0097539702402354 · Cited by 431
Inverted files versus signature files for text indexing
Zobel, J., Moffat, A., & Ramamohanarao, K. (1998) · ACM Transactions on Database Systems · doi:10.1145/296854.277632 · Cited by 341
Self-citation
Metadata
- Authors
- Moffat, A., & Zobel, J.
- Venue
- ACM Transactions on Information Systems
- Published
- 1996-10
- Volume
- 14
- Issue
- 4
- Pages
- 349-379
- ISSN
- 1046-8188 (ISSN-L)
- 1558-2868
- OpenAlex
- W2125203709
- Cited by
- 361
- References
- 18
- FWCI
- 8.65
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.