Structural proximity searching for large collections of semi-structured data

ABSTRACT

The richness of the XML data format allows data to be structured in a way which precisely captures the semantics required by the author. It is the structure of the data, however, which forms the basis of all XML query languages. Without at least some notion of the structure, a user cannot meaningfully query the data. This problem is compounded when one considers that heterogeneous data adhering to different schema are likely to exist in the database(s) being queried. This paper proposes a solution based on an efficient proximity index. In particular, we describe a family of encoding and compression schemes which enable us to build an index to efficiently implement the proximity search. Our index is extremely small, and can reflect updates in the underlying database in modest time. Experiments show that our algorithm and implementation are fast and scale well.

REFERENCES

• 1: Serge Abiteboul, Querying Semi-Structured Data, Proceedings of the 6th International Conference on Database Theory, p.1-18, January 08-10, 1997
• 2: T. Bray, J. Paoli, and C.M. Sperberg-McQueen. Extensible markup language (xml) 1.0. In W3C Recommendation, World Wide Web Consortium, 1998; available online at http://www.w3.org/TR/1998/REC-xml-19980210.
• 3: E. W. Dijkstra. A note on two problems in connexions with graphs. Numerische Mathematik, 1:269-271, 1959.
• 4: Daniela Florescu , Donald Kossmann , Ioana Manolescu, Integrating keyword search into XML query processing, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.119-135, June 2000
• 5: 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
• 6: Y.Hayashi, J. Tomita, and G. Kikui. Searching Text-rich XML Documents with Relevance Ranking. In ACM SIGIR 2000 Workshop on XML and Information Retrieval, July, 2000.
• 7: Ioana Manolescu , Daniela Florescu , Donald Kossmann, Answering XML Queries on Heterogeneous Data Sources, Proceedings of the 27th International Conference on Very Large Data Bases, p.241-250, September 11-14, 2001
• 8: Jason McHugh , Serge Abiteboul , Roy Goldman , Dallas Quass , Jennifer Widom, Lore: a database management system for semistructured data, ACM SIGMOD Record, v.26 n.3, p.54-66, Sept. 1997 [doi>10.1145/262762.262770]
• 9: Gonzalo Navarro , Ricardo Baeza-Yates, Proximal nodes: a model to query document databases by content and structure, ACM Transactions on Information Systems (TOIS), v.15 n.4, p.400-435, Oct. 1997 [doi>10.1145/263479.263482]
• 10: The SODA Research Group. SODA2: The Semistructured Object Database System, Version 2. http://dba.cse.unsw.edu.au.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

          Nouns: XML

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Design, Languages