Ranking objects based on relationships

ABSTRACT

In many document collections, documents are related to objects such as document authors, products described in the document, or persons referred to in the document. In many applications, the goal is to find these objects that best match a set of keywords. However, the keywords may not necessarily occur in the target objects; they occur only in the documents. For example, in a product review database, a user might search for names of products (say, laptops) using keywords like "lightweight" and "business use" that occur only in the reviews but not in the names of laptops. In order to answer these queries, we need to exploit relationships between documents containing the keywords and the target objects related to those documents. Current keyword query paradigms do not exploit these relationships effectively and hence are inefficient for these queries.In this paper, we consider a class of queries called the "object finder" queries. Our main intuition is to exploit the relationships between searchable documents and related objects and further "aggregate" the document scores from these relationships in order to find the best ranking target objects. Building upon existing keyword search engines such as full text search, we design efficient algorithms that exploit the requirement of only the best k target objects to terminate early. The main challenge here is to push early termination through blocking operators such as group by and aggregation. Our experiments with real datasets and workloads demonstrate the effectiveness of our techniques. Although we present our techniques in the context of keyword search, our techniques apply to other types of ranked searches (e.g., multimedia search) as well.

REFERENCES

• 1: DBXplorer: A System for Keyword-Based Search over Relational Databases, Proceedings of the 18th International Conference on Data Engineering, p.5, February 26-March 01, 2002
• 2: S. Agrawal, S. Chaudhuri, G. Das and A. Gionis. Automated Ranking of Database Query Results. In Proc. of CIDR, 2003.
• 3: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 4: A. Balmin, V. Hristidis and Y. Papakonstantinou, ObjectRank: Authority-Based Keyword Queries in Databases, In Proc. of VLDB, 2004.
• 5: Arvind Hulgeri , Charuta Nakhe, Keyword Searching and Browsing in Databases using BANKS, Proceedings of the 18th International Conference on Data Engineering, p.431, February 26-March 01, 2002
• 6: Surajit Chaudhuri , Luis Gravano, Evaluating Top-k Selection Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.397-410, September 07-10, 1999
• 7: S. Chaudhuri, R. Ramakrishnan and G. Weikum, Integrating DB and IR Technologies: What is the Sound of One Hand Clapping?, In Proc. of CIDR, 2005.
• 8: Jack G. Conrad , Mary Hunter Utt, A system for discovering relationships by feature extraction from text databases, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.260-270, July 03-06, 1994, Dublin, Ireland
• 9: Stefan Deßloch , Nelson Mendonça Mattos, Integrating SQL Databases with Content-Specific Search Engines, Proceedings of the 23rd International Conference on Very Large Data Bases, p.528-537, August 25-29, 1997
• 10: Ronald Fagin, Combining fuzzy information from multiple systems, Journal of Computer and System Sciences, v.58 n.1, p.83-99, Feb. 1999 [doi>10.1006/jcss.1998.1600]
• 11: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences, v.66 n.4, p.614-656, 1 June 2003 [doi>10.1016/S0022-0000(03)00026-6]
• 12: Ulrich Güntzer , Wolf-Tilo Balke , Werner Kießling, Optimizing Multi-Feature Queries for Image Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.419-428, September 10-14, 2000
• 13: V. Hristidis and Y. Papakonstantinou, DISCOVER: Keyword Search in Relational Databases, In Proc. of VLDB Conference, 2002
• 14: I. Ilyas, W. Aref and A. Elmagarmid, Supporting Top-k Join Queries in Relational Databases. In Proc. of VLDB, 2003.
• 15: D. Mattox, Expert Finder. MITRE Publications, 'The Edge', http://www.mitre.org/news/the_edge/june_98/third.html, Jun 1998
• 16: Query Processing Issues in Image(Multimedia) Databases, Proceedings of the 15th International Conference on Data Engineering, p.22, March 23-26, 1999
• 17: Zaiqing Nie , Yuanzhi Zhang , Ji-Rong Wen , Wei-Ying Ma, Object-level ranking: bringing order to Web objects, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060828]
• 18: E. Voorhees, Introduction to Information Extraction and Message Understanding Conferences, http://www.itl.nist.gov/iaui/894.02/related_projects/muc/

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

Keywords:
aggregation, early termination, keyword search, named entities, ranking, relationships, top-k queries