With the broader development of networking, data acquired from IoT and big data have grown significantly in various real-time applications. It provides a transparent role of human life as it shows an extensive bond with data provisioning. On the other hand, it has some challenging issues like verification of authenticity of the enormous data over an un-trusted environment like cloud. It causes privacy leakage, delay, and unidentified data size by third-party. Thus, there is a need for a novel authentication to handle all these problems using a tree data structure for establishing authentication for privacy preservation. Here, a novel graph-based traversing algorithm (GTA) is proposed for realizing the data stream verification and validates the arrival of data streams. This model reduces the failure rate and improves the authentication mechanism and robustness. An integrity verification scheme is used to handle privacy leakage issues during third-party analysis. The simulation is performed in MATLAB 2016b environment to project the significance of the model, and the outcomes are more desirable for authentication and privacy preservation during practical examination. Here, metrics like path length, total verification time, and total insertion time are evaluated. The proposed model gives a better trade-off compared to existing approaches. The path length variation of GTA is 1.3, 1.4, and 1.5 for depth rates 6, 8, and 10, respectively. The total verification time with data size is 1, 2, 3, and 4GB, respectively. The total insertion time of GTA is 5, 10, 15, and 18s for 1, 2, 3, and 4GB, respectively. It is remarkably lesser than P-ATHAT and Merkle tree, respectively. The time needed for two successive data verification is 16, 23, 43, and 57s for data sizes of 1, 2, 3, and 4GB, respectively. The proposed model consumes 15, 28, 44, and 54s, respectively, for the data size from 1GB to 4GB.