Shift-varying segmentation uses a shift-varying predicate function to evaluate input data within a sliding window to determine if the current sliding window position should be a segment boundary. The shift-varying predicate function is a function of both the input data within the sliding window and the position of the sliding window relative to a previous segment boundary or the beginning of the input data. The shift-varying predicate function includes a containment property and may compute a hash value from the input data in the sliding window. The hash value is compared to a threshold value that is a function of the sliding window position. As the sliding window position advances away from a previous segment boundary, the probability of a segment boundary at the window position increases. Shift-varying segmentation can be used in compression, transaction acceleration, and data storage applications.