Skyline queries enable more intuitive querying, essential for e.g. e-commerce applications. However, the performance of query execution will drastically deteriorate, if categorical data is involved. Unfortunately most Web data tends to be of exactly that nature. In this paper we show how to remedy the gap in current skylining algorithms and adapt them for the nature of Web data. Our innovative algorithm minimizes the amount of expensive object accesses over the Internet and allows for progressive delivery of correct result objects at an early stage. These can already be syndicated with all necessary information and returned to the user while the search is still running. This also optimizes the use of available bandwidth and thus paves the road to efficient Web information systems.