Demo Data from EDBT 2026 / reviewers in the wild / expert
Cynthia A. Phillips
dblp:18/1807
· DBLP profile ↗
56ranked-venue papers
10as first author
4since 2021 · last 2024
0000-0001-8914-9562ORCID · conflict
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 23 · 7 first-authorSystems, architecture and hardware · 16 · 2 first-author · 2 since 2021Computer networks · 6 · 1 since 2021Databases, data management, data science and information retrieval · 5 · 1 since 2021Graphics, computer vision, multimedia, augmented reality and games · 4 · 1 first-authorArtificial intelligence and machine learning · 1Security and privacy · 1Applied, interdisciplinary, general and emerging computing · 1
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Databases, data mining, and information retrieval
5 papers |
Data stream processing · 48% Indexing and storage engines · 45% Data mining · 8% | |
| Computer networks
3 papers |
Internet of things and sensor networks · 67% Vehicular, aerial and satellite networks · 12% Routing and switching · 12% | |
| Computer architecture, parallel and distributed computing, and storage systems
4 papers |
Performance modeling and evaluation · 52% Electronic design automation · 37% Storage systems · 8% | |
| Theoretical computer science
9 papers |
Algorithms and data structures · 51% Mathematical optimization · 23% Approximation and online algorithms · 14% | |
| Interdisciplinary, comprehensive, and emerging computing
4 papers |
Bioinformatics and computational biology · 50% Computational science and engineering · 50% |
Topics — the 30 heaviest of 47, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Data stream processing › frequency estimation
heavy hitter detection |
0.9 | 2 | 2021 | Timely Reporting of Heavy Hitters Using External Memory · ACM Trans. Database Syst. 2021 Timely Reporting of Heavy Hitters using External Memory · SIGMOD Conference 2020 |
Internet of things and sensor networks
underwater sensor networks |
0.5 | 2 | 2018 | Path Finding for Maximum Value of Information in Multi-Modal Underwater Wireless Sensor Networks · IEEE Trans. Mob. Comput. 2018 Maximizing the value of sensed information in underwater wireless sensor networks via an autonomous underwater vehicle · INFOCOM 2014 |
Indexing and storage engines
external memory data structure |
0.5 | 1 | 2021 | Timely Reporting of Heavy Hitters Using External Memory · ACM Trans. Database Syst. 2021 |
Internet of things and sensor networks
value of information |
0.4 | 2 | 2018 | Path Finding for Maximum Value of Information in Multi-Modal Underwater Wireless Sensor Networks · IEEE Trans. Mob. Comput. 2018 Maximizing the value of sensed information in underwater wireless sensor networks via an autonomous underwater vehicle · INFOCOM 2014 |
Electronic design automation
benchmark generation |
0.4 | 1 | 2019 | Scalable generation of graphs for benchmarking HPC community-detection algorithms · SC 2019 |
Performance modeling and evaluation
synthetic graph generation |
0.4 | 1 | 2019 | Scalable generation of graphs for benchmarking HPC community-detection algorithms · SC 2019 |
Algorithms and data structures › data structure design › search structures
skip list |
0.3 | 1 | 2017 | Write-Optimized Skip Lists · PODS 2017 |
Indexing and storage engines
b-tree |
0.2 | 1 | 2016 | Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries · PODS 2016 |
Vehicular, aerial and satellite networks
autonomous underwater vehicle |
0.2 | 1 | 2014 | Maximizing the value of sensed information in underwater wireless sensor networks via an autonomous underwater vehicle · INFOCOM 2014 |
Internet of things and sensor networks › wireless sensor network
data collection |
0.2 | 1 | 2014 | Maximizing the value of sensed information in underwater wireless sensor networks via an autonomous underwater vehicle · INFOCOM 2014 |
Routing and switching
path planning |
0.2 | 1 | 2014 | Maximizing the value of sensed information in underwater wireless sensor networks via an autonomous underwater vehicle · INFOCOM 2014 |
Performance modeling and evaluation
benchmarking |
0.1 | 1 | 2021 | Timely Reporting of Heavy Hitters Using External Memory · ACM Trans. Database Syst. 2021 |
Data mining › structured data mining › graph mining
community detection |
0.1 | 1 | 2019 | Scalable generation of graphs for benchmarking HPC community-detection algorithms · SC 2019 |
Data mining › structured data mining
graph mining |
0.1 | 1 | 2019 | Scalable generation of graphs for benchmarking HPC community-detection algorithms · SC 2019 |
Storage systems › flash and SSD › flash memory management › garbage collection
write amplification |
0.1 | 1 | 2017 | Write-Optimized Skip Lists · PODS 2017 |
Wireless networking
broadcast |
0.1 | 1 | 2008 | Sleeping on the job: energy-efficient and robust broadcast for radio networks · PODC 2008 |
Wireless networking
radio networks |
0.1 | 1 | 2008 | Sleeping on the job: energy-efficient and robust broadcast for radio networks · PODC 2008 |
Algorithms and data structures › memory hierarchy › external memory algorithms
cache-oblivious algorithms |
0.1 | 1 | 2016 | Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries · PODS 2016 |
Approximation and online algorithms › online algorithms
online scheduling |
0.0 | 2 | 2000 | Off-line admission control for general scheduling problems · SODA 2000 Optimal Time-Critical Scheduling via Resource Augmentation (Extended Abstract) · STOC 1997 |
Mathematical optimization
scheduling |
0.0 | 2 | 2000 | Off-line admission control for general scheduling problems · SODA 2000 Improved Scheduling Algorithms for Minsum Criteria · ICALP 1996 |
Bioinformatics and computational biology
phylogenetics |
0.0 | 2 | 1999 | Constructing Evolutionary Trees in the Presence of Polymorphic Characters · SIAM J. Comput. 1999 Constructing Evolutionary Trees in the Presence of Polymorphic Characters · STOC 1996 |
Algorithmic game theory and mechanism design › resource allocation › online resource allocation
admission control |
0.0 | 1 | 2000 | Off-line admission control for general scheduling problems · SODA 2000 |
Approximation and online algorithms
approximation algorithms |
0.0 | 1 | 2000 | Strengthening integrality gaps for capacitated network design and covering problems · SODA 2000 |
Mathematical optimization › optimization
capacitated network design |
0.0 | 1 | 2000 | Strengthening integrality gaps for capacitated network design and covering problems · SODA 2000 |
Mathematical optimization
integer programming |
0.0 | 1 | 2000 | Strengthening integrality gaps for capacitated network design and covering problems · SODA 2000 |
Mathematical optimization › linear programming relaxation
integrality gap |
0.0 | 1 | 2000 | Strengthening integrality gaps for capacitated network design and covering problems · SODA 2000 |
Mathematical optimization
linear programming relaxation |
0.0 | 1 | 2000 | Strengthening integrality gaps for capacitated network design and covering problems · SODA 2000 |
Energy-efficient computing
power management |
0.0 | 1 | 2008 | Sleeping on the job: energy-efficient and robust broadcast for radio networks · PODC 2008 |
Bioinformatics and computational biology › phylogenetics › computational phylogenetics
perfect phylogeny |
0.0 | 1 | 1999 | Constructing Evolutionary Trees in the Presence of Polymorphic Characters · SIAM J. Comput. 1999 |
Graph algorithms and graph theory › graph algorithms › tree algorithms
tree construction |
0.0 | 1 | 1999 | Constructing Evolutionary Trees in the Presence of Polymorphic Characters · SIAM J. Comput. 1999 |
Methods — techniques the papers use, named apart from their topics
multi-threaded implementation · 1.0probabilistic analysis · 0.9amortized analysis · 0.9LFR graph generator · 0.8integer linear programming · 0.5greedy heuristic · 0.5packed-memory array · 0.5external-memory skip list · 0.5external-memory algorithm · 0.5external memory algorithms · 0.5randomized scheduling · 0.2bad santa problem · 0.2polynomial-time algorithm · 0.0offline scheduling algorithms · 0.0integrality gap construction · 0.0LP relaxation · 0.0resource augmentation · 0.0monte carlo simulation · 0.0
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2024 | Shortest path network interdiction with asymmetric uncertaintyabstractAbstract This paper considers an extension of the shortest path network interdiction problem that incorporates robustness to account for parameter uncertainty. The shortest path interdiction problem is a game of two players with conflicting agendas and capabilities: an evader, who traverses the arcs of a network from a source node to a sink node using a path of shortest length, and an interdictor, who maximizes the length of the evader's shortest path by interdicting arcs on the network. It is usually assumed that the parameters defining the network are known exactly by both players. We consider the situation where the evader assumes the nominal parameter values while the interdictor uses robust optimization techniques to account for parameter uncertainty or sensor degradation. We formulate this problem as a nonlinear mixed‐integer semi‐infinite bilevel program and show that it can be converted into a mixed‐integer linear program with a second order cone constraint. We use random geometric networks and transportation networks to perform computational studies and demonstrate the unique decision strategies that our variant produces. Solving the shortest path interdiction problem with asymmetric uncertainty protects the interdictor from investing in a strategy that hinges on key interdictions performing as promised. It also provides an alternate strategy that mitigates the risk of these worst‐case possibilities. She'ifa Z. Punla-Green, John E. Mitchell 0001, Jared L. Gearhart, William E. Hart, Cynthia A. Phillips |
Networks | 5 |
| 2022 | Automatic HBM Management: Models and AlgorithmsabstractSome past and future supercomputer nodes incorporate High- Bandwidth Memory (HBM). Compared to standard DRAM, HBM has similar latency, higher bandwidth and lower capacity. Daniel DeLayo, Kenny Zhang, Kunal Agrawal 0001, Michael A. Bender, Jonathan W. Berry, Rathish Das, Benjamin Moseley, Cynthia A. Phillips |
SPAA | 8 |
| 2021 | Provable Advantages for Graph Algorithms in Spiking Neural NetworksabstractWe present a theoretical framework for designing and assessing the performance of algorithms executing in networks consisting of spiking artificial neurons. Although spiking neural networks (SNNs) are capable of general-purpose computation, few algorithmic results with rigorous asymptotic performance analysis are known. SNNs are exceptionally well-motivated practically, as neuromorphic computing systems with 100 million spiking neurons are available, and systems with a billion neurons are anticipated in the next few years. Beyond massive parallelism and scalability, neuromorphic computing systems offer energy consumption orders of magnitude lower than conventional high-performance computing systems. We employ our framework to design and analyze neuromorphic graph algorithms, focusing on shortest path problems. Our neuromorphic algorithms are message-passing algorithms relying critically on data movement for computation, and we develop data-movement lower bounds for conventional algorithms. A fair and rigorous comparison with conventional algorithms and architectures is challenging but paramount. We prove a polynomial-factor advantage even when we assume an SNN consisting of a simple grid-like network of neurons. To the best of our knowledge, this is one of the first examples of a provable asymptotic computational advantage for neuromorphic computing. James B. Aimone, Yang Ho, Ojas Parekh, Cynthia A. Phillips, Ali Pinar, William Severa, Yipu Wang |
SPAA | 4 |
| 2021 | Timely Reporting of Heavy Hitters Using External MemoryabstractGiven an input stream S of size N , a ɸ-heavy hitter is an item that occurs at least ɸN times in S . The problem of finding heavy-hitters is extensively studied in the database literature. We study a real-time heavy-hitters variant in which an element must be reported shortly after we see its T = ɸ N-th occurrence (and hence it becomes a heavy hitter). We call this the Timely Event Detection ( TED ) Problem. The TED problem models the needs of many real-world monitoring systems, which demand accurate (i.e., no false negatives) and timely reporting of all events from large, high-speed streams with a low reporting threshold (high sensitivity). Like the classic heavy-hitters problem, solving the TED problem without false-positives requires large space (Ω (N) words). Thus in-RAM heavy-hitters algorithms typically sacrifice accuracy (i.e., allow false positives), sensitivity, or timeliness (i.e., use multiple passes). We show how to adapt heavy-hitters algorithms to external memory to solve the TED problem on large high-speed streams while guaranteeing accuracy, sensitivity, and timeliness. Our data structures are limited only by I/O-bandwidth (not latency) and support a tunable tradeoff between reporting delay and I/O overhead. With a small bounded reporting delay, our algorithms incur only a logarithmic I/O overhead. We implement and validate our data structures empirically using the Firehose streaming benchmark. Multi-threaded versions of our structures can scale to process 11M observations per second before becoming CPU bound. In comparison, a naive adaptation of the standard heavy-hitters algorithm to external memory would be limited by the storage device’s random I/O throughput, i.e., ≈100K observations per second. Shikha Singh 0002, Prashant Pandey 0001, Michael A. Bender, Jonathan W. Berry, Martin Farach-Colton, Rob Johnson 0001, Tom M. Kroeger, Cynthia A. Phillips |
ACM Trans. Database Syst. | 8 |
| 2020 | Timely Reporting of Heavy Hitters using External MemoryabstractGiven an input stream of size N, a φ-heavy hitter is an item that occurs at least φ N times in S. The problem of finding heavy-hitters is extensively studied in the database literature. We study a real-time heavy-hitters variant in which an element must be reported shortly after we see its T = φ N-th occurrence (and hence becomes a heavy hitter). We call this the Timely Event Detection (TED) Problem. The TED problem models the needs of many real-world monitoring systems, which demand accurate (i.e., no false negatives) and timely reporting of all events from large, high-speed streams, and with a low reporting threshold (high sensitivity). Like the classic heavy-hitters problem, solving the TED problem without false-positives requires large space (Ω(N) words). Thus in-RAM heavy-hitters algorithms typically sacrifice accuracy (i.e., allow false positives), sensitivity, or timeliness (i.e., use multiple passes). We show how to adapt heavy-hitters algorithms to external memory to solve the TED problem on large high-speed streams while guaranteeing accuracy, sensitivity, and timeliness. Our data structures are limited only by I/O-bandwidth (not latency) and support a tunable trade-off between reporting delay and I/O overhead. With a small bounded reporting delay, our algorithms incur only a logarithmic I/O overhead. We implement and validate our data structures empirically using the Firehose streaming benchmark. Multi-threaded versions of our structures can scale to process 11M observations per second before becoming CPU bound. In comparison, a naive adaptation of the standard heavy-hitters algorithm to external memory would be limited by the storage device's random I/O throughput, i.e., ~100K observations per second. Prashant Pandey 0001, Shikha Singh 0002, Michael A. Bender, Jonathan W. Berry, Martin Farach-Colton, Rob Johnson 0001, Tom M. Kroeger, Cynthia A. Phillips |
SIGMOD Conference | 8 |
| 2020 | Provable Neuromorphic Advantages for Computing Shortest PathsabstractNeuromorphic computing offers the potential of an unprecedented level of parallelism at a local scale. Although in their infancy, current first-generation neuromorphic processing units (NPUs) deliver as many as 128K artificial neurons in a package smaller than current laptop CPUs and demanding significantly less energy. Neuromorphic systems consisting of such NPUs and offering a total of 100 million neurons are anticipated in 2020. NPUs were envisioned to accelerate machine learning, and designing neuromorphic algorithms to leverage the benefits of NPUs in other domains remains an open challenge. We design and analyze neuromorphic graph algorithms, focusing on shortest path problems. Our neuromorphic algorithms are packet-passing algorithms relying on data movement for computation, and we develop data-movement lower bounds for conventional algorithms. A fair and rigorous comparison with conventional algorithms and architectures is paramount, and we prove a polynomial-factor advantage even when we assume an NPU with a simple grid-like network of neurons. To the best of our knowledge, this is one of the first examples of a provable asymptotic computational advantage for neuromorphic computing. James B. Aimone, Yang Ho, Ojas Parekh, Cynthia A. Phillips, Ali Pinar, William Severa, Yipu Wang |
SPAA | 4 |
| 2020 | How to Manage High-Bandwidth Memory AutomaticallyabstractThis paper develops an algorithmic foundation for automated management of the multilevel-memory systems common to new supercomputers. In particular, the High-Bandwidth Memory (HBM) of these systems has a similar latency to that of DRAM and a smaller capacity, but it has much larger bandwidth. Systems equipped with HBM do not fit in classic memory-hierarchy models due to HBM's atypical characteristics. Rathish Das, Kunal Agrawal 0001, Michael A. Bender, Jonathan W. Berry, Benjamin Moseley, Cynthia A. Phillips |
SPAA | 6 |
| 2020 | Probing a Set of Trajectories to Maximize Captured InformationabstractWe study a trajectory analysis problem we call the Trajectory Capture Problem (TCP), in which, for a given input set T of trajectories in the plane, and an integer k≥ 2, we seek to compute a set of k points ("portals") to maximize the total weight of all subtrajectories of T between pairs of portals. This problem naturally arises in trajectory analysis and summarization. We show that the TCP is NP-hard (even in very special cases) and give some first approximation results. Our main focus is on attacking the TCP with practical algorithm-engineering approaches, including integer linear programming (to solve instances to provable optimality) and local search methods. We study the integrality gap arising from such approaches. We analyze our methods on different classes of data, including benchmark instances that we generate. Our goal is to understand the best performing heuristics, based on both solution time and solution quality. We demonstrate that we are able to compute provably optimal solutions for real-world instances. Sándor P. Fekete, Alexander Hill, Dominik Krupke, Tyler Mayer, Joseph S. B. Mitchell, Ojas Parekh, Cynthia A. Phillips |
SEA | 7 |
| 2019 | Enabling Onboard Detection of Events of Scientific Interest for the Europa Clipper SpacecraftabstractData analysis and machine learning methods have great potential to aid in planetary exploration. Spacecraft often operate at great distances from the Earth, and the ability to autonomously detect features of interest onboard can enable content-sensitive downlink prioritization to increase mission science return. We describe algorithms that we designed to assist in three specific scientific investigations to be conducted during flybys of Jupiter's moon Europa: the detection of thermal anomalies, compositional anomalies, and plumes of icy matter from Europa's subsurface ocean. We also share the unique constraints imposed by the onboard computing environment and several lessons learned in our collaboration with planetary scientists and mission designers. Kiri Wagstaff, Gary Doran, Ashley Davies, Saadat Anwar, Srija Chakraborty, Marissa Cameron, Ingrid Daubar, Cynthia A. Phillips |
KDD | 8 |
| 2019 | Scalable generation of graphs for benchmarking HPC community-detection algorithmsabstractCommunity detection in graphs is a canonical social network analysis method. We consider the problem of generating suites of teras-cale synthetic social networks to compare the solution quality of parallel community-detection methods. The standard method, based on the graph generator of Lancichinetti, Fortunato, and Radicchi (LFR), has been used extensively for modest-scale graphs, but has inherent scalability limitations. George M. Slota, Jonathan W. Berry, Simon D. Hammond, Stephen Olivier, Cynthia A. Phillips, Sivasankaran Rajamanickam |
SC | 5 |
| 2018 | Constant-Depth and Subcubic-Size Threshold Circuits for Matrix MultiplicationabstractBoolean circuits of McCulloch-Pitts threshold gates are a classic model of neural computation studied heavily in the late 20th century as a model of general computation. Recent advances in large-scale neural computing hardware has made their practical implementation a near-term possibility. We describe a theoretical approach for multiplying two N by N matrices that integrates threshold gate logic with conventional fast matrix multiplication algorithms, that perform $O(N^ømega)$ arithmetic operations for a positive constant $ømega < 3$. Our approach converts such a fast matrix multiplication algorithm into a constant-depth threshold circuit with approximately $O(N^ømega)$ gates. Prior to our work, it was not known whether the Θ(N^3)$-gate barrier for matrix multiplication was surmountable by constant-depth threshold circuits. Dense matrix multiplication is a core operation in convolutional neural network training. Performing this work on a neural architecture instead of off-loading it to a GPU may be an appealing option. Ojas Parekh, Cynthia A. Phillips, Conrad D. James, James B. Aimone |
SPAA | 2 |
| 2018 | Geometric Hitting Set for Segments of Few Orientations
Sándor P. Fekete, Kan Huang, Joseph S. B. Mitchell, Ojas Parekh, Cynthia A. Phillips |
Theory Comput. Syst. | 5 |
| 2018 | Path Finding for Maximum Value of Information in Multi-Modal Underwater Wireless Sensor NetworksabstractWe consider underwater multi-modal wireless sensor networks (UWSNs) suitable for applications on submarine surveillance and monitoring, where nodes offload data to a mobile autonomous underwater vehicle (AUV) via optical technology, and coordinate using acoustic communication. Sensed data are associated with a value, decaying in time. In this scenario, we address the problem of finding the path of the AUV so that the Value of Information (VoI) of the data delivered to a sink on the surface is maximized. We define a Greedy and Adaptive AUV Path-finding (GAAP) heuristic that drives the AUV to collect data from nodes depending on the VoI of their data. For benchmarking the performance of AUV path-finding heuristics, we define an integer linear programming (ILP) formulation that accurately models the considered scenario, deriving a path that drives the AUV to collect and deliver data with the maximum VoI. In our experiments GAAP consistently delivers more than 80 percent of the theoretical maximum VoI determined by the ILP model. We also compare the performance of GAAP with that of other strategies for driving the AUV among sensing nodes, namely, random paths, TSP-based paths and a “lawn mower”-like strategy. Our results show that GAAP always outperforms every other heuristic in terms of delivered VoI, also obtaining higher energy efficiency. Petrika Gjanci, Chiara Petrioli, Stefano Basagni, Cynthia A. Phillips, Ladislau Bölöni, Damla Turgut |
IEEE Trans. Mob. Comput. | 4 |
| 2017 | Write-Optimized Skip ListsabstractThe skip list is an elegant dictionary data structure that is commonly deployed in RAM. A skip list with N elements supports searches, inserts, and deletes in O(log N) operations with high probability (w.h.p.) and range queries returning K elements in O(log N + K) operations w.h.p. Michael A. Bender, Martin Farach-Colton, Rob Johnson 0001, Simon Mauras, Tyler Mayer, Cynthia A. Phillips, Helen Xu 0001 |
PODS | 6 |
| 2017 | Two-level main memory co-design: Multi-threaded algorithmic primitives, analysis, and simulation
Michael A. Bender, Jonathan W. Berry, Simon D. Hammond, Karl S. Hemmert, Samuel McCauley, Branden Moore, Benjamin Moseley, Cynthia A. Phillips, David S. Resnick, Arun Rodrigues |
J. Parallel Distributed Comput. | 8 |
| 2016 | Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and DictionariesabstractWe present history-independent alternatives to a B-tree, the primary indexing data structure used in databases. A data structure is history independent (HI) if it is impossible to deduce any information by examining the bit representation of the data structure that is not already available through the API. We show how to build a history-independent cache-oblivious B-tree and a history-independent external-memory skip list. One of the main contributions is a data structure we build on the way---a history-independent packed-memory array (PMA). The PMA supports efficient range queries, one of the most important operations for answering database queries. Michael A. Bender, Jonathan W. Berry, Rob Johnson 0001, Tom M. Kroeger, Samuel McCauley, Cynthia A. Phillips, Bertrand Simon 0001, Shikha Singh 0002, David Zage |
PODS | 6 |
| 2015 | Two-Level Main Memory Co-Design: Multi-threaded Algorithmic Primitives, Analysis, and SimulationabstractA fundamental challenge for supercomputer architecture is that processors cannot be fed data from DRAM as fast as CPUs can consume it. Therefore, many applications are memory-bandwidth bound. As the number of cores per chip increases, and traditional DDR DRAM speeds stagnate, the problem is only getting worse. A variety of non-DDR 3D memory technologies (Wide I/O 2, HBM) offer higher bandwidth and lower power by stacking DRAM chips on the processor or nearby on a silicon interposer. However, such a packaging scheme cannot contain sufficient memory capacity for a node. It seems likely that future systems will require at least two levels of main memory: high-bandwidth, low-power memory near the processor and low-bandwidth high-capacity memory further away. This near memory will probably not have significantly faster latency than the far memory. This, combined with the large size of the near memory (multiple GB) and power constraints, may make it difficult to treat it as a standard cache. In this paper, we explore some of the design space for a user-controlled multi-level main memory. We present algorithms designed for the heterogeneous bandwidth, using streaming to exploit data locality. We consider algorithms for the fundamental application of sorting. Our algorithms asymptotically reduce memory-block transfers under certain architectural parameter settings. We use and extend Sandia National Laboratories' SST simulation capability to demonstrate the relationship between increased bandwidth and improved algorithmic performance. Memory access counts from simulations corroborate predicted performance. This co-design effort suggests implementing two-level main memory systems may improve memory performance in fundamental applications. Michael A. Bender, Jonathan W. Berry, Simon D. Hammond, Karl S. Hemmert, Samuel McCauley, Branden Moore, Benjamin Moseley, Cynthia A. Phillips, David S. Resnick, Arun Rodrigues |
IPDPS | 8 |
| 2015 | Cooperative Computing for Autonomous Data CentersabstractWe present a new distributed model for graph computations motivated by limited information sharing. Two or more independent entities have collected large social graphs. They wish to compute the result of running graph algorithms on the entire set of relationships. Because the information is sensitive or economically valuable, they do not wish to simply combine the information in a single location. We consider two models for computing the solution to graph algorithms in this setting: 1) limited-sharing: the two entities can share only a poly logarithmic size subgraph, 2) low-trust: the entities must not reveal any information beyond the query answer, assuming they are all honest but curious. We believe this model captures realistic constraints on cooperating autonomous data centres' have results for both models for s-t connectivity, one of the simplest graph problems that requires global information in the worst case. In the limited-sharing model, our results exploit social network structure. Standard communication complexity gives polynomial lower bounds on s-t connectivity for general graphs. However, if the graph for each data centre has a giant component and these giant components intersect, then we can overcome this lower bound, computing-t connectivity while exchanging O(log ^2 n) bits for a constant number of data centers. We can also test the assumption that the giant components overlap using O(log ^2 n) bits provided the (unknown) overlap is sufficiently large. The second result is in the low trust model. We give a secure multi-party computation (MPC) algorithm that 1) does not make cryptographic assumptions when there are 3 or more entities, and 2) is efficient, especially when compared to the usual garbled circuit approach. The entities learn only the yes/no answer. No party learns anything about the others' graph, not even node names. This algorithm does not require any special graph structure. This secure MPC result for s-t connectivity is one of the first that involves a few parties computing on large inputs, instead of many parties computing on a few local values. Jonathan W. Berry, Michael J. Collins 0003, Aaron Kearns, Cynthia A. Phillips, Jared Saia, Randy Smith |
IPDPS | 4 |
| 2015 | Geometric Hitting Set for Segments of Few Orientations
Sándor P. Fekete, Kan Huang, Joseph S. B. Mitchell, Ojas Parekh, Cynthia A. Phillips |
WAOA | 5 |
| 2014 | Maximizing the value of sensed information in underwater wireless sensor networks via an autonomous underwater vehicleabstractThis paper considers underwater wireless sensor networks (UWSNs) for submarine surveillance and monitoring. Nodes produce data with an associated value, decaying in time. An autonomous underwater vehicle (AUV) is sent to retrieve information from the nodes, through optical communication, and periodically emerges to deliver the collected data to a sink, located on the surface or onshore. Our objective is to determine a collection path for the AUV so that the Value of Information (VoI) of the data delivered to the sink is maximized. To this purpose, we first define an Integer Linear Programming (ILP) model for path planning that considers realistic data communication rates, distances, and surfacing constraints. We then define the first heuristic for path finding that is adaptive to the occurrence of new events, relying only on acoustic communication for exchanging short control messages. Our Greedy and Adaptive AUV Path-finding (GAAP) heuristic drives the AUV to collect packets from nodes to maximize the VoI of the delivered data. We compare the VoI of data obtained by running the optimum solution derived by the ILP model to that obtained from running GAAP over UWSNs with realistic and desirable size. In our experiments GAAP consistently delivers more than 80% of the theoretical maximum VoI determined by the ILP model. Stefano Basagni, Ladislau Bölöni, Petrika Gjanci, Chiara Petrioli, Cynthia A. Phillips, Danila Turgut |
INFOCOM | 5 |
| 2014 | Why do simple algorithms for triangle enumeration work in the real world?abstractTriangle enumeration is a fundamental graph operation. Despite the lack of provably efficient (linear, or slightly super-linear) worst-case algorithms for this problem, practitioners run simple, efficient heuristics to find all triangles in graphs with millions of vertices. How are these heuristics exploiting the structure of these special graphs to provide major speedups in running time? Jonathan W. Berry, Luke Fostvedt, Daniel J. Nordman, Cynthia A. Phillips, Seshadhri Comandur, Alyson G. Wilson |
ITCS | 4 |
| 2014 | Sensor Mission Assignment in Rechargeable Wireless Sensor NetworksabstractSensor mission assignment involves matching the sensing resources of a wireless sensor network (WSN) to appropriate tasks (missions), which may come to the network dynamically. Although solutions for WSNs with battery-operated nodes have been proposed for this problem, no attention has been given to networks whose nodes have energy-harvesting capabilities and are powered in part by uncontrollable environmental sources, which impose quite a different energy model. In this article we address this problem by providing both an analytical model and a distributed heuristic, called EN-MASSE, specifically tailored for energy-harvesting mission-centric WSNs. To assess the performance of our proposed solution we have interfaced TelosB nodes with solar cells and performed extensive experiments to derive models and traces of solar energy acquisition. We use such real-life traces in our simulations. A comparative performance evaluation between EN-MASSE and other schemes previously proposed in the literature has shown that our solution significantly outperforms existing energy-harvesting-unaware mission assignment schemes. Moreover, using our analytical model as a benchmark, we also show that the profit earned by EN-MASSE is close to the optimum. Finally, we have implemented our proposed solution in TinyOS and experimentally validated its performance, showing the effectiveness of our approach. Thomas La Porta, Chiara Petrioli, Cynthia A. Phillips, Dora Spenza |
ACM Trans. Sens. Networks | 3 |
| 2013 | Efficient scheduling to minimize calibrationsabstractIntegrated Stockpile Evaluation (ISE) is a program to test nuclear weapons periodically. Tests are performed by machines that may require occasional calibration. These calibrations are expensive, so finding a schedule that minimizes calibrations allows more testing to be done for a given amount of money. Michael A. Bender, David P. Bunde, Vitus J. Leung, Samuel McCauley, Cynthia A. Phillips |
SPAA | 5 |
| 2013 | Best papers, IPDPS 2010
Cynthia A. Phillips |
J. Parallel Distributed Comput. | 1 |
| 2011 | Sleeping on the Job: Energy-Efficient and Robust Broadcast for Radio Networks
Valerie King, Cynthia A. Phillips, Jared Saia, Maxwell Young |
Algorithmica | 2 |
| 2011 | Coordinated and controlled mobility of multiple sinks for maximizing the lifetime of wireless sensor networks
Stefano Basagni, Alessio Carosi, Chiara Petrioli, Cynthia A. Phillips |
Wirel. Networks | 4 |
| 2010 | Message from the program chairabstractWelcome to the 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2010). The technical program for the “main meeting” has 123 paper presentations in 32 sessions, one session with 4 best papers, 3 keynote addresses, 1 panel discussion, 2 evening tutorials, and two poster sessions for the PhD Forum. There is also our traditional IPDPS banquet on Wednesday evening. The “main” conference is surrounded by related workshops: 10 workshops on the day before, and 8 workshops on the day after. Cynthia A. Phillips |
IPDPS | 1 |
| 2009 | Brief announcement: the impact of classical electronics constraints on a solid-state logical qubit memoryabstractWe present and analyze an architecture for a logical qubit memory that is tolerant of faults in the processing of silicon double quantum dot (DQD) qubits. A highlight of our analysis is an in-depth consideration of the constraints faced when integrating DQDs with classical control electronics. James E. Levy, Anand Ganti, Cynthia A. Phillips, Benjamin R. Hamlet, Andrew J. Landahl, Thomas M. Gurrieri, Robert D. Carr, Malcolm S. Carroll |
SPAA | 3 |
| 2008 | Moving multiple sinks through wireless sensor networks for lifetime maximizationabstractWe propose scalable models and centralized heuristics for the concurrent and coordinated movement of multiple sinks in a wireless sensor network (WSN). The proposed centralized heuristic runs in polynomial time given the solution to the linear program and achieves results that are within 2% of the LP-relaxation-based upper bound. It provides a useful benchmark for evaluating centralized and distributed schemes for controlled sink mobility. Stefano Basagni, Alessio Carosi, Chiara Petrioli, Cynthia A. Phillips |
MASS | 4 |
| 2008 | Sleeping on the job: energy-efficient and robust broadcast for radio networksabstractWe address the problem of minimizing power consumption when broadcasting a message from one node to all the other nodes in a radio network. To enable power savings for such a problem, we introduce a compelling new data streaming problem that we call the Bad Santa problem. Our results on this problem apply for any situation where: 1) a node can listen to a set of n nodes, out of which at least half are non-faulty and know the correct message; and 2) each of these n nodes sends according to some predetermined schedule which assigns each of them its own unique time slot. In this situation, we show that in order to receive the correct message with probability 1, it is necessary and sufficient for the listening node to listen to a Θ(√n) expected number of time slots. Moreover, if we allow for repetitions of transmissions so that each sending node sends the message O(log* n) times (i.e. in O(log* n) rounds each consisting of the n time slots), then listening to O(log* n) expected number of time slots suffices. We show that this is near optimal. Valerie King, Cynthia A. Phillips, Jared Saia, Maxwell Young |
PODC | 2 |
| 2008 | Communication-Aware Processor Allocation for Supercomputers: Finding Point Sets of Small Average Distance
Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, Cynthia A. Phillips |
Algorithmica | 7 |
| 2007 | Scheduling DAGs on asynchronous processorsabstractThis paper addresses the problem of scheduling a DAG of unit-length tasks on asynchronous processors, that is, processors having different and changing speeds. The objective is to minimize the makespan, that is, the time to execute the entire DAG. Asynchrony is modeled by an oblivious adversary, which is assumed to determine the processor speeds at each point in time. The oblivious adversary may change processor speeds arbitrarily and arbitrarily often, but makes speed decisions independently of any random choices of the scheduling algorithm. Michael A. Bender, Cynthia A. Phillips |
SPAA | 2 |
| 2007 | Editors Foreword to the Special Issue on Principles of Mobile Communications and Computing
Stefano Basagni, Cynthia A. Phillips |
Algorithmica | 2 |
| 2005 | Communication-Aware Processor Allocation for Supercomputers
Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, Cynthia A. Phillips |
WADS | 7 |
| 2004 | Scheduling an Industrial Production Facility
Eyjólfur Ingi Ásgeirsson, Jonathan W. Berry, Cynthia A. Phillips, David J. Phillips, Clifford Stein 0001, Joel Wein |
IPCO | 3 |
| 2002 | Processor Allocation on Cplant: Achieving General Processor Locality Using One-Dimensional Allocation StrategiesabstractThe Computational Plant or Cplant is a commodity-based supercomputer under development at Sandia National Laboratories. This paper describes resource-allocation strategies to achieve processor locality for parallel jobs in Cplant and other supercomputers. Users of Cplant and other Sandia supercomputers submit parallel jobs to a job queue. When a job is scheduled to run, it is assigned to a set of processors. To obtain maximum throughput, jobs should be allocated to localized clusters of processors to minimize communication costs and to avoid bandwidth contention caused by overlapping jobs. This paper introduces new allocation strategies and performance metrics based on space-filling curves and one dimensional allocation strategies. These algorithms are general and simple. Preliminary simulations and Cplant experiments indicate that both space-filling curves and one-dimensional packing improve processor locality compared to the sorted free list strategy previously used on Cplant. These new allocation strategies are implemented in the new release of the Cplant System Software, Version 2.0, phased into the Cplant systems at Sandia by May 2002. Vitus J. Leung, Esther M. Arkin, Michael A. Bender, David P. Bunde, Jeanette Johnston, Alok Lal, Joseph S. B. Mitchell, Cynthia A. Phillips, Steven S. Seiden |
CLUSTER | 8 |
| 2002 | Optimal Time-Critical Scheduling via Resource Augmentation
Cynthia A. Phillips, Clifford Stein 0001, Eric Torng, Joel Wein |
Algorithmica | 1 |
| 2000 | Strengthening integrality gaps for capacitated network design and covering problems
Robert D. Carr, Lisa Fleischer, Vitus J. Leung, Cynthia A. Phillips |
SODA | 4 |
| 2000 | Off-line admission control for general scheduling problems
Cynthia A. Phillips, R. N. Uma, Joel Wein |
SODA | 1 |
| 1999 | Approximation Algorithms for the Fixed-Topology Phylogenetic Number Problem
Mary Cryan, Leslie Ann Goldberg, Cynthia A. Phillips |
Algorithmica | 3 |
| 1999 | Constructing Evolutionary Trees in the Presence of Polymorphic CharactersabstractMost phylogenetics literature and construction methods based uponcharacters presume monomorphism (one state per character per species), yet polymorphism (multiple states per character per species) is well documented in both biology and historical linguistics. In this paper we consider the problem of inferring evolutionary trees for polymorphic characters. We show efficient algorithms for the construction of perfect phylogenies from polymorphic data. These methods have been used to help construct the evolutionary tree proposed by Warnow, Ringe, and Taylor for the Indo-European family of languages and presented by invitation at the National Academy of Sciences in November 1995. Maria Luisa Bonet, Cynthia A. Phillips, Tandy J. Warnow, Shibu Yooseph |
SIAM J. Comput. | 2 |
| 1998 | A cause and effect model of attacks on information systems : Some Analysis Based on That Model, and The Application of that Model for CyberWarfare in CID
Fred Cohen, Cynthia A. Phillips, Laura Painton Swiler, Timothy Gaylor, Patricia Leary, Fran Rupley, Richard Isler |
Comput. Secur. | 2 |
| 1997 | Approximation Algorithms for the Fixed-Topology Phylogenetic Number Problem
Mary Cryan, Leslie Ann Goldberg, Cynthia A. Phillips |
CPM | 3 |
| 1997 | Beyond islands (extended abstract): runs in clone-probe matricesabstractPhysical mapping is a fundamental component of the human genome project.A physical map consists of a set of probes which mark unique positions on a long fragment of DNA, together with the relative order of the probes on the DNA.This order is inferred from clone-probe hybridization experiments, which determine the probes contained within various fragments of the genome.In practice, the order of the probes is not completely determined by the hybridization experiments.To better design these experiments, researchers have analyzed the expected distribution of "islands" -groups of probes which are known to be near one another-that would result from hybridization experiments with different numbers of clones and probes.In this paper we analyze the distribution of "runs" -groups of probes whose relative order is completely determined by the hybridization experiment.We include analytic, numerical, Monte Carlo, and simulation results on runs, which can further assist in the design of these experiments. David Bruce Wilson, David S. Greenberg, Cynthia A. Phillips |
RECOMB | 3 |
| 1997 | Optimal Time-Critical Scheduling via Resource Augmentation (Extended Abstract)abstract) Cynthia A. Phillips Cliff Stein y Eric Torng z Joel Wein x Abstract We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of scheduling environments. When viewed from the perspective of traditional worst-case analysis, no good on-line algorithms exist for these problems, and for some variants no good off-line algorithms exist unless P = NP. We study these problems using a relaxed notion of competitive analysis, introduced by Kalyanasundaram and Pruhs, in which the on-line algorithm is allowed more resources than the optimal off-line algorithm to which it is compared. Using this approach, we establish that several well-known on-line algorithms, that have poor performance from an absolute worst-case perspective, are optimal for the problems in question when allowed moderately more resources. For the optimization of average flow time, these are th... Cynthia A. Phillips, Clifford Stein 0001, Eric Torng, Joel Wein |
STOC | 1 |
| 1997 | Task Scheduling in NetworksabstractScheduling a set of tasks on a set of machines so as to yield an efficient schedule is a basic problem in computer science and operations research. Most of the research on this problem incorporates the potentially unrealistic assumption that communication between the different machines is instantaneous. In this paper we remove this assumption and study the problem of network scheduling, where each job originates at some node of a network, and in order to be processed at another node must take the time to travel through the network to that node. Our main contribution is to give approximation algorithms and hardness proofs for fully general forms of the fundamental problems in network scheduling. We consider two basic scheduling objectives: minimizing the makespan and minimizing the average completion time. For the makespan, we prove small constant factor hardness-to-approximate and approximation results. For the average completion time, we give a log-squared approximation algorithm for the most general form of the problem. The techniques used in this approximation are fairly general and have several other applications. For example, we give the first nontrivial approximation algorithm to minimize the average weighted completion time of a set of jobs on related or unrelated machines, with or without a network. Cynthia A. Phillips, Clifford Stein 0001, Joel Wein |
SIAM J. Discret. Math. | 1 |
| 1996 | Constructing Computer Virus Phylogenies
Leslie Ann Goldberg, Paul W. Goldberg, Cynthia A. Phillips, Gregory B. Sorkin |
CPM | 3 |
| 1996 | The Asymmetric Median Tree - A New model for Building Consensus Trees
Cynthia A. Phillips, Tandy J. Warnow |
CPM | 1 |
| 1996 | Improved Scheduling Algorithms for Minsum Criteria
Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Clifford Stein 0001, Joel Wein |
ICALP | 2 |
| 1996 | Constructing Evolutionary Trees in the Presence of Polymorphic CharactersabstractMost phylogenetics literature and construction methods Maria Luisa Bonet, Cynthia A. Phillips, Tandy J. Warnow, Shibu Yooseph |
STOC | 2 |
| 1996 | Minimizing Phylogenetic Number To Find Good Evolutionary TreesabstractInferring phylogenetic trees is a fundamental problem in computational biology. We present a new objective criterion, the phylogenetic number, for evaluating evolutionary trees for species defined by biomolecular sequences or other qualitative characters. The phylogenetic number of a tree T is the maximum number of times that any given character state arises in T. By contrast, the classical parsimony criterion measures the total number of times that different character states arise in T. We consider the following related problems: finding the tree with minimum phylogenetic number, and computing the phylogenetic number of a given topology in which only the leaves are labeled by species. When the number of states is bounded (as is the case for biomolecular sequence characters), we can solve the second problem in polynomial time. Given the topology for an evolutionary tree, we can also compute a phylogeny with phylogenetic number 2 (when one exists) for an arbitrary number of states. This algorithm can be used to further distinguish trees that are equal under parsimony. We also consider a number of other related problems. Leslie Ann Goldberg, Paul W. Goldberg, Cynthia A. Phillips, Elizabeth Sweedyk, Tandy J. Warnow |
Discret. Appl. Math. | 3 |
| 1996 | The Asymmetric Median Tree - A New Model for Building Consensus TreesabstractInferring the consensus of a set of different evolutionary trees for a given species set is a well-studied problem, for which several different models have been proposed. In this paper, we propose a new optimization problem for consensus tree construction, which we call the asymmetric median tree, (AMT). Our main theoretical result is the equivalence between the asymmetric median tree problem on k trees and the maximum independent set (MIS) problem on k-colored graphs. Although the problem is NP-hard for three or more trees, we have polynomial-time algorithms to construct the AMT for two trees and an approximation algorithm for three or more trees. We define a measure of phylogenetic resolution and show that our algorithms (both exact and approximate) produce consensus trees that on every input are at least as resolved as the standard models in use (strict consensus, majority tree, Nelson tree). Finally, we show that the AMT combines desirable features of many of the standard consensus tree models in use. Cynthia A. Phillips, Tandy J. Warnow |
Discret. Appl. Math. | 1 |
| 1995 | Minimizing Phylogenetic Number to find Good Evolutionary Trees
Leslie Ann Goldberg, Paul W. Goldberg, Cynthia A. Phillips, Elizabeth Sweedyk, Tandy J. Warnow |
CPM | 3 |
| 1995 | Scheduling Jobs that Arrive Over Time (Extended Abstract)
Cynthia A. Phillips, Clifford Stein 0001, Joel Wein |
WADS | 1 |
| 1993 | Finding minimum-quotient cuts in planar graphsabstractArticle Free Access Share on Finding minimum-quotient cuts in planar graphs Authors: James K. Park View Profile , Cynthia A. Phillips View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 766–775https://doi.org/10.1145/167088.167284Online:01 June 1993Publication History 24citation746DownloadsMetricsTotal Citations24Total Downloads746Last 12 Months20Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF James K. Park, Cynthia A. Phillips |
STOC | 2 |
| 1993 | The network inhibition problemabstractArticle The network inhibition problem Share on Author: Cynthia A. Phillips View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 776–785https://doi.org/10.1145/167088.167286Online:01 June 1993Publication History 129citation1,560DownloadsMetricsTotal Citations129Total Downloads1,560Last 12 Months57Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access Cynthia A. Phillips |
STOC | 1 |