Phillip B. Gibbons - Papers (1996+)
Note: This collection of papers is updated infrequently, and often out
of date. Please see the publication list in my
c.v. for a more complete listing of my papers,
including papers published prior to 1996.
Please see the copyright notice below.
All papers are pdf files, unless otherwise noted.
-
D. Sundarraj, P. B. Gibbons and P. Pillai
Ensuring Spatio-Temporal Consistency in
Distributed Networks of Smart Cameras,
DSC'06. Held in conjunction with SenSys'06.
-
S. Nath, H. Yu, P. B. Gibbons and
S. Seshan
Subtleties in
Tolerating Correlated Failures in Wide-Area Storage
Systems, NSDI'06.
-
S. Nath, P. B. Gibbons and S. Seshan
Adaptive Data
Placement for Wide-Area Sensing Services, FAST'05.
-
J. Campbell, P. B. Gibbons, S. Nath, P. Pillai, S. Seshan and R. Sukthankar
IrisNet:
An Internet-Scale Architecture for Multimedia Sensors, MM'05.
-
B. Aksak, P. S. Bhat, J. Campbell, M. DeRosa, S. Funiak, P. B. Gibbons,
S. C. Goldstein, C. Guestrin, A. Gupta, C. Helfrich, J. Hoburg,
B. Kirby, J. Kuffner, P. Lee, T. C. Mowry, P. S. Pillai, R. Ravichandran,
B. D. Rister, S. Seshan, M. Sitti and H. Yu
Demo Abstract: Claytronics - Highly
Scalable Communications, Sensing, and Actuation Networks, SenSys'05.
-
S. Chen, P. B. Gibbons and S. Nath
Database-Centric Programming of Wide-Area
Sensor Systems, DCOSS'05.
-
A. Manjhi, S. Nath and P. B. Gibbons
Tributaries
and Deltas: Efficient and Robust Aggregation in
Sensor Network Streams, SIGMOD'05.
-
S. Nath, P. B. Gibbons, S. Seshan and
Z. Anderson
Synopsis
Diffusion for Robust Aggregation in Sensor Networks, SenSys'04.
-
S. Nath, Y. Ke, P. B. Gibbons, B. Karp and S. Seshan
A Distributed Filtering Architecture
for Multimedia Sensors, BaseNets'04. Winner, best paper award.
-
S. Nath, A. Deshpande, Y. Ke, P. B. Gibbons, B. Karp and S. Seshan
IrisNet: An Architecture for
Internet-Scale Sensing Services, demo abstract in VLDB'03.
-
P. B. Gibbons, B. Karp, Y. Ke, S. Nath and S. Seshan
IrisNet: An Architecture for a
Worldwide Sensor Web,
IEEE Pervasive Computing, 2:4 (2003).
-
A. Deshpande, S. Nath, P. B. Gibbons and S. Seshan
Cache-and-Query for Wide Area Sensor
Databases, SIGMOD'03.
-
A. Deshpande, S. Nath, P. B. Gibbons and S. Seshan
IrisNet: Internet-Scale
Resource-Intensive Sensor Services,
demo abstract in SIGMOD'03.
-
S. Nath, A. Deshpande, Y. Ke, P. B. Gibbons, B. Karp and S. Seshan
IrisNet: An Architecture for Compute-Intensive Wide-Area Sensor Network Services, Intel Research Pittsburgh TR 2002.
- A. Manjhi, P. B. Gibbons, A. Ailamaki, C. Garrod,
B. Maggs, T. C. Mowry, C. Olston, A. Tomasic and H. Yu
Invalidation Clues for Database Scalability Services, ICDE'07,
to appear.
-
S. Chen, A. Ailamaki, P. B. Gibbons and T. C. Mowry
Inspector Joins,
VLDB'05.
-
S. Venkataraman, D. Song, P. B. Gibbons and A. Blum
New
Streaming Algorithms for Fast Detection of Superspreaders, NDSS'05.
-
A. Manjhi, S. Nath and P. B. Gibbons
Tributaries and Deltas: Efficient and Robust Aggregation in
Sensor Network Streams, SIGMOD'05.
See above.
-
S. Nath, P. B. Gibbons, S. Seshan and Z. Anderson
Synopsis Diffusion for Robust Aggregation in Sensor Networks, SenSys'04.
See above.
-
A. Wong, L. Wu, P. B. Gibbons and C. Faloutsos
Fast Estimation of
Fractal Dimension and Correlation Integral on Stream Data,
IPL, 93:2 (2005).
-
S. Chen, A. Ailamaki, P. B. Gibbons and T. C. Mowry
Improving
Hash Join Performance Through Prefetching, ICDE'04,
co-winner of the ICDE'04 best paper award.
-
S. Papadimitriou, H. Kitawaga, P. B. Gibbons and C. Faluotsos
LOCI:
Fast Outlier Detection Using the Local Correlation Integral, ICDE'03.
-
P. B. Gibbons and S. Tirthapura
Distributed Streams Algorithms for Sliding
Windows, SPAA'02.
Journal version in TOCS 37 (2004).
-
C. R. Palmer, P. B. Gibbons and C. Faloutsos
ANF: A Fast and Scalable Tool for Data
Mining in Massive Graphs, KDD'02.
-
M. Garofalakis and P. B. Gibbons
Wavelet Synopses with Error
Guarantees, SIGMOD'02. Journal version,
Probabilistic
Wavelet Synopses, in TODS 29:1 (2004).
-
S. Chen, P. B. Gibbons, T. C. Mowry and G. Valentine
Fractal Prefetching B+ Trees: Optimizing
Both Cache and Disk Performance, SIGMOD'02.
Full version.
-
M. Garofalakis and P. B. Gibbons
Approximate Query Processing: Taming
the Terabytes (powerpoint), tutorial presented at VLDB'01.
-
P. B. Gibbons
Distinct
Sampling for Highly-Accurate Answers to Distinct Values Queries and Event
Reports, VLDB'01.
-
P. B. Gibbons and S. Tirthapura
Estimating
Simple Functions on the Union of Data Streams, SPAA'01.
An
earlier version with some of the proofs.
-
S. Chen, P. B. Gibbons and T. C. Mowry
Improving
Index Performance through Prefetching, SIGMOD'01.
Full version.
-
S. Acharya, P. B. Gibbons and V. Poosala
Congressional
Samples for Approximate Answering of Group-By Queries, SIGMOD'00.
Full version.
-
S. Acharya, P. B. Gibbons, V. Poosala and S. Ramaswamy
Join
Synopses for Approximate Query Answering, SIGMOD'99.
Full version.
-
P. B. Gibbons and Y. Matias
Synopsis Data Structures for Massive
Data Sets, Bell Labs TR 1998. Book
chapter in External Memory Algorithms, DIMACS Series in
Discrete Mathematics and Theoretical Computer Science.
Two-page summary appearing in SODA'99.
-
S. Acharya, P. B. Gibbons and V. Poosala
Aqua: A Fast Decision Support System
Using Approximate Query Answers, demo abstract in VLDB'99.
-
S. Acharya, P. B. Gibbons, V. Poosala and S. Ramaswamy
The
Aqua Approximate Query Answering System,
demo abstract in SIGMOD'99.
-
N. Alon, P. B. Gibbons, Y. Matias and M. Szegedy
Tracking
Join and Self-Join Sizes in Limited Storage, PODS'99.
Journal version in
JCSS 64:3 (2002).
-
P. B. Gibbons and Y. Matias
New
Sampling-Based Summary Statistics for Improving Approximate Query Answers,
SIGMOD'98.
-
P. B. Gibbons, Y. Matias and V. Poosala
Aqua
Project White Paper, Bell Labs TR 1997.
-
P. B. Gibbons, Y. Matias and V. Poosala
Fast
Incremental Maintenance of Approximate Histograms, VLDB'97.
Journal
version in TODS 27:3 (2002).
-
S. Ganguly, P. B. Gibbons, Y. Matias and A. Silberschatz
Bifocal
Sampling for Skew-Resistant Join Size Estimation, SIGMOD'96.
-
S. Chen, B. Falsafi, P. B. Gibbons, M. Kozuch, T. C. Mowry, R. Teodorescu,
A. Ailamaki, L. Fix, G. R. Ganger, B. Lin and S. W. Schlosser
Log-Based Architectures for General-Purpose Monitoring
of Deployed Code, brief announcement in ASID'06.
Held in conjunction with ASPLOS'06.
-
H. Yu, M. Kaminsky, P. B. Gibbons and A. Flaxman
SybilGuard:
Defending Against Sybil Attacks via Social Networks, SIGCOMM'06.
Full version.
-
V. Liaskovitis, S. Chen, P. B. Gibbons, A. Ailamaki, G. E. Blelloch,
B. Falsafi, L. Fix, N. Hardavellas, M. Kozuch, T. C Mowry and C. Wilkerson
Brief Announcement: Parallel Depth First vs.
Work Stealing Schedulers on CMP Architectures, SPAA'06 brief
announcement.
-
H. Yu, P. B. Gibbons and S. Nath
Availability of
Multi-Object Operations, NSDI'06,
co-winner of the NSDI'06 best paper award.
-
S. Nath, H. Yu, P. B. Gibbons and S. Seshan
Subtleties in Tolerating Correlated Failures in Wide-Area Storage
Systems, NSDI'06. See above.
-
P. Yalagandula, S. Nath, H. Yu, P. B. Gibbons and S. Seshan
Beyond Availability: Towards a Deeper
Understanding of Machine
Failure Characteristics in Large Distributed Systems, WORLDS'04.
-
G. E. Blelloch and P. B. Gibbons
Effectively
Sharing a Cache Among Threads, SPAA'04.
-
S. S. Muchnick and P. B. Gibbons
Retrospective:
Efficient Instruction Scheduling for a Pipelined Architecture, in
20 Years of PLDI (1979-1999): A Selection, 2004.
-
P. B. Gibbons and S. Tirthapura
Distributed Streams Algorithms for Sliding Windows, TOCS 37 (2004).
See above.
-
G. E. Blelloch, P. Cheng and P. B. Gibbons
Room Synchronizations, SPAA'01.
Journal version in
TOCS 36:5 (2003).
-
P. B. Gibbons and S. Tirthapura
Estimating Simple Functions on the Union of Data Streams,
SPAA'01. See above.
-
P. B. Gibbons, J. Bruno and S. Phillips
Post-Mortem
Black-Box Correctness Tests for Basic Parallel Data Structures, SPAA'99.
Journal version in TOCS 35 (2002).
-
R. Barve, E. Shriver, P. B.Gibbons, B. Hillyer, Y. Matias and J. S. Vitter
Modeling and
Optimizing I/O Throughput of Multiple Disks on a Bus, corrected
version of a SIGMETRICS'99 paper.
-
R. Barve, P. B.Gibbons, B. Hillyer, Y. Matias, E. Shriver and J. S. Vitter
Round-Like Behavior in Multiple Disks
on a Bus, IOPADS'99.
-
P. B. Gibbons, Y. Matias and V. Ramachandran
Can a Shared-Memory Model Serve as a Bridging
Model for Parallel Computation?, Theory of Computing Systems
(1999), special issue on SPAA'97.
-
M. Adler, P. B. Gibbons, Y. Matias and V. Ramachandran
Modeling Parallel Bandwidth: Local vs. Global
Restrictions, Algorithmica (1999), special issue on coarse-grained
parallel algorithms. A preliminary version appeared in SPAA'97.
-
P. B. Gibbons, Y. Matias and V. Ramachandran
The Queue-Read Queue-Write Asynchronous PRAM
Model, Theoretical Computer Science (1998), special issue
on EuroPar'96.
-
G. E. Blelloch, P. B. Gibbons, Y. Matias and G. J. Narlikar
Space-Efficient
Scheduling of Parallelism with Synchronization Variables, SPAA'97.
-
P. B. Gibbons
What Good are Shared Memory Models?,
ICPP'96 Workshop on Challenges for Parallel Processing,
invited position paper.
Updated versions of pre-1996 papers:
-
G. E. Blelloch, P. B. Gibbons and Y. Matias
Provably
Efficient Scheduling for Languages with Fine-Grained Parallelism,
JACM, 46:2 (1999). A preliminary version appeared in SPAA'95.
-
P. B. Gibbons, Y. Matias and V. Ramachandran
The Queue-Read
Queue-Write PRAM model: Accounting for Contention in Parallel Algorithms,
SICOMP, 28:2 (1998). A preliminary version appeared in SODA'94.
-
G. E. Blelloch, P. B. Gibbons, Y. Matias and M. Zagha
Accounting for Memory Bank Contention
and Delay in High-Bandwidth Multiprocessors, IEEE-TPDS, 8:9 (1997).
A preliminary version appeared in SPAA'95.
-
P. B. Gibbons and E. Korach
Testing Shared Memories, SICOMP, 26:4 (1997).
A preliminary version appeared in SPAA'94.
-
P. B. Gibbons, Y. Matias and V. Ramachandran
Efficient Low-Contention Parallel
Algorithms, JCSS, 53:3 (1996).
A preliminary version appeared in SPAA'94.
-
A. Manjhi, P. B. Gibbons, A. Ailamaki, C. Garrod, B. Maggs, T. C. Mowry,
C. Olston, A. Tomasic and H. Yu
Invalidation Clues for Database Scalability Services, ICDE'07.
See above.
-
C. R. Palmer, P. B. Gibbons and C. Faloutsos
ANF: A Fast and Scalable Tool for Data Mining in Massive Graphs,
KDD'02. See above.
-
M. Adler, P. B. Gibbons and Y. Matias
Scheduling Space-Sharing for Internet
Advertising, Journal of Scheduling, 5:2 (2002).
-
C. R. Palmer, G. Siganos, M. Faloutsos, C. Faloutsos and P. B.
Gibbons
The
Connectivity and Fault-Tolerance of the Internet Topology,
NRDM'01 Workshop.
-
E. Gabber, P. B. Gibbons, D. M. Kristol, Y. Matias and A. Mayer
Consistent
Yet Anonymous Web Access with LPWA, CACM (1999), special issue on internet
privacy.
-
E. Gabber, P. B. Gibbons, D. M. Kristol, Y. Matias and A. Mayer
On Secure and Pseudonymous
Client-Relationships with Multiple Servers, TISSEC (1999). A preliminary
version appeared in the USENIX Workshop on Electronic Commerce '98.
-
D. M. Kristol, E. Gabber, P. B. Gibbons, Y. Matias and A. Mayer
Design and Implementation of the Lucent
Personalized Web Assistant (LPWA), Bell Labs TR 1999.
-
E. Gabber, P. B. Gibbons, Y. Matias and A. Mayer
How to
Make Personalized Web Browsing Simple, Secure, and Anonymous,
Financial Cryptography '97.
Copyright Notice: Since most of
these papers are published, the copyright has been transferred to the
respective publishing houses. Therefore, the papers cannot be
duplicated for commercial purposes. The following is ACM's copyright notice.
The other
publishers have similar ones.
Copyright © YYYY
by the Association for Computing Machinery, Inc. Permission to make
digital or hard copies of part or all of this work for personal or
classroom use is granted without fee provided that copies are not made
or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. Copyrights
for components of this work owned by others than ACM must be
honored. Abstracting with credit is permitted.
Phillip
B. Gibbons Home Page