Distributed Algorithm for Relationship Queries on Large Graphs

ABSTRACT

Massive-sized graph-structured data is now ubiquitous, e.g., social networks, databases, knowledge-bases, web-graphs, etc. An important class of queries on graph-structured data is "relationship queries". Essentially, given a set of entities (corresponding to nodes in the graph), finding a ranked list of interesting interconnections among them. While this problem has been studied for many years, the solutions proposed in the literature so far focus on the non-distributed setting. Clearly, such solutions will not scale with large graphs having billions of nodes and edges that are becoming commonplace. In this paper, we present an algorithm for keyword search on large graphs, which is based on the distributed parallel processing paradigm. We also analyze why our algorithm generates optimal answers. Finally, we report on preliminary empirical results of relationship queries on a subset of the Linked-Open Data graph.

References

1. M. Bezensek and B. Robic. A survey of parallel and distributed algorithms for the steiner tree problem. International Journal of Parallel Programming, 2013.
2. G. Bhalotia, A. Hulgeri, C. Nakhe, S. Chakrabarti, and S. Sudarshan. Keyword searching and browsing in databases using banks. In Proc. of 18th International Conference on Data Engineering, ICDE '02.
3. C. Bizer, T. Heath, and T. Berners-Lee. Linked data-the story so far. In International Journal on Semantic Web and Information Systems, IJSWIS'09.
4. J. Coffman and A. C. Weaver. A framework for evaluating database keyword search strategies. In Proc. of the 19th ACM International Conference on Information and Knowledge Management, CIKM '10.
5. B. Dalvi, M. Kshirsagar, and S. Sudarshan. Keyword search on external memory data graphs. In Proc. of the 34th international conference on Very Large Databases, VLDB '08.
6. S. E. Dreyfus and R. A. Wagner. The steiner problem in graphs. Networks, 1971.
7. J. Feldman and M. Ruhl. The directed steiner network problem is tractable for a constant number of terminals. In 40th Annual Symposium on Foundations of Computer Science, 1999.
8. N. Garg, G. Konjevod, and R. Ravi. A polylogarithmic approximation algorithm for the group steiner tree problem. In Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '98.
9. H. He, H. Wang, J. Yang, and P. Yu. Blinks: ranked keyword searches on graphs. In Proc. of ACM SIGMOD international conference on Management of data, SIGMOD '07.
10. B. Kimelfeld and Y. Sagiv. Finding and approximating top-k answers in keyword proximity search. In Proc. of the 25th ACM Symposium on Principles of Database Systems, PODS '06.
11. G. Li, B. Ooi, J. Feng, J. Wang, and L. Zhou. Ease: an effective 3-in-1 keyword search method for unstructured, semi-structured and structured data. In Proc. of the ACM SIGMOD international conference on Management of data, SIGMOD '08.
12. G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In Proc. of the ACM SIGMOD international conference on Management of Data, SIGMOD'10.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Search methodologies

      • Discrete space search

      • Game tree search