Content-based document routing and index partitioning for scalable similarity-based searches in a large corpus

ABSTRACT

We present a document routing and index partitioning scheme for scalable similarity-based search of documents in a large corpus. We consider the case when similarity-based search is performed by finding documents that have features in common with the query document. While it is possible to store all the features of all the documents in one index, this suffers from obvious scalability problems. Our approach is to partition the feature index into multiple smaller partitions that can be hosted on separate servers, enabling scalable and parallel search execution. When a document is ingested into the repository, a small number of partitions are chosen to store the features of the document. To perform similarity-based search, also, only a small number of partitions are queried. Our approach is stateless and incremental. The decision as to which partitions the features of the document should be routed to (for storing at ingestion time, and for similarity based search at query time) is solely based on the features of the document.

Our approach scales very well. We show that executing similarity-based searches over such a partitioned search space has minimal impact on the precision and recall of search results, even though every search consults less than 3% of the total number of partitions.

REFERENCES

• 1: Atul Adya , William J. Bolosky , Miguel Castro , Gerald Cermak , Ronnie Chaiken , John R. Douceur , Jon Howell , Jacob R. Lorch , Marvin Theimer , Roger P. Wattenhofer, Farsite: federated, available, and reliable storage for an incompletely trusted environment, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060291]
• 2: Miklos Ajtai , Randal Burns , Ronald Fagin , Darrell D. E. Long , Larry Stockmeyer, Compactly encoding unstructured inputs with differential compression, Journal of the ACM (JACM), v.49 n.3, p.318-367, May 2002 [doi>10.1145/567112.567116]
• 3: Sergey Brin , James Davis , Héctor García-Molina, Copy detection mechanisms for digital documents, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.398-409, May 22-25, 1995, San Jose, California, United States
• 4: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 5: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations, Journal of Computer and System Sciences, v.60 n.3, p.630-659, June 2000 [doi>10.1006/jcss.1999.1690]
• 6: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Computer Networks and ISDN Systems, v.29 n.8-13, p.1157-1166, Sep. 1997
• 7: Joselíto J. Chua , Peter E. Tischer, Strategies for Cooperative Search in Distributed Databases, Proceedings of the IEEE/WIC International Conference on Intelligent Agent Technology, p.325, October 13-17, 2003
• 8: Brian F. Cooper, Guiding queries to information sources with InfoBeacons, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
• 9: Landon P. Cox , Christopher D. Murray , Brian D. Noble, Pastiche: making backup cheap and easy, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060316]
• 10: Peter B. Danzig , Jongsuk Ahn , John Noll , Katia Obraczka, Distributed indexing: a scalable mechanism for distributed information retrieval, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.220-229, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122883]
• 11: F. Douglis and A. Iyengar. Application-specific delta-encoding via resemblance detection. In Proceedings of the 2003 USENIX Annual Technical Conference, pages 113--126. USENIX, June 2003.
• 12: Peter Druschel , Antony Rowstron, PAST: A Large-Scale, Persistent Peer-to-Peer Storage Utility, Proceedings of the Eighth Workshop on Hot Topics in Operating Systems, p.75, May 20-22, 2001
• 13: K. Eshghi and H. K. Tang. A framework for analyzing and improving content-based chunking algorithms. Technical Report HPL-2005-30(R.1), Hewlett Packard Laboraties, Palo Alto, 2005.
• 14: Ronald Fagin , Ravi Kumar , D. Sivakumar, Comparing top k lists, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 15: George Forman , Kave Eshghi , Stephane Chiocchetti, Finding similar files in large document repositories, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081916]
• 16: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 17: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 18: Purushottam Kulkarni , Fred Douglis , Jason LaVoie , John M. Tracey, Redundancy elimination within large collections of files, Proceedings of the annual conference on USENIX Annual Technical Conference, p.5-5, June 27-July 02, 2004, Boston, MA
• 19: Mark Lillibridge , Sameh Elnikety , Andrew Birrell , Mike Burrows , Michael Isard, A cooperative internet backup scheme, Proceedings of the annual conference on USENIX Annual Technical Conference, p.3-3, June 09-14, 2003, San Antonio, Texas
• 20: Witold Litwin , Marie-Anna Neimat , Donovan A. Schneider, LH*—a scalable, distributed data structure, ACM Transactions on Database Systems (TODS), v.21 n.4, p.480-525, Dec. 1996 [doi>10.1145/236711.236713]
• 21: Jie Lu , Jamie Callan, User modeling for full-text federated search in peer-to-peer networks, 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.1148229]
• 22: Udi Manber, Finding similar files in a large file system, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.2-2, January 17-21, 1994, San Francisco, California
• 23: Gurmeet Singh Manku, Routing networks for distributed hash tables, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.133-142, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872054]
• 24: Athicha Muthitacharoen , Benjie Chen , David Mazières, A low-bandwidth network file system, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 25: Zan Ouyang , Nasir D. Memon , Torsten Suel , Dimitre Trendafilov, Cluster-Based Delta Compression of a Collection of Files, Proceedings of the 3rd International Conference on Web Information Systems Engineering, p.257-268, December 12-14, 2002
• 26: Sean Quinlan , Sean Dorward, Venti: A New Approach to Archival Storage, Proceedings of the Conference on File and Storage Technologies, p.89-101, January 28-30, 2002
• 27: M. O. Rabin. Fingerprinting by random polynomials. Technical Report TR-15-81, Center for Research in Computing Technology, Harvard University, 1981.
• 28: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 29: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 30: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 31: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 32: Hinrich Schütze , Craig Silverstein, Projections for efficient document clustering, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.74-81, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 33: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 34: N. Tolia, M. Kozuch, M. Satyanarayanan, B. Karp, T. Bressoud, and A. Perrig. Opportunistic use of content addressable storage for distributed file systems. In Proceedings of the 2003 USENIX Annual Technical Conference, pages 127--140, June 2003.
• 35: Lawrence L. You , Kristal T. Pollack , Darrell D. E. Long, Deep Store: An Archival Storage System Architecture, Proceedings of the 21st International Conference on Data Engineering, p.804-8015, April 05-08, 2005 [doi>10.1109/ICDE.2005.47]
• 36: B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz. Tapestry: A resilient global-scale overlay for service deployment. IEEE Journal on Selected Areas in Communications, 22(1):41--53, January 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Algorithms, Management, Performance

Keywords:
distributed indexing, document routing, index partitioning, scalability, similarity-based search