Search

International audience; Classical list scheduling is a very popular and efficient technique for scheduling jobs in parallel platforms. However, with the increasing number of processors, the cost for managing a single centralized list becomes prohibitive. The objective of this work is to study the extra cost that must be paid when the list is distributed among the processors. We present a general methodology for computing the expected makespan based on the analysis of an adequate potential function which represents the load unbalance between the local lists. A bound on the deviation from the mean is also derived. Then, we apply this technique to show that the expected makespan for scheduling W unit independent tasks on m processors is equal to W/m with an additional term in 3.65log2 W. Moreover, simulations show that our bound is very close to the exact value, approximately 50% off. This new analysis also enables to study the influence of the initial repartition of tasks and the reduction of the number of steals when several thieves can simultaneously steal work in the same processor's list.

In this paper, the performance of the content identification based on digital fingerprinting and order statistic list decoding is analyzed by evaluating the probabilities of correct identification, false acceptance and the probability mass function of queried binary fingerprint position on the list of candidates. The particular attention is dedicated to the cases when traditional maximum likelihood decoder fails to produce the reliable content identification. The maximum likelihood decoding is shown to be a particular case of order statistic list decoding for the list size equals 1. We demonstrate the efficiency of the proposed content identification system performance by investigating the probability mass function behavior and imposing the constraint on the cardinality of list size.

In this paper we propose a novel interaction technique to use with a prediction list. Our aim is to optimize the use of this assistive aid. A prediction list is generally used to reduce effort by presenting a list of candidate words that may continue the prefix of the user. However, this technique presents a disadvantage: sometimes the word that the user is aiming to write is not presented in the list. The user has to continue his typing manually. Our technique allows the user to click on any letter in a word of the list so that the substring from this letter is inserted in the text. We also present the experiments carried out to compare our system to the classical list.

In this paper, we present an algorithm for a generalization of list ranking called computation list evaluation. As a consequence of the generalization and the existence of this algorithm for computation list evaluation, we obtain a generalization of Euler Tour technique. Finally, we present several applications of the generalized Euler Tour technique. Of interest in the applications is the identification of a set of problem instances that are solvable using tree contraction and which can alternatively be solved using a simple algorithm based on the generalized Euler Tour technique.

SUMMARY A new internal array structure, called a double-array, implementing a trie structure is presented. The double-array combines the fast access of a matrix form with the compactness of a list form. The algorithms for retrieval, insertion and deletion are introduced through examples. Although insertion is rather slow, it is still practical, and both the deletion and the retrieval time can be improved from the list form. From the comparison with the list for various large sets of keys, it is shown that the size of the double-array can be about 17 per cent smaller than that of the list, and that the retrieval speed of the double-array can be from 3·1 to 5·1 times faster than that of the list.

We consider the problem of dynamic reorganization of a linear list, where requests for the elements are generated randomly with fixed probabilities. The objective is to obtain the smallest expected cost per access. It has been shown that when no a-priori information is given on the reference probabilities, the Counter Scheme(CS) provides an optimal reorganization rule which applies to all possible distributions. In this paper we examine strategies which may use partial a priori information on the access probabilities in the list reorganization process. Such useful knowledge may be either the correct relative order of a subset of the items, or the precise values of some of the probabilities. For the first case we show that a slight modification on the original CS bests all realizable policies. However, it turns out that in the last case there exists no such universal optimal policy. For this model we also show that the obvious organization by the Maximum Likelihood estimate may be inferior to the CS, which...

A suitable and dynamic neighbor cell list will increase the soft handoff success rate thus decrease the drop probability. Thus it is significant to design an effective neighbor cell list generating algorithm. The conventional algorithms generate the list by simply putting all the neighbor cells together. That will increase the pilot search time, so the handoff success rate reduces. This paper presents a dynamic neighbor cell list generating algorithm based on vote model. Besides, it is optimized by using the handoff statistical information to make the vote-coefficient adaptive by itself.

List update algorithms have been widely used as subroutines in compression schemas, most notably as part of Burrows-Wheeler compression. The Burrows-Wheeler transform (BWT), which is the basis of many state-of-the-art general purpose compressors applies a compression algorithm to a permuted version of the original text. List update algorithms are a common choice for this second stage of BWT-based compression. In this paper we perform an experimental comparison of various list update algorithms both as stand alone compression mechanisms and as a second stage of the BWT-based compression. Our experiments show MTF outperforms other list update algorithms in practice after BWT. This is consistent with the intuition that BWT increases locality of reference and the predicted result from the locality of reference model of Angelopoulos et al. [1]. Lastly, we observe that due to an often neglected difference in the cost models, good list update algorithms may be far from optimal for BWT compression and construct an explicit example of this phenomena. This is a fact that had yet to be supported theoretically in the literature.

FP-growth algorithm is one of the most efficient approaches for frequent item set mining. In this article, an improved FP-growth algorithm based on Compound Single Linked List is proposed. There are two contributions in the new algorithm. One is to use the sequencing table and single linked list as the main data structure, the other is that it does not need to generate conditional FP-tree. An experiment is conducted to compare the efficiency between the original one and the improved one. It shows that the new one improves the algorithm both in runtime and the main memory consumption.

Sorting is an important concept in the field of Computer Sciences. In this paper we presents an incremental sorting algorithm, which traverses the list in both directions (right and left) comparing first element of the list, with next two elements, and comparing last element with previous two elements in the list. Similarly by iteratively scanning the list, brings the list in sorting order.

In this paper we give a randomized on-line algorithm for the list update problem. Sleator and Tarjan show a deterministic algorithm, Move-to-Front, that achieves competitive ratio of ( 2L−1) L for lists of length L. Karp and Raghavan show that no deterministic algorithm can beat 2L (L+1) . We show that Move-to-Front in fact achieves an optimal competitive ratio of 2L (L+1) . We show a randomized algorithm that achieves a competitive ratio of (31L+1) 16(L+1) against an oblivious adversary. This is the first randomized strategy whose competitive factor beats a constant less than 2.

The author presents a deterministic parallel algorithm for the linked list prefix problem. It computes linked list prefixs for an input list of n elements in time O(n/p+logn) on a local memory PRAM model using p processors and p shared memory cells. >

The sphere decoder (SD) has been utilized for maximum likelihood (ML) detection in MIMO systems. In order to improve system performance, the SD is usually combined with the error correction codes where soft decoding is utilized. The list sphere decoder (LSD) was introduced to generate a candidate list, which can provide soft information to the outer decoder. Unlike the conventional sphere decoder, the LSD has the candidate list updating and new radius generation units, which causes extra complexity and latency. In this paper, we present a novel radius updating architecture, which can obtain a new radius much faster than the conventional method. Furthermore, we propose an efficient candidate list updating scheme, which can significantly save the complexity (without affecting the decoding speed) of updating the candidate list used to compute soft information.

It is known that in practice, request sequences for the list update problem exhibit a certain degree of locality of reference. Motivated by this observation we apply the locality of reference model for the paging problem due to Albers et al. [STOC 2002/JCSS 2005] in conjunction with bijective analysis [SODA 2007] to list update. Using this framework, we prove that Move-to-Front (MTF) is the unique optimal algorithm for list update. This addresses the open question of defining an appropriate model for capturing locality of reference in the context of list update [Hester and Hirschberg ACM Comp. Surv. 1985]. Our results hold both for the standard cost function of Sleator and Tarjan [CACM 1985] and the improved cost function proposed independently by Martinez and Roura [TCS 2000] and Munro [ESA 2000]. This result resolves an open problem of Martinez and Roura, namely proposing a measure which can successfully separate MTF from all other list-update algorithms.

Based on the ADT (abstract data type) definition, characteristics and storage structure of generalized list a new representation called GBLL (generalized binary linked list) is proposed. The purpose of GBLL is to improve generalized list in its application areas. A few algorithms of GBLL and the analyses of their complexities are provided. In order to reduce the runtime memory consumption and increase the execution efficiency, non-recursive algorithms are used most of time.

List update algorithms have been widely used as subroutines in compression schemas, most notably as part of Burrows-Wheeler compression. We performed an experimental comparison of various list update algorithms both as stand alone compression mechanisms and as a second stage of the BWT-based compression. We considered the following list update algorithms: move-to-front (MTF), sort-by-rank (SBR), frequency-count (FC), timestamp (TS), and transpose (TR) on text files of the Calgary Corpus. Our results showed that TR and FC usually outperform MTF and TS if we do not use BWT. This is in contrast with competitive analysis in which MTF and TS are superior to TS and FC. After BWT, MTF and TS have comparable performance and always outperform FC and TR. Our experiments are consistent with the intuition that BWT increases locality of reference and the predicted result from the locality of reference model of the work of Angelopoulos et al. (2008).

We compare the theory and practice of online algorithms, and show that in certain instances there is a large gap between the predictions from theory and observed practice. In particular, the competitive ratio which is the main technique for analysis of online algorithms is known to produce unrealistic measures of performance in certain settings. Motivated by this we examine first the case of paging. We present a study of the reasons behind this apparent failure of the theoretical model. We then show that a new measure derived from first principles and introduced by [Angelopoulos, Dorrigiv and Lopez-Ortiz, SODA 2007] better corresponds to observed practice. Using these ideas, we derive a new framework termed the cooperative ratio that generalizes to all other online analysis settings and illustrate with examples in list update.

We present a comprehensive study of the list update problem with locality of reference. More specifically, we present a combined theoretical and experimental study in which the theoretically proven and experimentally observed performance guarantees of algorithms match or nearly match. In the first part of the paper we introduce a new model of locality of reference that closely captures the concept of runs, representing sequences of requests to the same item. Using this model we develop refined theoretical analyses of popular list update algorithms. The second part of the paper is devoted to an extensive experimental study in which we have tested the algorithms on traces from benchmark libraries. It shows that the theoretical and experimental bounds differ by just a few percent. Our new theoretical bounds are substantially lower than those provided by standard competitive analysis. Another result is that the well-known Move-To-Front strategy exhibits the best performance. Its refined competitive ratio tends to 1 as the degree of locality in a request sequence increases. This confirms that Move-To-Front is the method of choice in practice. &nbsp

One of the more successful approaches to image segmentation involves formulating the problem as the minimisation of a Mumford-Shah functional and then applying region merging algorithms to approximate the minimiser. Moreover, it can be proved mathematically that such segmentations have desirable properties, and further, fast implementations are available. In this paper, we describe improvements to one such algorithm, the full lambda-schedule segmentation algorithm (FLSA). The FLSA maintains a list of merge costs (as measured by the Mumford-Shah functional) for all relevant pairs of neighbouring regions and at each step selects the best pair to merge from the list. This is done quickly and efficiently through the use sophisticated data structures. We present significant improvements to those data structures which further simplify the maintenance of the merge cost list. The new algorithm makes use of a new list, the edge list, which allows the regions neighbouring a newly merged pair to be searched more efficiently. Owing to a change in the way "multiple boundaries'' are handled, the new segmentations may differ slightly from the old ones but we argue that they are equally valid. We refer to the new algorithm as the FLSA Edge List (FLSA-EL) algorithm.

In this article a variation of binary search applicable to a linked list structure is examined. There are no additional data structure properties imposed on the list; that is the list may be singly or multiply linked, but it is not required that the list be represented as a binary tree. The process can be used with improved efficiency in place of linear search on a linked list where introducing additional data structures complexity on the list is not desirable.This procedure seems appropriate for inclusion in data structures courses where searching and sorting are discussed. The texts on data structures cover the binary search on a fixed length sequence, but the general consensus is that there is no advantage in trying to implement the binary search process on linked lists. One possible exception in this regard, where no details are provided, is [2, page 147].

This chapter introduces the list, map, and range. All are collections of references to other objects. The List and Map can reference objects of differing types. The Range represents a collection of integer values. The List and Map also grow dynamically. Each object referenced in a List is identified by an integer index. In contrast, a Map collection is indexed by a value of any kind. Because the class of the objects maintained by these collections is arbitrary, the elements of a List might be a Map and the elements of a Map might be a List. In this way, it can be used to create data structures of arbitrary complexity. The List is a structure used to store a collection of data items. In Groovy, the List holds a sequence of object references. The Groovy List class supports a host of methods that make list processing pleasing and easy. The List class removes much of the work that would otherwise have to be programmed in an application. A Map (also known as an associative array, dictionary, table, and hash) is an unordered collection of object references. The elements in a Map collection are accessed by a key value. The keys used in a Map can be of any class. The Map class supports a range of methods that make map processing very easy. A range is shorthand for specifying a sequence of values. A Range is denoted by the first and last values in the sequence, and Range can be inclusive or exclusive.

Most mobile phones today offer the option of using a word list to ease the typing of short messages (SMS). When a word list is used, a word is input as a sequence of digits by pressing the key corresponding to each letter once. The word list is used to look up the word(s) that correspond to this sequence of digits. This paper describes how a mobile phone keyboard layout can be obtained that is better suited for typing such messages. Two objectives are considered: the total cost of typing, and the total cost of word clashes that occur when a certain digit sequence corresponds to two or more words in the word list. A multi-start descent algorithm is developed to obtain a Pareto set of solutions.

In this paper we describe a simple parallel algorithm for list ranking. The algorithm is deterministic and runs in O(log n) time on EREW P-RAM with n/log n processor. The algorithm matches the performance of the Cole-Vishkin [CV86a] algorithm but is simple and has reasonable constant factors.

The latency and throughput of MPI messages are critically important to a range of parallel scientific applications. In many modern networks, both of these performance characteristics are largely driven by the performance of a processor on the network interface. Because of the semantics of MPI, this embedded processor is forced to traverse a linked list of posted receives each time a messages is received. As this list grows long, the latency of message reception grows and the throughput of MPI messages decreases. This paper presents a novel hardware feature to handle list management functions on a network interface. By moving functions such as list insertion, list traversal, and list deletion to the hardware unit, latencies are decreased by up to 20% in the zero length queue case with dramatic improvements in the presence of long queues. Similarly, the throughput is increased by up to 10% in the zero length queue case and by nearly 100% in the presence queues of 30 messages

The well-known TOP500 list ranks the 500 most powerful high-performance computers. However, the list lacks details about the job management and scheduling on these machines. As this statistic is interesting for researchers and system designers, this paper gives an overview and survey on scheduling relevant information for the first 50 entries in the TOP500 list.

In this paper we present a solution called Materialized Aggregate List designed for the efficient storing and processing of long aggregate lists. An aggregate list contains aggregates, calculated from the data stored in the database. In our approach, once created, the aggregates are materialized for further use. The list structure contains a table divided into pages. We present three different page-filling algorithms used when the list is browsed. We present test results and we use them for estimating the best combination of the configuration parameters: number of pages, size of a single page and number of available database connections. The Materialized Aggregate List can be applied on every aggregation level in various indexing structures, such as, an aR-tree.

The BEAST-APP decoding algorithm is a low-complexity bidirectional algorithm that searches code trees to find the list of the most likely codewords, which are used to compute approximate a posteriori probabilities (APPs) of the transmitted symbols. It can be applied to APP-decoding of any linear block code, as well as in iterative structures for decoding concatenated block codes. Previous work has shown that the list size sufficient to achieve the performance of true-APP decoding is very small. This paper aims at providing a theoretical justification for this result. The sufficient list size is estimated first via the minimum list distance - a parameter that is defined and analyzed as a key factor that governs the performance of list-based algorithms. Additionally, statistical properties of the codeword likelihoods are investigated and the typical list structure is presented. Preliminary simulation results for iterative BEAST decoding confirm the list-size estimates obtained from both approaches

Lock-free shared data structures implement distributed objects without the use of mutual exclusion, thus providing robustness and reliability. We present a new lock-free implementation of singly-linked lists. We prove that the worst-case amortized cost of the operations on our linked lists is linear in the length of the list plus the contention, which is better than in previous lock-free implementations of this data structure. Our implementation uses backlinks that are set when a node is deleted so that concurrent operations visiting the deleted node can recover. To avoid performance problems that would arise from traversing long chains of backlink pointers, we introduce flag bits, which indicate that a deletion of the next node is underway. We then give a lock-free implementation of a skip list dictionary data structure that uses the new linked list algorithms to implement individual levels. Our algorithms use the single-word C&S synchronization primitive.

A linear list is a collection of items that can be accessed sequentially. The cost of a request is the number of items that need to be examined before the desired item is located, i.e., the distance of the requested item from the beginning of the list. The transposition rule is one of the algorithms designed to reduce the search cost by organizing the list. In particular, upon a request for a given item, the item is transposed with the preceding one. We develop a new approach for analyzing the algorithm. The approach is based on a coupling with a certain constrained asymmetric exclusion process. This allows us to establish an asymptotic optimality of the rule for two families of request distributions., 11 pages, 2 figures

In this paper we present two algorithms for solving the list update problem which is to maintain a list of items to support such basic operations as access, insert and delete. The first algorithm proposed is an approximation to the optimal off-line algorithm. Knowing the complete request sequence, it provides a good approximation to the lower bound of the optimum cost and finds an approximately optimum service sequence in polynomial time of the list and the size of the request sequence. The underlying idea is to maintain the pairwise optimal ordering of the items except for the case of conflicts, when no exchange takes place. The approximate off-line algorithm takes O(n/sup 3/ m) time and O(1) space, where n is the length of the list and m is the number of requests. Our second algorithm is a deterministic on-line algorithm which is shown to be 2-competitive under any sequence of access requests. It can be efficiently implemented compared to the best known deterministic online algorithms such as MTF and TS (0). We also show that using the proposed on-line algorithm as a procedure in data compression techniques, it is possible to obtain better compression ratio.

The high frequency of applications involving large, ordered, nested lists suggests that list is the "next most" natural data type after set. A list differs from a set through positioning and nesting elements within the list. Directly supporting such position-related operations will greatly improve the performance of database systems targeting at the above applications. Unlike other attributes, the position will be changed by insertion and deletion within a list and known methods are not appropriate for indexing the position. We present an indexing structure, called the P-tree (where P for position), to index a set of lists. The P-tree generalizes the B-tree by dealing with a set of lists rather than a set of records, while preserving all the properties of the B-tree.

Future microcellular personal communications systems (PCSs) will be characterized by high user density and high mobility. It is expected that registrations will incur a large amount of the radio link signaling traffic. A profile-based strategy (PBS) is proposed to reduce the signaling traffic on the radio link by increasing the intelligence within the fixed network. The system maintains a sequential list of the most likely places where each user is located. The list is ranked from the most to the least likely place where a user is found. When a call arrives for a mobile, it is paged sequentially in each location within the list. When a user moves between location areas in this list, no location update is required. The list may be provided by the user or may be based on each user's past calling history. The method for doing this is outside the scope of this work. This work focuses on the potential performance improvements that can result from maintaining such a list. This paper compares the performance of the proposed strategy to the typical geographic-based location-tracking schemes being implemented in evolving digital cellular and cordless standards. Key performance measures for the comparison are radio bandwidth, fixed network SS7 traffic, and call setup delay. We investigate the conditions under which the PBS performs better than the traditional scheme. Results indicate that over a wide range of parameters, it may be possible to reduce both the radio bandwidth and fixed network signaling load for a modest increase in call setup delay.

This article presents a distributed directory based cache coherence protocol that improves performance and facilitates error recovery in large scale multiprocessors. A number of distributed directory based protocols, such as the Scalable Coherent Interface (SCI, ANSI/IEEE Std 1596), use a linked list structure to maintain cache coherence. While they work well for small to medium size systems, the list traversal overhead becomes high when the system size grows into the thousands of processors range. Also, the system is vulnerable to a single node failure in that the recovery from such a failure involves all the processors in the system. Single node failure can happen relatively frequently when a protocol is applied to SCI-based Local Area MultiProcessors (LAMP) where individual nodes are autonomous computers and can power up and down individually. We propose an enhancement to the linked list approach. A redundant spanning list is constructed when the list is built, which achieves two goals: 1) the list traversal time is reduced from O(N) to O(/spl radic/N) and 2) recovery from single node failure is confined to the processors involved in the failed list, unless the head of the list is lost.

The agents described in the article were used to create a system which does most of the creation, addition, and maintenance of an annotated reference list page. This system has been used to maintain a telecommunications Web page for the last two years. The strength of this system is that it automatically locates a large number of potential links which may be included in the Web page, and uses a fairly fast method of interfacing with the list maintainer to verify links before their inclusion. The paper discusses the implementation of agents to automate the task of maintaining an annotated reference list.

Wide acceptance of inexpensive writing tablets with high fractionality motivates the development of individualized, adaptive online recognition of cursive script. We demonstrate a lexical algorithm based on bigram matches. The solution we propose is to: 1) generate a match list by partial-word matching against a reference list in the owner's script; and 2) identify each unknown word by eliminating, from a large lexicon, every word that partially matches the transcript of any word on the reference list that is not on the match list, or that fails to match any word on the match list. With perfect feature-level matching, a surprisingly short reference list yields a high recognition rate.

The optimal competitive ratio for a randomized online list update algorithm is known to be at least 1.5 and at most 1.6, but the remaining gap is not yet closed. We present a new lower bound of 1.50084 for the partial cost model. The construction is based on game trees with incomplete information, which seem to be generally useful for the competitive analysis of online algorithms. 2001 Elsevier Science B.V.

The class of memoryless heuristics for maintaining a Doubly-Linked List in an approximately optimal order is studied. Two mappings that relate Singly-Linked List and Doubly-Linked List heuristics are defined, and theorems involving these mappings are presented. A new heuristic referred to as the Swap heuristic for the Doubly-Linked List is introduced, and its asymptotic distribution has been derived

The list update problem is a classical online problem, with an optimal competitive ratio that is still open, somewhere between 1.5 and 1.6. An algorithm with competitive ratio 1.6, the smallest known to date, is COMB, a randomized combination of BIT and TIMESTAMP. This and many other known algorithms, like MTF, are projective in the sense that they can be defined by only looking at any pair of list items at a time. Projectivity simplifies both the description of the algorithm and its analysis, and so far seems to be the only way to define a good online algorithm for lists of arbitrary length. In this paper we characterize all projective list update algorithms and show their competitive ratio is never smaller than 1.6. Therefore, COMB is a best possible projective algorithm, and any better algorithm, if it exists, would need a non-projective approach.

International audience; This paper adresses the definition and properties of list scheduling in the context of scheduling a cyclic set of n non-preemptive and non-reentrant-dependent tasks on m identical processors when the reduced precedence graph is assumed to be strongly connected. It is first shown that the average cycle time of an arbitrary list schedule is at most (2-1/m) times the absolute minimum average cycle time. K-periodic list schedules are then shown to be the list schedules associated with special priority mappings called K-periodic linear orders. Moreover, given a list that offers the performance ratio p in the non-cyclic case and whose structure is quasi K-periodic in the cyclic case, it is shown that each of its corresponding K-periodic linear orders provides a list schedule with the same guarantee. Since the well-known Coffman-Graham's list is shown to be quasi K-periodic, its performance may be transferred to UET cyclic problems.

We show how to reduce the time overhead for implementing two-way movement on a singly linked list to O ( n ϵ ) per operation without modifying the list and without making use of storage other than a finite number of pointers into the list. We also prove a matching lower bound.These results add precision to the intuitive feeling that doubly linked lists are more efficient than singly linked lists, and quantify the efficiency gap in a read-only situation. We further analyze the number of points of access into the list (pointers) necessary for obtaining a desired value of ϵ. We obtain tight tradeoffs which also separate the amortized and worst-case settings.Our upper bound implies that read-only programs with singly-linked input can do string matching much faster than previously expected.

An on-line algorithm for the list update problem has been proposed and is shown to be 2-competitive under any sequence of access requests. The simpler version of the algorithm can be easily and efficiently implemented. Further, using this algorithm as a procedure in data compression technique it is possible to obtain better compression ratio than other known algorithms.

The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system algorithm, called the work function algorithm, has constant competitive ratio for list update. In the process, we present a new formulation of the well-known "list factoring" technique in terms of a partial order on the elements of the list. This approach leads to a new simple proof that a large class of online algorithms, including Move-To-Front, is (2 - 1/k)-competitive.

The Stanford distributed-directory (SDD) cache-coherence protocol, based on a singly linked list of distributed directories, is examined. Sharing-list additions and removals are explained diagramatically. Reads, writes, pending signals, replacement, and synchronization are discussed. Replacing lines linked in a list is done by invalidating the lower part of the list. A doubly linked list may be used to patch the list in case of replacements. However, in practice, performance improvement depends on the list lengths and access patterns. A distributed-directory cache-coherence protocol allows efficient implementation of locks at minimal extra cost. The SDD protocol allows a lock implementation that minimizes network traffic. >

We consider the online list accessing problem and present a new family of competitive-optimal deterministic list update algorithms which is the largest class of such algorithms known to-date. This family, called SORT-BY-RANK (SBR), is parametrized with a real 0 ≤ α ≤ 1, where SBR(0) is the MOVE-TO-FRONT algorithm and SBR(1) is equivalent to the TIMESTAMP algorithm. The behaviour of SBR(α) mediates between the eager strategy of MOVE-TO-FRONT and the more conservative behaviour of TIMESTAMP. We also present a family of algorithms SORT-BY-DELAY (SBD) which is parametrized by the positive integers, where SBD(1) is MOVE-TO-FRONT and SBD(2) is equivalent to TIMESTAMP. In general, SBD(k) is k- competitive for k ≥ 2. This is the first class of algorithms that is asymptotically optimal for independent, identically distributed requests while each algorithm is constant-competitive. Empirical studies with with both generated and real-world data are also included.

Let Xi i=1 t8 be independent random variables, assuming values in [0, 1], having a common mean μ, and variances bounded by σ2. Let Sn = Σ i=1 n Xi . We give a general and simple method for obtaining asymptotically optimal upper bounds on probabilities of events of the form Sn - E[Sn] ≥ na with explicit dependence on μ and σ2. For general bounded random variables the method yields the Bennett inequality, with a simplified proof. For specific classes of distributions the method can be used to derive bounds that are tighter than those achieved by the Bennett inequality. We demonstrate the power of the method by applying it to the case of symmetric three-point distributions, thus improving previous results for the List Update Problem.

This article concerns the static analysis of programs that perform destructive updating on heap-allocated storage. We give an algorithm that uses finite shape graphs to approximate conservatively the possible “shapes” that heap-allocated structures in a program can take on. For certain programs, our technique is able to determine such properties as (1) when the input to the program is a list, the output is also a list and (2) when the input to the program is a tree, the output is also a tree. For example, the method can determine that “listness” is preserved by (1) a program that performs list reversal via destructive updating of the input list and (2) a program that searches a list and splices a new element into the list. None of the previously known methods that use graphs to model the program's store are capable of determining that “listness” is preserved on these examples (or examples of similar complexity). In contrast with most previous work, our shape analysis algorithm is even accurate for certain programs that update cyclic data structures; that is, it is sometimes able to show that when the input to the program is a circular list, the output is also a circular list. For example, the shape-analysis algorithm can determine that an insertion into a circular list preserves “circular listness.”

The extraction of operation level parallelism from sequential code has become an important problem in compiler research due to the proliferation of superscalar and VLIW architectures. This problem becomes especially hard for code containing a large number of conditional branches. In this paper we extend previous work on straight line code scheduling by looking at branching task systems whose control flow graph is acyclic. First, we define an optimality measure based on the probability of the various execution paths. Then, we apply a list scheduling algorithm to these systems and derive a worst case performance guarantee for this method. Finally, we show that there are branching task systems for which this bound is almost tight.