Ubiquitous trajectory data provides new opportunities for production and update of the road network. A number of methods have been proposed for road network construction and update based on trajectory data. However, existing methods were mainly focused on reconstruction of the existing road network, and the update of newly added roads was not given much attention. Besides, most of existing methods were designed for high sampling rate trajectory data, while the commonly available GPS trajectory data are usually low-quality data with noise, low sampling rates, and uneven spatial distributions. In this paper, we present an automatic method for detection and update of newly added roads based on the common low-quality trajectory data. First, additive changes (i.e., newly added roads) are detected using a point-to-segment matching algorithm. Then, the geometric structures of new roads are constructed based on a newly developed decomposition-combination map generation algorithm. Finally, the detected new roads are refined and combined with the original road network. Seven trajectory data were used to test the proposed method. Experiments show that the proposed method can successfully detect the additive changes and generate a road network which updates efficiently.