Award Abstract # 1447793
BIGDATA: F: DKA: Collaborative Research: Dealing Efficiently with Big Social Network Data

NSF Org: IIS
Division of Information & Intelligent Systems
Recipient: RUTGERS, THE STATE UNIVERSITY
Initial Amendment Date: August 27, 2014
Latest Amendment Date: August 27, 2014
Award Number: 1447793
Award Instrument: Standard Grant
Program Manager: Sylvia Spengler
sspengle@nsf.gov
 (703)292-7347
IIS
 Division of Information & Intelligent Systems
CSE
 Directorate for Computer and Information Science and Engineering
Start Date: September 1, 2014
End Date: August 31, 2018 (Estimated)
Total Intended Award Amount: $300,000.00
Total Awarded Amount to Date: $300,000.00
Funds Obligated to Date: FY 2014 = $300,000.00
History of Investigator:
  • Shanmugavelayu Muthukrishnan (Principal Investigator)
    muthu@cs.rutgers.edu
Recipient Sponsored Research Office: Rutgers University New Brunswick
3 RUTGERS PLZ
NEW BRUNSWICK
NJ  US  08901-8559
(848)932-0150
Sponsor Congressional District: 12
Primary Place of Performance: Rutgers University New Brunswick
110 Frelinghuysen Road
Piscataway
NJ  US  08854-8072
Primary Place of Performance
Congressional District:
06
Unique Entity Identifier (UEI): M1LVPE5GLSD9
Parent UEI:
NSF Program(s): Algorithmic Foundations,
Big Data Science &Engineering
Primary Program Source: 01001415DB NSF RESEARCH & RELATED ACTIVIT
Program Reference Code(s): 7433, 8083
Program Element Code(s): 779600, 808300
Award Agency Code: 4900
Fund Agency Code: 4900
Assistance Listing Number(s): 47.070

ABSTRACT

The past decade has seen dramatic growth in systems that collect data from human activities. Online social networks record not just friendships, but interactions, messages, photos, and interests. Mobile devices track location via GPS information. Online stores monitor millions of customers as they explore and transact. Sensors, wearable and otherwise, produce detailed behavioral data. Collectively, this provides ever-larger collections of human social-activity information -- we refer to this as Big Social Data. While Big Social Data is growing rapidly, the available processing resources -- CPU, memory, communication -- are growing at a slower pace. To realize the promise of big social data, we need algorithms that use only sublinear resources, that is, resources growing much less than the growth of the data in suitable parameters. Designing these algorithms will be the core activity of this research project. This work will be in consultation with practitioners handling Big Social Data, leading to many opportunities for technology transfer. The research program both enables and benefits from an education and outreach program that will help develop the new breed of algorithmically-trained data scientists for Big Social Data.

Emerging systems -- MapReduce, Hadoop, Spark, Storm, etc. -- use large scale distributed computation: clusters of machines not only gathering and storing data in parallel, but also working together to perform computations. Often, these systems and applications work via incremental processing, storing and returning only approximate solutions, trading off quality and certainty for efficiency. In addition, these systems take a data-centric view, wherein the data is stored as pairs. This project will address fundamental problems with Big Social Data -- search, ranking, and optimization, etc. in these modern computing and data models. For these problems, this project will design algorithms that are sublinear in the relevant parameter -- number of keys, size of values, computing time per key or over all keys, and other variations that map to underlying storage, number of machines, bandwidth and other computational constraints.

For further information, see the project web site at http://www.stanford.edu/~ashishg/socialdata.html .

PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH

Note:  When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

Aaron Cahn and Scott Alfeld and Paul Barford and S. Muthukrishnan "An Empirical Study of Web Cookies" Proceedings of the 25th International Conference on World Wide Web, WWW 2016, , 2016 , p.891
Aaron Cahn and Scott Alfeld and Paul Barford and S. Muthukrishnan "What's in the community cookie jar?" 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM , 2016 , p.567
Aman Gupta and S. Muthukrishnan and Smita Wadhwa "Optimizing callout in unified ad markets" 2016 IEEE International Conference on Big Data, BigData , 2016 , p.1315
Priya Govindan, Chenghong Wang, Chumeng Xu, Hongyu Duan, Sucheta Soundarajan. "The k-peak Decomposition: Mapping the Global Structure of Graphs." WWW 2017 , 2017 , p.1441
Priya Govindan, Morteza Monemizadeh, S. Muthukrishnan "Streaming Algorithms for Measuring H-Impact." PODS 2017 , 2017 , p.337
Qiang Ma and Han Hee Song and S. Muthukrishnan and Antonio Nucci "Joining user profiles across online social networks: From the perspective of an adversary" 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM , 2016 , p.178
Qiang Ma and Musen Wen and Zhen Xia and Datong Chen "A Sub-linear, Massive-scale Look-alike Audience Extension System" Proceedings of the 5th International Workshop on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications, BigMine 2016 , 2016 , p.51
Qiang Ma and S. Muthukrishnan and William Simpson "App2Vec: Vector modeling of mobile apps and applications" 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM , 2016 , p.599

Please report errors in award information by writing to: awardsearch@nsf.gov.

Print this page

Back to Top of page