Compressed web indexes

ABSTRACT

Web search engines use indexes to efficiently retrieve pages containing specified query terms, as well as pages linking to specified pages. The problem of compressed indexes that permit such fast retrieval has a long history. We consider the problem: assuming that the terms in (or links to) a page are generated from a probability distribution, how well compactly can we build such indexes that allow fast retrieval? Of particular interest is the case when the probability distribution is Zipfian (or a similar power law), since these are the distributions that arise on the web. We obtain sharp bounds on the space requirement of Boolean indexes for text documents that follow Zipf's law. In the process we develop a general technique that applies to any probability distribution, not necessarily a power law; this is the first analysis of compression in indexes under arbitrary distributions. Our bounds lead to quantitative versions of rules of thumb that are folklore in indexing. Our experiments on several document collections show that the distribution of terms appears to follow a double-Pareto law rather than Zipf's law. Despite widely varying sets of documents, the index sizes observed in the experiments conform well to our theoretical predictions.

REFERENCES

• 1: T. M. Apostol. Introduction to Analytic Number Theory. Springer-Verlag, 1976.
• 2: Ricardo Baeza-Yates , Gonzalo Nevarro, Block addressing indices for approximate text retrieval, Journal of the American Society for Information Science, v.51 n.1, p.69-82, Jan. 2000 [doi>10.1002/(SICI)1097-4571(2000)51:1<69::AID-ASI10>3.0.CO;2-C]
• 3: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 4: Albert-Laszlo Barabasi, Linked: How Everything Is Connected to Everything Else and What It Means, Plume, 2003
• 5: Dan Blandford , Guy Blelloch, Index Compression through Document Reordering, Proceedings of the Data Compression Conference, p.342, April 02-04, 2002
• 6: P. Boldi , S. Vigna, The webgraph framework I: compression techniques, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988752]
• 7: Paolo Boldi , Sebastiano Vigna, The WebGraph Framework II: Codes For The World-Wide Web, Proceedings of the Conference on Data Compression, p.528, March 23-25, 2004
• 8: Alexander F. Gelbukh , Grigori Sidorov, Zipf and Heaps Laws' Coefficients Depend on Language, Proceedings of the Second International Conference on Computational Linguistics and Intelligent Text Processing, p.332-335, February 18-24, 2001
• 9: L. Q. Ha, E. I. Sicilia-Garcia, J. Ming, and F. J. Smith. Extension of Zipf's law to word and character n-grams for English and Chinese. Computational Linguistics and Chinese Language Processing, 8(1):77--102, 2003.
• 10: H. S. Heaps, Information Retrieval: Computational and Theoretical Aspects, Academic Press, Inc., Orlando, FL, 1978
• 11: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1481-1493, May 17, 1999
• 12: W. Li. Random texts exhibit Zipf's-law-like word frequency distribution. IEEE Transactions on Information Theory, 38(6):1842--1845, 1992.
• 13: B. Mandelbrot. An information theory of the statistical structure of language. In W. Jackson, editor, Communication Theory, pages 486--502. Academic Press, 1953.
• 14: Christopher D. Manning , Prabhakar Raghavan , Hinrich Schtze, Introduction to Information Retrieval, Cambridge University Press, New York, NY, 2008
• 15: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 16: M. Mitzenmacher. Dynamic models for file sizes and double Pareto distributions. Internet Mathematics, 1(3):305--333, 2003.
• 17: M. Molloy and B. Reed. Graph Coloring and the Probabilistic Method. Springer-Verlag, 2002.
• 18: Mark Newman , Albert-Laszlo Barabasi , Duncan J. Watts, The Structure and Dynamics of Networks: (Princeton Studies in Complexity), Princeton University Press, Princeton, NJ, 2006
• 19: W. J. Reed and M. Jorgensen. The double Pareto-lognormal distribution - A new parametric model for size distributions. Communications in Statistics: Theory and Methods, 33(8):1733--1753, 2004.
• 20: Wann-Yun Shieh , Tien-Fu Chen , Jean Jyh-Jiun Shann , Chung-Ping Chung, Inverted file compression through document identifier reassignment, Information Processing and Management: an International Journal, v.39 n.1, p.117-131, January 2003 [doi>10.1016/S0306-4573(02)00020-1]
• 21: Fabrizio Silvestri , Raffaele Perego , Salvatore Orlando, Assigning document identifiers to enhance compressibility of Web Search Engines indexes, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968024]
• 22: H. A. Simon. On a class of skew distribution functions. Biometrika, 42:425--440, 1955.
• 23: D. C. van Leijenhorst , Th. P. van der Weide, A formal derivation of Heaps' Law, Information Sciences—Informatics and Computer Science: An International Journal, v.170 n.2-4, p.263-272, 25 February 2005 [doi>10.1016/j.ins.2004.03.006]
• 24: D. Watts. Six Degrees: The Science of a Connected Age. W. W. Norton, 2003.
• 25: H. E. Williams and J. Zobel. Searchable words on the web. International Journal on Digital Libraries, 5(2):99--105, 2005.
• 26: Ian H. Witten , T. C. Bell, Source models for natural language text, International Journal of Man-Machine Studies, v.32 n.5, p.545-579, May 1990 [doi>10.1016/S0020-7373(05)80033-1]
• 27: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 28: G. K. Zipf. Human Behavior and the Principle of Least Effort. Addison-Wesley, Cambridge MA, 1949

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
compression, double-pareto, index size, power law