Explore the vast range of titles available.

A new and conceptually simple data structure, called a suffix array, for on-line string searches is introduced in this paper. Constructing and querying suffix arrays is reduced to a sort and search paradigm that employs novel algorithms. The main advantage of suffix arrays over suffix trees is that, in practice, they use three to five times less space. From a complexity standpoint, suffix arrays permit on-line string searches of the type, \"Is $W$ a substring of $A$?\" to be answered in time $O(P + \\log N)$, where $P$ is the length of $W$ and $N$ is the length of $A$, which is competitive with (and in some cases slightly better than) suffix trees. The only drawback is that in those instances where the underlying alphabet is finite and small, suffix trees can be constructed in $O(N)$ time in the worst case, versus $O(N\\log N)$ time for suffix arrays. However, an augmented algorithm is given that, regardless of the alphabet size, constructs suffix arrays in $O(N)$expected time, albeit with lesser space efficiency. It is believed that suffix arrays will prove to be better in practice than suffix trees for many applications.

The identification of novel disease associations using big-data for patient care has had limited success. In this study, we created a longitudinal disease network of traced readmissions (disease trajectories), merging data from over 10.4 million inpatients through the Healthcare Cost and Utilization Project, which allowed the representation of disease progression mapping over 300 diseases. From these disease trajectories, we discovered an interesting association between schizophrenia and rhabdomyolysis, a rare muscle disease (incidence < 1E-04) (relative risk, 2.21 [1.80–2.71, confidence interval = 0.95], P-value 9.54E-15). We validated this association by using independent electronic medical records from over 830,000 patients at the University of California, San Francisco (UCSF) medical center. A case review of 29 rhabdomyolysis incidents in schizophrenia patients at UCSF demonstrated that 62% are idiopathic, without the use of any drug known to lead to this adverse event, suggesting a warning to physicians to watch for this unexpected risk of schizophrenia. Large-scale analysis of disease trajectories can help physicians understand potential sequential events in their patients.

This paper considers the amount of cooperation required for independent asynchronous processes to share a simple dynamic data structure. We present a scheme for designing efficient concurrent algorithms to add and remove elements from a shared pool of elements. The efficiency is measured mainly by the number of non-local operations that a process may have to make. Non-local operations may involve writing into a shared variable, locking, or sending a message, hence they introduce interference (or require cooperation). We derive upper and lower bounds on the interference in the worst case. Applications to distributed computation are also discussed.

While it has been technically feasible to create longitudinal representations of individual health at a nationwide scale, the use of these techniques to identify novel disease associations for the risk stratification of patients has had limited success. Here, we created a large-scale US longitudinal disease network of traced readmission patterns (i.e., disease trajectories), merging data from over 10.4 million inpatients from 350 California hospitals through the Healthcare Cost and Utilization Project between 1980 and 2010. We were able to create longitudinal representations of disease progression mapping over 300 common diseases, including the well-known complication of heart failure after acute myocardial infarction. Surprisingly, out of these generated disease trajectories, we discovered an unknown association between schizophrenia, a chronic mental disorder, and rhabdomyolysis, a rare disease of muscle breakdown. It was found that 92 of 3674 patients (2.5%) with schizophrenia were readmitted for rhabdomyolysis (relative risk, 2.21 [1.80-2.71, confidence interval = 0.95] P-value 9.54E-15), which has a general population incidence of 1 in 10,000. We validated this association using independent electronic health records from over 830,000 patients treated over seven years at the University of California, San Francisco (UCSF) medical center. A case review of 29 patients at UCSF who were treated for schizophrenia and who went on to develop rhabdomyolysis demonstrated that the majority of cases (62%) are idiopathic, which suggests a biological connection between these two diseases. Together, these findings demonstrate the power of using public disease registries in combination with electronic medical records to discover novel disease associations.

A generalization of Dobkin and Lipton's element uniqueness problem is introduced. For any fixed undirected graph $G$ on vertex set $\\{ v _1 , v_2 , \\cdots , v_n \\} $, the problem is to determine, given $n$ real numbers $x_1 ,x_2 , \\cdots ,x_n $, whether $x_i \\ne x_j $ for every edge $\\{ \\upsilon _i ,\\upsilon _j \\} $ in $G$. This problem is shown to have upper and lower bounds of $\\Theta (n\\log n)$ linear comparisons if $G$ is any dense graph. The proof of the lower bound involves showing that any dense graph must contain a subgraph with many Hamiltonian paths, and demonstrating the relevance of these Hamiltonian paths to a geometric argument. In addition, we exhibit relatively sparse graphs for which the same lower bound holds, and relatively dense graphs for which a linear upper bound holds.

An incremental approach to addressing algorithmic problems is suggested.