The DOI matches its Crossref record; 86 of the 86 references it cites were found in a registry or an index.
Inverted files for text search engines
Open accessAbstract
The technology underlying text search engines has advanced dramatically in the past decade. The development of a family of new index representations has led to a wide range of innovations in index storage, index construction, and query evaluation. While some of these developments have been consolidated in textbooks, many specific techniques are not widely known or the textbook descriptions are out of date. In this tutorial, we introduce the key techniques in the area, describing both a core implementation and how the core can be enhanced through a range of extensions. We conclude with a comprehensive bibliography of text indexing literature.
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
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004
Baeza-Yates, R. A., & Ribeiro-Neto, B. A. (1999) · Cited by 11,505
Introduction to Modern Information Retrieval
Salton, G., & McGill, M. J. (1983) · Virtual Defense Library (Ministerio de Defensa) · Cited by 11,392
Foundations of statistical natural language processing
Manning, C. D., & Schütze, H. (1999) · Cited by 9,816
Term-weighting approaches in automatic text retrieval
Salton, G., & Buckley, C. (1988) · Information Processing & Management · doi:10.1016/0306-4573(88)90021-0 · Cited by 9,740
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 8,959
A vector space model for automatic indexing
Salton, G., Wong, A., & Yang, C. S. (1975) · Communications of the ACM · doi:10.1145/361219.361220 · Cited by 7,521
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
Information Retrieval: Data Structures and Algorithms
Frakes, W. B., & Baeza-Yates, R. A. (1992) · Cited by 2,757
A Language Modeling Approach to Information Retrieval
Ponte, J. M., & Croft, W. B. (2017) · ACM SIGIR Forum · doi:10.1145/3130348.3130368 · Cited by 2,503
The SMART Retrieval System—Experiments in Automatic Document Processing
Salton, G. (1971) · CERN Document Server (European Organization for Nuclear Research) · Cited by 2,252
Robertson, S. E., Walker, S., Jones, S., Hancock‐Beaulieu, M., & Gatford, M. (1994) · Text REtrieval Conference · Cited by 2,212
Introduction to Data Compression
(2018) · Elsevier eBooks · doi:10.1016/c2015-0-06248-7 · Cited by 2,129
A language modeling approach to information retrieval
Ponte, J. M., & Croft, W. B. (1998) · Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/290941.291008 · Cited by 1,821
Data Compression: The Complete Reference
(2009) · Kybernetes · doi:10.1108/k.2009.06738eae.001 · Cited by 1,591
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
THE PROBABILITY RANKING PRINCIPLE IN IR
ROBERTSON, S. E. (1977) · Journal of Documentation · doi:10.1108/eb026647 · Cited by 1,103
A Statistical Approach to Mechanized Encoding and Searching of Literary Information
Luhn, H. P. (1957) · IBM Journal of Research and Development · doi:10.1147/rd.14.0309 · Cited by 1,093
Searching the web: The public and their queries
Spink, A., Wolfram, D., Jansen, M. B. J., & Saracevic, T. (2001) · Journal of the American Society for Information Science and Technology · doi:10.1002/1097-4571(2000)9999:9999<::aid-asi1591>3.0.co;2-r · Cited by 1,084
Readings in information retrieval
Jones, K. S., & Willett, P. (1997) · Morgan Kaufmann Publishers Inc. eBooks · Cited by 1,069
Web search for a planet: the google cluster architecture
Barroso, L. A., Dean, J., & Holzle, U. (2003) · IEEE Micro · doi:10.1109/mm.2003.1196112 · Cited by 1,025
Run-length encodings (Corresp.)
Golomb, S. (1966) · IEEE Transactions on Information Theory · doi:10.1109/tit.1966.1053907 · Cited by 988
Bell, T., Cleary, J. G., & Witten, I. H. (1990) · Cited by 988
A probabilistic model of information retrieval: development and comparative experiments
Sparck Jones, K., Walker, S., & Robertson, S. E. (2000) · Information Processing & Management · doi:10.1016/s0306-4573(00)00015-7 · Cited by 942
On Relevance, Probabilistic Indexing and Information Retrieval
Maron, M. E., & Kuhns, J. L. (1960) · Journal of the ACM · doi:10.1145/321033.321035 · Cited by 907
Pivoted Document Length Normalization
Singhal, A., Buckley, C., & Mitra, M. (2017) · ACM SIGIR Forum · doi:10.1145/3130348.3130365 · Cited by 848
TREC: Experiment and evaluation in information retrieval
Vicedo, J. L., & Gómez, J. (2007) · Journal of the American Society for Information Science and Technology · doi:10.1002/asi.20583 · Cited by 837
Santini, S., & Jain, R. (1999) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.790428 · Cited by 761
Managing gigabytes (2nd ed.): compressing and indexing documents and images
Witten, I. H., Moffat, A., & Bell, T. (1999) · Morgan Kaufmann Publishers Inc. eBooks · Cited by 705
Self-citationProceedings of the International Conference on Very Large Data Bases
Kerr, D. S. (1975) · ACM eBooks · Cited by 701
Information retrieval, computational and theoretical aspects
Heaps, H. S. (1978) · CERN Document Server (European Organization for Nuclear Research) · Cited by 598
Information retrieval on the web
Kobayashi, M., & Takeda, K. (2000) · ACM Computing Surveys · doi:10.1145/358923.358934 · Cited by 562
Pivoted document length normalization
Singhal, A., Buckley, C., & Mitra, M. (1996) · Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval - SIGIR '96 · doi:10.1145/243199.243206 · Cited by 551
Information Retrieval: Algorithms and Heuristics
Grossman, D. A., & Frieder, O. (1998) · The Kluwer International Series in Engineering and Computer Science · doi:10.1007/978-1-4615-5539-1 · Cited by 537
Arasu, A., Cho, J., Garcia-Molina, H., Paepcke, A., & Raghavan, S. (2001) · ACM Transactions on Internet Technology · doi:10.1145/383034.383035 · Cited by 505
Voorhees, E. M., & Harman, D. K. (2005) · The MIT Press eBooks · Cited by 392
Distributed Information Retrieval
Callan, J. (2005) · Kluwer Academic Publishers eBooks · doi:10.1007/0-306-47019-5_5 · Cited by 389
Exploring the similarity space
Zobel, J., & Moffat, A. (1998) · ACM SIGIR Forum · doi:10.1145/281250.281256 · Cited by 378
Self-citationResearch and Development in Information Retrieval
(1983) · Lecture Notes in Computer Science · doi:10.1007/bfb0036332 · Cited by 378
Language Modeling for Information Retrieval
(2003) · Springer eBooks · doi:10.1007/978-94-017-0171-6 · Cited by 371
Self-indexing inverted files for fast text retrieval
Moffat, A., & Zobel, J. (1996) · ACM Transactions on Information Systems · doi:10.1145/237496.237497 · Cited by 361
Self-citationInverted 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-citationTREC: Experiment and Evaluation in Information Retrieval
(2007) · Online Information Review · doi:10.1108/14684520710832478 · Cited by 323
Analysis and performance of inverted data base structures
Cárdenas, A. F. (1975) · Communications of the ACM · doi:10.1145/360762.360766 · Cited by 306
Query evaluation: Strategies and optimizations
Turtle, H., & Flood, J. (1995) · Information Processing & Management · doi:10.1016/0306-4573(95)00020-h · Cited by 305
Combinatorial Algorithms on Words
(1985) · Springer eBooks · doi:10.1007/978-3-642-82456-2 · Cited by 289
Some practical universal noiseless coding techniques
Rice, R. F. (1979) · NASA STI Repository (National Aeronautics and Space Administration) · Cited by 271
GLIMPSE: a tool to search through entire file systems
Manber, U., & Wu, S. (1994) · USENIX Winter Technical Conference · Cited by 251
Optimization 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
Vector-space ranking with effective early termination
Anh, V. N., de Kretser, O., & Moffat, A. (2001) · Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/383952.383957 · Cited by 207
Self-citationStatic index pruning for information retrieval systems
Carmel, D., Cohen, D., Fagin, R., Farchi, E., Herscovici, M., Maarek, Y. S., & Soffer, A. (2001) · Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/383952.383958 · Cited by 207
Grossman, D. A., & Frieder, O. (2004) · Springer eBooks · Cited by 197
A compression method for clustered bit-vectors
Teuhola, J. (1978) · Information Processing Letters · doi:10.1016/0020-0190(78)90024-8 · Cited by 197
A survey of information retrieval and filtering methods
Faloutsos, C., & Oard, D. W. (1995) · University Libraries (University of Maryland) · Cited by 193
Predictive caching and prefetching of query results in search engines
Lempel, R., & Moran, S. (2003) · Proceedings of the twelfth international conference on World Wide Web - WWW '03 · doi:10.1145/775152.775156 · Cited by 176
Relevance ranking for one to three term queries
Clarke, C. L. A., Cormack, G. V., & Tudhope, E. A. (2000) · Information Processing & Management · doi:10.1016/s0306-4573(99)00017-5 · Cited by 170
Automatic abstracting and indexing—survey and recommendations
Edmundson, H. P., & Wyllys, R. E. (1961) · Communications of the ACM · doi:10.1145/366532.366545 · Cited by 166
The SMART retrieval system; experiments in automatic document processing
Hayes, R. M. (1973) · Information Processing & Management · doi:10.1016/0020-0271(73)90067-3 · Cited by 136
Walzer, M. (2004) · Cited by 135
Rank-preserving two-level caching for scalable search engines
Saraiva, P. C., de Moura, E. S., Ziviani, N., Meira, W., Fonseca, R., & Ribeiro-Neto, B. A. (2001) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/383952.383959 · Cited by 134
Indexing Techniques for Advanced Database Systems
Bertino, E., Ooi, B. C., Sacks‐Davis, R., Tan, K., Zobel, J., Shidlovsky, B., & Catania, B. (1997) · Springer eBooks · doi:10.1007/978-1-4615-6227-6 · Cited by 130
Self-citationRetrieving 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
A pipelined architecture for distributed text query evaluation
Moffat, A., Webber, W., Zobel, J., & Baeza-Yates, R. A. (2006) · Information Retrieval · doi:10.1007/s10791-006-9014-4 · Cited by 110
Self-citationOptimization strategies for complex queries
Strohman, T., Turtle, H. R., & Croft, W. B. (2005) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/1076034.1076074 · Cited by 103
Adding Compression to Block Addressing Inverted Indexes
Navarro, G., de Moura, E. S., Neubert, M., Ziviani, N., & Baeza-Yates, R. A. (2000) · Information Retrieval · doi:10.1023/a:1009934302807 · Cited by 101
Efficient passage ranking for document databases
Kaszkiel, M., Zobel, J., & Sacks‐Davis, R. (1999) · ACM Transactions on Information Systems · doi:10.1145/326440.326445 · Cited by 83
Self-citationSalton, G., & Buckley, C. (1988) · Communications of the ACM · doi:10.1145/42372.42380 · Cited by 73
Effective document presentation with a locality-based similarity heuristic
de Kretser, O., & Moffat, A. (1999) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/312624.312664 · Cited by 73
Self-citationA review of the use of inverted files for best match searching in information retrieval systems
Perry, S. A., & Willett, P. (1983) · Journal of Information Science · doi:10.1177/016555158300600204 · Cited by 67
Building a distributed full-text index for the web
Melink, S., Raghavan, S., Yang, B., & García-Molina, H. (2001) · ACM Transactions on Information Systems · doi:10.1145/502115.502116 · Cited by 61
Compressed inverted files with reduced decoding overheads
Vo, A. N., & Moffat, A. (1998) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/290941.291011 · Cited by 59
Self-citationImplementing ranking strategies using text signatures
Croft, W. B., & Savino, P. (1988) · ACM Transactions on Information Systems · doi:10.1145/42279.45947 · Cited by 58
The nearest neighbour problem in information retrieval: an algorithm using upperbounds
Smeaton, A. F., & van Rijsbergen, C. J. (1981) · ACM SIGIR Forum · doi:10.1145/1013228.511767 · Cited by 56
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-citationOptimizing result prefetching in web search engines with segmented indices
Lempel, R., & Moran, S. (2004) · ACM Transactions on Internet Technology · doi:10.1145/967030.967032 · Cited by 46
Assigning identifiers to documents to enhance the clustering property of fulltext indexes
Silvestri, F., Orlando, S., & Perego, R. (2004) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/1008992.1009046 · Cited by 43
Space-Limited Ranked Query Evaluation Using Adaptive Pruning
Lester, N., Moffat, A., Webber, W., & Zobel, J. (2005) · Lecture notes in computer science · doi:10.1007/11581062_37 · Cited by 38
Self-citationGarcia, S., Williams, H. E., & Cannane, A. (2004) · Cited by 37
Parallel text searching in serial files using a processor farm
Cringean, J. K., England, R., Manson, G. A., & Willett, P. (1989) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/96749.98249 · Cited by 25
Competitive caching of query results in search engines
Lempel, R., & Moran, S. (2004) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.05.018 · Cited by 15
The nearest neighbour problem in information retrieval: an algorithm using upperbounds
Smeaton, A. F., & van Rijsbergen, C. J. (1981) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/511754.511767 · Cited by 15
An inverted index implementation
McDonell, K. J. (1977) · The Computer Journal · doi:10.1093/comjnl/20.2.116 · Cited by 10
Cited by
The RDF-3X engine for scalable management of RDF data
Neumann, T., & Weikum, G. (2010) · The VLDB Journal · doi:10.1007/s00778-009-0165-y · Cited by 635
RDF-3X: a RISC-style engine for RDF
Neumann, T., & Weikum, G. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1453856.1453927 · Cited by 562
A review on automatic image annotation techniques
Zhang, D., Islam, M. M., & Lu, G. (2012) · Pattern Recognition · doi:10.1016/j.patcog.2011.05.013 · Cited by 479
Data-intensive text processing with MapReduce
Lin, J., & Dyer, C. (2009) · Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Companion Volume: Tutorial Abstracts on - NAACL '09 · doi:10.3115/1620950.1620951 · Cited by 445
Sketch-Based Image Retrieval: Benchmark and Bag-of-Features Descriptors
Eitz, M., Hildebrand, K., Boubekeur, T., & Alexa, M. (2011) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2010.266 · Cited by 413
Metadata
- Authors
- Zobel, J., & Moffat, A.
- Venue
- ACM Computing Surveys
- Published
- 2006-07-25
- Volume
- 38
- Issue
- 2
- Pages
- 6
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W2138662031
- Cited by
- 1,081
- References
- 86
- FWCI
- 65.44
- Type
- journal article
- Language
- en
- Open access
- green
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.