Abstract: Skyline queries are capable of retrieving interesting points from a large data set according to multiple criteria. As an essential query, skyline computation over data stream is very important for many online applications, including mobile environment, network monitoring, communication, sensor network and stock market trading, etc. The problem of skyline computation has attracted considerable research attention. Different from most popular skyline processing methods, this paper focuses on constrained skyline and dynamic skyline processing over data stream. Instead of computing the skyline results on the whole data set, this kind of skyline query only needs to process parts of the data set, and there are maybe thousands of such queries in the system. To deal with the challenges of the random additions and deletions of the tuples over data stream, we employ a grid based index to store the tuples and put forward an algorithm to compute and maintain skyline set based on it. By making use of the advantage of grid index, we define influence area for every query to minimize the cells need to be processed when new tuples arrive and old tuples expire. Only tuples in the cells that belong to influence area will be processed. This way, the tuples which are not in the influence area will be ignored and the CPU time is saved. Theoretical analysis and experimental evidences show the efficiency of the proposed approaches.