The Neural Basis of Involuntary Episodic Memories

Involuntary episodic memories are memories that come into consciousness without preceding retrieval effort. These memories are commonplace and are relevant to multiple mental disorders. However, they are vastly understudied. We use a novel paradigm to elicit involuntary memories in the laboratory so that we can study their neural basis. In session one, an encoding session, sounds are presented with picture pairs or alone. In session two, in the scanner, sounds-picture pairs and unpaired sounds are reencoded. Immediately following, participants are split into two groups: a voluntary and an involuntary group. Both groups perform a sound localization task in which they hear the sounds and indicate the side from which they are coming. The voluntary group additionally tries to remember the pictures that were paired with the sounds. Looking at neural activity, we find a main effect of condition (paired vs. unpaired sounds) showing similar activity in both groups for voluntary and involuntary memories in regions typically associated with retrieval. There is also a main effect of group (voluntary vs. involuntary) in the dorsolateral prefrontal cortex, a region typically associated with cognitive control. Turning to connectivity similarities and differences between groups again, there is a main effect of condition showing paired > unpaired sounds are associated with a recollection network. In addition, three group differences were found: (1) increased connectivity between the pulvinar nucleus of the thalamus and the recollection network for the voluntary group, (2) a higher association between the voluntary group and a network that includes regions typically found in frontoparietal and cingulo-opercular networks, and (3) shorter path length for about half of the nodes in these networks for the voluntary group. Finally, we use the same paradigm to compare involuntary memories in people with posttraumatic stress disorder (PTSD) to trauma-controls. This study also included the addition of emotional pictures. There were two main findings. (1) A similar pattern of activity was found for paired > unpaired sounds for both groups but this activity was delayed in the PTSD group. (2) A similar pattern of activity was found for high > low emotion stimuli but it occurred early in the PTSD group compared to the control group. Our results suggest that involuntary and voluntary memories share the same neural representation but that voluntary memories are associated with additional cognitive control processes. They also suggest that disorders associated with cognitive deficits, like PTSD, can affect the processing of involuntary memories.

Algorithms for Geometric Matching, Clustering, and Covering

With the popularization of GPS-enabled devices such as mobile phones, location data are becoming available at an unprecedented scale. The locations may be collected from many different sources such as vehicles moving around a city, user check-ins in social networks, and geo-tagged micro-blogging photos or messages. Besides the longitude and latitude, each location record may also have a timestamp and additional information such as the name of the location. Time-ordered sequences of these locations form trajectories, which together contain useful high-level information about people's movement patterns.

The first part of this thesis focuses on a few geometric problems motivated by the matching and clustering of trajectories. We first give a new algorithm for computing a matching between a pair of curves under existing models such as dynamic time warping (DTW). The algorithm is more efficient than standard dynamic programming algorithms both theoretically and practically. We then propose a new matching model for trajectories that avoids the drawbacks of existing models. For trajectory clustering, we present an algorithm that computes clusters of subtrajectories, which correspond to common movement patterns. We also consider trajectories of check-ins, and propose a statistical generative model, which identifies check-in clusters as well as the transition patterns between the clusters.

The second part of the thesis considers the problem of covering shortest paths in a road network, motivated by an EV charging station placement problem. More specifically, a subset of vertices in the road network are selected to place charging stations so that every shortest path contains enough charging stations and can be traveled by an EV without draining the battery. We first introduce a general technique for the geometric set cover problem. This technique leads to near-linear-time approximation algorithms, which are the state-of-the-art algorithms for this problem in either running time or approximation ratio. We then use this technique to develop a near-linear-time algorithm for this

shortest-path cover problem.