Authority-based keyword search in databases

ABSTRACT

Our system applies authority-based ranking to keyword search in databases modeled as labeled graphs. Three ranking factors are used: the relevance to the query, the specificity and the importance of the result. All factors are handled using authority-flow techniques that exploit the link-structure of the data graph, in contrast to traditional Information Retrieval. We address the performance challenges in computing the authority flows in databases by using precomputation and exploiting the database schema if present. We conducted user surveys and performance experiments on multiple real and synthetic datasets, to assess the semantic meaningfulness and performance of our system.

REFERENCES

• 1: Serge Abiteboul , Peter Buneman , Dan Suciu, Data on the Web: from relations to semistructured data and XML, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 2: 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
• 3: Akiko Aizawa, The feature quantity: an information theoretic perspective of Tfidf-like measures, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.104-111, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345556]
• 4: Andrey Balmin , Vagelis Hristidis , Yannis Papakonstantinou, Objectrank: authority-based keyword search in databases, Proceedings of the Thirtieth international conference on Very large data bases, p.564-575, August 31-September 03, 2004, Toronto, Canada
• 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: Krishna Bharat , Monika R. Henzinger, Improved algorithms for topic distillation in a hyperlinked environment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.104-111, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290972]
• 7: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 8: David Carmel , Doron Cohen , Ronald Fagin , Eitan Farchi , Michael Herscovici , Yoelle S. Maarek , Aya Soffer, Static index pruning for information retrieval systems, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.43-50, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383958]
• 9: Soumen Chakrabarti , Byron Dom , Prabhakar Raghavan , Sridhar Rajagopalan , David Gibson , Jon Kleinberg, Automatic resource compilation by analyzing hyperlink structure and associated text, Proceedings of the seventh international conference on World Wide Web 7, p.65-74, April 1998, Brisbane, Australia
• 10: Yen-Yu Chen , Qingqing Gan , Torsten Suel, I/O-efficient techniques for computing pagerank, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584882]
• 11: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 12: Nick Craswell , Stephen Robertson , Hugo Zaragoza , Michael Taylor, Relevance weighting for query independent evidence, 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.1076106]
• 13: Croft, W. B. 2000. Combining approaches to information retrieval. In Advances in Information Retrieval: Recent Research from the CIIR, Chapter 1, Kluwer.
• 14: Shaul Dar , Gadi Entin , Shai Geva , Eran Palmon, DTL's DataSpot: Database Exploration Using Plain Language, Proceedings of the 24rd International Conference on Very Large Data Bases, p.645-649, August 24-27, 1998
• 15: Doyle, P. G. and Snell, J. L. 1984. Random Walks and Electric Networks. Mathematical Association of America, Washington, DC.
• 16: 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
• 17: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 18: Christos Faloutsos , Kevin S. McCurley , Andrew Tomkins, Fast discovery of connection subgraphs, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014068]
• 19: Floris Geerts , Heikki Mannila , Evimaria Terzi, Relational link-based ranking, Proceedings of the Thirtieth international conference on Very large data bases, p.552-563, August 31-September 03, 2004, Toronto, Canada
• 20: Golub, G. H. and Loan, C. F. 1996. Matrix Computations. Johns Hopkins.
• 21: Gu, X., Nahrstedt, K., Yuan, W., Wichadakul, D., and Xu, D. 2002. An XML-based quality of service enabling language for the web. J. Visual Langu. Comput. 13, 1, 61--95.
• 22: Lin Guo , Feng Shao , Chavdar Botev , Jayavel Shanmugasundaram, XRANK: ranked keyword search over XML documents, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872762]
• 23: Zoltán Gyöngyi , Hector Garcia-Molina , Jan Pedersen, Combating web spam with trustrank, Proceedings of the Thirtieth international conference on Very large data bases, p.576-587, August 31-September 03, 2004, Toronto, Canada
• 24: Haveliwala, T. 1999. Efficient computation of PageRank. Tech. rep. Stanford University (http://www.stanford.edu/~taherh/papers/efficient-pr.pdf).
• 25: Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
• 26: Vagelis Hristidis , Luis Gravano , Yannis Papakonstantinou, Efficient IR-style keyword search over relational databases, Proceedings of the 29th international conference on Very large data bases, p.850-861, September 09-12, 2003, Berlin, Germany
• 27: Vagelis Hristidis , Yannis Papakonstantinou, Discover: keyword search in relational databases, Proceedings of the 28th international conference on Very Large Data Bases, p.670-681, August 20-23, 2002, Hong Kong, China
• 28: Hristidis, V., Papakonstantinou, Y., and Balmin, A. 2003. Keyword proximity search on XML graphs. In Proceedings of the International Conference on Data Engineering (ICDE).
• 29: Huang, A., Xue, Q., and Yang, J. 2003. TupleRank and implicit relationship discovery in relational databases. In Proceedings of the International Conference on Web-Age Information Management (WAIM).
• 30: Heasoo Hwang , Vagelis Hristidis , Yannis Papakonstantinou, ObjectRank: a system for authority-based search on databases, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142593]
• 31: Glen Jeh , Jennifer Widom, Scaling personalized web search, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775191]
• 32: Sepandar D. Kamvar , Taher H. Haveliwala , Christopher D. Manning , Gene H. Golub, Extrapolation methods for accelerating PageRank computations, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775190]
• 33: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 34: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 35: Raghu Ramakrishnan, Database management systems, McGraw-Hill, Inc., New York, NY, 1997
• 36: Louiqa Raschid , Yao Wu , Woei-Jyh Lee , María Esther Vidal , Panayiotis Tsaparas , Padmini Srinivasan , Aditya Kumar Sehgal, Ranking target objects of navigational queries, Proceedings of the 8th annual ACM international workshop on Web information and data management, November 10-10, 2006, Arlington, Virginia, USA [doi>10.1145/1183550.1183558]
• 37: Richardson, M. and Domingos, P. 2002. The intelligent surfer: Probabilistic combination of link and content information in PageRank. Advances in Neural Information Processing Systems 14, MIT Press.
• 38: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 39: Jacques Savoy, Bayesian inference networks and spreading activation in hypertext systems, Information Processing and Management: an International Journal, v.28 n.3, p.389-406, 1992 [doi>10.1016/0306-4573(92)90082-B]
• 40: Shafer, P., Isganitis, T., and Yona, G. 2006. Hubs of knowledge: Using the functional link structure in Biozon to mine for biologically significant entities. BMC Bioinformatics. 15, 7, 71.
• 41: Singhal, A. 2001. Modern information retrieval: A brief overview. IEEE Data Engin. Bull., Special Issue on Text and Databases 24, 4.
• 42: Hanghang Tong , Christos Faloutsos, Center-piece subgraphs: problem definition and fast solutions, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150448]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

Keywords:
Authority flow, PageRank, quality experiments, ranking, specificity