- talks - lists.cs.princeton.edu

Today 4:30-5:30: Deep Learning in Detection and Recognition
by Jianxiong Xiao 02 Jul '14

02 Jul '14

Speaker: Xiaogang Wang Room: CS 402 Time: July 2nd Wednesday 4:30-5:30 Title: Deep Learning in Detection and Recognition Abstract: In this seminar, I will introduce our recent works on developing deep models to solve several computer vision problems, especially focusing on pedestrian detection and face recognition. Deep models significantly advance the state-of-the-art on these challenges because of their capability of automatically learning hierarchical feature representations from data, disentangling hidden factors, jointly optimizing key components in a computer vision system, and their learning capacity. Through examples, I will share our experience on how to formulate a vision problem with deep learning, and how to effectively train a deep neural network. Instead of treating a deep model as a black box, we investigate the connection between deep models and existing vision systems, such that a lot of insights and experience accumulated from vision research can be used to develop new deep models and effective training strategies. Taking pedestrian detection as an example, pedestrian detection, new layers are designed to function as part detectors, modeling deformations and inferring the visibility of body parts. I will also report our results on face recognition which can be addressed by deep learning in several different ways. Bio: Xiaogang Wang received his Bachelor degree in Electrical Engineering and Information Science from the Special Class of Gifted Young at the University of Science and Technology of China in 2001, M. Phil. degree in Information Engineering from the Chinese University of Hong Kong in 2004, and PhD degree in Computer Science from Massachusetts Institute of Technology in 2009. He is an assistant professor in the Department of Electronic Engineering at the Chinese University of Hong Kong since August 2009. He received the Outstanding Young Researcher in Automatic Human Behaviour Analysis Award in 2011, Hong Kong RGC Early Career Award in 2012, and Young Researcher Award of the Chinese University of Hong Kong. He is the associate editor of the Image and Visual Computing Journal. He was the area chair of ICCV 2011, ECCV 2014 and ACCV 2014. His research interests include computer vision, deep learning, crowd video surveillance, object detection, and face recognition.

1 0

Logan Stafman's Generals: Thursday, May 22, 2014 (2pm) in Rm. 402
by Nicki Gotsis 15 May '14

15 May '14

Logan Stafman will present the General Exam on Thursday, May 22, 2014 (2pm) in Rm. 402. The members of Logan's committee are Margaret Martonosi, Jennifer Rexford, and Vivek Pai. Everyone is invited to attend Logan's talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Logan's abstract and reading list follow below. Abstract Recently, we have been asking for our mobile phones to do more computation than ever before, while maintaining energy efficiency. Many mobile apps, in particular sensing apps, approach the problem of energy usage optimization by offloading heavy computation to the cloud. While this approach helps to save computation energy, it can often increase latency, bandwidth usage, and communication energy. As compute capability and heterogeneity of mobile devices both increase, the tradeoffs regarding when to offload computation to the cloud, whether from a latency, bandwidth, or energy standpoint, have become complex. While researchers have developed some systems to automate this offloading process in applications by offloading entire virtual machines and automatically partitioning applications, more remains to be done. This work studies automated techniques for optimizing application partitioning and offload. We consider energy and bandwidth oriented partitioning approaches. In addition, we discuss how the addition of new application modules (such as compression) can improve the payoff from offloading. Our work uses two example applications: SignalGuru and Sphinx. For SignalGuru, our partitioning approach improves bandwidth usage by up to 10x and offers energy savings as well. We discuss how these applications need to be adapted to obtain these goals, and how this process can be automated. We will also discuss how differences in the hardware of mobile devices can strongly affect the optimal partitioning choices for these applications. Reading List SignalGuru - Emmanouil Koukoumidis, Li-Shiuan Peh, and Margaret Martonosi. 2011. SignalGuru: leveraging mobile phones for collaborative traffic signal schedule advisory. In Proceedings of the 9th international conference on Mobile systems, applications, and services (MobiSys '11). MAUI - Eduardo Cuervo, Aruna Balasubramanian, Dae-ki Cho, Alec Wolman, Stefan Saroiu, Ranveer Chandra, and Paramvir Bahl. 2010. MAUI: making smartphones last longer with code offload. In Proceedings of the 8th international conference on Mobile systems, applications, and services (MobiSys '10). CloneCloud - Byung-Gon Chun, Sunghwan Ihm, Petros Maniatis, Mayur Naik, and Ashwin Patti. 2011. CloneCloud: elastic execution between mobile device and cloud. In Proceedings of the sixth conference on Computer systems (EuroSys '11). Junxian Huang, Feng Qian, Alexandre Gerber, Z. Morley Mao, Subhabrata Sen, and Oliver Spatscheck. 2012. A close examination of performance and power characteristics of 4G LTE networks. In Proceedings of the 10th international conference on Mobile systems, applications, and services (MobiSys '12). ACM, New York, NY, USA, 225-238. DOI=10.1145/2307636.2307658 Brian D. Noble, M. Satyanarayanan, Dushyanth Narayanan, James Eric Tilton, Jason Flinn, and Kevin R. Walker. 1997. Agile application-aware adaptation for mobility. In Proceedings of the sixteenth ACM symposium on Operating systems principles (SOSP '97), William M. Waite (Ed.). ACM, New York, NY, USA, 276-287. DOI=10.1145/268998.266708 Flinn, Jason; SoYoung Park; Satyanarayanan, M., "Balancing performance, energy, and quality in pervasive computing," Distributed Computing Systems, 2002. Proceedings. 22nd International Conference on , vol., no., pp.217,226, 2002 doi: 10.1109/ICDCS.2002.1022259 Jason Flinn and M. Satyanarayanan. 1999. Energy-aware adaptation for mobile applications. In Proceedings of the seventeenth ACM symposium on Operating systems principles (SOSP '99). ACM, New York, NY, USA, 48-63. DOI=10.1145/319151.319155 Balan, Rajesh Krishna, et al. "Tactics-based remote execution for mobile computing." Proceedings of the 1st international conference on Mobile systems, applications and services . ACM, 2003. Robert LiKamWa, Bodhi Priyantha, Matthai Philipose, Lin Zhong, and Paramvir Bahl. 2013. Energy characterization and optimization of image sensing toward continuous mobile vision. In Proceeding of the 11th annual international conference on Mobile systems, applications, and services (MobiSys '13). ACM, New York, NY, USA, 69-82. DOI=10.1145/2462456.2464448 Book: Operating Systems: Internals and Design Principles, 7th Edition - William Stallings

1 0

Special seminar - Jonathan Viventi, NYU poly
by Scott Karlin 15 May '14

15 May '14

“High-Resolution Brain Machine Interfaces using Flexible Silicon Electronics" Jonathan Viventi, Department of Electrical and Computer Engineering & Center for Neural Science, New York University Date: Thursday, May 29th Time: 4:30pm Location: A32 Princeton Neuroscience Institute Abstract Current implantable brain devices for clinical and research applications require that each electrode is individually wired to a separate electronic system. Establishing a high-resolution interface over broad regions of the brain is infeasible under this constraint, as an electrode array with thousands of passive contacts would require thousands of wires to be individually connected. To overcome this limitation, we have developed new implantable electrode array technology that incorporates active, flexible electronics. This technology has enabled extremely flexible arrays of 1,024 electrodes and soon, thousands of multiplexed and amplified sensors spaced as closely as 250 µm apart, which are connected using just a few wires. These devices yield an unprecedented level of spatial and temporal micro-electrocorticographic (µECoG) resolution for recording and stimulating distributed neural networks. I will present the development of this technology and data from in vivo recordings. I will also present examples of finely detailed spatial and temporal patterns from feline neocortex that give rise to seizures and suggest new stimulation paradigms to treat epilepsy. Finally, I will discuss new electrode designs and supporting hardware to enable chronic implantation of µECoG arrays with multiplexed recording and stimulation to enable a bi-directional interface with the brain. Bio Jonathan Viventi is an Assistant Professor of Electrical and Computer Engineering at the New York University Polytechnic School of Engineering and an Assistant Professor of Neural Science at New York University. Dr. Viventi earned his Ph.D. in Bioengineering from the University of Pennsylvania and his M.Eng. and B.S.E. degrees in Electrical Engineering from Princeton University. Dr. Viventi's research applies innovations in flexible electronics, low power analog circuits, and machine learning to create new technology for interfacing with the brain at a much finer scale and with broader coverage than previously possible. He creates new tools for neuroscience research and technology to diagnose and treat neurological disorders, such as epilepsy. Using these tools, he collaborates with neuroscientists and clinicians to explore the fundamental properties of brain networks in both health and disease. His research program works closely with industry, including filing five patents and several licensing agreements. His work has been featured as cover articles in Science Translational Medicine and Nature Materials, and has also appeared in Nature Neuroscience, the Journal of Neurophysiology, and Brain. Dr. Viventi has received several awards for his work, including a Taking Flight Award from Citizens United for Research in Epilepsy (CURE), a “Grand Challenge” award from New York University, the Mahoney Institute of Neurological Sciences / Neuroscience Graduate Group Flexner Award for Best Neuroscience Thesis at the University of Pennsylvania, the Solomon R. Pollack Award for Best Thesis in the Department of Bioengineering at the University of Pennsylvania, and the Nano/Bio-Interface Center Graduate Research Award for Best Graduate Research on Nanotechnology Applied to Biology at the University of Pennsylvania. Host: Uri Hasson

1 0

Aleksey Boyko: PreFPO on Wednesday, May 21st 12pm, Rm. 402
by Nicki Gotsis 14 May '14

14 May '14

Aleksey Boyko will present his Pre FPO which is scheduled for Wednesday, May 21st at noon in Rm. 402. Members of his committee are: Thomas Funkhouser (advisor), Brian Kernighan (reader), Szymon Rusinkiewicz (reader), Adam Finkelstein (non-reader), and Jianxiong Xiao(non-reader). Everyone is invited to attend his talk. The title and abstract are below. Title: "On tools and interfaces for efficient and accurate interactive annotation of static 3D point clouds" Abstract: Collecting massive 3D scans of real world environments has become a common practice for many private companies and government agencies. This data is accurate and rich enough to provide impressive visualizations of these environments. However, to truly tap into the potential that such a precise digital depiction of the world offers, these scans need to be annotated. Existing automatic methods report high accuracies for object localization and segmentation, thus greatly improving the complexity of the task. However, the central task of annotation, proper label assignment to the discovered objects, is still a challenging task for existing systems. The goal of this work is to design an interface that facilitates the process of labeling objects in large natural 3D scenes. Prior efforts in this field span a variety of approaches, from purely manual to automatic, to achieve different levels of success. Manual annotation systems produce near perfect results at a cost of enormous human effort. Automatic methods aim at requiring less human input but achieve much lower accuracy, which in turn requires more human interaction. Machine-aided tools attempt to balance these two extremes, however the necessary level of annotator's effort is rarely considered, while the task of training a model that hopefully achieves higher accuracy still takes the center stage. Noticing that the machines have yet a long way to go to match humans' ability to understand real world, and how prone to fatigue and frustration humans are, a preferable approach is to make user effort a priority in any annotation interface. This dissertation assumes the necessity of the human annotator to confirm labels for all objects in order to ensure correctness and explicitly focuses on the tools and interfaces that streamline and facilitate this process. Taking advantage of the scene continuity of the 3D scan data this work advances in two principal directions. First, annotation of objects in groups is proposed to increase the throughput of the information flow from the user to the machine. Second, the non-essential yet time consuming tasks (e.g., scene navigation, selection decisions) are relayed onto a machine by employing an active learning approach to streamline the annotation process and diminish user fatigue and distraction. After evaluating these two directions, a third hybrid approach is proposed---a group active interface. This method takes advantage of the human ability to understand entire scenes and queries objects in groups that are easy to understand and label together thus further increasing the throughput of the annotation process. Empirical evaluation of this approach on a pre-segmented object data indicates an improvement by a factor of 1.7 in annotation time compared to other methods discussed without loss in accuracy.

1 0

Jingwan Lu's FPO: Weds., May 14, 2014 at 10am in Room 402
by Nicki Gotsis 12 May '14

12 May '14

Jingwan Lu will present his FPO on Wednesday, May 14, 2014 at 10am in Room 402. The members of his committee are: Adam Finkelstein, (adviser), Szymon Rusinkiewicz, (reader), Stephen DiVerdi, (reader), Thomas A. Funkhouser, (non-reader), Jianxiong Xiao (non-reader) A copy of Jingwan's thesis, is available in Room 310. Everyone is invited to attend Jinwan's talk.

1 1

Andrej Risteski General Exam: Monday, May 12, 2014 at 2pm in Room 302
by Nicki Gotsis 12 May '14

12 May '14

Andrej Risteski will present his General Exam on Monday, May 12, 2014 at 2pm in Room 302. The members of his committee are Sanjeev Arora (advisor), Moses Charikar, David Blei. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Abstract: Some simple provably convergent cases for variational inference Variational inference is a fairly commonly used tool in machine learning to do inference in graphical models. The way they work is to try to reduce the problem of calculating a marginal probability to some suitable, usually non-convex, mathematical program. More precisely, one assumes the marginal distribution belongs to some well-behaved/tractable family of distributions by assuming independence between some variables that are actually not independent. Then, one tries to find the best distribution in this family that matches the marginal we are trying to find. Unfortunately, they rarely come with any guarantees. First, it's difficult to know how much one looses by assuming the independencies, and solving the non-convex program is usually done with some gradient descent-like procedure, so it's unclear how good of a solution we will get. I will discuss some simple cases where one can prove convergence to the right value in the setting of topic modeling. With some suitably (strong) assumptions on the model, and some (unfortunately also strong) initializations, we will prove variational inference works. We'll complement this with some experimentally constructed (natural) counter-examples where dropping these assumptions causes us to not converge to the right value anymore (at least with the vanilla methods we are analyzing). While the assumptions we are making are arguably not very realistic, they are a step forward in analyzing variational inference in more interesting settings. Reading list: 0. Algorithm Design; Kleinberg, Tardos 1. Graphical Models, Exponential Families, and Variational Inference; Jordan, Wainwright [Chapters 1,2,3,4,7,9] 2. Latent Dirichlet Allocation; Blei, Ng, Jordan 3. Learning Topic Models - Going beyond SVD; Arora, Moitra 4. A Practical Algorithm for Topic Modeling with Provable Guarantees; Arora et al. 5. Computing a Nonnegative Matrix Factorization --- Provably; Arora, Kannan, Moitra 6. Complexity of Inference in Graphical Models; Chandresekaran, Srebro, Harsha 7. Understanding Belief Propagation and its Generalizations; Yedidia, Freeman, Weiss 8. Convexity Arguments for Efficient Minimization of the Bethe and Kikuchi Free Energies; Heskes 9. Convexifying the Bethe Free Energy; Meshi, Jaimovich, Globerson, Friedman 10. Counting independent sets up to the tree threshold; Weitz 11. Counting Independent Sets Using the Bethe Approximation; Chandrasekaran, Chertkov, Gamarnik, Shah, Shin 12. Clustering with Spectral Norm and the k-means Algorithm; Kumar, Kannan

1 1

Aman Dhesi Generals: Monday, May 19, 2014 at 2pm in Room 402
by Nicki Gotsis 08 May '14

08 May '14

Aman Dhesi will present his general exam on Monday, May 19, 2014 at 2pm in Room 402. His committee members are Moses Charikar, Mark Braverman, and Bernard Chazelle. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below: Abstract: Matching problems arise in many contexts - matching jobs to machines, patients to hospitals, ad impressions to advertisers. In general, one class of objects (items) need to be matched to another class of objects (agents) and the agents have some form of preference or utility function over the items. Our work focuses on the online version of the matching problem, where the items are revealed one-by-one and need to be irrevocably matched as soon as they arrive. We consider a significant generalization of the online matching and budgeted allocation (AdWords) problems, where agents have concave utility functions. Building upon the work of Devanur and Jain who characterize the optimal competitive ratio as the solution to a differential equation, we design a constructive algorithm that is 1-1/e competitive using the primal-dual framework. We also show that if the online input is uniformly randomly ordered, a simple Greedy algorithm is 1-1/e competitive. This is joint work with Prof. Moses Charikar. Reading List: 1. (Book) T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, Third Edition. The MIT Press, 2009 2. Mehta, A., Saberi, A., Vazirani, U., and Vazirani, V. 2005. Adwords and generalized on-line matching. In FOCS 05 3. Karp, R. M., Vazirani, U. V., and Vazirani, V. V. 1990. An optimal algorithm for on-line bipartite matching. In STOC '90 4. Devanur, N. R. and Hayes, T. P. 2009. The adwords problem: online keyword matching with budgeted bidders under random permutations. In ACM Conference on Electronic Commerce 2009 5. N. Buchbinder, K. Jain, and J. S. Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In ESA’07 6. G. Goel and A. Mehta. Online budgeted matching in random input models with applications to adwords. In SODA ’08 7. N. Devanur, K. Jain and R. Kleinberg. Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching. In SODA ‘13 8. G. Aggarwal, G. Goel, C. Karande, and A. Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In SODA 2011 9. N. Devanur, K. Jain. Online Matching with Concave Returns. In STOC 2012 10. N. Devanur, Z. Huang. Primal Dual Gives Almost Optimal Energy Efficient Online Algorithms. In SODA 2014 11. N. Devanur. Online Algorithms with Stochastic Input. In ACM SIGEcom Exchanges, 2011

1 0

Ohad Fried presents Generals Thursday, May 15, 2014 at 3pm in Rm. 402
by Nicki Gotsis 08 May '14

08 May '14

Ohad Fried will present his General Exam on Thursday, May 15, 2014 at 3pm in Rm. 402. The members of his/her committee are Adam Finkelstein (advisor), Szymon Rusinkiewicz, Jianxiong Xiao. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Abstract: --------- Collections of objects such as images are often presented visually in a grid because it is a compact representation that lends itself well for search and exploration. Most grid layouts are sorted using very basic criteria, such as date or filename. We present a method to arrange collections of objects respecting an arbitrary distance measure. Pairwise distances are preserved as much as possible, while still producing the specific target arrangement which may be a 2D grid, the surface of a sphere, a hierarchy, or any other shape. We show that our method can be used for infographics, collection exploration, summarization, data visualization, and sound exploration. We present a fast algorithm that can work on large collections and quantitatively evaluate how well distances are preserved. Reading List: ------------- Book: Computer Graphics with OpenGL, 4th Ed., Hearn, Baker, and Carithers. Prentice Hall, 2010. ISBN: 978-0136053583. Papers: TENENBAUM, J. B., DE SILVA, V., AND LANGFORD, J. C. 2000. A global geometric framework for nonlinear dimensionality reduction. Science (New York, N.Y.) 290, 5500 (Dec.), 2319–23. ROWEIS, S. T., AND SAUL, L. K. 2000. Nonlinear dimensionality reduction by locally linear embedding. Science 290, 5500 (Dec.), 2323–6. XING, E. P., NG, A. Y., JORDAN, M. I., AND RUSSELL, S. 2003. Distance metric learning, with application to clustering with side-information. Advances in Neural Information Processing Systems 15, 505–512. QUADRIANTO, N., SMOLA, A. J., SONG, L., AND TUYTELAARS, T. 2010. Kernelized sorting. Transactions on Pattern Analysis and Machine Intelligence 32, 10 (Oct.), 1809–21. KUHN, H. 1955. The Hungarian Method for The Assignment Problem. Naval research logistics quarterly 2, 83–87. HUANG, S.-S., SHAMIR, A., SHEN, C.-H., ZHANG, H., SHEFFER, A., HU, S.-M., AND COHEN-OR, D. 2013. Qualitative organization of collections of shapes via quartet analysis. ACM Transactions on Graphics, 32(4). PLANT, W., AND SCHAEFER, G. 2010. Image Retrieval On The Honeycomb Image Browser. 17th IEEE International Conference on Image Processing (ICIP). SCHOEFFMANN, K., AND AHLSTROM, D. 2011. Similarity-Based Visualization for Image Browsing Revisited. International Symposium on Multimedia (Dec.), 422–427. TZANETAKIS, G., BENNING, M. S., NESS, S. R., MINIFIE, D., AND LIVINGSTON, N. 2009. Assistive music browsing using self-organizing maps. Proceedings of the 2nd International Conference on Pervasive Technologies Related to Assistive Environments - PETRA ’09, 1–7.

1 0

Yingfei Wang Generals: Thursday, May 15, 2014 at 1pm in Room 402
by Nicki Gotsis 08 May '14

08 May '14

Yingfei Wang will present the general exam on Thursday, May 15, 2014 at 1pm in Room 402 . Yingfei Wang's committee members are Warren Powell, Robert Schapire and David Blei. Everyone is invited to attend the talk and those faculty wishing to remain for the oral exam following are welcome to do so. Yingfei's abstract and reading list follow below: Abstract： We consider theoretical analysis, algorithm development and real world applications on optimizing sequential design-of-experiments problems. One goal can be to find the alternative with the best underlying average performance within a limited measurement budget, which is often addressed in online Bayesian Ranking and Selection Problems. We derived the first finite-time bound of the knowledge-gradient policy for ranking and selection problems under the condition that the value of information is submodular. We build a new, public-domain, Matlab-based testing environment for comparing a number of policies on a wide range of learning problems, providing the most comprehensive testbed that has yet appeared in the literature. We then consider decision making problems, motivated by applications in experimental science, in which the learner has the ability to repeatedly select a batch, that is, a multi-set of size B over M possible alternatives or a nested batch with the B alternatives sharing the same values of several controllable parameters, and then receives the payoffs for just the selected alternatives. The goal is to find out the one set of tunable control parameters that maximizes some utility function. We extend the sequential ranking and selection problem into a general framework for batch-mode learning and nested-batch-mode learning. By formulating the problem within a dynamic programming framework, we derive the Knowledge-Gradient variants to tackle both batch and nested-batch measurements. A Monte Carlo sampling procedure is applied to tackle intractable expectations computation. Readings: Stuart Russell and Peter Norvig, Artificial intelligence: a modern approach (Chapters 3, 4.1, 5, 7, 13-15, 17-18, 21), Sebastien Bubeck and Nicolo Cesa-bianchi, Regret Analysis of Stochastic and Non-stochastoc Multi-armed Bandit Problems (Chapters 1-5). Robert Schapire’s lecture notes for the course Theoretical Machine Learning. http://www.cs.princeton.edu/courses/archive/spring13/cos511/index.html John Gittins, Kevin Glazebrook, and Richard Weber, Multi-armed Bandit Allocation Indices end Edition (Chapter 2). Ilya Ryzhov, Warren Powell, and Peter Frazier, The knowledge gradient algorithm for a general class of online learning problems. Operations Research, 2012, 60(1): 180-195. Martijn Mes, Warren Powell, and Peter Frazier, Hierarchical knowledge gradient for sequential sampling. The Journal of Machine Learning Research, 2011, 12: 2931-2974. Peter Frazier, and Warren Powell, Consistency of sequential Bayesian sampling policies. SIAM Journal on Control and Optimization, 2011, 49(2): 712-731. Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer, Finite-time analysis of the multiarmed bandit problem. Machine learning, 2002, 47(2-3): 235-256. Daniel Golovin and Andreas Krause, Adaptive submodularity: A new approach to active learning and stochastic optimization. COLT. 2010: 333-345. Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire, The non-stochastic multi-armed bandit problem. SIAM Journal on Computing, 2002, 32(1): 48-77.

1 0

Linpeng Tang: General Exam Monday, May 12, 2014 at 10am in Room 402
by Nicki Gotsis 06 May '14

06 May '14

Linpeng Tang will present the General Exam on Monday, May 12, 2014 at 10am in Room 402. The members of Linpeng's committee are Kai Li, Mike Freedman and Vivek Pai. Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Linpeng's abstract and reading list follow below. Abstract An effective approach to improve the throughput of a static content delivery system, such as the Facebook’s photo-serving stack, is to build read-only storage caches on flash devices because they provide much higher random read throughput than disk drives and much larger capacity than DRAM. The key design challenge for these flash-based static content caches is that advanced caching algorithms generate many small random writes, even though all requests are reads, and the Flash Translation Layer on flash devices performs poorly with random writes, lowering throughput and decreasing device life- time. Coping strategies include under-utilizing the space on the device, which yields a smaller cache, or only using simple caching algorithms like FIFO, which yields lower hit ratios and decreases the utility of the cache. In this paper, we propose the novel RIPQ (Restricted Insertion Priority Queue) framework that solves this dilemma, allowing advanced caching algorithms with large cache sizes, high throughput, and long de- vice lifetime. RIPQ maintains an approximate priority queue efficiently on flash by aggregating small random writes into large writes to a restricted set of insertion points, lazily moving items, and co-locating items with similar priorities. We show that two families of advanced caching algorithms, Segmented-LRU and GDSF (Greedy-Dual-Size-Frequency), can be easily implemented with RIPQ. Our evaluation results on traces from Facebook’s photo-serving stack show that GDSF algorithms with RIPQ can improve cache hit ratios by ~20% over the current production system. Reading List Papers Beaver, Doug, et al. "Finding a Needle in Haystack: Facebook's Photo Storage." OSDI. Vol. 2010. 2010. Huang, Qi, et al. "An analysis of Facebook photo caching." Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles. ACM, 2013. Zhou, Yuanyuan, James Philbin, and Kai Li. "The Multi-Queue Replacement Algorithm for Second Level Buffer Caches." USENIX Annual Technical Conference, General Track. 2001. Min, Changwoo, et al. "SFS: Random write considered harmful in solid state drives." Proc. of the 10th USENIX Conf. on File and Storage Tech. 2012. Badam, Anirudh, et al. "HashCache: Cache Storage for the Next Billion." NSDI. Vol. 9. 2009. Lim, Hyeontaek, et al. "SILT: A memory-efficient, high-performance key-value store." Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles. ACM, 2011. Lee, Sang-Won, et al. "A log buffer-based flash translation layer using fully-associative sector translation." ACM Transactions on Embedded Computing Systems (TECS) 6.3 (2007): 18. Breslau, Lee, et al. "Web caching and Zipf-like distributions: Evidence and implications." INFOCOM'99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. Vol. 1. IEEE, 1999. Rosenblum, Mendel, and John K. Ousterhout. "The design and implementation of a log-structured file system." ACM Transactions on Computer Systems (TOCS) 10.1 (1992): 26-52. Cao, Pei, and Sandy Irani. "Cost-Aware WWW Proxy Caching Algorithms."Usenix symposium on internet technologies and systems. Vol. 12. No. 97. 1997. Book Tanenbaum, Andrew S. Modern operating systems. Prentice Hall Press, 2007. Chapter 2 Processes and Threads Chapter 3 Memory Management Chapter 4 File Systems Chapter 5 Input/Output

1 0