XRANK: ranked keyword search over XML documents

ABSTRACT

We consider the problem of efficiently producing ranked results for keyword search queries over hyperlinked XML documents. Evaluating keyword search queries over hierarchical XML documents, as opposed to (conceptually) flat HTML documents, introduces many new challenges. First, XML keyword search queries do not always return entire documents, but can return deeply nested XML elements that contain the desired keywords. Second, the nested structure of XML implies that the notion of ranking is no longer at the granularity of a document, but at the granularity of an XML element. Finally, the notion of keyword proximity is more complex in the hierarchical XML data model. In this paper, we present the XRANK system that is designed to handle these novel features of XML keyword search. Our experimental results show that XRANK offers both space and performance benefits when compared with existing approaches. An interesting feature of XRANK is that it naturally generalizes a hyperlink based HTML search engine such as Google. XRANK can thus be used to query a mix of HTML and XML documents.

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: V. Aguilera, S. Cluet, F. Wattez, "Xyleme Query Architecture", WWW Conf., 2001.
• 3: Vo Ngoc Anh , Owen de Kretser , Alistair Moffat, Vector-space ranking with effective early termination, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.35-42, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383957]
• 4: G. Bhalotia, et al., "Keyword Searching and Browsing in Databases using BANKS", ICDE Conf., 2002.
• 5: Klemens Böhm , Karl Aberer , Erich J. Neuhold , Xiaoya Yang, Structured document storage and refined declarative and navigational access mechanisms in HyperStorM, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.4, p.296-311, November 1997 [doi>10.1007/s007780050047]
• 6: 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
• 7: Eric W. Brown , James P. Callan , W. Bruce Croft, Fast Incremental Indexing for Full-Text Information Retrieval, Proceedings of the 20th International Conference on Very Large Data Bases, p.192-202, September 12-15, 1994
• 8: L. J. Brown , M. P. Consens , I. J. Davis , C. R. Palmer , F. W. Tompa, A structured text ADT for object-relational databases, Theory and Practice of Object Systems, v.4 n.4, p.227-244, Oct. 12, 1998 [doi>10.1002/(SICI)1096-9942(1998)4:4<227::AID-TAPO3>3.3.CO;2-L]
• 9: Chris Buckley , Alan F. Lewit, Optimization of inverted vector searches, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.97-110, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253515]
• 10: Soumen Chakrabarti , Mukul Joshi , Vivek Tawde, Enhanced topic distillation using text, markup tags, and hyperlinks, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.208-216, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383990]
• 11: V. Christophides , S. Abiteboul , S. Cluet , M. Scholl, From structured documents to novel query facilities, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.313-324, May 24-27, 1994, Minneapolis, Minnesota, United States
• 12: Tuong Dao , Ron Sacks-Davis , James A. Thom, An Indexing Scheme for Structured Documents and its Implementation, Proceedings of the Fifth International Conference on Database Systems for Advanced Applications (DASFAA), p.125-134, April 01-04, 1997
• 13: 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
• 14: 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]
• 15: Daniela Florescu , Donald Kossmann , Ioana Manolescu, Integrating keyword search into XML query processing, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.119-135, June 2000, Amsterdam, The Netherlands
• 16: Norbert Fuhr , Kai Großjohann, XIRQL: a query language for information retrieval in XML documents, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.172-180, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383985]
• 17: Roy Goldman , Narayanan Shivakumar , Suresh Venkatasubramanian , Hector Garcia-Molina, Proximity Search in Databases, Proceedings of the 24rd International Conference on Very Large Data Bases, p.26-37, August 24-27, 1998
• 18: L. Guo, F. Shao, C. Botev, J. Shanmugasundaram, "XRANK: Ranked Keyword Search Over XML Documents", Cornell University Technical Report, 2003.
• 19: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• 20: V. Hristidis, Y. Papakonstantinou, "DISCOVER: Keyword Search in Relational Databases", VLDB Conf., 2002.
• 21: HyTime, http://www.hytime.org.
• 22: Guy Jacobson , Balachander Krishnamurthy , Divesh Srivastava , Dan Suciu, Focusing search in hierarchical structures with directory sets, Proceedings of the seventh international conference on Information and knowledge management, p.1-9, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288635]
• 23: H. V. Jagadish , Laks V. S. Lakshmanan , Tova Milo , Divesh Srivastava , Dimitra Vista, Querying network directories, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.133-144, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 24: 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]
• 25: Yong Kyu Lee , Seong-Joon Yoo , Kyoungro Yoon , P. Bruce Berra, Index structures for structured documents, Proceedings of the first ACM international conference on Digital libraries, p.91-99, March 20-23, 1996, Bethesda, Maryland, United States [doi>10.1145/226931.226950]
• 26: R. Luk, et al., "A Survey of Search Engines for XML Documents", SIGIR Workshop on XML and IR, 2000.
• 27: Sung Hyon Myaeng , Don-Hyun Jang , Mun-Seok Kim , Zong-Cheol Zhoo, A flexible model for retrieval of SGML documents, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.138-145, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290980]
• 28: Michael Persin, Document filtering for fast ranking, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.339-348, July 03-06, 1994, Dublin, Ireland
• 29: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 30: Albrecht Schmidt , Martin L. Kersten , Menzo Windhouwer, Querying XML Documents Made Easy: Nearest Concept Queries, Proceedings of the 17th International Conference on Data Engineering, p.321-329, April 02-06, 2001
• 31: A. R. Schmidt , Florian Waas , Martin L. Kersten , D. Florescu , I. Manolescu , M. J. Carey , R. Busse, The XML benchmark project, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 2001
• 32: Igor Tatarinov , Stratis D. Viglas , Kevin Beyer , Jayavel Shanmugasundaram , Eugene Shekita , Chun Zhang, Storing and querying ordered XML using a relational database system, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564715]
• 33: Anja Theobald , Gerhard Weikum, The Index-Based XXL Search Engine for Querying XML Data with Relevance Ranking, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.477-495, March 25-27, 2002
• 34: Anthony Tomasic , Héctor García-Molina , Kurt Shoens, Incremental updates of inverted lists for text document retrieval, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.289-300, May 24-27, 1994, Minneapolis, Minnesota, United States
• 35: World Wide Web Consortium, http://www.w3.org.

INDEX TERMS

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

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

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Hypertext/hypermedia
          Nouns: XML

General Terms:
Algorithms, Design, Experimentation, Performance