Information filtering and query indexing for an information retrieval model

ABSTRACT

In the information filtering paradigm, clients subscribe to a server with continuous queries or profiles that express their information needs. Clients can also publish documents to servers. Whenever a document is published, the continuous queries satisfying this document are found and notifications are sent to appropriate clients. This article deals with the filtering problem that needs to be solved efficiently by each server: Given a database of continuous queries db and a document d, find all queries q ∈ db that match d. We present data structures and indexing algorithms that enable us to solve the filtering problem efficiently for large databases of queries expressed in the model AWP. AWP is based on named attributes with values of type text, and its query language includes Boolean and word proximity operators.

REFERENCES

• 1: Ioannis Aekaterinidis , Peter Triantafillou, Internet scale string attribute publish/subscribe data networks, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099565]
• 2: Marcos K. Aguilera , Robert E. Strom , Daniel C. Sturman , Mark Astley , Tushar D. Chandra, Matching events in a content-based subscription system, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.53-61, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301326]
• 3: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 4: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 5: Mehmet Altinel , Demet Aksoy , Thomas Baby , Michael Franklin , William Shapiro , Stan Zdonik, DBIS-toolkit: adaptable middleware for large scale data delivery, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.544-546, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 6: Mehmet Altinel , Michael J. Franklin, Efficient Filtering of XML Documents for Selective Dissemination of Information, Proceedings of the 26th International Conference on Very Large Data Bases, p.53-64, September 10-14, 2000
• 7: S. Amer-Yahia , C. Botev , J. Shanmugasundaram, Texquery: a full-text search extension to xquery, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988751]
• 8: Jun-ichi Aoe , Katsushi Morimoto , Takashi Sato, An efficient implementation of trie structures, Software—Practice & Experience, v.22 n.9, p.695-721, Sept. 1992 [doi>10.1002/spe.4380220902]
• 9: Ricardo A. Baeza-Yates , Gaston H. Gonnet, Fast text searching for regular expressions or automaton searching on tries, Journal of the ACM (JACM), v.43 n.6, p.915-936, Nov. 1996 [doi>10.1145/235809.235810]
• 10: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 11: Nicholas J. Belkin , W. Bruce Croft, Information filtering and information retrieval: two sides of the same coin?, Communications of the ACM, v.35 n.12, p.29-38, Dec. 1992 [doi>10.1145/138859.138861]
• 12: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 13: Timothy A. H. Bell , Alistair Moffat, The design of a high performance information filtering system, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.12-20, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243203]
• 14: Ashwin R. Bharambe , Mukesh Agrawal , Srinivasan Seshan, Mercury: supporting scalable multi-attribute range queries, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 15: Ashwin R. Bharambe , Sanjay Rao , Srinivasan Seshan, Mercury: a scalable publish-subscribe system for internet games, Proceedings of the 1st workshop on Network and system support for games, p.3-9, April 16-17, 2002, Braunschweig, Germany [doi>10.1145/566500.566501]
• 16: Jamie Callan, Document filtering with inference networks, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.262-269, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243273]
• 17: Jamie Callan, Learning while filtering documents, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.224-231, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290998]
• 18: Callan, J., Croft, W., and Harding, S. 1992. The INQUERY retrieval system. In Proceedings of the 3rd International Conference on Database and Expert Systems Applications. Springer-Verlag, 78--83.
• 19: Alexis Campailla , Sagar Chaki , Edmund Clarke , Somesh Jha , Helmut Veith, Efficient filtering in publish-subscribe systems using binary decision diagrams, Proceedings of the 23rd International Conference on Software Engineering, p.443-452, May 12-19, 2001, Toronto, Ontario, Canada
• 20: Antonio Carzaniga , David S. Rosenblum , Alexander L. Wolf, Design and evaluation of a wide-area event notification service, ACM Transactions on Computer Systems (TOCS), v.19 n.3, p.332-383, Aug. 2001 [doi>10.1145/380749.380767]
• 21: Antonio Carzaniga , David S. Rosenblum , Alexander L. Wolf, Achieving scalability and expressiveness in an Internet-scale event notification service, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.219-227, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343622]
• 22: Efficient Filtering of XML Documents with XPath Expressions, Proceedings of the 18th International Conference on Data Engineering, p.235, February 26-March 01, 2002
• 23: Kevin Chen-Chuan Chang , Hector Garcia-Molina, Query and data mapping across heterogeneous information sources, Stanford University, Stanford, CA, 2001
• 24: Kevin Chen-Chuan Chang , Hector Garcia-Molina , Andreas Paepcke, Boolean Query Mapping Across Heterogeneous Information Sources, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.515-521, August 1996 [doi>10.1109/69.536244]
• 25: Chen-Chuan K. Chang , Héctor Garcia-Molina , Andreas Paepcke, Predicate rewriting for translating Boolean queries in a heterogeneous information system, ACM Transactions on Information Systems (TOIS), v.17 n.1, p.1-39, Jan. 1999 [doi>10.1145/297117.297120]
• 26: Taurai Tapiwa Chinenyanga , Nicholas Kushmerick, Expressive retrieval from XML documents, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.163-171, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383982]
• 27: William W. Cohen, WHIRL: a word-based information representation language, Artificial Intelligence, v.118 n.1-2, p.163-196, April 2000 [doi>10.1016/S0004-3702(99)00102-2]
• 28: Douglas Comer, Analysis of a heuristic for full trie minimization, ACM Transactions on Database Systems (TODS), v.6 n.3, p.513-537, Sept. 1981 [doi>10.1145/319587.319618]
• 29: Douglas Comer , Ravi Sethi, The Complexity of Trie Index Construction, Journal of the ACM (JACM), v.24 n.3, p.428-440, July 1977 [doi>10.1145/322017.322023]
• 30: Arturo Crespo , Hector Garcia-Molina, Routing Indices For Peer-to-Peer Systems, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.23, July 02-05, 2002
• 31: Rene De La Briandais, File searching using variable length keys, Papers presented at the the March 3-5, 1959, western joint computer conference, p.295-298, March 03-05, 1959, San Francisco, California [doi>10.1145/1457838.1457895]
• 32: Peter J. Denning, ACM president's letter: electronic junk, Communications of the ACM, v.25 n.3, p.163-165, March 1982 [doi>10.1145/358453.358454]
• 33: Devroye, L. 1992. A study of trie-like structures under the density model. Annals Appl. Prob. 2, 2, 402--434.
• 34: David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 35: Yanlei Diao , Mehmet Altinel , Michael J. Franklin , Hao Zhang , Peter Fischer, Path sharing and predicate evaluation for high-performance XML filtering, ACM Transactions on Database Systems (TODS), v.28 n.4, p.467-516, December 2003 [doi>10.1145/958942.958947]
• 36: Dong, L. 2002. Automatic term extraction and similarity assessment in a domain specific document corpus. M.S. thesis, Department of Computer Science, Dalhousie University, Halifax, Canada.
• 37: Françoise Fabret , H. Arno Jacobsen , François Llirbat , Joăo Pereira , Kenneth A. Ross , Dennis Shasha, Filtering algorithms and implementation for very fast publish/subscribe systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.115-126, May 21-24, 2001, Santa Barbara, California, United States
• 38: Flajolet, P. 1983. On the performance evaluation of extendible hashing and trie searching. Acta Informatica 20, 345--369.
• 39: Philippe Flajolet , Claude Puech, Partial match retrieval of multidimensional data, Journal of the ACM (JACM), v.33 n.2, p.371-407, April 1986 [doi>10.1145/5383.5453]
• 40: Peter W. Foltz , Susan T. Dumais, Personalized information delivery: an analysis of information filtering methods, Communications of the ACM, v.35 n.12, p.51-60, Dec. 1992 [doi>10.1145/138859.138866]
• 41: Michael Franklin , Stan Zdonik, “Data in your face”: push technology in perspective, ACM SIGMOD Record, v.27 n.2, p.516-519, June 1998
• 42: Frantzi, K., Ananiadou, S., and Mima, H. 2000. Automatic recognition of multiword terms:the c-value/nc-value method. JODL 5, 2.
• 43: Edward Fredkin, Trie memory, Communications of the ACM, v.3 n.9, p.490-499, September 1960 [doi>10.1145/367390.367400]
• 44: Norbert Fuhr , Kai Groβjohann, XIRQL: An XML query language based on information retrieval concepts, ACM Transactions on Information Systems (TOIS), v.22 n.2, p.313-356, April 2004 [doi>10.1145/984321.984326]
• 45: H. Garcia-Molina , K. Salem, Main Memory Database Systems: An Overview, IEEE Transactions on Knowledge and Data Engineering, v.4 n.6, p.509-516, December 1992 [doi>10.1109/69.180602]
• 46: Bugra Gedik , Ling Liu, PeerCQ: A Decentralized and Self-Configuring Peer-to-Peer Information Monitoring System, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.490, May 19-22, 2003
• 47: Todd J. Green , Gerome Miklau , Makoto Onizuka , Dan Suciu, Processing XML Streams with Deterministic Automata, Proceedings of the 9th International Conference on Database Theory, p.173-189, January 08-10, 2003
• 48: Abhishek Gupta , Ozgur D. Sahin , Divyakant Agrawal , Amr El Abbadi, Meghdoot: content-based publish/subscribe over P2P networks, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
• 49: David A. Hull , Jan O. Pedersen , Hinrich Schütze, Method combination for document filtering, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.279-287, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243275]
• 50: Stratos Idreos , Manolis Koubarakis , Christos Tryfonopoulos, P2P-DIET: an extensible P2P service that unifies ad-hoc and continuous querying in super-peer networks, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007704]
• 51: Idreos, S., Koubarakis, M., and Tryfonopoulos, C. 2004b. P2P-DIET: One-time and continuous queries in super-peer networks. In Proceedings of the 9th International Conference on Extending Database Technology (EDBT). 851--853.
• 52: Jacquet, P. and Szpankowski, W. 1991. Analysis of digital tries with Markovian dependency. IEEE Trans. Inform. Theor. 37, 5, 1470--1475.
• 53: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 54: Knuth, D. 1973a. The Art of Computer Programming. Vol. 3: Sorting and Searching. Addison-Wesley, Reading, MA.
• 55: Knuth, D. 1973b. The Art of Computer Programming. Vol. 1: Fundamental Algorithms. Addison-Wesley, Reading, MA.
• 56: Manolis Koubarakis , T. Koutris , C. Tryfonopoulos , P. Raftopoulou, Information Alert in Distributed Digital Libraries: The Models, Languages, and Architecture of DIAS, Proceedings of the 6th European Conference on Research and Advanced Technology for Digital Libraries, p.527-542, September 16-18, 2002
• 57: Manolis Koubarakis , Spiros Skiadopoulos , Christos Tryfonopoulos, Logic and Computational Complexity for Boolean Information Retrieval, IEEE Transactions on Knowledge and Data Engineering, v.18 n.12, p.1659-1666, December 2006 [doi>10.1109/TKDE.2006.193]
• 58: Manolis Koubarakis , Christos Tryfonopoulos , Stratos Idreos , Yannis Drougas, Selective information dissemination in P2P networks: problems and solutions, ACM SIGMOD Record, v.32 n.3, September 2003 [doi>10.1145/945721.945736]
• 59: Manolis Koubarakis , C. Tryfonopoulos , P. Raftopoulou , T. Koutris, Data Models and Languages for Agent-Based Textual Information Dissemination, Proceedings of the 6th International Workshop on Cooperative Information Agents VI, p.179-193, September 18-20, 2002
• 60: Luhn, H. 1958. A business intelligence system. IBM J. Reasear. Devel. 2, 4, 314--319.
• 61: Milios, E., Zhang, Y., He, B., and Dong, L. 2003. Automatic term extraction and document similarity in special text corpora. In Proceedings of the 6th Conference of the Pacific Association for Computational Linguistics (PACLing). 275--284.
• 62: Masahiro Morita , Yoichi Shinoda, Information filtering based on user behavior analysis and best match text retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.272-281, July 03-06, 1994, Dublin, Ireland
• 63: Gonzalo Navarro , Ricardo Baeza-Yates, Proximal nodes: a model to query document databases by content and structure, ACM Transactions on Information Systems (TOIS), v.15 n.4, p.400-435, Oct. 1997 [doi>10.1145/263479.263482]
• 64: Benjamin Nguyen , Serge Abiteboul , Grégory Cobena , Mihaí Preda, Monitoring XML data on the Web, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.437-448, May 21-24, 2001, Santa Barbara, California, United States
• 65: Nilsson, S. and Karlsson, G. 1999. IP-address lookup using LC-tries. IEEE J. Select. Areas Comm. 17, 6, 1083--1092.
• 66: James L. Peterson, Computer programs for detecting and correcting spelling errors, Communications of the ACM, v.23 n.12, p.676-687, Dec. 1980 [doi>10.1145/359038.359041]
• 67: Ulrich Pfeifer , Norbert Fuhr , Tung Huynh, Searching structured documents with the enhanced retrieval functionality of free WAIS-sf and SFgate, Computer Networks and ISDN Systems, v.27 n.6, p.1027-1036, April 1995
• 68: Pietzuch, P. and Bacon, J. 2002. Hermes: A distributed event-based middleware architecture. In Proceedings of the 1st International Workshop on Distributed Event-Based Systems (DEBS'02).
• 69: Paraskevi Raftopoulou , Euripides G. Petrakis , Christos Tryfonopoulos , Gerhard Weikum, Information Retrieval and Filtering over Self-organising Digital Libraries, Proceedings of the 12th European conference on Research and Advanced Technology for Digital Libraries, September 14-19, 2008, Aarhus, Denmark [doi>10.1007/978-3-540-87599-4_34]
• 70: 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
• 71: Regnier, M. and Jacquet, P. 1989. New results on the size of tries. IEEE Trans. Inform. Theor. 35, 1, 203--205.
• 72: Rivest, R. L. 1976. Partial-match retrieval algorithms. SIAM J. Comput. 5, 1, 19--50.
• 73: 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
• 74: Antony I. T. Rowstron , Anne-Marie Kermarrec , Miguel Castro , Peter Druschel, SCRIBE: The Design of a Large-Scale Event Notification Infrastructure, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.30-43, November 07-09, 2001
• 75: Severance, C. and Pramanik, S. 1990. Distributed linear hashing for main memory databases. In Proceedings of the International Conference on Parallel Processing. 92--95.
• 76: 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
• 77: Edward H. Sussenguth, Jr., Use of tree structures for processing files, Communications of the ACM, v.6 n.5, p.272-279, May 1963 [doi>10.1145/366552.366600]
• 78: Tam, D., Azimi, R., and Jacobsen, H.-A. 2003. Building content-based publish/subscribe systems with distributed hash tables. In Proceedings of the 1st International Workshop On Databases, Information Systems and Peer-to-Peer Computing.
• 79: Tang, C. and Xu, Z. 2003. pFilter: Global information filtering and dissemination using structured overlays. In FTDCS.
• 80: Wesley W. Terpstra , Stefan Behnel , Ludger Fiege , Andreas Zeidler , Alejandro P. Buchmann, A peer-to-peer approach to content-based publish/subscribe, Proceedings of the 2nd international workshop on Distributed event-based systems, June 08-08, 2003, San Diego, California [doi>10.1145/966618.966627]
• 81: Anja Theobald , Gerhard Weikum, Adding Relevance to XML, Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.105-124, May 18-19, 2000
• 82: Martin Theobald , Ralf Schenkel , Gerhard Weikum, An efficient and versatile query engine for TopX search, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 83: Tryfonopoulos, C., Idreos, S., and Koubarakis, M. 2005a. LibraRing: An architecture for distributed digital libraries based on DHTs. In Proceedings of the 9th European Conference on Research and Advanced Technology for Digital Libraries (ECDL). 25--36.
• 84: Christos Tryfonopoulos , Stratos Idreos , Manolis Koubarakis, Publish/subscribe functionality in IR environments using structured overlay networks, 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.1076090]
• 85: Tryfonopoulos, C. and Koubarakis, M. 2002. Selective dissemination of information in P2P systems: Data models, query languages, algorithms and computational complexity. Tech. Rep. TR-ISL-02-2003, Department of Electronic and Computer Engineering, Technical University of Crete.
• 86: Christos Tryfonopoulos , Manolis Koubarakis , Yannis Drougas, Filtering algorithms for information retrieval models with named attributes and proximity operators, 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.1009047]
• 87: Christos Tryfonopoulos , Christian Zimmer , Gerhard Weikum , Manolis Koubarakis, Architectural Alternatives for Information Filtering in Structured Overlays, IEEE Internet Computing, v.11 n.4, p.24-34, July 2007 [doi>10.1109/MIC.2007.79]
• 88: Tak W. Yan , Hector Garcia-Molina, Index Structures for Information Filtering Under the Vector Space Model, Proceedings of the Tenth International Conference on Data Engineering, p.337-347, February 14-18, 1994
• 89: Tak W. Yan , Héctor García-Molina, Index structures for selective dissemination of information under the Boolean model, ACM Transactions on Database Systems (TODS), v.19 n.2, p.332-364, June 1994 [doi>10.1145/176567.176573]
• 90: Tak W. Yan , Hector Garcia-Molina, The SIFT information dissemination system, ACM Transactions on Database Systems (TODS), v.24 n.4, p.529-565, Dec. 1999 [doi>10.1145/331983.331992]
• 91: Yang, B. and Garcia-Molina, H. 2003. Designing a super-peer network. In Proceedings of the 19th International Conference on Data Engineering (ICDE'03).
• 92: Yochum, J. A. 1985. A high-speed text scanning algorithm utilising least frequent trigraphs. In Proceedings of the IEEE Symposium on New Directions in Computing.
• 93: Yi Zhang , Jamie Callan, Maximum likelihood estimation for filtering thresholds, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.294-302, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384012]
• 94: Christian Zimmer , Christos Tryfonopoulos , Klaus Berberich , Manolis Koubarakis , Gerhard Weikum, Approximate Information Filtering in Peer-to-Peer Networks, Proceedings of the 9th international conference on Web Information Systems Engineering, September 01-03, 2008, Auckland, New Zealand [doi>10.1007/978-3-540-85481-4_3]
• 95: Zimmer, C., Tryfonopoulos, C., and Weikum, G. 2007. MinervaDL: An architecture for information retrieval and filtering in distributed digital libraries. In Proceedings of the 11th European Conference on Research and Advanced Technology for Digital Libraries (ECDL). 148--160.
• 96: Christian Zimmer , Christos Tryfonopoulos , Gerhard Weikum, Exploiting correlated keywords to improve approximate information filtering, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390390]

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: Information filtering

General Terms:
Algorithms, Performance

Keywords:
Information filtering, performance evaluation, query indexing algorithms, selective dissemination of information