Race: finding and ranking compact connected trees for keyword proximity search over xml documents

ABSTRACT

In this paper, we study the problem of keyword proximity search over XML documents and leverage the efficiency and effectiveness. We take the disjunctive semantics among input keywords into consideration and identify meaningful compact connected trees as the answers of keyword proximity queries. We introduce the notions of Compact Lowest Common Ancestor (CLCA) and Maximal CLCA (MCLCA) and propose Compact Connected Trees (CCTrees) and Maximal CCTrees (MCCTrees) to efficiently and effectively answer keyword queries. We propose a novel ranking mechanism, RACE, to Rank compAct Connected trEes, by taking into consideration both the structural similarity and the textual similarity. Our extensive experimental study shows that our method achieves both high search efficiency and effectiveness, and outperforms existing approaches significantly.

REFERENCES

• 1: Sara Cohen , Jonathan Mamou , Yaron Kanza , Yehoshua Sagiv, XSEarch: a semantic search engine for XML, Proceedings of the 29th international conference on Very large data bases, p.45-56, September 09-12, 2003, Berlin, Germany
• 2: 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]
• 3: Vagelis Hristidis , Nick Koudas , Yannis Papakonstantinou , Divesh Srivastava, Keyword Proximity Search in XML Trees, IEEE Transactions on Knowledge and Data Engineering, v.18 n.4, p.525-539, April 2006 [doi>10.1109/TKDE.2006.61]
• 4: Guoliang Li , Jianhua Feng , Jianyong Wang , Lizhu Zhou, Effective keyword search for valuable lcas over xml documents, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321447]
• 5: Guoliang Li , Jianhua Feng , Jianyong Wang , Xiaoming Song , Lizhu Zhou, Sailer: an effective search engine for unified retrieval of heterogeneous xml and web documents, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367656]
• 6: G. Li, B. C. Ooi, J. Feng, J. Wang, and L. Zhou. EASE: Efficient and Adaptive Keyword Search on Unstructured, Semi-structured and Structured Data. In SIGMOD, 2008.
• 7: Chong Sun , Chee-Yong Chan , Amit K. Goenka, Multiway SLCA-based keyword search in XML data, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242713]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Scientific databases

General Terms:
Algorithms, Management

Keywords:
compact lca (clca), lowest common ancestor (lca), maximal clca (mclca)