Incremental cluster-based retrieval using compressed cluster-skipping inverted files

ABSTRACT

We propose a unique cluster-based retrieval (CBR) strategy using a new cluster-skipping inverted file for improving query processing efficiency. The new inverted file incorporates cluster membership and centroid information along with the usual document information into a single structure. In our incremental-CBR strategy, during query evaluation, both best(-matching) clusters and the best(-matching) documents of such clusters are computed together with a single posting-list access per query term. As we switch from term to term, the best clusters are recomputed and can dynamically change. During query-document matching, only relevant portions of the posting lists corresponding to the best clusters are considered and the rest are skipped. The proposed approach is essentially tailored for environments where inverted files are compressed, and provides substantial efficiency improvement while yielding comparable, or sometimes better, effectiveness figures. Our experiments with various collections show that the incremental-CBR strategy using a compressed cluster-skipping inverted file significantly improves CPU time efficiency, regardless of query length. The new compressed inverted file imposes an acceptable storage overhead in comparison to a typical inverted file. We also show that our approach scales well with the collection size.

REFERENCES

• 1: Altingovde, I. S., Can, F., and Ulusoy, Ö. 2006. Algorithms for within-cluster searches using inverted files. In Proceedings of the International Symposium on Computer and Information Sciences (ISCIS). 707--716.
• 2: Ismail Sengor Altingovde , Rifat Ozcan , Huseyin Cagdas Ocalan , Fazli Can , Özgür Ulusoy, Large-scale cluster-based retrieval experiments on Turkish texts, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277961]
• 3: Vo Ngoc Anh , Owen de Kretser , Alistair Moffat, Vector-space ranking with effective early termination, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.35-42, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383957]
• 4: Vo Ngoc Anh , Alistair Moffat, Inverted Index Compression Using Word-Aligned Binary Codes, Information Retrieval, v.8 n.1, p.151-166, January 2005 [doi>10.1023/B:INRT.0000048490.99518.5c]
• 5: Vo Ngoc Anh , Alistair Moffat, Simplified similarity scoring using term ranks, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076075]
• 6: Vo Ngoc Anh , Alistair Moffat, Pruned query evaluation using pre-computed impacts, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148235]
• 7: Ricardo Baeza-Yates , Aristides Gionis , Flavio Junqueira , Vanessa Murdock , Vassilis Plachouras , Fabrizio Silvestri, The impact of caching on search engines, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277775]
• 8: Dan Blandford , Guy Blelloch, Index Compression through Document Reordering, Proceedings of the Data Compression Conference (DCC '02), p.342, April 02-04, 2002
• 9: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 10: Eric W. Brown, Fast evaluation of structured queries for information retrieval, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.30-38, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215329]
• 11: Chris Buckley , Alan F. Lewit, Optimization of inverted vector searches, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.97-110, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253515]
• 12: Chris Buckley , Ellen M. Voorhees, Evaluating evaluation measure stability, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.33-40, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345543]
• 13: Cacheda, F. and Baeza-Yates, R. 2004. An optimistic model for searching Web directories. In Proceedings of the 26th European Conference on IR Research (ECIR). 364--377.
• 14: Cacheda, F., Carneiro, V., Guerrero, C., and Viña, Á. 2003. Optimization of restricted searches in Web directories using hybrid data structures. In Proceedings of the 25th European Conference on IR Research (ECIR). 436--451.
• 15: Cambazoglu, B. B. 2006. Models and algorithms for parallel text retrieval. Ph.D. thesis, Bilkent University, Ankara, Turkey.
• 16: B. Barla Cambazoglu , Cevdet Aykanat, Performance of query processing implementations in ranking-based text retrieval systems using inverted indices, Information Processing and Management: an International Journal, v.42 n.4, p.875-898, July 2006 [doi>10.1016/j.ipm.2005.06.004]
• 17: Fazli Can, Incremental clustering for dynamic information processing, ACM Transactions on Information Systems (TOIS), v.11 n.2, p.143-164, April 1993 [doi>10.1145/130226.134466]
• 18: Fazli Can, On the efficiency of best-match cluster searches, Information Processing and Management: an International Journal, v.30 n.3, p.343-361, May-June 1994 [doi>10.1016/0306-4573(94)90049-3]
• 19: Fazli Can , Ismail Sengör Altingövde , Engin Demir, Efficiency and effectiveness of query processing in cluster-based retrieval, Information Systems, v.29 n.8, p.697-717, December 2004 [doi>10.1016/S0306-4379(03)00062-0]
• 20: Fazli Can , Esen A. Ozkarahan, Concepts and effectiveness of the cover-coefficient-based clustering methodology for text databases, ACM Transactions on Database Systems (TODS), v.15 n.4, p.483-517, Dec. 1990 [doi>10.1145/99935.99938]
• 21: Croft, W. B. 1980. A model of cluster searching based on classification. Inf. Syst. 5, 3, 189--195.
• 22: Donna Harman, Ranking algorithms, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 23: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 24: Jardine, N. and van Rijsbergen, C. J. 1971. The use of hierarchical clustering in information retrieval. Inf. Storage Retr. 7, 217--240.
• 25: Lester, N., Moffat, A., Webber, W., and Zobel, J. 2005. Space-Limited ranked query evaluation using adaptive pruning. In Proceedings of the 6th International Conference on Web Information Systems Engineering, New York, 470--477.
• 26: Xiaoyong Liu , W. Bruce Croft, Cluster-based retrieval using language models, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009026]
• 27: Xiaohui Long , Torsten Suel, Optimized query execution in large search engines with global page ordering, Proceedings of the 29th international conference on Very large data bases, p.129-140, September 09-12, 2003, Berlin, Germany
• 28: Alistair Moffat , Justin Zobel, Self-indexing inverted files for fast text retrieval, ACM Transactions on Information Systems (TOIS), v.14 n.4, p.349-379, Oct. 1996 [doi>10.1145/237496.237497]
• 29: Daniel Mcclure Murray, Document retrieval based on clustered files, Cornell University, Ithaca, NY, 1972
• 30: Rabia Nuray , Fazli Can, Automatic ranking of information retrieval systems using data fusion, Information Processing and Management: an International Journal, v.42 n.3, p.595-614, May 2006 [doi>10.1016/j.ipm.2005.03.023]
• 31: Michael Persin, Document filtering for fast ranking, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.339-348, July 03-06, 1994, Dublin, Ireland
• 32: Michael Persin , Justin Zobel , Ron Sacks-Davis, Filtered document retrieval with frequency-sorted indexes, Journal of the American Society for Information Science, v.47 n.10, p.749-764, Oct. 1996 [doi>10.1002/(SICI)1097-4571(199610)47:10<749::AID-ASI3>3.3.CO;2-U]
• 33: Gerard Salton, Dynamic information and library processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1975
• 34: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 35: Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0]
• 36: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 37: Fabrizio Silvestri , Salvatore Orlando , Raffaele Perego, Assigning identifiers to documents to enhance the clustering property of fulltext indexes, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009046]
• 38: Silvestri, F. 2007. Sorting out the document identifier assignment problem. In Proceedings of the 29th European Conference on IR Research (ECIR). 101--112.
• 39: Stanford University. 2007. Webbase project Web site. www-diglib.stanford.edu/~testbed/doc2/WebBase.
• 40: Trevor Strohman , W. Bruce Croft, Efficient document retrieval in main memory, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277774]
• 41: Trec 2006. Trec. Web site. http://trec.nist.gov.
• 42: Tombros, A. 2002. The effectiveness of query-based hierarchic clustering of documents for information retrieval. Ph.D. thesis, University of Glasgow, Glasgow, UK.
• 43: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 44: Ellen M. Voorhees, The cluster hypothesis revisited, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.188-196, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253524]
• 45: Ellen Marie Voorhees, The effectiveness and efficiency of agglomerative hierarchic clustering in document retrieval, Cornell University, Ithaca, NY, 1986
• 46: Ellen M. Voorhees, The efficiency of inverted index and cluster searches, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.164-174, September 1986, Palazzo dei Congressi, Pisa, Italy [doi>10.1145/253168.253203]
• 47: Peter Willett, Recent trends in hierarchic document clustering: a critical review, Information Processing and Management: an International Journal, v.24 n.5, p.577-597, 1988 [doi>10.1016/0306-4573(88)90027-1]
• 48: Ian H. Witten , Timothy C. Bell , Alistair Moffat, Managing Gigabytes: Compressing and Indexing Documents and Images, John Wiley & Sons, Inc., New York, NY, 1994
• 49: Zettair 2007. The Zettair search engine. http://www.seg.rmit.edu.au/zettair/.
• 50: Justin Zobel , Alistair Moffat, Inverted files for text search engines, ACM Computing Surveys (CSUR), v.38 n.2, p.6-es, 2006 [doi>10.1145/1132956.1132959]

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization
      H.3.3 Information Search and Retrieval
          Subjects: Clustering; Search process

General Terms:
Experimentation, Measurement, Performance

Keywords:
Best match, cluster-based retrieval (CBR), cluster-skipping inverted index structure (CS-IIS), full search (FS), index compression, inverted index structure (IIS), query processing