Faculty Publications
Permanent URI for this communityhttps://idr.nitk.ac.in/handle/123456789/18736
Publications by NITK Faculty
Browse
2 results
Search Results
Item Dynamic structure for web graphs with extended functionalities(Association for Computing Machinery acmhelp@acm.org, 2016) Goyal, S.; Bindu, P.V.; Santhi Thilagam, P.S.The hyperlink structure of World Wide Web is modeled as a directed, dynamic, and huge web graph. Web graphs are analyzed for determining page rank, fighting web spam, detecting communities, and so on, by performing tasks such as clustering, classification, and reachability. These tasks involve operations such as graph navigation, checking link existence, and identifying active links, which demand scanning of entire graphs. Frequent scanning of very large graphs involves more I/O operations and memory overheads. To rectify these issues, several data structures have been proposed to represent graphs in a compact manner. Even though the problem of representing graphs has been actively studied in the literature, there has been much less focus on representation of dynamic graphs. In this paper, we propose Tree- Dictionary-Representation (TDR), a compressed graph representation that supports dynamic nature of graphs as well as the various graph operations. Our experimental study shows that this representation works efficiently with limited main memory use and provides fast traversal of edges. © 2016 ACM.Item In-memory representations for mining big graphs(Institute of Electrical and Electronics Engineers Inc., 2017) Goyal, S.; Bindu, P.V.; Santhi Thilagam, P.S.Graphs are ubiquitous and are the best data structure for representing linked data because of their flexibility, scalability, and power to deal with complexity. Storing big graphs in graph databases leads to difficult computation and increased time complexity. The best alternative is to use inmemory representations such as compact data structures. They compress the graph sufficiently such that it can be stored in memory and can allow all the possible operations in compressed form itself. In this paper we discuss about five compression techniques: WebGraph, Re-pair, BFS, k2, and dk2. In addition, we compare them based on four parameters: compression ratio, supported functionalities, supported graph types, and dynamic support. The paper is concluded by bringing out the need to have a more advanced, dynamic, and versatile compression technique. © 2016 IEEE.