Phillip B. Gibbons

Space Profiling for Parallel Functional Programs (2009)

Estimating the number of distinct values is a wellstudied problem, due to its frequent occurrence in queries and its importance in selecting good query plans. Previous work has shown powerful...

Daniel Spoonhower, Guy E. Blelloch, Robert Harper, Phillip B. Gibbons

This paper presents a semantic space profiler for parallel functional programs. Building on previous work in sequential profiling, our tools help programmers to relate runtime resource use back to...

Space Profiling for Parallel Functional Programs (2009)

Daniel Spoonhower, Guy E. Blelloch, Robert Harper, Phillip B. Gibbons

This paper presents a semantic space profiler for parallel functional programs. Building on previous work in sequential profiling, our tools help programmers to relate runtime resource use back to...

Defragmenting DHT-based Distributed File Systems (2009)

Jeffrey Pang, Phillip B. Gibbons, Michael Kaminsky, Srinivasan Seshan, Haifeng Yu

Existing DHT-based file systems use consistent hashing to assign file blocks to random machines. As a result, a user task accessing an entire file or multiple files needs to retrieve blocks from many...

Parallelizing Dynamic Information Flow Tracking (2009)

Olatunji Ruwase, Phillip B. Gibbons, Todd C. Mowry, Vijaya Ramach, Shimin Chen, Michael Kozuch, ...

Dynamic information flow tracking (DIFT) is an important tool for detecting common security attacks and memory bugs. A DIFT tool tracks the flow of information through a monitored program’s...

Abstract Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors (2009)

Guy E. Blelloch, Phillip B. Gibbons, Yossi Matias, Marco Zagha

This paper considers issues of memory performance in shared memory multiprocessors that provide a high-bandwidth net-work and in which the memory banks are slower than the processors. We are...

LOCI: Fast Outlier Detection Using The Local Correlation Integral, (2009)

Outlier Detection, C. Faloutsos, Spiros Papadimitriou, Hiroyuki Kitagawa, Phillip B. Gibbons, Christos Faloutsos, ...

What is an outlier? Why outlier detection?

Abstract Space-E cient Scheduling of Parallelism with Synchronization Variables (2008)

Guy E. Blelloch, Phillip B. Gibbons

Recent work on scheduling algorithms has resulted in provable bounds on the space taken by parallel computations in relation to the space taken by sequential computations. The results for online...

Synopsis Data Structures for Massive Data Sets (2008)

Abstract New Sampling-Based Summary Statistics for Improving Approximate Query Answers (2008)

Abstract. Massive data sets with terabytes of data are becoming commonplace. There is an increasing demand for algorithms and data structures that provide fast response times to queries on such data...

IrisNet: An Architecture for Internet-Scale Sensing (2008)

In large data recording and warehousing environments, it is of-ten advantageous to provide fast, approximate answers to queries, whenever possible. Before DBMSs providing highly-accurate ap-proximate...

Phillip B. Gibbons, Brad Karp, Yan Ke, Suman Nath, Srinivasan Seshan

The time has come to consider wide-area architectures for pervasive sensing. Today’s low-cost PCs are deployed globally, connected to the Internet, and routinely have diverse

Content Delivery Networks, Distributed Hash Tables, distributed (2008)

Suman Nath, Haifeng Yu, Phillip B. Gibbons, Srinivasan Seshan

Recently, there has been increasing interest in systems (e.g.,

Abstract Modeling and optimizing I/O throughput of multiple disks on a bus (2008)

Rakesh Barve, Elizabeth Shriver, Phillip B. Gibbons, Bruce K. Hillyer, Yossi Matias, Je Scott Vitter

In modern I/O architectures, multiple disk drives are attachedtoeach I/O controller. A study of the performance of such architectures under I/O-intensive workloads has revealed a performance...

Theory of Computing Systems (2008)

Data Management in the Worldwide Sensor Web (2008)

Abstract. Massive data sets often arise as physically distributed, parallel data streams, and it is important to estimate various aggregates and statistics on the union of these streams. This paper...

Magdalena Balazinska, Amol Deshpande, Michael J. Franklin, Phillip B. Gibbons, Jim Gray, Suman Nath, ...

Harvesting the benefits of a sensor-rich world presents many data management challenges. Recent advances in research and industry aim to address these challenges.

Rakesh Barve’ (2008)

Distinct-values estimation over data streams (2008)

rbarve&s.duke.edu Round-like behavior in multiple disks on a bus

SENSOR AND ACTUATOR NETWORKS IrisNet: An Architecture for a Worldwide Sensor Web (2008)

Abstract. In this chapter, we consider the problem of estimating the number of distinct values in a data stream with repeated values. Distinctvalues estimation was one of the first data stream...

Phillip B. Gibbons, Brad Karp, Yan Ke, Suman Nath, Srinivasan Seshan

Today’s common computing hardware—Internet connected desktop PCs and inexpensive, commodity off-the-shelf sensors such as Webcams—is an ideal platform for a worldwide sensor web. IrisNet...

Stored Procedures for Distributed XML Databases (2008)

Shimin Chen, Shimin Chen, Phillip B. Gibbons, Phillip B. Gibbons, Suman Nath, Suman Nath

OTHER INTELLECTUAL PROPERTY RIGHT. Intel products are not intended for use in

for Multimedia Sensors (2008)

Jason Campbell, Phillip B. Gibbons, Suman Nath, Padmanabhan Pillai, Srinivasan Seshan, Rahul Sukthankar, ...

OTHER INTELLECTUAL PROPERTY RIGHT. Intel products are not intended for use in

and (2008)

Abstract New Sampling-Based Summary Statistics for Improving Approximate Query Answers (2008)

Recent work has demonstrated the effectiveness of the wavelet decomposition in reducing large amounts of data to compact sets of wavelet coefficients (termed “wavelet synopses”) that can be used...

Abstract Tracking Join and Self-Join Sizes in Limited Storage (2008)

In large data recording and warehousing environments, it is often advantageous to provide fast, approximate answers to queries, whenever possible. Before DBMSs providing highly-accurate approximate...

Noga Alon, Phillip B. Gibbons

Query optimizers rely on fast, high-quality estimates of result sizes in order to select between various join plans. Selfjoin sizes of relations provide bounds on the join size of any pairs of such...

Abstract Tracking Join and Self-Join Sizes in Limited Storage (2008)

Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy

gibbonsOresearch.bell-labs.com Query optimizers rely on fast, high-quality estimates of re-sult sizes in order to select between various join plans. Self-join sizes of relations provide bounds on the...

Abstract Bifocal Sampling for Skew-Resistant Join Size Estimation (2008)

Sumit Ganguly, Phillip B. Gibbons

This paper introduces bifocal sampling, a new technique for estimating the size of an equi-join of two relations. Bifocal sampling classi es tuples in each relation into two groups, sparse and dense,...

Abstract (2008)

Phillip B. Gibbons, Yossi Matias, Vijaya Ramachandran

This paper presents results for the queue-read, queue-write asynchronous parallel random access machine (qrqw asynchronous pram) model, which is the asynchronous variant of the qrqw pram model. The...

Shared Memory Support for Unstructured Problems (2008)

One difficulty in designing parallel algorithms is the large number of different models and machines. Algorithms (programs) are redesigned for each new model (machine). We are developing a general...

Queries (2008)

Å�ÒÝ ÓÑÑ�Ö ��Ð ��Ø��× � ×Ý×Ø�Ñ × Ñ��ÒØ��Ò ��×ØÓ�Ö�Ñ × ØÓ ×ÙÑÑ�Ö�Þ � Ø� � ÓÒØ�ÒØ × Ó � Ð�Ö� � Ö� (2008)

In large data recording and warehousing environments, it is of-

Phillip B. Gibbons, Yossi Matias, Viswanath Poosala

� ÙÒ��ÓÖÑÐÝ Ö�Ò�ÓÑ ×�ÑÔÐ � Ó � � Ö�Ð�Ø�ÓÒ �Ò Ø� � ÔÖ�×�Ò � Ó � ÙÔ��Ø� × ØÓ Ø� � Ö�Ð�Ø�ÓÒ Ì� � �...

ABSTRACT IrisNet: An Internet-Scale Architecture for Multimedia Sensors (2008)

Jason Campbell, Phillip B. Gibbons, Suman Nath, Padmanabhan Pillai, Srinivasan Seshan, Rahul Sukthankar

Most current sensor network research explores the use of extremely simple sensors on small devices called motes and focuses on overcoming the resource constraints of these devices. In contrast, our...

The Connectivity and Fault-Tolerance of the Internet Topology (2008)

Christopher R. Palmer\lambda, Georgos Siganosy, Michalis Faloutsosz, Christos Faloutsosx, Phillip B. Gibbons

SENSOR AND ACTUATOR NETWORKS IrisNet: An Architecture for a Worldwide Sensor Web (2008)

Phillip B. Gibbons, Brad Karp, Yan Ke, Suman Nath, Srinivasan Seshan

Today’s common computing hardware—Internet connected desktop PCs and inexpensive, commodity off-the-shelf sensors such as Webcams—is an ideal platform for a worldwide sensor web. IrisNet...

Brief Announcement: Parallel Depth First vs. Work Stealing Schedulers on CMP Architectures (2008)

Vasileios Liaskovitis, Shimin Chen, Phillip B. Gibbons, Anastassia Ailamaki, Guy E. Blelloch, Babak Falsafi, ...

In chip multiprocessors (CMPs), limiting the number of off-chip cache misses is crucial for good performance. Many multithreaded programs provide opportunities for constructive cache sharing, in...

SybilLimit: A Near-Optimal Social Network Defense against Sybil Attacks (2008)

YU, Haifeng, GIBBONS, Phillip B., XIAO, Feng

Decentralized distributed systems such as peer-to-peer systems are particularly vulnerable to {\em sybil attacks}, where a malicious user pretends to have multiple identities (called {\em sybil...

Provably good multicore cache performance for divide-and-conquer algorithms (2008)

Guy E. Blelloch, Rezaul A. Chowdhury, Phillip B. Gibbons, Vijaya Ramachandran, Shimin Chen, Michael Kozuch

This paper presents a multicore-cache model that reflects the reality that multicore processors have both per-processor private (L1) caches and a large shared (L2) cache on chip. We consider a broad...

Flexible hardware acceleration for instruction-grain program monitoring (2008)

Chen, Shimin, Kozuch, Michael, Strigkos, Theodoros, Falsafi, Babak, Gibbons, Phillip B., Mowry, Todd C., ...

Instruction-grain program monitoring tools, which check and analyze executing programs at the granularity of individual instructions, are invaluable for quickly detecting bugs and security attacks...

Space Profiling for Parallel Functional Programs (2008)

Daniel Spoonhower, Guy E. Blelloch, Phillip B. Gibbons, Robert Harper

This paper presents a semantic space profiler for parallel functional programs. Building on previous work in sequential profiling, our tools help programmers to relate runtime resource use back to...

and Theoretical Computer Science Synopsis Data Structures for Massive Data Sets (2007)

Phillip B. Gibbons, Yossi Matias, Vijaya Ramachandran

Abstract. Massive data sets with terabytes of data are becoming commonplace. There is an increasing demand for algorithms and data structures that provide fast response times to queries on such data...

z (2007)

There has been a great deal of interest recently in the development of general-purpose bridging models for parallel computation. Models such as the bsp and logp have been proposed as more realistic...

Modeling Parallel Bandwidth: Local vs. Global Restrictions (2007)

Micah Adler, Phillip B. Gibbons, Yossi Matias, Vijaya Ramachandran

Recently there has been an increasing interest in models of parallel computation that account for the bandwidth limitations in communication networks. Some models (e.g., bsp, logp, and qsm) account...

crpalmercs. cmu. edu (2007)

Christopher R. Palmer, Phillip B. Gibbons, Christos Faloutsos

christoscs. cmu. edu Graphs are an increasingly important data source, with such important graphs as the Internet and the Web. Other familiar graphs include CAD circuits, phone records, gene...

y (2007)

Rakesh Barve, Elizabeth Shriver, Phillip B. Gibbons, Bruce K. Hillyer, Yossi Matias, Jeffrey Scott Vitter

Abstract For a wide variety of computational tasks, disk I/O continues to be a serious obstacle to high performance. The focus of the present paper is on systems that use multiple disks per SCSI bus....

Fast Approximation of the “Neighbourhood ” Function for Massive Graphs (2007)

Christopher R. Palmer, Phillip B. Gibbons, Christos Faloutsos

The neighbourhood function, N(h), is the number of pairs of nodes that are within dis-tance h. The neighbourhood function provides useful information for graphs such as the struc-ture of XML...

Abstract (2007)

Hiroyuki Kitawaga, Spiros Papadimitriou, Spiros Papadimitriou, Phillip B. Gibbons, Phillip B. Gibbons, Hiroyuki Kitagawa, ...

Outlier detection is an integral part of data mining and has attracted much attention recently [8, 15, 20]. In this paper, we propose a new method for evaluating outlier-ness, which we call the Local...

Theory of Computing Systems (2007)

Guy E. Blelloch, Perry Cheng, Phillip B. Gibbons

Abstract. This paper presents a scalable solution to the group mutual exclusion problem, with applications to linearizable stacks and queues, and related problems. Our solution allows entry and exit...

Scheduling threads for constructive cache sharing on CMPs (2007)

Chen, Shimin, Gibbons, Phillip B., Kozuch, Michael, Liaskovitis, Vasileios, Ailamaki, Anastassia, Blelloch, Guy E., ...

Invalidation Clues for Database Scalability Services (2007)

Manjhi, Amit, Gibbons, Phillip B., Ailamaki, Anastassia, Garrod, Charles, Maggs, Bruce M., Mowry, Todd C., ...

Thesis Proposal: Scheduling Parallel Functional Programs (2007)

Daniel Spoonhower, Committee Guy, E. Blelloch, Phillip B. Gibbons

Parallelism abounds! To continue to improve performance, programmers must use parallel algorithms to take advantage of multi-core and other parallel architectures. Existing declarative languages...

Scheduling threads for constructive cache sharing on CMPs (2007)

Shimin Chen, Phillip B. Gibbons, Michael Kozuch, Vasileios Liaskovitis, Anastassia Ailamaki, Guy E. Blelloch, ...

In chip multiprocessors (CMPs), limiting the number of offchip cache misses is crucial for good performance. Many multithreaded programs provide opportunities for constructive cache sharing, in which...

Defragmenting DHT-based Distributed File Systems (2007)

Jeffrey Pang, Phillip B. Gibbons, Michael Kaminsky, Srinivasan Seshan, Haifeng Yu

Existing DHT-based file systems use consistent hashing to assign file blocks to random machines. As a result, a user task accessing an entire file or multiple files needs to retrieve blocks from many...

Just-In-Time Indexing for Interactive Data Exploration (2007)

Phillip B. Gibbons, Lily Mummert, Rahul Sukthankar, M. Satyanarayanan, Larry Huston

Interactive search of complex data poses significant challenges for traditional indexing methods because of the infeasibility of determining an effective set of indices a priori. This paper proposes...

Scheduling threads for constructive cache sharing on CMPs (2007)

Chen, Shimin, Gibbons, Phillip B., Kozuch, Michael, Liaskovitis, Vasileios, Ailamaki, Anastassia, Blelloch, Guy E., ...

In chip multiprocessors (CMPs), limiting the number of offchip cache misses is crucial for good performance. Many multithreaded programs provide opportunities for constructive cache sharing, in which...

Improving hash join performance through prefetching (2007)

Chen, Shimin, Ailamaki, Anastassia, Gibbons, Phillip B., Mowry, Todd C.

Scheduling threads for constructive cache sharing on CMPs (2007)

Shimin Chen, Phillip B. Gibbons, Michael Kozuch, Vasileios Liaskovitis, Anastassia Ailamaki, Guy E. Blelloch, ...

In chip multiprocessors (CMPs), limiting the number of offchip cache misses is crucial for good performance. Many multithreaded programs provide opportunities for constructive cache sharing, in which...

Log-based architectures for general-purpose monitoring of deployed code (2006)

Chen, Shimin, Falsafi, Babak, Gibbons, Phillip B., Kozuch, Michael, Mowry, Todd C., Teodorescu, Radu, ...

Runtime monitoring tools are invaluable for detecting various types of bugs, in both sequential and multi-threaded programs. However, these tools often slow down the monitored program by an order of...

Parallel depth first vs. work stealing schedulers on CMP architectures (2006)

Liaskovitis, Vasileios, Chen, Shimin, Gibbons, Phillip B., Ailamaki, Anastassia, Blelloch, Guy E., Falsafi, Babak, ...

In chip multiprocessors (CMPs), limiting the number of off-chip cache misses is crucial for good performance. Many multithreaded programs provide opportunities for constructive cache sharing, in...

Subtleties in tolerating correlated failures in wide-area storage systems (2006)

Suman Nath, Haifeng Yu, Phillip B. Gibbons

High availability is widely accepted as an explicit requirement for distributed storage systems. Tolerating correlated failures is a key issue in achieving high availability in today’s wide-area...

Invalidation clues for database scalability services (2006)

Amit Manjhi, Phillip B. Gibbons, Anastassia Ailamaki, Charles Garrod, Bruce M. Maggs, Todd C. Mowry, ...

For their scalability needs, data-intensive Web applications can use a Database Scalability Service (DBSS), which caches applications ’ query results and answers queries on their behalf. One way...

Subtleties in tolerating correlated failures in wide-area storage systems (2006)

Suman Nath, Haifeng Yu, Phillip B. Gibbons

High availability is widely accepted as an explicit requirement for distributed storage systems. Tolerating correlated failures is a key issue in achieving high availability in today’s wide-area...

Invalidation clues for database scalability services (2006)

Amit Manjhi, Phillip B. Gibbons, Anastassia Ailamaki, Charles Garrod, Bruce M. Maggs, Todd C. Mowry, ...

For their scalability needs, data-intensive Web applications can use a Database Scalability Service (DBSS), which caches applications ’ query results and answers queries on their behalf. One way...

Subtleties in tolerating correlated failures in wide-area storage systems (2006)

Suman Nath, Haifeng Yu, Phillip B. Gibbons

High availability is widely accepted as an explicit requirement for distributed storage systems. Tolerating correlated failures is a key issue in achieving high availability in today’s wide-area...

Sybilguard: Defending against sybil attacks via social networks (2006)

Haifeng Yu, Michael Kaminsky, Phillip B. Gibbons, Abraham Flaxman

Peer-to-peer and other decentralized, distributed systems are known to be particularly vulnerable to sybil attacks. In a sybil attack, a malicious user obtains multiple fake identities and pretends...

Sybilguard: Defending against sybil attacks via social networks (2006)

Haifeng Yu, Michael Kaminsky, Phillip B. Gibbons, Abraham Flaxman

Peer-to-peer and other decentralized, distributed systems are known to be particularly vulnerable to sybil attacks. In a sybil attack, a malicious user obtains multiple fake identities and pretends...

the previous technical report. (2006)

Amit Manjhi, Phillip B. Gibbons, Anastassia Ailamaki, Charles Garrod, Bruce M. Maggs, Todd C. Mowry, ...

For their scalability needs, data-intensive Web applications can use a Database Scalability Service (DBSS), which caches applications ’ query results and answers queries on their behalf. One way...

Invalidation clues for database scalability services (2006)

Amit Manjhi, Phillip B. Gibbons, Anastassia Ailamaki, Charles Garrod, Bruce M. Maggs, Todd C. Mowry, ...

For their scalability needs, data-intensive Web applications can use a Database Scalability Service (DBSS), which caches applications ’ query results and answers queries on their behalf. To address...

Sybilguard: Defending against sybil attacks via social networks (2006)

Haifeng Yu, Michael Kaminsky, Phillip B. Gibbons, Abraham Flaxman

Peer-to-peer and other decentralized, distributed systems are known to be particularly vulnerable to sybil attacks. In a sybil attack, a malicious user obtains multiple fake identities and pretends...

Invalidation clues for database scalability services (2006)

Amit Manjhi, Phillip B. Gibbons, Anastassia Ailamaki, Charles Garrod, Bruce M. Maggs, Todd C. Mowry, ...

For their scalability needs, data-intensive Web applications can use a Database Scalability Service (DBSS), which caches applications ’ query results and answers queries on their behalf. To address...

Sybilguard: Defending against sybil attacks via social networks (2006)

Haifeng Yu, Michael Kaminsky, Phillip B. Gibbons, Abraham Flaxman

Peer-to-peer and other decentralized, distributed systems are known to be particularly vulnerable to sybil attacks. In a sybil attack, a malicious user obtains multiple fake identities and pretends...

Distance-Sensitive Information Brokerage in Sensor Networks (2006)

Funke, Stefan, Guibas, Leonidas, Nguyen, An, Wang, Yusu, Gibbons, Phillip B., Abdelzaher, Tarek F., ...

In a sensor network information from multiple nodes must usually be aggregated in order to accomplish a certain task. A natural way to view this information gathering is in terms of interactions...

SybilGuard: Defending against sybil attacks via social networks (2006)

Haifeng Yu, Michael Kaminsky, Phillip B. Gibbons, Abraham Flaxman

Peer-to-peer and other decentralized, distributed systems are known to be particularly vulnerable to sybil attacks. In a sybil attack, a malicious user obtains multiple fake identities and pretends...

Inspector Joins (2005)

Chen, Shimin, Ailamaki, Anastassia, Gibbons, Phillip B., Mowry, Todd C.

Database-centric programming for wide-area sensor systems (2005)

Shimin Chen, Phillip B. Gibbons, Suman Nath

Abstract. A wide-area sensor system is a complex, dynamic, resource-rich collection of Internet-connected sensing devices. In this paper, we propose X-Tree Programming, a novel database-centric...

Database-centric programming for wide-area sensor systems (2005)

Phillp B. Gibbons, Shimin Chen, Shimin Chen, Phillip B. Gibbons, Suman Nath, Suman Nath

OTHER INTELLECTUAL PROPERTY RIGHT. Intel products are not intended for use in

New Streaming Algorithms for Fast Detection of Superspreaders (2005)

Shobha Venkataraman, Dawn Song, Phillip B. Gibbons, Avrim Blum

High-speed monitoring of Internet traffic is an important and challenging problem, with applications to realtime attack detection and mitigation, traffic engineering, etc. However, packet-level...

Inspector Joins (2005)

Shimin Chen Anastassia, Shimin Chen, Anastassia Ailamaki, Phillip B. Gibbons, Todd C. Mowry

The key idea behind Inspector Joins is that during the I/O partitioning phase of a hash-based join, we have the opportunity to look at the actual data itself and then use this knowledge in two ways:...

Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams (2005)

Amit Manjhi, Suman Nath, Phillip B. Gibbons

in sensor networks can be classified into two categories, tree-based and multi-path-based, with each having unique strengths and weaknesses. In this paper, we introduce Tributary -Delta, a novel...

Fast estimation of fractal dimension and correlation integral on stream data (2005)

Angeline Wong, Leejay Wu, Phillip B. Gibbons

Given a cloud of N points in an E-dimensional space, we often need to estimate the intrinsic dimensionality D of this cloud. For example, a set of points in 3-dimensional space all following along a...

Redesigning Database Systems in Light of CPU Cache Prefetching (2005)

Shimin Chen, Todd C. Mowry, Christos Faloutsos, Phillip B. Gibbons

through a generous fellowship. The views and conclusions contained in this document are those of the author and should not be interpreted as representing the official policies, either expressed or...

Exploiting Redundancy for Robust Sensing (2005)

Suman Nath, Phillip B. Gibbons, M. Satyanarayanan

views and conclusions contained in this document are those of the author and should not be interpreted as representing the official policies, either expressed or implied, of any sponsoring...

Inspector joins (2005)

Shimin Chen, Anastassia Ailamaki, Phillip B. Gibbons, Todd C. Mowry

The key idea behind Inspector Joins is that during the I/O partitioning phase of a hash-based join, we have the opportunity to look at the actual data itself and then use this knowledge in two ways:...

Adaptive Data Placement for Wide-Area Sensing Services (2005)

Suman Nath, Phillip B. Gibbons

Wide-area sensing services enable users to query data collected from multitudes of widely distributed sensors. In this paper, we consider the novel distributed database workload characteristics of...

New Streaming Algorithms for Fast Detection of Superspreaders (2005)

Shobha Venkataraman, Dawn Song, Phillip B. Gibbons, Avrim Blum

High-speed monitoring of Internet traffic is an important and challenging problem, with applications to realtime attack detection and mitigation, traffic engineering, etc. However, packet-level...

Database-centric programming for wide-area sensor systems (2005)

Shimin Chen, Phillip B. Gibbons, Suman Nath

A wide-area sensor system is a complex, dynamic, resource-rich cloud of Internet-connected sensing devices. In this paper, we propose X-Tree Programming, a novel database-centric programming model...

Database-centric programming for wide-area sensor systems (2005)

Shimin Chen, Phillip B. Gibbons, Suman Nath

Abstract. A wide-area sensor system is a complex, dynamic, resource-rich collection of Internet-connected sensing devices. In this paper, we propose X-Tree Programming, a novel database-centric...

Improving Hash Join Performance through Prefetching (2004)

Chen, Shimin, Ailamaki, Anastassia, Gibbons, Phillip B., Mowry, Todd C.

Beyond Availability: Towards a Deeper Understanding of Machine Failure Characteristics in Large Distributed Systems (2004)

Praveen Yalag, Suman Nath, Haifeng Yu, Phillip B. Gibbons, Srinivasan Seshan

Although many previous research efforts have investigated machine failure characteristics in distributed systems, availability research has reached a point where properties beyond these initial...

Effectively sharing a cache among threads (2004)

Guy E. Belloch, Phillip B. Gibbons, Guy E. Blelloch

OTHER INTELLECTUAL PROPERTY RIGHT. Intel products are not intended for use in

Improving Hash Join Performance through (2004)

Shimin Chen, Anastassia Ailamaki, Phillip B. Gibbons, Todd C. Mowry

This is a preliminary release of an article accepted by ACM Transactions on Database Systems. The definitive version is currently in production at ACM and, when released, will supersede this version.

A distributed filtering architecture for multimedia sensors (2004)

Suman Nath, Yan Ke, Phillip B. Gibbons, Brad Karp, Srinivasan Seshan

The use of high bit-rate multimedia sensors in networked applications poses a number of scalability challenges. In this paper, we present how IRISNET, a software infrastructure for authoring...

New Streaming Algorithms for Fast Detection (2004)

Shobha Venkataraman, Dawn Song, Phillip B. Gibbons, Avrim Blum, Of Superspreaders, Shobha Venkataraman, ...

OTHER INTELLECTUAL PROPERTY RIGHT. Intel products are not intended for use in

Synopsis diffusion for robust aggregation in sensor networks (2004)

Haifeng Yu, Phillip B. Gibbons, Srinivasan Seshan, Suman Nath, Suman Nath

OTHER INTELLECTUAL PROPERTY RIGHT. Intel products are not intended for use in

Beyond Availability: Towards a Deeper Understanding of Machine Failure Characteristics in Large Distributed Systems (2004)

Praveen Yalag, Suman Nath, Haifeng Yu, Phillip B. Gibbons, Srinivasan Seshan

Although many previous research efforts have investigated machine failure characteristics in distributed systems, availability research has reached a point where properties beyond these initial...

A distributed filtering architecture for multimedia sensors (2004)

Suman Nath, Yan Ke, Phillip B. Gibbons, Brad Karp, Srinivasan Seshan, Suman Nath, ...

OTHER INTELLECTUAL PROPERTY RIGHT. Intel products are not intended for use in

Beyond Availability: Towards a Deeper Understanding of Machine Failure Characteristics in Large Distributed Systems (2004)

Praveen Yalag, Suman Nath, Haifeng Yu, Phillip B. Gibbons, Srinivasan Seshan

Although many previous research efforts have investigated machine failure characteristics in distributed systems, availability research has reached a point where properties beyond these initial...

Beyond Availability: Towards a Deeper Understanding of Machine Failure Characteristics in Large Distributed Systems (2004)

Praveen Yalag, Suman Nath, Haifeng Yu, Phillip B. Gibbons, Srinivasan Seshan

Although many previous research efforts have investigated machine failure characteristics in distributed systems, availability research has reached a point where properties beyond these initial...

Synopsis diffusion for robust aggregation in sensor networks (2004)

Suman Nath, Suman Nath, Phillip B. Gibbons, Phillip B. Gibbons

Aggregating sensor readings within the network is an essential technique for conserving energy in sensor networks. Previous work proposes aggregating along a tree overlay topology in order to...

Synopsis Diffusion for Robust Aggregation in Sensor Networks (2004)

Suman Nath, Phillip B. Gibbons, Srinivasan Seshan, Zachary R. Anderson

Beyond Availability: Towards a Deeper Understanding of (2004)

Machine Failure Characteristics, Praveen Yalag, Suman Nath, Haifeng Yu, Phillip B. Gibbons, Srinivasan Seshan

Although many previous research efforts have investigated machine failure characteristics in distributed systems, availability research has reached a point where properties beyond these initial...

Beyond Availability: Towards a Deeper Understanding of Machine Failure Characteristics in Large Distributed Systems (2004)

Phillip B, Praveen Yalag, Praveen Yalag, Suman Nath, Suman Nath, Haifeng Yu, ...

OTHER INTELLECTUAL PROPERTY RIGHT. Intel products are not intended for use in

Improving Hash Join Performance through Prefetching (2004)

Shimin Chen, Anastassia Ailamaki, Phillip B. Gibbons, Todd C. Mowry

Hash join algorithms suffer from extensive CPU cache stalls. This paper shows that the standard hash join algorithm for disk-oriented databases (i.e. GRACE) spends over 73 % of its user time stalled...

Improving Hash Join Performance through Prefetching (2004)

Shimin Chen, Anastassia Ailamaki, Phillip B. Gibbons, Todd C. Mowry

Hash join algorithms suffer from extensive CPU cache stalls. This paper shows that the standard hash join algorithm for disk-oriented databases (i.e. GRACE) spends over 73 % of its user time stalled...

Improving Hash Join Performance through Prefetching (2004)

Shimin Chen, Anastassia Ailamaki, Phillip B. Gibbons, Todd C. Mowry

Hash join algorithms suffer from extensive CPU cache stalls. This paper shows that the standard hash join algorithm for disk-oriented databases (i.e. GRACE) spends over 73 % of its user time stalled...

New Streaming Algorithms for Fast Detection of (2004)

Shobha Venkataraman, Dawn Song, Phillip B. Gibbons, Avrim Blum

conclusions contained here are those of the authors and should not be interpreted as necessarily representing the

Effectively Sharing a Cache Among Threads (2004)

Guy Blelloch Carnegie, Guy E. Blelloch, Phillip B. Gibbons

We compare the number of cache misses M1 for running a computation on a single processor with cache size C1 to the total number of misses Mp for the same computation when using p processors or...

Synopsis diffusion for robust aggregation in sensor networks (2004)

Suman Nath, Phillip B. Gibbons, Zachary Anderson

Previous approaches for computing duplicate-sensitive aggregates in wireless sensor networks have used a tree topology, in order to conserve energy and to avoid double-counting sensor readings....

Tolerating Correlated Failures in Wide-Area Monitoring Services (2004)

Suman Nath, Suman Nath, Haifeng Yu, Haifeng Yu, Phillip B. Gibbons, Phillip B. Gibbons, ...

OTHER INTELLECTUAL PROPERTY RIGHT. Intel products are not intended for use in

A distributed filtering architecture for multimedia sensors. Intel Research Pittsburgh (2004)

Suman Nath, Yan Ke, Phillip B. Gibbons, Brad Karp, Srinivasan Seshan

The use of high bit-rate multimedia sensors in networked applications poses a number of scalability challenges. In this paper, we present how IRISNET, a software infrastructure for authoring...

IrisNet: An architecture for enabling sensor-enriched Internet service (2003)

Suman Nath, Yan Ke, Phillip B. Gibbons, Brad Karp, Srinivasan Seshan, Suman Nath, ...

The proliferation and affordability of webcams and other smart sensors have created opportunities for novel sensor-enriched Internet services, which combine traditional data sources with information...

Irisnet: An architecture for internet-scale sensing services. Demo and abstract (2003)

Suman Nath, Amol Deshp, Yan Ke, Phillip B. Gibbons, Brad Karp, Srinivasan Seshan

We demonstrate the design and an early prototype of IrisNet (Internet-scale Resource-Intensive Sensor Network services), a common, scalable networked infrastructure for deploying wide area sensing...

Improving Hash Join Performance through Prefetching (2003)

Shimin Chen Anastassia, Shimin Chen, Anastassia Ailamaki, Phillip B. Gibbons, Todd C. Mowry

Hash join algorithms suffer from extensive CPU cache stalls. This paper shows that the standard hash join algorithm for disk-oriented databases (i.e. GRACE) spends over 73% of its user time stalled...

Synopsis Diffusion for Robust Aggregation in Sensor Networks (2003)

Suman Nath, Phillip B. Gibbons, Srinivasan Seshan, Zachary R. Anderson

Previous approaches for computing duplicate-sensitive aggregates in sensor networks (e.g., in TAG) have used a tree topology, in order to conserve energy and to avoid double-counting sensor readings....

LOCI: Fast outlier detection using the local correlation integral (2003)

Spiros Papadimitriou, Hiroyuki Kitagawa, Christos Faloutsos, Phillip B. Gibbons

Outlier detection is an integral part of data mining and has attracted much attention recently [8, 15, 19]. In this paper, we propose a new method for evaluating outlierness, which we call the Local...

LOCI: Fast outlier detection using the local correlation integral (2003)

Spiros Papadimitriou, Hiroyuki Kitagawa, Phillip B. Gibbons, Christos Faloutsos

under Contract No. N66001-00-1-8936. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the...

LOCI: Fast outlier detection using the local correlation integral (2003)

Spiros Papadimitriou, Hiroyuki Kitagawa, Christos Faloutsos, Phillip B. Gibbons

Outlier detection is an integral part of data mining and has attracted much attention recently [8, 15, 19]. In this paper, we propose a new method for evaluating outlierness, which we call the Local...

ANF: A Fast and Scalable (2002)

Tool For Data, Phillip B. Gibbons, Christos Faloutsos, Christopher R. Palmer, Christopher R. Palmer

Graphs are an increasingly important data source, with such important graphs as the Internet and the Web. Other familiar graphs include CAD circuits, phone records, gene sequences, city streets,...

Distributed Streams Algorithms for Sliding Windows (2002)

Srikanta Tirthapura, Phillip B. Gibbons, Phillip B. Gibbons

This paper presents algorithms for estimating aggregate functions over a "sliding window" of the N most recent data items in one or more streams. Our results include: 1. For a single...

Mining a World of Smart Sensors (2002)

Amol Deshpande, Phillip B. Gibbons, Srinivasan Seshan, Suman Nath, Suman Nath, Amol Deshpande

The proliferation and affordability of webcams has created opportunities for exciting new classes of distributed services. A key stumbling block to mining these rich information sources is the lack...

Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance (2002)

Fractal Prefetching B, Shimin Chen, Phillip B. Gibbons, Todd C. Mowry, Gary Valentin

Trees have been traditionally optimized for I/O performance with disk pages as tree nodes. Recently, researchers have proposed new types of B -Trees optimized for CPU cache performance in main memory...

ANF: A Fast and Scalable Tool for Data Mining (2002)

In Massive Graphs, Christopher R. Palmer, Phillip B. Gibbons, Christos Faloutsos

Graphs are an increasingly important data source, with such important graphs as the Internet and the Web. Other familiar graphs include CAD circuits, phone records, gene sequences, city streets,...

Tracking Join and Self-Join Sizes in Limited Storage (2002)

Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy

This paper presents algorithms for tracking (approximate) join and self-join sizes in limited storage, in the presence of insertions and deletions to the data set(s). Such algorithms detect changes...

Distributed streams algorithms for sliding windows (2002)

Distributed Streams Algorithms for Sliding Windows (2002)

This paper presents algorithms for estimating aggregate functions over a “sliding window ” of the N most recent data items in one or more streams. Our results include: 1. For a single stream, we...

Distributed streams algorithms for sliding windows (2002)

This paper presents algorithms for estimating aggregate functions over a \sliding window" of the N most recent data items in one or more streams. Our results include: 1. For a single stream, we...

IrisNet: An Architecture for Compute-Intensive Wide-Area Sensor Network Services (2002)

This paper presents algorithms for estimating aggregate functions over a “sliding window ” of the N most recent data items in one or more streams. Our results include: 1. For a single stream, we...

Suman Nath, Suman Nath, Amol Deshpande, Amol Deshp, Yan Ke, Yan Ke, ...

Previous work on sensor networks has targeted ad hoc wireless networks of closely-colocated, resourceconstrained scalar sensor motes. Such work has overlooked richer sensor types such as webcams and...

ANF: A fast and scalable tool for data mining in massive graphs (2002)

Christopher R. Palmer, Phillip B. Gibbons, Christos Faloutsos

Graphs are an increasingly important data source, with such important graphs as the Internet and the Web. Other familiar graphs include CAD circuits, phone records, gene sequences, city streets,...

Distributed streams algorithms for sliding windows (2002)

Distributed streams algorithms for sliding windows (2002)

Massive data sets often arise as physically distributed, parallel data streams, and it is important to estimate various aggregates and statistics on the union of these streams. This paper presents...

Fractal prefetching B+-trees: optimizing both cache and disk performance (2002)

This paper presents algorithms for estimating aggregate functions over a \sliding window " of the N most recent data items in one or more streams. Our results include: 1. For a single stream, we...

Shimin Chen, Phillip B. Gibbons, Todd C. Mowry, Gary Valentin

Estimating simple functions on the union of data streams (2001)

Estimating simple functions on the union of data streams (2001)

Estimating simple functions on the union of data streams (2001)

Massive data sets often arise as physically distributed, par-allel data streams. We present algorithms for estimating simple functions on the union of such data streams, while using only logarithmic...

Distinct sampling for highly-accurate answers to distinct values queries and event reports (2001)

Improving Index Performance through Prefetching (2001)

Estimating the number of distinct values is a wellstudied problem, due to its frequent occurrence in queries and its importance in selecting good query plans. Previous work has shown powerful...

Shimin Chen, Phillip B. Gibbons, Todd C. Mowry

This paper proposes and evaluates Prefetching B

Distinct sampling for highly-accurate answers to distinct values queries and event reports (2001)

Distinct sampling for highly-accurate answers to distinct values queries and event reports (2001)

Estimating the number of distinct values is a wellstudied problem, due to its frequent occurrence in queries and its importance in selecting good query plans. Previous work has shown powerful...

Improving Index Performance through Prefetching (2001)

Estimating the number of distinct values is a wellstudied problem, due to its frequent occurrence in queries and its importance in selecting good query plans. Previous work has shown powerful...

Shimin Chen, Phillip B. Gibbons, Todd C. Mowry

ToddC.Mowry is partially supported by an Alfred P. Sloan Research Fellowship and by aFaculty Development Award from IBM. In recognition of the crucial role that cache hierarchies play in database...

Congressional samples for approximate answering of group-by queries (2000)

Swarup Acharya, Phillip B. Gibbons, Viswanath Poosala

In large data warehousing environments, it is often advantageous to provide fast, approximate answers to complex decision support queries using precomputed summary statistics, such as samples....

Join synopses for approximate query answering (1999)

Swarup Acharya, Phillip B. Gibbons, Viswanath Poosala, Sridhar Ramaswamy

In large data warehousing environments, it is often advantageous to provide fast, approximate answers to complex aggregate queries based on statistical summaries of the full data. In this paper, we...

On Secure and Pseudonymous Client-Relationships with Multiple Servers (1999)

Eran Gabber, Phillip B. Gibbons, David M. Kristol, Yossi Matias, Alain Mayer, Name Yossi Matias

This paper introduces a cryptographic engine, Janus, that assists clients in establishing and maintaining secure and pseudonymous relationships with multiple servers. The setting is such that clients...

Aqua: A fast decision support system using approximate query answers (1999)

Swarup Acharya, Phillip B. Gibbons, Viswanath Poosala

Aqua is a system for providing fast, approximate answers to aggregate queries, which are very common in OLAP applications. It has been designed to run on top of any commercial relational DBMS. Aqua...

Consistent, yet anonymous, web access with LPWA (1999)

Eran Gabber, Phillip B. Gibbons, David M. Kristol, Yossi Matias, Alain Mayer

The Lucent Personalized Web Assistant offers a single, effective method for adopting differing personae.

Aqua: A fast decision support system using approximate query answers (1999)

Swarup Acharya, Phillip B. Gibbons, Viswanath Poosala

Aqua is a system for providing fast, approximate answers to aggregate queries, which are very common in OLAP applications. It has been designed to run on top of any commercial relational DBMS. Aqua...

On Secure and Pseudonymous (1999)

Eran Gabber, Phillip B. Gibbons, David M. Kristol, Yossi Matias, Alain Mayer, ...

This paper introduces a cryptographic engine, Janus, that assists clients in establishing and maintaining secure and pseudonymous relationships with multiple servers. The setting is such that clients...

Modeling and optimizing I/O throughput of multiple disks on a bus (1999)

Rakesh Barve, Elizabeth Shriver, Phillip B. Gibbons, Bruce K. Hillyer, Yossi Matias

Abstract For a wide variety of computational tasks, disk I/O continues to be a serious obstacle to high performance. The focus of the present paper is on systems that use multiple disks per SCSI bus....

On Secure and Pseudonymous Client-Relationships with Multiple Servers (1999)

Eran Gabber, Phillip B. Gibbons, David M. Kristol, Yossi Matias, Alain Mayer, Name Yossi Matias

This paper introduces a cryptographic engine, Janus, that assists clients in establishing and maintaining secure and pseudonymous relationships with multiple servers. The setting is such that clients...

Consistent, yet anonymous, web access with LPWA (1999)

Eran Gabber, Phillip B. Gibbons, David M. Kristol, Yossi Matias, Alain Mayer

In recent years the World Wide Web (WWW) has become an immensely popular and powerful medium. To attract more users, many web-sites o er personalized services, whereby users identify themselves and...

Modeling and Optimizing I/O Throughput of Multiple Disks on a Bus (1999)

Rakesh Barve, Elizabeth Shriver, Phillip B. Gibbons, Bruce K. Hillyer, Yossi Matias, Je Scott Vitter

In modern I/O architectures, multiple disk drives are attachedtoeachI/O controller. A study of the performance of such architectures under I/O-intensive workloads has revealed a performance...

Improving Index Performance through Prefetching (1998)

Chen, Shimin, Gibbons, Phillip B., Mowry, Todd C.

In recognition of the crucial role that cache hierarchies play in database performance, recent studies have revisited core database algorithms and data structures in an effort to reduce the number of...

How toMakePersonalized Web Browsing Simple, Secure, and Anonymous (1998)

Eran Gabber, Phillip B. Gibbons, Yossi Matias, Alain Mayer

Abstract. An increasing number of web-sites require users to establish an account before they can access the information stored on that site (\personalized web browsing"). Typically, the...

On Secure and Pseudonymous Client-Relationships with Multiple Servers (1998)

Daniel Bleichenbacher, Daniel Bleichenbacher, Eran Gabber, Eran Gabber, Phillip B. Gibbons, Phillip B. Gibbons, ...

This paper introduces a cryptographic engine, Janus, that assists clients in establishing and maintaining secure and pseudonymous relationships with multiple servers. The setting is such that clients...

The Queue-Read Queue-Write Asynchronous PRAM Model (1998)

Phillip B. Gibbons, Yossi Matias, Vijaya Ramachandran

This paper presents results for the queue-read, queue-write asynchronous parallel random access machine (qrqw asynchronous pram) model, which is the asynchronous variant of the qrqw pram model. The...

Scheduling Space-Sharing for Internet Advertising (1998)

Micah Adler Phillip, Phillip B. Gibbons, Yossi Matias

This paper provides the first in-depth study of the algorithmic questions involved in the scheduling of space-sharing for Internet advertising. Given a set of ads specified by geometry and display...

Scheduling Space-Sharing for Internet Advertising (1998)

Micah Adler, Phillip B. Gibbons, Yossi Matias

This paper provides the first in-depth study of the algorithmic questions involved in the scheduling of space-sharing for Internet advertising. We consider the scheduling problem where each...

Design and Implementation of the Lucent Personalized Web Assistant (LPWA) (1998)

David M. Kristol, Eran Gabber, Phillip B. Gibbons, Yossi Matias, Alain Mayer

This paper describes the design and implementation of the Lucent Personalized Web Assistant (LPWA). LPWA is a software system that enables a user to browse the Web in a personalized, simple, private,...

On Secure and Pseudonymous Client-Relationships with Multiple Servers (1998)

Daniel Bleichenbacher, Eran Gabber, Phillip B. Gibbons, Yossi Matias, Alain Mayer

This paper introduces a cryptographic engine, Janus, that assists clients in establishing and maintaining secure and pseudonymous relationships with multiple servers. The setting is such that clients...

How toMakePersonalized Web Browsing Simple, Secure, and Anonymous (1998)

Eran Gabber, Phillip B. Gibbons, Yossi Matias, Alain Mayer

Abstract. An increasing number of web-sites require users to establish an account before they can access the information stored on that site (\personalized web browsing"). Typically, the...

On Secure and Pseudonymous Client-Relationships with Multiple Servers (1998)

Daniel Bleichenbacher, Eran Gabber, Phillip B. Gibbons, Yossi Matias, Alain Mayer

This paper introduces a cryptographic engine, Janus, that assists clients in establishing and maintaining secure and pseudonymous relationships with multiple servers. The setting is such that clients...

Scheduling Space-Sharing for Internet Advertising (1998)

Micah Adler, Phillip B. Gibbons, Yossi Matias

This paper provides the rst in-depth study of the algorithmic questions involved in the scheduling of space-sharing for Internet advertising. Given a set of ads speci ed by geometry and display...

Design and implementation of the Lucent Personalized Web Assistant (LPWA (1998)

David M. Kristol, Eran Gabber, Phillip B. Gibbons, Yossi Matias, Alain Mayer

This paper describes the design and implementation of the Lucent Personalized Web Assistant (LPWA). LPWA isasoftware system that enables a user to browse the Web in a personalized, simple, private,...

Design and implementation of the Lucent Personalized Web Assistant (LPWA (1998)

David M. Kristol, Eran Gabber, Phillip B. Gibbons, Yossi Matias, Alain Mayer

This paper describes the design and implementation of the Lucent Personalized Web Assistant (LPWA). LPWA isasoftware system that enables a user to browse the Web in a personalized, simple, private,...

Fast Incremental Maintenance of Approximate Histograms (1997)

Phillip B. Gibbons, Yossi Matias, Viswanath Poosala

Many commercial database systems maintain his-tograms to summarize the contents of large re-lations and permit efficient estimation of query result sizes for use in query optimizers. Delay-ing the...

Testing shared memories (1997)

Phillip B. Gibbons, Ephraim Korach

Abstract. Sequential consistency is the most widely used correctness condition for multiprocessor memory systems. This paper studies the problem of testing shared-memory multiprocessors to determine...

Fast Incremental Maintenance of Approximate Histograms (1997)

Phillip B. Gibbons, Yossi Matias, Viswanath Poosala

Many commercial database systems maintain histograms to summarize the contents of large relations and permit efficient estimation of query result sizes for use in query optimizers. Delaying the...

The Queue-Read Queue-Write PRAM Model: Accounting for Contention in Parallel Algorithms (1997)

Phillip B. Gibbons, Yossi Matias, Vijaya Ramachandran

Abstract. This paper introduces the queue-read queue-write (qrqw) parallel random access machine (pram) model, which permits concurrent reading and writing to shared-memory locations, but at a cost...

Accounting for memory bank contention and delay in high-bandwidth multiprocessors (1997)

Guy E. Blelloch, Phillip B. Gibbons, Yossi Matias, Marco Zagha

Abstract—For years, the computation rate of processors has been much faster than the access rate of memory banks, and this divergence in speeds has been constantly increasing in recent years. As a...

Aqua project white paper (1997)