{'fraction_non_alphanumeric': 0.02996845425867508, 'fraction_numerical': 0.01025236593059937, 'mean_word_length': 4.821100917431193, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Page Migration Algorithms Using Work Functions

The page migration problem is the management problem for a globally addressed shared memory in a multiprocessor system. Each physical page of memory is located at a given processor, and memory references to that page by other processors incur a cost equal to the network distance. At times the page may migrate between processors, at a cost equal to the distance times the page size factor, D. The problem is to schedule movements on-line so as to minimize the total cost of memory references. We consider the problem under the restriction that movement can only occur after a request has been served and before the next request is known. The major results are: we give randomized (2+1/2D)-competitive on-line algorithms for trees (and products of trees, including the hypercube), and for a uniform space when D=1,2. We show that these algorithms are optimal. We prove a 85/27 lower bound on the competitiveness constant of a deterministic algorithm (in arbitrary spaces) with D=1, disproving a conjecture by Black and Sleator. We show a deterministic (2+1/2D)-competitive algorithm for continuous trees. Our analysis is based on work functions, which provide a systematic approach to many competitive analysis problems.