Ranking objects based on relationships

Kaushik Chakrabarti, Venkatesh Ganti, Jiawei Han, Dong Xin

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationSIGMOD 2006 - Proceedings of the ACM SIGMOD International Conference on Management of Data
Number of pages12
StatePublished - 2006
Event2006 ACM SIGMOD International Conference on Management of Data - Chicago, IL, United States
Duration: Jun 27 2006Jun 29 2006

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078


Other2006 ACM SIGMOD International Conference on Management of Data
Country/TerritoryUnited States
CityChicago, IL


  • Aggregation
  • Early termination
  • Keyword search
  • Named entities
  • Ranking
  • Relationships
  • Top-k queries

ASJC Scopus subject areas

  • Software
  • Information Systems


Dive into the research topics of 'Ranking objects based on relationships'. Together they form a unique fingerprint.

Cite this