We present a new data structure for maintaining a set of n d-dimensional points with insertion and deletion in time O(lg^{d-1}(n) lg lg(n)) and querying for the set of Pareto-maximal points in time O(k^{floor(d/2)} lg^{d-1}(n) lg lg(n)) where k denotes the number of Pareto-maximal points. We also present another version with update time O(n) and query time O(k).