Andrea Pietracaprina's Research Activities


Areas of Interest

  • MapReduce Algorithmics
  • Data Mining
  • High-Performance Computing: Models, Algorithms and Data Structures
  • Interconnection Networks and Routing

Current Projects

  • BiD-Algo: Big Data Algorithmics. University of Padova: 2013-2015 (Principal Investigator)
  • AMANDA: Algorithmics for MAssive and Networked DAta. MIUR-PRIN: 2014-2017 (Padova-Site Leader)

Program Committees

  • European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (PKDD) 2015: PC Member
  • ACM International Conference on Computing Frontiers 2015: PC Member
  • Int. EURO-PAR Conference 2014: Global Chair of Topic 12 "Theory and Algorithms for Parallel Computation"
  • ICALP (Int. Colloquium on Automata, Languages, and Programming) 2014: PC Member (Track C)
  • IC3 (Int. Conference on Contemporary Computing) 2011: PC Member
  • SPIRE (Int. Symposium on String Processing and Information Retrieval) 2011: PC Member
  • HPPD-DM (Int. Conf. on High Performance Computing & Simulation. Special Session on High Performance Parallel and Distributed Data Mining) 2011: PC Member
  • HPPD-DM (Int. Conf. on High Performance Computing & Simulation. Special Session on High Performance Parallel and Distributed Data Mining) 2010: PC Member
  • ACM International Conference on Computing Frontiers 2010: PC Member
  • IPDPS (IEEE International Parallel and Distributed Processing Symposium) 2010: PC member
  • International EURO-PAR Conference 2009. Global Chair of Topic 12 "Theory and Algorithms for Parallel Computation"
  • HPPC (Workshop on Highly Parallel Processing on a Chip) 2008: PC member
  • SPAA (ACM Symposium on Parallelism in Algorithms and Architectures) 2008: PC member
  • IPDPS (IEEE International Parallel and Distributed Processing Symposium) 2008: PC member
  • HPPC (Workshop on Highly Parallel Processing on a Chip) 2007: PC member
  • PACT (Parallel Architectures and Compilation Techniques) 2007: PC member
  • I-SPAN (International Symposium on Parallel Architectures, Algorithms, and Networks) 2005: PC member
  • SPAA (ACM Symposium on Parallelism in Algorithms and Architectures) 2005: PC member
  • HLPP (International Workshop on High-level Parallel Programming and Applications) 2005: PC member
  • International EURO-PAR Conference 2005: Global Chair of Topic 12 "Theory and Algorithms for Parallel Computation"
  • WEA (International Workshop on Efficient and Experimental Algorithms) 2005: PC member
  • FUN (International Conference on FUN with Algorithms) 2004: PC member
  • International EURO-PAR Conference 2004: PC member
  • PDCN (Iasted International Conference on Parallel and Distributed Computing and Networks) 2004: PC member
  • ICTCS (Italian Conference on Theoretical Computer Science) 2003: PC member
  • SPAA (ACM Symposium on Parallel Algorithms and Architectures) 2002: PC member
  • International EURO-PAR Conference 1998: PC member
Other Committees

  • ICALP (International Colloquium on Automata, Languages and Programming) 2006: Co-Chair of Organizing Committee for Satellite Events
  • International EURO-PAR Conference (1999-present): member of Advisory Board
  • SPAA (ACM Symposium on Parallel Algorithms and Architectures) 1996: member of the Organizing Committee
  • ESA (European Symposium on Algorithms) 1998: member of the Organizing Committee and co-editor of the Proceedings
  • 1st Italian-Israeli Workshop on Algorithmic Aspects of Molecular Biology, Padova, I, December 1994: Member of the Organizing Committee

Editorial Boards

  • Elsevier Journal of Discrete Algorithms: Editor (2010-2014)
  • IEEE Transactions on Parallel and Distributed Computing:   Associate Editor (2004-2009)
  • Theoretical Computer Science: Guest Co-Editor of Special Issue in honour of F. Preparata

Current PhD Students and PostDocs


Publications

Please note that the copyrights of the papers with full citations
have been signed over to the publishers.

Book Chapters

  • G. Bilardi, A. Pietracaprina. Theoretical Models of Computation. Encyclopedia of Parallel Computing, Springer 2011: 1150-1158. Publisher's page.
  • N.M. Amato, D.T. Lee, A. Pietracaprina, R. Tamassia (eds). Excursions in Algorithmics: A Collection of Papers in Honor of Franco P. Preparata. Preface. Special Issue of Theoretical Computer Science 408(2-3):97-98, 2008.
  • G. Bilardi, A. Pietracaprina, and G. Pucci. Decomposable BSP: A Bandwidth-Latency Model for Parallel and Hierarchical Computation. In Handbook of Parallel Computing (J. Reif and S. Rajasekaran Eds.), CRC Press, Boca Raton Fl USA, 2007. Publisher's page.
  • G. Bilardi, G. Italiano, A. Pietracaprina and G. Pucci (eds). Algorithms - ESA'98. Proceedings of the 6th Annual European Symposium. LNCS 1461, Springer Verlag, Berlin, D, 1998.
Journal Papers

  • N. Lazzarini, L. Nanni, C. Fantozzi, A. Pietracaprina, G. Pucci, T.M. Seccia, G.P. Rossi. Heterogeneous Machine Learning System for Diagnosing Primary Aldosteronism. Journal of Hypertension (e-supplement) 31:e409, 2013. (IF:4.021.) Also in Proc. European Meeting on Hypertension and Cardiovascular Protection (ESH13) (Poster Session), Milan I, June 2013.
  • A. Pettarin, A. Pietracaprina, and G. Pucci. On the Expansion and Diameter of Bluetooth-like Topologies. Theory of Computing Systems 52(2):319-339, 2013. (IF:0.442.)
  • A. Kirsch, M. Mitzenmacher, A. Pietracaprina, G. Pucci, E. Upfal, and F. Vandin. An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets. Journal of the ACM 59(3):12-1-12-22, 2012. (IF:2.717.)
  • R. Grossi, A. Pietracaprina, N. Pisanti, G. Pucci, E. Upfal, and F. Vandin. MADMX: A Strategy for Maximal Dense Motif Extraction. Journal of Computational Biology, 18(4):535-545, 2011. (IF:1.694.)
  • S. Nasso, F. Silvestri, F. Tisiot, B. DI Camillo, A. Pietracaprina, G. Toffolo. An optimized data structure for high-throughput 3D proteomics data: mzRTree.Journal of Proteomics 73:1176-1182. (IF:5.074)
  • A. Pietracaprina, M. Riondato, E. Upfal, F. Vandin. Mining Top-K Frequent Itemsets Through Progressive Sampling. Data Min. Knowl. Discov. 21(2): 310-326, 2010. (IF: 1.238)
  • P. Crescenzi, C. Nocentini, A. Pietracaprina, and G. Pucci. On the Connectivity of Bluetooth-Based Ad Hoc Networks. Concurrency and Computation: Practice and Experience 21(7): 875-887, 2009. Special Issue on EURO-PAR'07. (IF:1.791)
  • P. Bertasi, M. Bianco, A. Pietracaprina, G. Pucci. Obtaining Performance Measures through Microbenchmarking in a Peer-to-Peer Overlay Computer. International Journal of Computational Intelligence Research. 4(1), 2008.
  • K.T. Herley, A. Pietracaprina, and G. Pucci. Store-and-Forward Multicast Routing on the Mesh. Theory of Computing Systems, (42):519-535, 2008. (IF:0.766)
  • C. Fantozzi, A. Pietracaprina, and G. Pucci. Translating Submachine Locality into Locality of Reference. Journal of Parallel and Distributed Computing 66(5):633-646, 2006. Special issue on the four Best Papers of IPDPS. (IF: 1.168)
  • G. Bilardi, K.T. Herley, A. Pietracaprina, and G. Pucci. On Stalling in LogP. Journal of Parallel and Distributed Computing 65(3):307-312, 2005. (IF: 1.168)
  • A. Pietracaprina and G. Pucci. Optimal Many-to-One Routing on the Mesh with Constant Queues. Information Processing Letters 96(1):24-29, 2005. (IF:1.504)
  • C. Fantozzi, A. Pietracaprina, and G. Pucci. A General PRAM Simulation Scheme for Clustered Machines. Int.l Journal on Foundations of Computer Science 14(6):1147-1164, 2003. (IF: 0.554)
  • K. Herley, A. Pietracaprina, and G. Pucci. Deterministic parallel backtrack search. Theoretical Computer Science, 270(1-2):309-324, 2002.(IF:0.806)
  • R. Grossi, A. Pietracaprina, and G. Pucci. Optimal deterministic protocols for mobile robots on a grid. Information and Computation, 173(2):132-142, 2002.(IF:1.504)
  • K.T. Herley, A. Pietracaprina, and G. Pucci. Implementing shared memory on mesh-connected computers and on the fat-tree. Information and Computation, 165(2):123-143, 2001. (IF:1.504)
  • A. Pietracaprina, G. Pucci, and J. Sibeyn. Constructive, deterministic implementation of shared memory on meshes. SIAM Journal on Computing, 30(2):625-648, 2000. (IF: 1.459)
  • K.T. Herley, A. Pietracaprina, and G. Pucci. Deterministic branch-and-bound on distributed memory machines. International Journal of Foundations of Computer Science, 10(4):391-404, 1999. Special Issue for IRREGULAR'99. (IF: 0.554)
  • K.T. Herley, A. Pietracaprina, and G. Pucci. Fast deterministic parallel branch-and-bound. Parallel Processing Letters, 9(3):325-334, 1999.
  • G. Bilardi, K.T. Herley, A. Pietracaprina, G. Pucci, and P. Spirakis. BSP versus LogP. Algorithmica, 24:405-422, 1999. Special Issue on Coarse Grained Parallel Algorithms. (IF: 0.825)
  • A. Baumker, W. Dittrich, and A. Pietracaprina. The complexity of parallel multisearch on coarse grained machines. Algoritmica, 24:209-242, 1999. Special Issue on Coarse Grained Parallel Algorithms.
  • A. Pietracaprina and G. Pucci. The complexity of deterministic PRAM simulation on distributed memory machines. Theory of Computing Systems, 30(3):231-247, 1997. (IF:0.442)
  • A. Pietracaprina and F.P. Preparata. Practical constructive schemes for deterministic shared-memory access. Theory of Computing Systems, Special Issue for SPAA'93, 30(1):3-37, Jan/Feb 1997. (IF:0.442)
  • A. Krishna, A. Pietracaprina, and B. Hajek. Sharper analysis of packet routing on a butterfly. Networks, 24(2):91-101, 1994. (IF: 0.645)
  • F. Luccio, A. Pietracaprina, and G. Pucci. Analysis and implementation of parallel uniform hashing. International Journal of Foundations of Computer Science, 3(1):55-63, 1992. (IF: 0.554)
  • F. Luccio, A. Pietracaprina, and G. Pucci. Analysis of parallel uniform hashing. Information Processing Letters, 37:67-69, 1991. (IF:0.706)
  • F. Luccio, A. Pietracaprina, and G. Pucci. A new scheme for the deterministic simulation of PRAMs in VLSI. Algorithmica, 5(4):529-544, 1990. (IF: 0.825)
  • F. Luccio, A. Pietracaprina, and G. Pucci. A probabilistic simulation of PRAMs on a bounded degree network. Information Processing Letters, 28:141-147, 1988. (IF:0.706)
Conference Papers

  • A. Pietracaprina, G. Pucci, F. Silvestri and F. Vandin. Space-Efficient Parallel Algorithms for Combinatorial Search Problems. In Proc. 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013, Klosterneuburg OST, pages 717-728, August 2013. arXiv version
  • A. Pietracaprina, G. Pucci, M. Riondato, F. Silvestri and E. Upfal. Space-Round Tradeoffs for MapReduce Computations. In Proc. 26th ACM International Conference on Supercomputing, ICS 2012, Venice I, June 2012. arXiv version
  • A. Pettarin, A. Pietracaprina G. Pucci, and E. Upfal. Tight Bounds on Information Dissemination in Sparse Mobile Networks. In Proc. 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2011, San Jose, CA USA, June 2011.
  • A. Pettarin, A. Pietracaprina, and G. Pucci. On the Expansion and Diameter of Bluetooth-like Topologies. In Proc. 17th Annual European Symposium on Algorithms (ESA) 2009, pages 528-539, 2009.
  • R. Grossi, A. Pietracaprina, N. Pisanti, G. Pucci, E. Upfal, and F. Vandin. MADMX: A Novel Strategy for Maximal Dense Motif Extraction. In Proc. 9th Workshop on Algorithms in Bioinformatics (WABI) 2009, pages 362-374, 2009.
  • A. Kirsch, M. Mitzenmacher, A. Pietracaprina, G. Pucci, E. Upfal, and F. Vandin. An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets. In Proc. 27th ACM Symposium on Principles of Database Systems (PODS) 2009,
  • A. Pietracaprina, and F. Vandin. Efficient Incremental Mining of Top-K Frequent Closed Itemsets. In Proc. Discovery Science (DS) 2007, LNCS 4755, pages 275-280, 2007.
  • P. Crescenzi, C. Nocentini, A. Pietracaprina, G. Pucci, and C. Sandri. On the Connectivity of Bluetooth-Based Ad Hoc Networks In Proc. EURO-PAR'07 Parallel Processing, LNCS Vol. 4641, pages 960-969, 2007.
  • P. Bertasi, M. Bianco, A. Pietracaprina, and G. Pucci. Obtaining Performance Measures through Microbenchmarking in a Peer-to-Peer Overlay Computer. In Proc. 1st International Workshop on P2P, Parallel, Grid and Internet Computing, 3PGIC-2007.
  • G. Bilardi, A. Pietracaprina, G. Pucci, F. Silvestri. Network-Oblivious Algorithms. In Proc. 21st International Parallel and Distributed Processing Symposium, IPDPS 2007. arXiv version
  • A. Pietracaprina, G. Pucci, F. Silvestri. Cache-Oblivious Simulation of Parallel Programs. In Proc. 8th IPDPS Workshop on Advances in Parallel and Distributed Computational Models, APDCM 2006.
  • G. Bilardi, A. Pietracaprina, G. Pucci, F. Schifano and R. Tripiccione. The Potential of On-Chip Multiprocessing for QCD Machines. In Proc. 12th International Conference on High-Performance Computing (HiPC), LNCS Vol. 3769, pages 386-397, 2005.
  • C. Fantozzi, A. Pietracaprina, and G. Pucci. Translating Submachine Locality into Locality of Reference. In Proc. 18th International Parallel and Distributed Processing Symposium, IPDPS 2004. Paper recepient of Best Paper Award, Algorithms Track (4 tracks, 142 entries).
  • A. Pietracaprina and D. Zandolin. Mining Frequent Itemsets Using Patricia Tries. In Proc. 1st Workshop on Frequent Itemset Mining Implementations, FIMI 2003.
    Paper: CEUR-WS Workshop On-line Proceedings, Vol. 90 Code: PATRICIAMINE.tar.gz
  • C. Fantozzi, A. Pietracaprina and G. Pucci. Seamless integration of parallelism and memory hierarchy. In Proc. 29th International Colloquium on Automata, Languages, and Programming, ICALP'02, LNCS 2380, pages 856-867, Malaga, E, July 2002.
  • F. Dehne, S. Mardegan, A. Pietracaprina and G. Prencipe. Distribution sweeping on clustered machines with hierarchical memories. In Proc. International Parallel and Distributed Processing Symposium, IPDPS 2002, Fort Lauderdale, USA, April 2002.
  • A. Pietracaprina and G. Pucci. Optimal many-to-one routing on the mesh. In Proc. EURO-PAR'2001 - Parallel Processing, pages 645-650, Manchester, UK, August 2001.
  • K.T. Herley, A. Pietracaprina and G. Pucci. One-to-many routing on the mesh. In Proc. 13th ACM Symp. on Parallel Algorithms and Architectures, SPAA'01, pages 31-37, Heraklion, GR, Jun. 2001.
  • G. Bilardi, C. Fantozzi, A. Pietracaprina and G. Pucci. On the effectiveness of D-BSP as a bridging model of parallel computation. In Proc. International Conference on Computational Science, ICCS 2001, LNCS 2074, pages 579-588, San Francisco, USA, May 2001.
  • C. Fantozzi, A. Pietracaprina and G. Pucci. Implementing shared memory on clustered machines. In Proc. International Parallel and Distributed Processing Symposium, IPDPS 2001, San Francisco, USA, April 2001.
  • G. Bilardi, A. Pietracaprina, and P. D'Alberto. On the space and access complexity of computation dags. In Proc. 26th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2000, LNCS 1928, pages 47-58, Konstanz, D, June 2000.
  • G. Bilardi, K.T. Herley, A. Pietracaprina, and G. Pucci. On stalling in LogP. In Proc. Workshop on Advances in Parallel and Distributed Computational Models, LNCS 1800, pages 109-115, Cancun, MEX, May 2000.
  • N.M. Amato, J. Perdue, A. Pietracaprina, G. Pucci, and M. Mathis. Predicting performance on SMP's. A case study: The SGI Power Challenge. In Proc. International Parallel and Distributed Processing Symposium, IPDPS 2000, pages 729-37, Cancun, MEX, May 2000.
  • G. Bilardi, A. Pietracaprina, and G. Pucci. A quantitative measure of portability with application to bandwidth-latency models for parallel computing. In Proc. EURO-PAR'99 Parallel Processing, LNCS 1685, pages 543-551, Toulouse, F, Aug./Sep. 1999.
  • K.T. Herley, A. Pietracaprina and G. Pucci. Deterministic branch-and-bound on distributed memory machines. In Proc. IRREGULAR'99, pages 1085-1094, Puerto Rico, USA, April 1999.
  • R. Grossi, A. Pietracaprina and G. Pucci. Optimal deterministic protocols for mobile robots on a grid. In Proc. 6th Scandinavian Workshop on Algorithm Theory, LNCS 1432, pages 181-192, Stockholm, S, July 1998.
  • N. Amato, L.K. Dale and J.Perdue, A. Pietracaprina, G. Pucci. A cost model for communication on a symmetric multiprocessor. In Proc 10th ACM Symp. on Parallel Algorithms and Architectures, Revue Session, Puerto Vallarta, MEX, June-July 1998.
  • A. Pietracaprina. Deterministic routing of h-relations on the multibutterfly. In Proc. 1st Merged IPPS/SPDP Symposium: 12th Int.l Parallel Processing Symposium and 9th Symposium on Parallel and Distributed Processing, pages 375-379, Orlando, Florida, March-April 1998.
  • K.T. Herley, A. Pietracaprina, and G. Pucci. Fast deterministic backtrack search. In Proc. 23rd International Colloquium on Automata, Languages, and Programming, ICALP'96, LNCS 1099, pages 598-609, Paderborn, D, Jul. 1996.
  • A. Baumker, W. Dittrich, and A. Pietracaprina. The deterministic complexity of parallel multisearch. In Proc. ot the 5th Scandinavian Workshop on Algorithm Theory, SWAT'96, LNCS 1097, pages 404-415, Reykjavik, Iceland, 1996.
  • G. Bilardi, K.T. Herley, A. Pietracaprina, G. Pucci, and P. Spirakis. BSP vs LogP. In Proc. 8th ACM Symp. on Parallel Algorithms and Architectures, SPAA'96, pages 25-32, Padova, I, Jun. 1996.
  • K.T. Herley, A. Pietracaprina, and G. Pucci. Implementing shared memory on multi-dimensional meshes and on the fat-tree. In Proc. 3rd European Symposium on Algorithms, ESA'95, LNCS 979, pages 60-74, Corfu, GR, Sep. 1995.
  • A. Pietracaprina and G. Pucci. Improved deterministic PRAM simulation on the mesh. In Proc. 22nd International Colloquium on Automata, Languages, and Programming, ICALP'95, LNCS 944, pages 372-383, Szeged, H, July 1995.
  • A. Pietracaprina and G. Pucci. Tight bounds on deterministic PRAM emulations with constant redundancy. In Proc. 2nd European Symposium on Algorithms, ESA'94, LNCS 885, pages 319-400, Utrecht, NL, Sep. 1994.
  • A. Pietracaprina, G. Pucci, and J. Sibeyn. Constructive deterministic PRAM simulation on a mesh-connected computer. In Proc. 6th ACM Symp. on Parallel Algorithms and Architectures, SPAA'94, pages 248-256, Cape May NJ, USA, Jun. 1994.
  • A. Pietracaprina and F.P. Preparata. A practical constructive scheme for deterministic shared-memory access. In Proc. 5th ACM Symp. on Parallel Algorithms and Architectures, SPAA'93, pages 100-109, Velen, D, 1993.
  • A. Pietracaprina and F.P. Preparata. An N^(1/2)-worst-case-time solution to the granularity problem. In Proc. 10th Symp. on Theoretical Aspects of Computer Science, STACS'93 , LNCS 665, pages 110-119, Wurzburg, D, February 1993.
  • A. Krishna, A. Pietracaprina, and B. Hajek. Packet routing in optimal time on a butterfly. In Proc. of the 10th IEEE INFOCOM, pages 0840-0849, Bal Harbour, FL, April 1991.
  • F. Luccio, A. Pietracaprina, and G. Pucci. Analysis and implementation of parallel uniform hashing. In Proc. 1st Italian Conference on Algorithms and Complexity, CIAC'90, pages 1-12, Roma, I, Oct. 1990.

Last Update: March 11, 2015 Back to Home Page