Witten et al. (1999, Chapter 5) present an extensive treatment of the subject of index construction and additional indexing algorithms with different tradeoffs of memory, disk space, and time. In general, blocked sort-based indexing does well on all three counts. However, if conserving memory or disk space is the main criterion, then other algorithms may be a better choice. See Witten et al. (1999), Tables 5.4 and 5.5; BSBI is closest to ``sort-based multiway merge,'' but the two algorithms differ in dictionary structure and use of compression.
Moffat and Bell (1995) show how to construct an index ``in situ,'' that is, with disk space usage close to what is needed for the final index and with a minimum of additional temporary files (cf. also Harman and Candela (1990)). They give Lesk (1988) and Somogyi (1990) credit for being among the first to employ sorting for index construction.
The SPIMI method in Section 4.3 is from (Heinz and Zobel, 2003). We have simplified several aspects of the algorithm, including compression and the fact that each term's data structure also contains, in addition to the postings list, its document frequency and house keeping information. We recommend Heinz and Zobel (2003) and Zobel and Moffat (2006) as up-do-date, in-depth treatments of index construction. Other algorithms with good scaling properties with respect to vocabulary size require several passes through the data, e.g., FAST-INV (Harman et al., 1992, Fox and Lee, 1991).
The MapReduce architecture was introduced by Dean and Ghemawat (2004). An open source implementation of MapReduce is available at http://lucene.apache.org/hadoop/. Ribeiro-Neto et al. (1999) and Melnik et al. (2001) describe other approaches to distributed indexing. Introductory chapters on distributed IR are (Baeza-Yates and Ribeiro-Neto, 1999, Chapter 9) and (Grossman and Frieder, 2004, Chapter 8). See also Callan (2000).
Lester et al. (2005) and Büttcher and Clarke (2005a) analyze the properties of logarithmic merging and compare it with other construction methods. One of the first uses of this method was in Lucene (http://lucene.apache.org). Other dynamic indexing methods are discussed by Büttcher et al. (2006) and Lester et al. (2006). The latter paper also discusses the strategy of replacing the old index by one built from scratch.
Heinz et al. (2002) compare data structures for accumulating the vocabulary in memory. Büttcher and Clarke (2005b) discuss security models for a common inverted index for multiple users. A detailed characterization of the Reuters-RCV1 collection can be found in (Lewis et al., 2004). NIST distributes the collection (see http://trec.nist.gov/data/reuters/reuters.html).
Garcia-Molina et al. (1999, Chapter 2) review computer hardware relevant to system design in depth.
An effective indexer for enterprise search needs to be able to communicate efficiently with a number of applications that hold text data in corporations, including Microsoft Outlook, IBM's Lotus software, databases like Oracle and MySQL, content management systems like Open Text, and enterprise resource planning software like SAP.