Information discovery in loosely integrated data

ABSTRACT

We model heterogeneous data sources with cross references, such as those crawled on the (enterprise) web, as a labeled graph with data objects as typed nodes and references or links as edges. Given the labeled data graph, we introduce flexible and efficient querying capabilities that go beyond existing capabilities by additionally discovering meaningful relationships between objects that satisfy keyword and/or structured query filters. We introduce the relationship search operator that exploits the link structure between data objects to rank objects related to the result of a filter. We implement the search operator using the ObjectRank [1] algorithm that uses the random surfer model. We study several alternatives for constructing summary graphs for query results that consist of individual and aggregate nodes that are somehow linked to qualifying result nodes. Some of the summary graphs are useful for presenting query results to the user, while others could be used to evaluate subsequent queries efficiently without considering all the nodes and links in the original data graph.

REFERENCES

• 1: Andrey Balmin, Vagelis Hristidis, Yannis Papakonstantinou: ObjectRank: Authority-Based Keyword Search in Databases. VLDB 2004: 564--575.
• 2: Paul Brown, Peter J. Haas, Jussi Myllymaki, Hamid Pirahesh, Berthold Reinwald, Yannis Sismanis: Toward Automated large-scale Information Integration and Discovery. Data Management in a Connected World 2005: 161--180.
• 3: IBM Entity Analytic Solutions (EAS)-Solution Overview www.ibm.com/software/data/db2/eas/
• 4: Yannis Sismanis , Paul Brown , Peter J. Haas , Berthold Reinwald, GORDIAN: efficient and scalable discovery of composite keys, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Textual databases; Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Selection process; Search process; Information filtering

General Terms:
Algorithms

Keywords:
XML, information discovery, search