1. I. Introduction

nternet of Things (IoT) is a new technology, which is rapidly gaining momentum in the smart city applications. This concept enables the ubiquitous presence around us of a variety of objects or things such as RFID tags, sensors, actuators, and cell phones. The rise of IoT has affected many areas of smart city applications, such as e-learning, e-health, transportation, waste management, etc. By 2020, more than 5 billion devices will be connected worldwide will become the pioneer to provide information accessible across the globe in milliseconds. Almost all smart city applications are running using the internet and they utilized the services to the cloud [1]. The IoT technology is upgrading day by day with the rapid implementation of a smart city [7]. Every smart city application requires the processing speed to process data and storage space to store the processed data for further use. The main challenge of the smart city [8,9] applications are to store the data and analysis it. Data is stored in a memory in the form of the graph. In many applications of graph mining, reduction plays an important role. No doubt, several techniques as total reduction, total reduction with edge weight, etc. are available to reduce the call graph but there are drawbacks in some cases while reducing call graph by these techniques, sometimes information of the program is lost or changed, loosing or changing of information affects the accuracy of program that is unacceptable.

2. II. Call Graph

A call graph is a directed graph whose nodes represent the functions of the program and directed edges symbolize function calls [2,14]. Nodes can represent either one of the following two types of functions: 1. Local functions, implemented by the program designer. 2. External functions: system and library calls. Call graphs are formally defined as follows:

3. Definition

A call graph is a directed graph G with vertex set V=V (G), representing the functions, and edge set E=E(G), where E(G) V(G)×V(G), in correspondence with the function calls.

4. Types of Call Graph

The call graph can be classified as static and dynamic call graph.

A static call graph can be obtained from the source code. It represents all methods of a program as nodes and all possible method invocations as edges. Discovering the static call graph from the source text requires two steps: finding the source text for the program, and scanning and parsing that text [15,19].

ii.

A dynamic call graph is the invocation relation that represents a specific set of run-time executions of a program. Dynamic call graph extraction is a typical application of dynamic analysis to aid compiler optimization, program understanding, performance analysis etc [3,4].

5. c) Call Graph Reduction

The call graph is representations of program executions [11]. Raw call graphs typically become much too large. The program might be executed for a long period. Therefore, it is essential to compress the graphs by a process called reduction. It is usually done by a Lossy compression technique [5]. This involves the trade-off between keeping as much information as possible and a strong compression. When call graph is being reduced it is essential that no function call is missed [16].

The specifications of all the functions/methods must be clear. It is also noticeable that no information is lost when the label is changed [6]. Call frequency must be clearly specified. Two approaches are center of the focus to reduce the call graph 1. Total Reduction 2. Zero-one-many reduction In total reduction, a node represents every function. A direct edge is connected with the corresponding nodes when one function has called another function. Total reduction technique shortens the size of the source call graph. In this technique, every method occurs just once within the graph. The major shortcoming of this technique is that it changes the structure of the graph. On the other side, much information about the program execution is lost, e.g., frequencies of the execution of methods and information on different structural patterns within the graphs. So it is very difficult to retrieve the required information from this reduced graph [17,18].

The other approach is Zero-one-many reduction which covers the drawback of Total Reduction as it does not change the structure but the reduction is not properly done. The improper reduction increases its complexity and it is difficult to find frequent substructure from the graph. The reduced graph can provide near information about call frequency but exact information is not known.

6. III. Problem Statement

Smart city applications generated the very high amount of data every millisecond, which required a very high amount of storage space [10]. Various existing techniques reduce the size of data but the originality and quality of data may also suffer. Surely, the size of data is reduced but the complete information of that data is also changed [13]. Researchers have proposed a number of techniques to reduce the graph but most of the techniques suffer from one or more shortcomings. Majority of techniques are not able to store the graph with all information in computer memory [12]. So, some new techniques or algorithms are needed to store the information of the graph in computer memory and reduce the graph in such a manner that its information is not lost and the graph is easily mined. Major objectives of this paper are:

? To find an efficient method to store the graph in computer memory with information about all the nodes and its parents.

? Once the storage is done efficiently, the reduction of the graph is required. The graph must be reduced in such a manner that its information is not lost and it should have minimum edges and nodes. ? Structure of the graph should not be changed after reduction.

7. IV. Proposed Approach

Researchers proposed many approaches for reduction of call graph but they could not propose any approach to saving the call graph in computer memory. The main task is to save the node into computer memory with its parent's information, which is not possible with adjacency list or adjacency matrix. Therefore the parent of each child is stored in the matrix. Once the call graph is saved in memory, it is reduced using the proposed algorithm. In this approach, the reduced call graph shows the call frequency of each node without changing the structure of the source call graph. First, all functions of source code are labeled so that it can easily be interpreted. Then a call graph is made using these labeled functions. To understand the

8. print "Enter the label of (x) children" 12. j[i][x].label = Input(label) 13. print "Enter the parent of (x) children" 14. j[i][x].parent = Input(parent) 15. end for 16. end for 17. foreach k?levels down to 0 do 18. foreach l?count[levels-1] down to 0 do 19. foreach m?l-1 down to 0 do 20. if j[k-1] [m-1]. label=j [l-1] [m-1]. label AND j[l-1] [m-1].parent=j[k-1] [m-1]. parent AND j [k-1] [m-1]. label ? '\0' then 21. j[k][l].parent = -1 22. end if 23. end for 24. end for 25. end for

algorithm call graphs is constructed from any code and apply the algorithm step by step. Figure 3 shows the call graph which is generated by a code

9. V. Implementation and Results

The first part of the algorithm is used for call graph storage. The call graph will be saved in the computer memory by using matrix. There are 5 levels in the call graph and so matrix will have 5 rows. 1st row represent the proposed algorithm the same level nodes with the same parent are merged resulting in a single node with the same label. In the graph same level is level 5, the same label is F and the same parent is D. so after applying the algorithm 3 F's are merged to single F with call frequency. The result is as shown in figure 4.1st level the second row represent 2nd level and so on. Corresponding nodes with parent's information will be saved. 1st-row stores the information about a node which is in 1st level and hasn't any parent as it is root node so store the information as -1.at 2nd level b and c stored in 2nd row with its parent information which is a and so on. According to the algorithm, the next step is to reduce the call graph. This approach is bottom-up approach so the 5th level is considered first and then move to 4th, 3rd, and 4th Fig. 3: Source Call Graph so on.5 level has 6 nodes labeled as f. according to the The same process is applied in level 4 resulting in figure 5. The 3rd level will be worked at C appears 3 times D and E appear singly. Hence, C is concentrated on. 3 Cs will be merged resulting in single C with frequency 3. This will also affect its children. Therefore, they will also be reduced according to the same procedure as shown in figure 5. Finally reduced call graph is shown above is created. In this graph, every node has the information about call frequency. The graph obtained from the same source code is also reduced with both techniques.

As shown in the figure the graph generated from the Liu et al technique has reduced the graph with lesser edges and nodes but it could not able to retain the basic structure of the call graph wherein the other hand as shown in figure Zero-one-many reduction could not reduce the same and lost the information of nodes. In contrast to both of them, the call graph generated from the proposed algorithm is able to reduce the graph and retain the information of nodes as well. Both techniques Total Reduction and Zero-onemany reductions lost the information of the nodes and reduce the graph from 22 to 6 and 15 nodes along with edges from 21 to 6 and 14 respectively. The result obtained from the proposed algorithm have positive results with reducing graph without losing information and basic structure i.e. from 22 nodes to 10 nodes and 21 edges to 9 edges

10. VI. Conclusion & Future Scope

Every year the government to their tradition city to update it to the smart city spends a very huge amount. Smart city applications generate the high amount of data at every second. In this paper, the data storage scheme is proposed. The main benefit of this algorithm is to develop a technique to stores the parent information in the matrix and reduced at each level drastically. Information about each node is retained by using the call frequency by annotating each edge with a numerical weight. Similarly, the algorithm used to reduced call graph has various advantages over traditional techniques. It takes various parameters for consideration such as information of nodes, basic structure of graphs and call frequency. Here the detailed study of call graph reduction in graph mining made the study of various other techniques in bug localization very easy. The proposed algorithm works only when there are same types of nodes at a particular level in a call graph. In future this work can be extended to multiple levels of call graph will make the graph mining algorithm efficiently. Secondly the storage of graph can be upgraded with any new storage technique where it would require lesser storage space as well as lesser access time leading to further optimize reduction of call graph.

Figure 1: Structure for Node StorageRows represent the levels of call graph as 1st row represent 1st level's nodes, 2nd row represent 2nd level's nodes and so on. Every node also contains the information about its parent. The basic structure for saving the node with its parent information is shown in fig. — Figure 1. Figure 1 :A

Call Graph Reduction Based Novel Storage Allocation Scheme for Smart City Applications Algorithm: Reducing Call Graph Input: children, label, parent Output: Reduced Call Graph 1. Set j=Getstr[100][] 2. foreach aa?1 to 10 do 3. Set j[aa-1] = Getstr[200] 4. end for 5. Set count= GetArray(level) 6. foreach i?0 to levels-1 do 7. print "Enter no. of children at level 0" 8. Input(children) 9. count[i]=children 10. foreach x?0 to children -1 do 11. — Figure 2. A

Figure 2: Structure for Call Graph Storage — Figure 3. Figure 2 :A

Figure 4: Reduction at 5th Level — Figure 4. Figure 4 :

Figure 5: Reduction at 4th Level — Figure 5. Figure 5 :

Figure: 6: Reduction at 3rd Level — Figure 6. Figure: 6 :

Figure 7: Reduction at 2nd Level — Figure 8. Figure 7 :

Figure 8: Completely Reduced Graph — Figure 9. Figure 8 :

Figure 9: Reduced with Total Reduction Technique — Figure 10. Figure 9 :

Figure 11. Table 1 :

	Reduction Techniques
Reduction	No Of	No of	Effects	on
algorithm	Nodes	Edges	Structure
Source code	22	21
Total Reduction	6	6	Lost information structure and Changed
Zero-one-many	15	14	Lost information but remain same
reduction			structure
Proposed Algorithm	10	9	No Remain loss information and in Same
			structure

Appendix A

Technical approach for the inclusion of superconducting magnetic energy storage in a smart city, A Colmenar-Santos , E Luis-Molina , E Rosales-Asensio , Á Lopez-Rey . 2018. Energy.
A novel big data analytics framework for smart cities. A M S Osman . Future Generation Computer Systems 2019. 91 p. .
A call graph mining and matching based defect localization technique. A Yousefi , A Wassyng . 2013 IEEE Sixth International Conference on Software Testing, Verification and Validation Workshops, 2013. March. IEEE. p. .
Three-factor control protocol based on elliptic curve cryptosystem for universal serial bus mass storage devices. C C Lee , C T Chen , P H Wu , T Y Chen . IET Computers & Digital Techniques 2013. 7 (1) p. .
Optimal charging control of energy storage and electric vehicle of an individual in the internet of energy with energy trading. C C Lin , D J Deng , C C Kuo , Y L Liang . IEEE Transactions on Industrial Informatics 2018. 14 (6) p. .
Simultaneous demand-driven data-flow and call graph analysis. G Agrawal . Software Maintenance, 1999.(ICSM'99) Proceedings. IEEE International Conference on, 1999. IEEE. p. .
A Data-Driven Stochastic Optimization Approach to the Seasonal Storage Energy Management. G Darivianakis , A Eichler , R S Smith , J Lygeros . IEEE control systems letters 2017. 1 (2) p. .
Greening the smart cities: Energy-efficient massive content delivery via D2D communications. IEEE Transactions on Industrial Informatics 14 (4) p. .
Moving towards smart cities: Solutions that lead to the Smart City Transformation Framework. H Kumar , M K Singh , M P Gupta , J Madaan . Technological Forecasting and Social Change 2018.
A Lightweight And privacy-preserving public cloud auditing scheme without bilinear pairings in smart cities. J Han , Y Li , W Chen . Computer Standards & Interfaces 2018.
Constructing a Knowledge Base for Software Security Detection Based on Similar Call Graph. J Xue , C Hu , K Wang , R Ma , B Leng . Computer and Electrical Engineering, 2009. ICCEE'09. Second International Conference on, 2009. December. IEEE. 1 p. .
Malware similarity identification using call graph based system call subsequence features. K Blokhin , J Saxe , D Mentis . 2013 IEEE 33rd International Conference on Distributed Computing Systems Workshops, 2013. July. IEEE. p. .
OLAP Visual Analytics on Large Software Call Graphs with Hierarchical ChordMap. L Wang , J Gong , L Shi . 2015 IEEE International Conference on, 2015. November. IEEE. p. . (Data Mining Workshop)
, L Zhou , D Wu , J Chen , Z Dong . 2018.
Efficient Certificate Revocation Management Schemes for IoT-based Advanced Metering Infrastructures in Smart Cities, M Cebe , K Akkaya . 2018. Ad Hoc Networks.
An embedding graph-based model for software watermarking. M Chroni , S D Nikolopoulos . Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP), 2012. July. 2012. IEEE. p. . (Eighth International Conference on)
Temporal analysis of telecom call graphs. S Gurukar , B Ravindran . Communication Systems and Networks (COMSNETS), 2014. January. 2014. IEEE. p. . (Sixth International Conference on)
Cutting a method call graph for supporting feature location. T Kato , S Hayashi , M Saeki . Fourth International Workshop on Empirical Software Engineering in Practice 2012. October. 2012. IEEE. p. .
Topology characters of the linux call graph. Y F Wang , D W Ding . 2015 2nd International Conference on Information Science and Control Engineering (ICISCE), 2015. April. IEEE. p. .
Social-Aware Data Collection Scheme Through Opportunistic Communication in Vehicular Mobile Networks. Z Tang , A Liu , C Huang . IEEE Access 2016. 4 p. .

A Call Graph Reduction based Novel Storage Allocation Scheme for Smart City Applications

Table of contents