May 2007 - talks - lists.cs.princeton.edu

JiMin Song general exam
by Melissa M Lawson 10 May '07

10 May '07

JiMin's exam is at 10AM this morning. It was not mentioned in the talk announcement. Sorry!

1 0

C Kim general exam
by Melissa M Lawson 10 May '07

10 May '07

Chang Kim will present his research seminar/general exam on Tuesday May 15 at 10AM in Room 402. The members of his committee are Jennifer Rexford (advisor), Margaret Martonosi, and David August. 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. ---------------------------------- SEIZE: Scalable and Efficient Zero-configuration Enterprise Architecture Abstract Most conventional enterprise or campus networks consist of Ethernet-based IP subnets interconnected by routers. Although each subnet runs with minimal (or zero) configuration by virtue of Ethernet's flat-addressing and self-learning capability, interconnecting subnets at the IP-level introduces a significant amount of configuration and management overhead on both end-hosts and routers. The configuration problem becomes more serious as an enterprise network grows by merging multiple remote sites or by supporting a large number of mobile end-hosts. Deploying enterprise-wide Ethernet, however, cannot solve this problem because Ethernet bridging does not scale. As an alternative, we propose a scalable and efficient zero-configuration architecture (SEIZE) for enterprise networks. SEIZE provides "plug-and-play" capability via flat addressing and yet allows for scalability and efficiency through a combination of shortest-path routing and hash-based location resolution. Networking nodes perform location resolution on an on-demand basis and can cache the results to optimize routing paths and to avoid redundant resolution as well. We implemented a SEIZE prototype system using a collection of Click modular router elements and the XORP routing protocol daemon. For evaluation, we run the system on Emulab with real enterprise traffic traces. Our experiments show that SEIZE exhibits near-optimal path efficiency, while limiting the number of host information entries replicated over a network and reducing the control overhead as much as two orders of magnitude compared with the conventional Ethernet bridging. Papers 1. L. Kleinrock, and F. Kamoun, "Hierarchical Routing for Large Networks; Performance Evaluation and Optimization," Computer Networks vol. 1, 1977. 2. R. Perlman, " An Algorithm for Distributed Computation of a Spanning Tree in <http://www1.cs.columbia.edu/%7Eji/F02/ir02/p44-perlman.pdf> an Extended LAN," Proc. ninth Data Communications Symposium, 1985. 3. D. Peleg, and E. Upfal, " A Trade-Off between Space and Efficiency for Routing <http://portal.acm.org/ft_gateway.cfm?id=62217&type=pdf&coll=GUIDE&dl=GUIDE&… CFTOKEN=37897046> Tables," Journal of the ACM, 1989. 4. T. Rodeheffer, C. Thekkath, and D. Anderson, "SmartBridge: A scalable bridge architecture <http://www.sigcomm.org/sigcomm2000/conf/paper/sigcomm2000-6-2.pdf> ," Proc. ACM SIGCOMM, 2000. 5. Andy Myers, T. S. Eugene Ng, and H. Zhang, "Rethinking the Service Model: Scaling Ethernet to a Million <http://www.cs.cmu.edu/%7Eacm/papers/myers-hotnetsIII.pdf> Nodes," Proc. of HotNets-III, 2004. 6. R. Perlman, " <http://www.ieee-infocom.org/2004/Papers/26_1.PDF> Rbridges: Transparent routing," Proc. of IEEE Infocom, 2004. 7. S. Sharma, K. Gopalan, S. Nanda, and T. Chiueh, "Viking: <http://www.ieee-infocom.org/2004/Papers/47_3.PDF> A multi-spanning-tree Ethernet architecture for metropolitan area and cluster networks," Proc. of IEEE Infocom, 2004. 8. D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin, and R. Panigrahy, " Consistent hashing and random trees: distributed caching <http://www.akamai.com/dl/technical_publications/ConsistenHashingandRandomTr… CachingprotocolsforrelievingHotSpotsontheworldwideweb.pdf> protocol for relieving hot spots on the World Wide Web," Proc. ACM STOC, 1997. 9. J. Eriksson, M. Faloutsos, and S. Krishnamurthy, "PeerNet: Pushing Peer-to-Peer Down the Stack <http://iptps03.cs.berkeley.edu/final-papers/peernet.pdf> ," Proc. of International Workshop on Peer-to-Peer Systems, 2003. 10. D. Clark, R. Braden, A. Falk, and V. Pingali, "FARA: Reorganizing the addressing architecture <http://www.isi.edu/newarch/DOCUMENTS/FARA.FDNA03.pdf> ," Proc. of ACM SIGCOMM Workshop on Future Directions in Network Architecture, 2003. 11. M. Caesar, T. Condie, J. Kannan, K. Lakshminarayanan, I. Stoica, and S. Shenker, "ROFL: Routing on Flat Labels <http://project-iris.net/irisbib/papers/flatlabels:sigcomm2006/paper.pdf> ," Proc. of ACM SIGCOMM, 2006. 12. M. Caesar, M. Castro, E. Nightingale, Gerg O, and A. Rowstron, "Virtual Ring Routing: Network Routing Inspired by <http://www.sigcomm.org/sigcomm2006/discussion/getpaper.php?paper_id=33> DHTs," Proc. of ACM SIGCOMM, 2006. Textbooks 1. L. Peterson, and B. Davie, Computer Networks: A Systems Approach, Morgan Kaufmann, 3e, 2003 2. R. Perlman, Interconnections: Bridges, Routers, Switches, and Internetworking Protocols, Addison-Wesley, 2e, 1999

1 0

J Song general exam
by Melissa M Lawson 10 May '07

10 May '07

JiMin Song will present her research seminar/general exam on Thursday May 10 in Room 302 (note room!). The members of her committee are: Mona Singh (advisor), Olga Troyanskaya, and Tom Funkhouser. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. -------------------------------- Abstract Protein interactions play a key role in almost all biological processes. Recently, high-throughput experiments have uncovered large networks of protein-protein interactions for several species, including human, fruit fly and yeast. It has been postulated that analysis of these protein interaction maps should provide hints to the cell's higher-level organization, and help uncover protein functions, complexes and pathways. A protein-protein interaction network is considered as an undirected graph such that nodes are proteins and edges are interactions between two proteins. Graph clustering methods provide one way for analyzing these networks in order to uncover functional modules and protein complexes. I introduce an evaluation framework for analyzing graph clustering methods. I consider six different evaluation measures, taking into account biological process, cellular component, and protein complex annotations, to compare four diverse graph clustering algorithms. I selected four graph clustering methods, a spectral clustering method, a Markov clustering method, a density-periphery based clustering method, and a clique-finding clustering method. I find that the clique-finding clustering method consistently out performs the others, suggesting that future research along these lines should focus on methods with similar properties. Reading list Textbook: Bioinformatics by Mount - Chapters: 3, 4, 5, 7, 10. Papers: - E Alm and AP Arkin, Biological networks, Curr. Opin. Struct. Biol 2003 - LH Hartwell et al, From molecular to modular cell biology, Nature 1999 - Spirin and Mirny, Protein complexes and functional modules in molecular networks, PNAS 2003 - Sharan et al, Network-based prediction of protein function, EMBO 2007 - Newman, Modularity and community structure in networks, PNAS 2006 - Enright et al, An efficient algorithm for large-scale detection of protein families, NAR 2002 - Altaf-Ul-Amin, Development and implementation of an algorithm for detection of protein complexes in large interaction networks, BMC Bioinformatics 2006 - Palla et al, Uncovering the overlapping community structure of complex networks in nature and society, Nature 2005 - Brohee and van Helden, Evaluation of clustering algorithms for protein-protein interaction networks, BMC Bioinformatics 2006

2 1

A Feldman general exam
by Melissa M Lawson 09 May '07

09 May '07

Ari Feldman will present his research seminar/general exam on Tuesday May 15 at 2PM in Room 402. The members of his committee are Ed Felten (advisor), Andrew Appel, and David Walker. 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. ----------------------------------- Security Analysis of the Diebold AccuVote-TS Voting Machine The Diebold AccuVote-TS is the most widely deployed electronic voting platform in the United States. It belongs to a class of voting systems known as Direct Recording Electronic (DRE) voting machines, which are essentially general-purpose computers running specialized software that displays the ballots, records each voter's choices, and tabulates the votes. Since, on DREs, the most important parts of the voting process depend entirely on software, the possibility that malicious software could be installed on them poses a grave threat to the accuracy and trustworthiness of elections. Although computer scientists have long recognized the threat of malicious code to DREs, election officials and policy-makers have, until recently, been slow to accept it. Moreover, often attention in this area has focused on the threat posed by a malicious developer employed by a voting machine manufacturer. In this talk, I describe how malicious software running on a single AccuVote-TS can steal votes with little if any risk of detection. The malicious software can modify all of the records, audit logs, and counters kept by the voting machine, so that even careful forensic examination of these records will find nothing amiss. I also show how anyone who has physical access to a voting machine, or to a memory card that will later be inserted into a machine, can install malicious code in as little as one minute. Furthermore, I explain how the AccuVote-TS is susceptible to viruses that can spread a vote-stealing payload automatically from machine to machine during normal pre- and post-election activity. Finally, I discuss the following strategies for mitigating the threat of malicious software on voting machines: hardware modifications, limiting access to voting machines and memory cards, parallel testing, whole system certification, and software independent design. I argue that, of these, only software independent design can provide an acceptable level of security. Reading List: Books Niels Ferguson, Bruce Schneier. Practical Cryptography. Indianapolis: Wiley, 2003. Matt Bishop. Computer Security. Addison-Wesley, 2003. Chapters 1-3, 10, 12-14, 20, 22-24, 29. Papers William A. Arbaugh, David J. Farber, Jonathan M. Smith. A Secure and Reliable Bootstrap Architecture. Available at: http://www.cs.umd.edu/~waa/pubs/oakland97.pdf. Arel Cordero, David Wagner, David Dill. The Role of Dice in Election Audits -- Extended Abstract. Available at: http://www.cs.berkeley.edu/~daw/papers/dice-wote06.pdf. June 2006. Douglas W. Jones. Counting Mark-Sense Ballots. 2003. Available at: http://www.cs.uiowa.edu/~jones/voting/optical/. Douglas W. Jones. Voting on Paper Ballots. Available at: http://www.cs.uiowa.edu/~jones/voting/paper.html. Chris Karlof, Naveen Sastry, David Wagner. Cryptographic Voting Protocols: A Systems Perspective. Available at: http://www.cs.berkeley.edu/~daw/papers/neffchaum-usenix05.pdf. Tadayoshi Kohno, Adam Stubblefield, Aviel D. Rubin, Dan S. Wallach. Analysis of an Electronic Voting System. February 2004. Available at: http://avirubin.com/vote.pdf. C. Andrew Neff. Practical High Certainty Intent Verification for Encrypted Votes. Available at: http://www.votehere.com/vhti/documentation/vsv-2.0.3638.pdf. October 2004. C. Andrew Neff. Verifiable Mixing (Shuffling) of ElGamal Pairs. Available at: http://www.votehere.com/vhti/documentation/egshuf-2.0.3638.pdf. April 2004. Lawrence Norden et al. The Machinery of Democracy: Voting System Security Accessibility, Usability, and Cost. Brennan Center for Justice. pp. 38-121 (Accessibility, Usability). Available at: http://www.brennancenter.org/dynamic/subpages/download_file_38150.pdf. Stefan Popoveniuc, Ben Hosp. An Introduction to Punchscan. Available at: http://www.punchscan.org/papers/ popoveniuc_hosp_punchscan_introduction.pdf. October 2006. Ronald L. Rivest. On Estimating The Size of a Statistical Audit. Available at: http://theory.lcs.mit.edu/~rivest/Rivest- OnEstimatingTheSizeOfAStatisticalAudit.pdf. November 2006. Ronald L. Rivest, John P. Wack. On the notion of "software independence" in voting systems. Available at: http://vote.nist.gov/SI-in-voting.pdf. July 2006. Naveen Sastry, Tadayoshi Kohno, David Wagner. Designing Voting Machines for Verification. Available at: http://www.cs.berkeley.edu/~daw/papers/varch-use06.pdf.

1 0

A Agarwal preFPO
by Melissa M Lawson 08 May '07

08 May '07

Amit Agarwal will present his preFPO on Monday May 14 at 3:30PM in Room 302 (note room!). The members of his committee are: Moses Charikar, advisor; Rob Schapire and Sanjeev Khanna (U Penn), readers; Ken Steiglitz and Bob Tarjan, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------------------- Optimization has emerged as a field of central importance for its practical applications in operations research, physics, chemistry, applied mathematics, and computer science. As our understanding of optimization has deepened, it has emerged that several important optimization problems are difficult to solve exactly in reasonable amount of time, assuming widely believed complexity assumptions. The natural approach in such cases is to obtain approximate solutions. There is a huge body of work towards designing algorithms with provable guarantees about their sub-optimality. In general, two kinds of error estimation techniques have been evolved for such problems: multiplicative and additive. In the study of approximation algorithms one typically looks for multiplicative approximation to problems which are NP-hard. On the other hand, results in the field of online optimization typically have additive errors. The latter work also has connections to machine learning and statistics. I will present three results in the broad area of approximate optimization: (i) The first result is on improved approximation for directed cut problems from joint work with Noga Alon and Moses Charikar. (ii) The second result bridges the field of approximation algorithms and network coding theory. We show that certain integrality gaps studied by the approximation algorithms community are the same as certain parameters in network coding. This is joint work with Moses Charikar. (iii) Finally we present faster algorithms for online optimization with applications to portfolio management. This is based on papers with Elad Hazan, Robert Schapire, Satyen Kale, and Adam Kalai.

1 0

Q Xi general exam
by Melissa M Lawson 08 May '07

08 May '07

Qian Xi will present her research seminar/general exam on Monday May 14 at 10:30AM in Room 402. The members of her committee are JP Singh (advisor), David August, and Vivek Pai. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. ----------------------------------------------------------------------------- Abstract: Writing multi-threaded programs on chip multi-processors is a challenge. Because of the runtime unpredictability, access to shared data should be arranged carefully to guarantee correctness and efficiency. Lock-based mechanisms are conventional ways to provide mutual exclusion, but locks aren't easy to manage and they can cause serious problems such as deadlock. Maurice Herlihy et al. proposed a lock-free data structure called Transactional Memory (TM) to eliminate the problems induced by locks. TM systems have received a lot of interest recently due to advent of multi-core processors, and due to a widespread belief that TM provides a higher-level and less error-prone parallel programming model than locks, while still achieving comparable performance. Most TM implementations have used toy or kernel benchmarks to measure performance, and almost exclusively small data structures. This benchmarks gave little insight into how real applications will behave with TM. In this project, we present a CMP benchmark suite implemented in software TM (STM), containing both kernel and real application level programs, from scientific computing and multimedia domains. We aim not only to understand performance profiles under STM relative to the more conventional threads+locks programming model, but more importantly, to understand whether STM is a preferable interface for programming on CMP. In the current experimental study, we find that STM achieves good performance, nearly the same as lock-based mechanisms, for small sizes of shared data. On the other hand, programs with large shared data size incur a loss of performance for several reasons in STM. Then, from a programmer's aspect of view, we summarize the benefits and drawbacks of current STM systems while writing parallel programs. We also compare interfaces of different STM implementations and comment on appropriate STM primitives for parallel programming. Readling list: Book: David E. Culler, Jaswinder Pal Singh, Anoop Gupta. Parallel Computer Architecture: A Hardware/Software Approach (2nd edition) Papers: - Maurice Herlihy, J. Eliot B. Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. Proceedings of the 20th International Symposium in Computer Architecture, 1993, pp. 289300. - Nir Shavit, Dan Touitou. Software Transactional Memory. Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing , 1995, pp. 204-213. - Kunle Olukotun, Basem A. Nayfeh, Lance Hammond, Ken Wilson, and Kunyung Chang. The Case for a Single-Chip Multiprocessor. ACM SIGOPS Operating Systems Review, 1996, pp. 2-10. - Austen McDonald et al. Characterization of TCC on Chip-Multiprocessors. Proceedings of the 14th International Conference on Parallel Architecture and Compilation Techniques, 2005. - Kevin E. Moore et al. LogTM: Log-based Transactional Memory. Proceedings of the 12th Annual International Symposium on High Performance Computer Architecture, 2006. - Tim Harris, Simon Marlow, Simon Peyton Jones, Maurice Herlihy. Composable Memory Transactions. ACM Conference on Principles and Practice of Parallel Programming 2005. - Maurice Herlihy, Victor Luchangco, Mark Moir, William Scherer. Software Transactional Memory for Dynamic-Sized Data Structures. Proceedings of the 22nd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2003. - Austen McDonald et al. Architectural Semantics for Practical Transactional Memory. Proceedings of the 33rd annual international symposium on Computer Architecture, 2006.

1 0

X Ma general exam
by Melissa M Lawson 03 May '07

03 May '07

Xiaojuan Ma will present her research seminar/general exam on Wednesday May 9 at 10 AM in Room 301 (note room!). The members of her committee are Fei-Fei Li, Szymon Rusinkiewicz, Tom Funkhouser. Her advisor is Perry Cook. Everyone is invited to attend her talk, and those faculty members wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. -------------------------------------------- Abstract: Assistive devices and tools for persons with aphasia, a debilitating condition that robs an individual of the ability to communicate, have traditionally depended on icons to convey the meaning of words that the individuals have lost. Despite the predominant use of icons, which are created by artists, speech language pathologists suggest that personal digital photographs may be easier for people to map to the real phenomena. Also, compared to other visual art resources such as icons, images are cheaper, ubiquitous, numerous, and varied. A concept of picture-as-language, which uses digital photographs as a language has shown some significant and long-lasting effects on the learning for people with mental retardation, developmental disabilities, or learning disabilities. Designing for a population that relies heavily on picture representations, it is important to understand to what extent the choice of icons and images affects the adoption and usability of assistive technology. A study with unimpaired members of an older demographic likely to be affected by aphasia shows that, for sentences with words replaced by either images or icons, the word-level and sentence-level meaning are retained equally well for both images and icons. It is also supported by a further study with our target group, people with aphasia, on the effectiveness of icons and images on conveying noun concepts. However, compared to concrete nouns, both studies showed that neither icons or images performed as well on abstract nouns. What's more, the study with senior citizens revealed that both icons and images did a poor job of embodying verbs and attributes. A third study evaluating the efficacy of four different visual representations of verbs for subjects from the general population addressed the question of the best representation of both motion and abstract verbs. Related video and image database for verb illustrations is under construction. Books: Preece, J., Rogers, Y., and Sharp, H. Interaction Design: Beyond Human-Computer Interaction. New York: John Wiley & Sons, Inc., 2002. Shneiderman, B. Designing the User Interface: Strategies for Effective Human-Computer Interaction. Boston: Addison Wesley, 1997. Chapters: 1-4, 10, 11 Papers: Newell A.F., Carmichael, A., Gregor, P., and Alm, N. Information Technology for Cognitive Support. The Human-Computer Interaction Handbook, Jacko, J. and Sears, A. (Editors). Mahwah, NJ: Lawrence Erlbaum Associates, Inc, 2002. 464-481. R. D. Steele, M. Weinrich, R. T. Wertz, M. K. Kleczewska, and G. S. Carlson. Computer-Based Visual Communication in Aphasia. Neuropsychologia, 27(4):409-426, 1989. van de Sandt-Koenderman, M. W. M. E. High-tech AAC and aphasia: widening horizons? Aphasiology (2004), 18 (3), 245-263. Baecker, R., Small, I., and Mander, R. Bringing Icons to Life. Proceedings of CHI '91 Human Factors in Computing Systems. New York: ACM, 1991, pp. 1-6. J. L. Boyd-Graber, S. S. Nikolova, K. A. Moffatt, K. C. Kin, J. Y. Lee, L.W. Mackey, M. M. Tremaine, and M. M. Klawe. Participatory design with proxies: Developing a desktop-PDA system to support people with aphasia. In Proc. CHI2006, pages 151-160. ACM Press, 2006. K. Tee, K. Moffatt, L. Findlater, E. MacGregor, J. Mc-Grenere, B. Purves, and S. S. Fels. A visual recipe book for persons with language impairments. In Proc. CHI 2005, pages 501-510. ACM Press, 2005. Danielsson, H. and Svensk. A. Digital Pictures as Cognitive Assistance. In Proceedings of the 6th European Conference for the Advancement of Assitive Technology, 2001. (5 pages) R. Mihalcea and B. Leong. Toward communicating simple sentences using pictoral representations. In Proc. of the Conf. of the Assoc. for Machine Translation in the Americas 2006, Boston, MA, 2006. T. Takasaki. Pictnet: Semantic infrastructure for pictogram communication. In P. Sojka, K.-S. Choi, C. Fellbaum, and P. Vossen, editors, Proc. Global WordNet Conference 2006, pages 276-289. GlobalWordNet Association, January 2006. Pettersson, Rune. Interpretation of Image Content. Educational Communication and Technology Journal, v36 n1 p45-55 Spr 1988.

1 0

Y Shao FPO
by Melissa M Lawson 03 May '07

03 May '07

Yilei Shao will present her FPO on Thursday May 10 at 10:30AM in Room 402. The members of her committee are: Andrea LaPaugh, advisor; J.P. Singh and Moses Charikar, readers; Kai Li and Jennifer Rexford, nonreaders. A copy of her thesis "Exploring Social Networks in Computer Science" is on display in Room 310. Everyone is invited to attend her talk.

1 0

T O'Connor general exam
by Melissa M Lawson 03 May '07

03 May '07

Tim O'Connor will present his research seminar/general exam on Thursday May 10 at 2PM in Room 302 (note room!). The members of his committee are: Manuel Llinas (Molecular Biology, advisor), Olga Troyanskaya, and 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 Plasmodium falciparum is the causative agent of the most virulent strain of malaria, a disease that causes over one million deaths per year. Recently, this organism's genome was sequenced, but only a minority of the genes have known function, with an even smaller proportion having any detailed functional description. While manual examination of individual genes continually expands this functional knowledge base, it is a both slow and expensive way to tackle the roughly 3000 uncharacterized genes. By identifying functionally described genes related to an unknown query gene, the biological processes in which that query gene is involved can be elucidated. Several computational methods that integrate multiple, genome-wide data sets have been developed to identify functional relationships between pairs of genes. The problem of identifying functional relationships turns into a supervised machine learning problem with two class labels. Several methods can address the problem, including logistic regression, kernel methods and support vector machines, neural networks, and Bayesian networks. Our method of data integration is through the use of statistical inference with Bayesian networks, permitting multiple datasets of different types to be integrated in a way that can incorporate prior knowledge. To train the network, a benchmark gold standard of known or high confidence interactions was developed for P. falciparum. The class labels in the gold standard were obtained first from the Gene Ontology (GO) consortium using GRIFn's expert-derived approach. Secondly, labels were derived from the Malaria Parasite Metabolic Pathways (MPMP) database, which is a manually curated version of the Kyoto Encyclopedia of Genes and Genomes (KEGG) Pathways database specifically for P falciparum. Forty-th ree diverse datasets including features based on DNA sequence, comparative genomics, RNA expression profiles, and growth perturbation experiments were used as input with the predictor's parameters trained using the expectation-maximization algorithm. Functional relationship prediction accuracy was estimated using cross validation with an ROC curve of comparable to accuracy to a similar approach for yeast, which is a much more well characterized organism. The resulting predictions have been analyzed to assess the scope of the uncharacterized genome fraction which can be shown to be related to known biological processes. These predictions have also been compared to those done in yeast showing only two highly similar processes of protein synthesis and protein degradation. The predictions will be made accessible through a graphical web interface. Prior work Date, S.V. & Stoeckert, C.J., Jr. Computational modeling of the Plasmodium falciparum interactome reveals protein function on a genome-wide scale. Genome Res. 2006 Apr;16(4):542-9. Epub 2006 Mar 6. Wuchty S, Ipsaro JJ. A Draft of Protein Interactions in the Malaria Parasite P. falciparum. J Proteome Res. 2007 Feb 15 Data Integration Troyanskaya OG, Dolinski K, Owen AB, Altman RB, and Botstein D. A Bayesian framework for combining heterogeneous data sources for gene function prediction (in S. cerevisiae). Proc Natl Acad Sci USA 100(14): 8348-53, 2003. Myers CL, Robson D, Wible A, Hibbs MA, Chiriac C, Theesfeld CL, Dolinski K, Troyanskaya OG. Discovery of biological networks from diverse functional genomic data. Genome Biology6(13):R114, 2005. Russell S, Norvig P (1995) Artificial Intelligence: A Modern Approach, Prentice Hall Series in Artificial Intelligence. Englewood Cliffs, New Jersey. Chapter 20:Statistical Learning Methods Hastie T, Tibshirani R, Friedman J (2001). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Series in Statistics. Chapter 8:Model Inference and Averaging. Gold Standard & Data Processing Myers CL, Barrett D, Hibbs MA, Huttenhower C, Troyanskaya OG. Finding function: evaluation methods for functional genomic data. BMC Genomics 2006, 7:187. Ginsburg H. Progress in in silico functional genomics: the malaria Metabolic Pathways database. Trends Parasitol. 2006 Jun;22(6):238-40. Storey JD, Xiao W, Leek JT, Tompkins RG, and Davis RW. (2005) Significance analysis of time course microarray experiments. Proceedings of the National Academy of Sciences, 102: 12837-12842. Plasmodium Gardner MJ, Hall N, Fung E, White O, et al. Genome sequence of the human malaria parasite Plasmodium falciparum. Nature. 2002 Oct 3;419(6906):498-511. Bozdech Z, Llinas M, Pulliam BL, Wong ED, Zhu J, DeRisi JL. The transcriptome of the intraerythrocytic developmental cycle of Plasmodium falciparum. PLoS Biol. 2003 Oct;1(1):E5.

1 0

W Dong general exam
by Melissa M Lawson 03 May '07

03 May '07

Wei Dong will present his research seminar/general exam on Wednesday May 9 at 2PM in Room 301 (note room!) The members of his committee are: Kai Li (advisor), Moses Charikar, and Andrea LaPaugh. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His final abstract and reading list appear below. ---------------------------------------- Abstract K-Nearest Neighbor (K-NN) search on high dimensional feature vectors is the principal problem underlying content based similarity search systems. The recently developed Locality Sensitive Hashing approach has advantages over traditional space partitioning methods, which suffer from the curse of dimensionality. In this project we aim at addressing some practical issues when applying LSH to a real system. First, we propose an LSH based compact representation of feature vectors (aka sketch). We have been using main memory indices of feature vectors to reduce access time. By keeping sketches in place of the original feature vectors, we can significantly reduce the memory overhead and maintain high precision and low query time. Second, we study the geometric and statistical characteristics of different data sets and identify some common properties with a set of associated parameters. Basing on that we build a performance model of LSH, making it possible to tune the parameters of LSH automatically. Finally, we show that local geometric properties have a non-trivial impact on query results. A fixed set of parameters optimized for the global average can still yield poor results on some of the queries. We address this problem by adaptively guiding the search process of each query using partial results seen so far. Reading List Text book: Tanenbaum, Modern Operating Systems Hector Garcia, Jeffrey Ullman, Jennifer Widom, Database Systems The Complete Book, Chapter 11-14 Papers: Bohm, C.; Berchtold, S. & Keim, D. A. (2001), 'Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases', /ACM Comput. Surv./ *33*(3), 322--373. Bawa, M.; Condie, T. & Ganesan, P. (2005),LSH forest: self-tuning indexes for similarity search, /in /'WWW '05: Proceedings of the 14th international conference on World Wide Web', ACM Press, New York, NY, USA, pp. 651--660. Datar, M.; Immorlica, N.; Indyk, P. & Mirrokni, V. S. (2004),Locality-sensitive hashing scheme based on p-stable distributions, /in /'SCG '04: Proceedings of the twentieth annual symposium on Computational geometry', ACM Press, New York, NY, USA, pp. 253--262. Indyk, P. & Motwani, R. (1998),Approximate nearest neighbors: towards removing the curse of dimensionality, /in /'STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing', ACM Press, New York, NY, USA, pp. 604--613. Lv, Q.; Josephson, W.; Wang, Z.; Charikar, M.; Li, K.(2006) Efficient Filtering with Sketches in the Ferret Toolkit. In Proceedings of the 8th ACM SIGMM International Workshop on Multimedia Information Retrieval (MIR). Santa Barbara, CA, USA. October 2006. Lv, Q.; Josephson, W.; Wang, Z.; Charikar, M.; Li, K.(2006) A Time-Space Efficient Locality Sensitive Hashing Method for Similarity Search in High Dimensions. Technical report. ftp://ftp.cs.princeton.edu/techreports/2006/759.pdf Panigrahy, R. (2006),Entropy based nearest neighbor search in high dimensions, /in /'SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm', ACM Press, New York, NY, USA, pp. 1186--1195. Weber, R.; Schek, H. & Blott, S. (1998),A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, /in /'VLDB '98: Proceedings of the 24rd International Conference on Very Large Data Bases', Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, pp. 194--205. Henzinger, M. 2006. Finding near-duplicate web pages: a large-scale evaluation of algorithms. In Proceedings of the 29th Annual international ACM SIGIR Conference on Research and Development in information Retrieval

1 0