Optimal Solutions for the Temporal Precedence Problem

Abstract. In this paper we refer to the Temporal Precedence Problem on Pure Pointer Machines . This problem asks for the design of a data structure, maintaining a set of stored elements and supporting the following two operations: insert and precedes . The operation insert (a) introduces a new element a in the structure, while the operation precedes (a,b) returns true iff element a was inserted before element b temporally. In [11] a solution was provided to the problem with worst-case time complexity O (log log n ) per operation and O(n log log n) space, where n is the number of elements inserted. It was also demonstrated that the precedes operation has a lower bound of Ω (log log n ) for the Pure Pointer Machine model of computation. In this paper we present two simple solutions with linear space and worst-case constant insertion time. In addition, we describe two algorithms that can handle the precedes (a,b) operation in O (log log d ) time, where d is the temporal distance between the elements a and b .     

Local community detection with hints

Local community detection is a widely used method for identifying groups of nodes starting from seeding nodes. The seed(s) are usually selected either randomly or based only on structural properties of the network. However, in many cases the choice of seed(s) incorporates external knowledge that attaches to these nodes an additional importance for their community. This knowledge, may be derived from an expert on the domain, or may arise from the network’s side information and it constitutes our motivation for the present work; this additional information about the importance of seed(s) can be exploited for detection of better and more relevant communities. We call such biased seed(s), hint(s). Our approach, is to reflect the importance of hints by changing appropriately the network in their vicinity. To the best of our knowledge, no such viewpoint of the seeding nodes in local community detection has been considered before. The aim of this study is to identify a single community which contains the hint(s). Our key contribution is the proposed Hint Enhancement Framework(HEF) that applies a two-step procedure to discover the community of the hint(s): 1) it changes the network by amplifying the hint(s) using re-weighting or re-wiring strategies so as to materialize the bias towards them and 2) it applies local community detection algorithms on the altered network of step 1. We experimentally evaluate HEF in synthetic and real datasets, and demonstrate the positive aspects of the framework in identifying better communities, in comparison with plain local community detection algorithms as well as a global one.

     

ART: sub-logarithmic decentralized range query processing with probabilistic guarantees

We focus on range query processing on large-scale, typically distributed infrastructures, such as clouds of thousands of nodes of shared-datacenters, of p2p distributed overlays, etc. In such distributed environments, efficient range query processing is the key for managing the distributed data sets per se, and for monitoring the infrastructure’s resources. We wish to develop an architecture that can support range queries in such large-scale decentralized environments and can scale in terms of the number of nodes as well as in terms of the data items stored. Of course, in the last few years there have been a number of solutions (mostly from researchers in the p2p domain) for designing such large-scale systems. However, these are inadequate for our purposes, since at the envisaged scales the classic logarithmic complexity (for point queries) is still too expensive while for range queries it is even more disappointing. In this paper we go one step further and achieve a sub-logarithmic complexity. We contribute the ART (Autonomous Range Tree) structure, which outperforms the most popular decentralized structures, including Chord (and some of its successors), BATON (and its successor) and Skip-Graphs. We contribute theoretical analysis, backed up by detailed experimental results, showing that the communication cost of query and update operations is $O(\log_{b}^{2} \log N)$ hops, where the base b is a double-exponentially power of two and N is the total number of nodes. Moreover, ART is a fully dynamic and fault-tolerant structure, which supports the join/leave node operations in O(loglogN) expected w.h.p. number of hops. Our experimental performance studies include a detailed performance comparison which showcases the improved performance, scalability, and robustness of ART.     

Scheduling algorithms for procrastinators

This paper presents scheduling algorithms for procrastinators, where the speed that a procrastinator executes a job increases as the due date approaches. We give optimal off-line scheduling policies for linearly increasing speed functions. We then explain the computational/numerical issues involved in implementing this policy. We next explore the online setting, showing that there exist adversaries that force any online scheduling policy to miss due dates. This impossibility result motivates the problem of minimizing the maximum interval stretch of any job; the interval stretch of a job is the job’s flow time divided by the job’s due date minus release time. We show that several common scheduling strategies, including the “hit-the-highest-nail” strategy beloved by procrastinators, have arbitrarily large maximum interval stretch. Then we give the “thrashing” scheduling policy and show that it is a Θ(1) approximation algorithm for the maximum interval stretch. Research of M.A. Bender was supported in part by NSF Grants CCR-0208670, CCF-0621439/0621425, CCF-0540897/05414009, CCF-0634793/0632838, and CNS-0627645.     

Improved Bounds for Finger Search on a RAM

We present a new finger search tree with O(loglogd) expected search time in the Random Access Machine (RAM) model of computation for a large class of input distributions. The parameter d represents the number of elements (distance) between the search element and an element pointed to by a finger, in a finger search tree that stores n elements. Our data structure improves upon a previous result by Andersson and Mattsson that exhibits expected O(loglogn) search time by incorporating the distance d into the search time complexity, and thus removing the dependence on n. We are also able to show that the search time is O(loglogd+?(n)) with high probability, where ?(n) is any slowly growing function of n. For the need of the analysis we model the updates by a “balls and bins” combinatorial game that is interesting in its own right as it involves insertions and deletions of balls according to an unknown distribution.