| 1. |
- Chalermsook, P., et al.
(författare)
-
Greedy is an almost optimal deque
- 2015
-
Ingår i: 14th International Symposium on Algorithms and Data Structures, WADS 2015. - Cham : Springer. - 9783319218397 ; , s. 152-165
-
Konferensbidrag (refereegranskat)abstract
- In this paper we extend the geometric binary search tree (BST) model of Demaine, Harmon, Iacono, Kane, and Pătraşcu (DHIKP) to accommodate for insertions and deletions. Within this extended model, we study the online GREEDY BST algorithm introduced by DHIKP. GREEDY BST is known to be equivalent to a maximally greedy (but inherently offline) algorithm introduced independently by Lucas in 1988 and Munro in 2000, conjectured to be dynamically optimal. With the application of forbidden-submatrix theory, we prove a quasilinear upper bound on the performance of GREEDY BST on deque sequences. It has been conjectured (Tarjan, 1985) that splay trees (Sleator and Tarjan, 1983) can serve such sequences in linear time. Currently neither splay trees, nor other general-purpose BST algorithms are known to fulfill this requirement. As a special case, we show that GREEDY BST can serve output-restricted deque sequences in linear time. A similar result is known for splay trees (Tarjan, 1985; Elmasry, 2004). As a further application of the insert-delete model, we give a simple proof that, given a set U of permutations of [n], the access cost of any BST algorithm is Ω(log |U| + n) on “most” of the permutations from U. In particular, this implies that the access cost for a random permutation of [n] is Ω(n log n) with high probability. Besides the splay tree noted before, GREEDY BST has recently emerged as a plausible candidate for dynamic optimality. Compared to splay trees, much less effort has gone into analyzing GREEDY BST. Our work is intended as a step towards a full understanding of GREEDY BST, and we remark that forbidden-submatrix arguments seem particularly well suited for carrying out this program.
|
|
| 2. |
- Chalermsook, P., et al.
(författare)
-
Multi-finger binary search trees
- 2018
-
Ingår i: Leibniz International Proceedings in Informatics, LIPIcs. - : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. - 9783959770941 ; , s. 55:1-55:26
-
Konferensbidrag (refereegranskat)abstract
- We study multi-finger binary search trees (BSTs), a far-reaching extension of the classical BST model, with connections to the well-studied k-server problem. Finger search is a popular technique for speeding up BST operations when a query sequence has locality of reference. BSTs with multiple fingers can exploit more general regularities in the input. In this paper we consider the cost of serving a sequence of queries in an optimal (offline) BST with k fingers, a powerful benchmark against which other algorithms can be measured. We show that the k-finger optimum can be matched by a standard dynamic BST (having a single root-finger) with an O(log k) factor overhead. This result is tight for all k, improving the O(k) factor implicit in earlier work. Furthermore, we describe new online BSTs that match this bound up to a (log k) O (1) factor. Previously only the “one-finger” special case was known to hold for an online BST (Iacono, Langerman, 2016; Cole et al., 2000). Splay trees, assuming their conjectured optimality (Sleator and Tarjan, 1983), would have to match our bounds for all k. Our online algorithms are randomized and combine techniques developed for the k-server problem with a multiplicative-weights scheme for learning tree metrics. To our knowledge, this is the first time when tools developed for the k-server problem are used in BSTs. As an application of our k-finger results, we show that BSTs can efficiently serve queries that are close to some recently accessed item. This is a (restricted) form of the unified property (Iacono, 2001) that was previously not known to hold for any BST algorithm, online or offline.
|
|
| 3. |
- Chalermsook, P., et al.
(författare)
-
Pattern-Avoiding Access in Binary Search Trees
- 2015
-
Ingår i: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. - : Institute of Electrical and Electronics Engineers (IEEE). - 9781467381918 ; , s. 410-423
-
Konferensbidrag (refereegranskat)abstract
- The dynamic optimality conjecture is perhaps the most fundamental open question about binary search trees (BST). It postulates the existence of an asymptotically optimal online BST, i.e. One that is constant factor competitive with any BST on any input access sequence. The two main candidates for dynamic optimality in the literature are splay trees [Sleator and Tarjan, 1985], and Greedy [Lucas, 1988, Munro, 2000, Demaine et al. 2009]. Despite BSTs being among the simplest data structures in computer science, and despite extensive effort over the past three decades, the conjecture remains elusive. Dynamic optimality is trivial for almost all sequences: the optimum access cost of most length-n sequences is Theta(n log n), achievable by any balanced BST. Thus, the obvious missing step towards the conjecture is an understanding of the 'easy' access sequences, and indeed the most fruitful research direction so far has been the study of specific sequences, whose 'easiness' is captured by a parameter of interest. For instance, splay provably achieves the bound of O(nd) when d roughly measures the distances between consecutive accesses (dynamic finger), the average entropy (static optimality), or the delays between multiple accesses of an element(working set). The difficulty of proving dynamic optimality is witnessed by other highly restricted special cases that remain unresolved, one prominent example is the traversal conjecture [Sleator and Tarjan, 1985], which states that preorder sequences (whose optimum is linear) are linear-time accessed by splay trees, no online BST is known to satisfy this conjecture. In this paper, we prove two different relaxations of the traversal conjecture for Greedy: (i) Greedy is almost linear for preorder traversal, (ii) if a linear-time preprocessing is allowed, Greedy is in fact linear. These statements are corollaries of our more general results that express the complexity of access sequences in terms of a pattern avoidance parameter k. Pattern avoidance is a well-established concept in combinatorics, and the classes of input sequences thus defined are rich, e.g. The k = 3 case includes preorder sequences. For any sequence X with parameter k, our most general result shows that Greedy achieves the cost n2α(n)O(k) where α is the inverse Ackermann function. Furthermore, a broad subclass of parameter-k sequences has a natural combinatorial interpretation as k-decomposable sequences. For this class of inputs, we obtain an n∗2O(k) bound for Greedy when preprocessing is allowed. For k = 3, these results imply (i) and (ii). To our knowledge, these are the first upper bounds for Greedy that are not known to hold for any other online BST. To obtain these results we identify an input-revealing property of Greedy. Informally, this means that the execution log partially reveals the structure of the access sequence. This property facilitates the use of rich technical tools from forbidden sub matrix theory. Further studying the intrinsic complexity of k-decomposable sequences, we make several observations. First, in order to obtain an offline optimal BST, it is enough to bound Greedy on non-decomposable access sequences. Furthermore, we show that the optimal cost for k-decomposable sequences is Theta(n log k), which is well below the proven performance of all known BST algorithms. Hence, sequences in this class can be seen as a 'candidate counterexample' to dynamic optimality.
|
|
| 4. |
|
|
| 5. |
- Gumaelius, Lena, et al.
(författare)
-
Outreach initiatives operated by universities for increasing interest in science and technology
- 2016
-
Ingår i: European Journal of Engineering Education. - : Taylor & Francis Group. - 0304-3797 .- 1469-5898. ; , s. 1-34
-
Tidskriftsartikel (refereegranskat)abstract
- Since the 1990s, the low number of students choosing to study science and technology in higher education has been on the societal agenda and many initiatives have been launched to promote awareness regarding career options. The initiatives particularly focus on increasing enrolment in the engineering programmes. This article describes and compares eight European initiatives that have been established and operated by universities (and in some cases through collaboration with other actors in society). Each initiative is summarised in a short essay that discusses motivation, organisation, pedagogical approach, and activities. The initiatives are characterised by comparing the driving forces behind their creation, how the initiative activities relate to the activities at the university, size based on the number of participants and cost per participant and pedagogical framework. There seem to be two main tracks for building outreach activities, one where outreach activities are based on the university's normal activities, and one where outreach activities are designed specifically for the visiting students.
|
|
| 6. |
- Meeuwsen, John A.L., et al.
(författare)
-
High levels of (un)switched memory B cells are associated with better outcome in patients with advanced atherosclerotic disease
- 2017
-
Ingår i: Journal of the American Heart Association. - 2047-9980. ; 6:9
-
Tidskriftsartikel (refereegranskat)abstract
- Background--Atherosclerosis is an inflammatory lipid disorder and the main underlying pathology of acute ischemic events. Despite a vast amount of data from murine atherosclerosis models, evidence of B-cell involvement in human atherosclerotic disease is limited. We therefore investigated the association of circulating B-cell subtypes with the occurrence of secondary cardiovascular events in advanced atherosclerotic disease. Methods and Results--This cohort study consists of 168 patients who were included in the Athero-Express biobank between 2009 and 2011. Before surgery, peripheral blood mononuclear cells were isolated and stored in liquid nitrogen. After gentle thawing of the peripheral blood mononuclear cells, different B-cell subtypes including naïve, (un)switched memory, and CD27+CD43+ B1-like B cells, were analyzed by flow cytometry. Univariable and multivariable Cox proportional hazard models were used to analyze associations between B-cell subtypes, circulating antibodies and secondary cardiovascular manifestations during the 3-year follow-up period. Mean age was 70.1±9.6 years, males represented 62.8% of the population, and 54 patients had secondary manifestations during follow-up. High numbers of unswitched memory cells were protective against secondary outcome (hazard ratio, 0.30 [95% CI, 0.13-0.69]; P < 0.01). Similar results were obtained for the switched memory cells that also showed to be protective against secondary outcome (hazard ratio, 0.33 [95% CI, 0.14-0.77]; P = 0.01). Conclusions--A high number of (un)switched memory B cells is associated with better outcome following carotid artery endarterectomy. These findings suggest a potential role for B-cell subsets in prediction and prevention of secondary cardiovascular events in patients with atherosclerosis.
|
|
