Flexible query answering on graph-modeled data

ABSTRACT

The largeness and the heterogeneity of most graph-modeled datasets in several database application areas make the query process a real challenge because of the lack of a complete knowledge of the vocabulary used, as well as of the information about the structural relationships between the data.

To overcome these problems, flexible query answering capabilities are an essential need. In this paper we present a general model for supporting approximate queries on graph-modeled data. Approximation is both on the vocabularies and the structure. The model is general in that it is not bound to a specific graph data model, rather it gracefully accommodates labeled directed/undirected data graphs with labeled/unlabeled edges. The query answering principles underlying the model are not compelled to a specific data graph, instead they are founded on properties inferable from the data model the data graph conforms to. We complement the work with a ranking model to deal with data approximations and with an efficient top-k retrieval algorithm which smartly accesses ad-hoc data structures and generates the most promising answers in an order correlated with the ranking measures. Experimental results prove the good effectiveness and efficiency of our proposal on different real world datasets.

REFERENCES

• 1: S. Agrawal, S. Chaudhuri, and G. Das. DBXplorer: A System for Keyword-Based Search over Relational Databases. In ICDE, 2002.
• 2: Sihem Amer-Yahia , Laks V. S. Lakshmanan , Shashank Pandit, FleXPath: flexible structure and full-text querying for XML, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007581]
• 3: 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
• 4: 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
• 5: Xin Dong , Alon Halevy, Indexing dataspaces, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247487]
• 6: 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]
• 7: G. W. Furnas , T. K. Landauer , L. M. Gomez , S. T. Dumais, The vocabulary problem in human-system communication, Communications of the ACM, v.30 n.11, p.964-971, Nov. 1987 [doi>10.1145/32206.32212]
• 8: L. Guo, J. Shanmugasundaram, and G. Yona. Topology Search over Biological Databases. In ICDE, 2007.
• 9: Hao He , Haixun Wang , Jun Yang , Philip S. Yu, BLINKS: ranked keyword searches on graphs, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247516]
• 10: 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]
• 11: Varun Kacholia , Shashank Pandit , Soumen Chakrabarti , S. Sudarshan , Rushi Desai , Hrishikesh Karambelkar, Bidirectional expansion for keyword search on graph databases, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 12: G. Kasneci, F. Suchanek, G. Ifrim, M. Ramanath, and G. Weikum. NAGA: Searching and Ranking Knowledge. In ICDE, 2007.
• 13: C. Leacock and M. Chodorow. Combining Local Context and WordNet Similarity for Word Sense Identification. In C. Fellbaum, editor, WordNet: An Electronic Lexical Database, pages 256--283. MIT Press, 1998.
• 14: Guoliang Li , Beng Chin Ooi , Jianhua Feng , Jianyong Wang , Lizhu Zhou, EASE: an effective 3-in-1 keyword search method for unstructured, semi-structured and structured data, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376706]
• 15: Federica Mandreoli , Riccardo Martoglia , Enrico Ronchetti, Versatile structural disambiguation for semantic-aware applications, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099593]
• 16: Alkis Simitsis , Georgia Koutrika , Yannis Ioannidis, Précis: from unstructured keywords as queries to structured databases as answers, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.1, p.117-149, January 2008 [doi>10.1007/s00778-007-0075-9]
• 17: Fabian M. Suchanek , Gjergji Kasneci , Gerhard Weikum, Yago: a core of semantic knowledge, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242667]
• 18: Y. Tian and J. Patel. TALE: A Tool for Approximate Large Graph Matching. In ICDE, 2008.
• 19: Yu Xu , Yannis Papakonstantinou, Efficient keyword search for smallest LCAs in XML databases, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066217]
• 20: Xifeng Yan , Philip S. Yu , Jiawei Han, Substructure similarity search in graph databases, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066244]
• 21: Cong Yu , H. V. Jagadish, Querying complex structured databases, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 22: Xuan Zhou , Julien Gaugaz , Wolf-Tilo Balke , Wolfgang Nejdl, Query relaxation using malleable schemas, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247541]