Copyright Statement: The copyrights for all the publications rest with the respective publishers. The versions posted here are author's versions and are meant for personal use and not for redistribution.

A link to my DBLP/DBLPvis/Google Scholar/Google Scholar Citations/ArnetMiner pages.

Conference & Journal Papers       Technical Reports       Talks      

Conference & Journal Papers

2011

• Sudipto Das, Shoji Nishimura, Divyakant Agrawal, Amr El Abbadi, "Albatross: Lightweight Elasticity in Shared Storage Databases for the Cloud using Live Data Migration",[Paper],[Talk] In the 37th International Conference on Very Large Data Bases (VLDB) 2011 [PVLDB 4(8) 494-505 2011].
  
  Show Abstract
  
  Database systems serving cloud platforms must serve large numbers of applications (or tenants). In addition to managing tenants with small data footprints, different schemas, and variable load patterns, such multitenant data platforms must minimize their operating costs by efficient resource sharing. When deployed over a pay-per-use infrastructure, elastic scaling and load balancing, enabled by low cost live migration of tenant databases, is critical to tolerate load variations while minimizing operating cost. However, existing databases—relational databases and Key-Value stores alike—lack low cost live migration techniques, thus resulting in heavy performance impact during elastic scaling. We present Albatross, a technique for live migration in a multitenant database serving OLTP style workloads where the persistent database image is stored in a network attached storage. Albatross migrates the database cache and the state of active transactions to ensure minimal impact on transaction execution while allowing transactions active during migration to continue execution. It also guarantees serializability while ensuring correctness during failures. Our evaluation using two OLTP benchmarks shows that Albatross can migrate a live tenant database with no aborted transactions, negligible impact on transaction latency and throughput both during and after migration, and an unavailability window as low as 300 ms.

  Hide Abstract

• Aaron Elmore, Sudipto Das, Divyakant Agrawal, Amr El Abbadi, "Zephyr: Live Migration in Shared Nothing Databases for Elastic Cloud Platforms",[Paper],[Talk] In the ACM International Conference on Management of Data (SIGMOD) 2011, pp 301-312. [Acceptance Rate: 87/375 (23%)]
  
  Show Abstract
  
  Multitenant data infrastructures for large cloud platforms hosting hundreds of thousands of applications face the challenge of serving applications characterized by small data footprint and unpredictable load patterns. When such a platform is built on an elastic pay-per-use infrastructure, an added challenge is to minimize the system’s operating cost while guaranteeing the tenants’ service level agreements (SLA). Elastic load balancing is therefore an important feature to enable scale-up during high load while scaling down when the load is low. Live migration, a technique to migrate tenants with minimal service interruption and no downtime, is critical to allow lightweight elastic scaling. We focus on the problem of live migration in the database layer. We propose Zephyr, a technique to efficiently migrate a live database in a shared nothing transactional database architecture. Zephyr uses phases of ondemand pull and asynchronous push of data, requires minimal synchronization, results no service unavailability and few or no aborted transactions, minimizes the data transfer overhead, provides ACID guarantees during migration, and ensures correctness in the presence of failures. We outline a prototype implementation using an open source relational database engine and an present a thorough evaluation using various transactional workloads. Zephyr’s efficiency is evident from the few tens of failed operations, 10-20% change in average transaction latency, minimal messaging, and no overhead during normal operation when migrating a live database.

  Hide Abstract

• Shoji Nishimura, Sudipto Das, Divyakant Agrawal, Amr El Abbadi, "MD-HBase: A Scalable Multi-dimensional Data Infrastructure for Location Aware Services", [Talk] In the 12th International Conference on Mobile Data Management (MDM) 2011, pp 7-16. [Acceptance Rate: 22/88 (25%)]
  Recipient of Best Runner-up Paper Award.
  
  Show Abstract
  
  The ubiquity of location enabled devices has resulted in a wide proliferation of location based applications and services. To handle the growing scale, database management systems driving such location based services (LBS) must cope with high insert rates for location updates of millions of devices, while supporting efficient real-time analysis on latest location. Traditional DBMSs, equipped with multi-dimensional index structures, can efficiently handle spatio-temporal data. However, popular opensource relational database systems are overwhelmed by the high insertion rates, real-time querying requirements, and terabytes of data that these systems must handle. Key-value stores have recently gained popularity as they effectively support large scale operation. However, they do not natively support multi-attribute accesses. As a result, the rich querying functionality, such as spatio-temporal range queries and nearest neighbor queries, essential for the LBSs cannot be efficiently processed by Keyvalue stores. We present MD-HBase, a scalable data management system for LBSs that bridges this gap between scale and functionality. Our approach leverages a multi-dimensional index structure layered over a Key-value store. The underlying Keyvalue store allows the system to sustain high insert throughput and large data volumes, while ensuring fault-tolerance, and high availablability. On the other hand, the index layer allows efficient multi-dimensional query processing. We present the design of MD-HBase that builds two standard index structures—the K-d tree and the Quad tree—over a range partitioned Key-value store. Our prototype implementation using HBase, a standard opensource Key-value store, can handle hundreds of thousands of inserts per second using a modest 16 node cluster, while efficiently processing multi-dimensional range queries and nearest neighbor queries in real-time with response times as low as hundreds of milliseconds.

  Hide Abstract

• Phil Bernstein, Colin Reid, Sudipto Das, "Hyder -- A Transactional Record Manager for Shared Flash",[Talk] In the 5th Biennial Conference on Innovative Data Research (CIDR) 2011, pp 9--20.
  Recipient of Best Paper Award. Related UCSB CS Dept. news article.
  
  Show Abstract
  
  Hyder supports reads and writes on indexed records within classi-cal multi-step transactions. It is designed to run on a cluster of servers that have shared access to a large pool of network-addressable raw flash chips. The flash chips store the indexed records as a multiversion log-structured database. Log-structuring leverages the high random I/O rate of flash and automatically wear-levels it. Hyder uses a data-sharing architecture that scales out without partitioning the database or application. Each transac-tion executes on a snapshot, logs its updates in one record, and broadcasts the log record to all servers. Each server rolls forward the log against its locally-cached partial-copy of the last committed state, using optimistic concurrency control to determine whether each transaction commits. This paper explains the architecture of the overall system and its three main components: the log, the index, and the roll-forward algorithm. Simulations and prototype measurements are presented that show Hyder can scale out to support high transaction rates.

  Hide Abstract

• Divyakant Agrawal, Sudipto Das, Amr El Abbadi "Big Data and Cloud Computing: Current State and Future Opportunities",Slides: [Part1], [Part2] Tutorial presentation at EDBT 2011 Conference, March 2011 pp 530-533.
  
  Show Abstract
  
  Cloud computing is an extremely successful paradigm of service oriented computing, and has revolutionized the way computing infrastructure is used. This success has seen a proliferation in the number of applications which leverage various cloud platforms, resulting in a tremendous increase in the scale of the data generated as well as consumed by such applications. Scalable database management systems . both for update intensive application workloads, as well as decision support systems for descriptive and deep analytics . are thus a critical part of the cloud infrastructure. The quest for conquering the challenges posed by the management of big data has led to a plethora of systems. This tutorial aims to clarify some of the critical concepts in the design space of big data and cloud computing such as: the appropriate systems for a specific set of application requirements, the research challenges in data management for the cloud, and what is novel in the cloud for database researchers? We also aim to address one basic question: Whether cloud computing poses new challenges in scalable data management or it is just a reincarnation of old problems? We provide a comprehensive background study of state-of-the-art systems for scalable data management and analysis. We also identify the critical aspects in the design of different systems and the applicability and scope of these systems. A thorough understanding of current solutions and a precise characterization of the design space are essential for clearing the "cloudy skies of data management" and ensuring the success of DBMSs in the cloud, thus emulating the success enjoyed by relational databases in traditional enterprise settings.

  Hide Abstract

• Divyakant Agrawal, Amr El Abbadi, Sudipto Das, Aaron Elmore, "Database Scalability, Elasticity, and Autonomy in the Cloud",(Extended Abstract),[Paper] in the 16th International Conference on Database Systems for Advanced Applications (DASFAA) 2011, April 2011, pp 2-15.
  
  Show Abstract
  
  Cloud computing has emerged as an extremely successful paradigm for deploying web applications. Scalability, elasticity, pay-per-use pricing, and economies of scale from large scale operations are the major reasons for the successful and widespread adoption of cloud infrastructures. Since a majority of cloud applications are data driven, database management systems (DBMSs) powering these applications form a critical component in the cloud software stack. In this article, we present an overview of our work on instilling these above mentioned “cloud features” in a database system designed to support a variety of applications deployed in the cloud: designing scalable database management architectures using the concepts of data fission and data fusion, enabling lightweight elasticity using low cost live database migration, and designing intelligent and autonomic controllers for system management without human intervention.

  Hide Abstract

2010

• Sudipto Das, Ömer Egecioglu, Amr El Abbadi, "Anonimos: An LP based Approach for Anonymizing Weighted Social Network Graphs", To appear in IEEE Transactions of Knowledge and Data Engineering (TKDE).
  
  Show Abstract
  
  The increasing popularity of social networks has initiated a fertile research area in information extraction and data mining. Anonymization of these social graphs is important to facilitate publishing these data sets for analysis by external entities. Prior work has concentrated mostly on node identity anonymization and structural anonymization. But with the growing interest in analyzing social networks as a weighted network, edge weight anonymization is also gaining importance. We present An\'onimos, a Linear Programming based technique for anonymization of edge weights that preserves linear properties of graphs. Such properties form the foundation of many important graph-theoretic algorithms such as shortest paths problem, k-nearest neighbors, minimum cost spanning tree, and maximizing information spread. As a proof of concept, we apply An\'onimos to the shortest paths problem and its extensions, prove the correctness, analyze complexity, and experimentally evaluate it using real social network data sets. Our experiments demonstrate that An\'onimos anonymizes the weights, improves k-anonymity of the weights, and also scrambles the relative ordering of the edges sorted by weights, thereby providing robust and effective anonymization of the sensitive edge-weights. Additionally, we demonstrate the composability of different models generated using An\'onimos, a property that allows a single anonymized graph to preserve multiple linear properties.

  Hide Abstract

• Divyakant Agrawal, Sudipto Das, Amr El Abbadi "Big Data and Cloud Computing: New Wine or just New Bottles?",Slides: [Part1], [Part2] Tutorial presentation at VLDB 2010 Conference, September 2010 [PVLDB 3(2) 1647-1648].
  
  Show Abstract
  
  Cloud computing is an extremely successful paradigm of service oriented computing, and has revolutionized the way computing infrastructure is used. This success has seen a proliferation in the number of applications which leverage various cloud platforms, resulting in a tremendous increase in the scale of the data generated as well as consumed by such applications. Scalable database management systems . both for update intensive application workloads, as well as decision support systems for descriptive and deep analytics . are thus a critical part of the cloud infrastructure. The quest for conquering the challenges posed by the management of big data has led to a plethora of systems. This tutorial aims to clarify some of the critical concepts in the design space of big data and cloud computing such as: the appropriate systems for a specific set of application requirements, the research challenges in data management for the cloud, and what is novel in the cloud for database researchers? We also aim to address one basic question: Whether cloud computing poses new challenges in scalable data management or it is just a reincarnation of old problems? We provide a comprehensive background study of state-of-the-art systems for scalable data management and analysis. We also identify the critical aspects in the design of different systems and the applicability and scope of these systems. A thorough understanding of current solutions and a precise characterization of the design space are essential for clearing the "cloudy skies of data management" and ensuring the success of DBMSs in the cloud, thus emulating the success enjoyed by relational databases in traditional enterprise settings.

  Hide Abstract

• Sudipto Das, Yannis Sismanis, Kevin S. Beyer, Rainer Gemulla, Peter J. Haas, John McPherson "Ricardo: Integrating R and Hadoop",[Paper], [Talk] in 2010 ACM SIGMOD Conference, pp. 987-998, June 2010.
  
  Show Abstract
  
  Many modern enterprises are collecting data at the most detailed level possible, creating data repositories ranging from terabytes to petabytes in size. The ability to apply sophisticated statistical analysis methods to this data is becoming essential for marketplace competitiveness. This need to perform deep analysis over huge data repositories poses a significant challenge to existing statistical software and data management systems. On the one hand, statistical software provides rich functionality for data analysis and modeling, but can handle only limited amounts of data; e.g., popular packages like R and SPSS operate entirely in main memory. On the other hand, data management systems.such as MapReduce-based systems.can scale to petabytes of data, but provide insufficient analytical functionality. We report our experiences in building Ricardo, a scalable platform for deep analytics. Ricardo is part of the eXtreme Analytics Platform (XAP) project at the IBM Almaden Research Center, and rests on a decomposition of data-analysis algorithms into parts executed by the R statistical analysis system and parts handled by the Hadoop data management system. This decomposition attempts to minimize the transfer of data across system boundaries. Ricardo contrasts with previous approaches, which try to get along with only one type of system, and allows analysts to work on huge datasets from within a popular, well supported, and powerful analysis environment. Because our approach avoids the need to re-implement either statistical or data-management functionality, it can be used to solve complex problems right now.

  Hide Abstract

• Divyakant Agrawal, Amr El Abbadi, Shyam Antony, Sudipto Das, "Data Management Challenges in Cloud Computing Infrastructures",(Keynote Address),[Paper] in the 6th International Workshop on Databases in Networked Information Systems (DNIS 2010), pp. 1-10, March 2010.
  
  Show Abstract
  
  The challenge of building consistent, available, and scalable data management systems capable of serving petabytes of data for millions of users has confronted the data management research community as well as large internet enterprises. Current proposed solutions to scalable data management, driven primarily by prevalent application requirements, limit consistent access to only the granularity of single objects, rows, or keys, thereby trading off consistency for high scalability and availability. But the growing popularity of cloud computing, the resulting shift of a large number of internet applications to the cloud, and the quest towards providing data management services in the cloud, has opened up the challenge for designing data management systems that provide consistency guarantees at a granularity larger than single rows and keys. In this paper we analyze the design choices that allowed modern scalable data management systems to achieve orders of magnitude higher levels of scalability compared to traditional databases. With this understanding, we highlight some design principles for systems providing scalable and consistent data management as a service in the cloud.

  Hide Abstract

• Sudipto Das, Divyakant Agrawal, Amr El Abbadi, "G-Store: A Scalable Data Store for Transactional Multi key Access in the Cloud",[Paper], [Talk] in the 1st ACM Symposium on Cloud Computing 2010 (ACM SOCC 2010), pp. 163-174. [Acceptance Rate: 23/119 (19%)].
  
  Show Abstract
  
  Cloud computing has emerged as a preferred platform for deploying scalable web-applications. With the growing scale of these applications and the data associated with them, scalable data management systems form a crucial part of the cloud infrastructure. Key-Value stores . such as Bigtable, PNUTS, Dynamo, and their open source analogues. have been the preferred data stores for applications in the cloud. In these systems, data is represented as Key- Value pairs, and atomic access is provided only at the granularity of single keys. While these properties work well for current applications, they are insufficient for the next generation web applications . such as online gaming, social networks, collaborative editing, and many more . which emphasize collaboration. Since collaboration by definition requires consistent access to groups of keys, scalable and consistent multi key access is critical for such applications. We propose the Key Group abstraction that defines a relationship between a group of keys and is the granule for on-demand transactional access. This abstraction allows the Key Grouping protocol to collocate control for the keys in the group to allow efficient access to the group of keys. Using the Key Grouping protocol, we design and implement G-Store which uses a key-value store as an underlying substrate to provide efficient, scalable, and transactional multi key access. Our implementation using a standard key-value store and experiments using a cluster of commodity machines show that G-Store preserves the desired properties of key-value stores, while providing multi key access functionality at a very low overhead.

  Hide Abstract

• Sudipto Das, Ömer Egecioglu, Amr El Abbadi, "Anonymizing Weighted Social Network Graphs",[Paper], [Talk], [Poster] in the 26th International Conference on Data Engineering (ICDE) 2010, pp 904 - 907. [Acceptance Rate: 110/523 (21%)].
  
  Show Abstract
  
  The increasing popularity of social networks has initiated a fertile research area in information extraction and data mining. Although such analysis can facilitate better understanding of sociological, behavioral, and other interesting phenomena, there is growing concern about personal privacy being breached, thereby requiring effective anonymization techniques. In this paper, we consider edge weight anonymization in social graphs. Our approach builds a linear programming (LP) model which preserves properties of the graph that are expressible as linear functions of the edge weights. Such properties form the foundations of many important graph-theoretic algorithms such as shortest paths, k-nearest neighbors, minimum spanning tree, etc. Off-the-shelf LP solvers can then be used to find solutions to the resulting model where the computed solution constitutes the weights in the anonymized graph. As a proof of concept, we choose the shortest paths problem, and experimentally evaluate the proposed techniques using real social network data sets.

  Hide Abstract

2009

• Sudipto Das, Shyam Antony, Divyakant Agrawal, Amr El Abbadi, "Thread Cooperation in Multicore Architectures for Frequency Counting Over Multiple Data Streams",[Paper], [Talk] in the 35th International Conference on Very Large Data Bases (VLDB) 2009 [PVLDB 2(1) 217-228]. [Core DB Track Acceptance Rate: 51/351 (17%)].
  
  Show Abstract
  
  Many real-world data stream analysis applications such as network monitoring, click stream analysis, and others, require combining multiple streams of data arriving from multiple sources. This is referred to as multi-stream analysis. To deal with high stream arrival rates, it is desirable that such systems be capable of supporting very high processing throughput. The advent of multicore processors and powerful servers driven by these processors calls for efficient parallel designs that can effectively utilize the parallelism of the multicores, since performance improvement is possible only through effective parallelism. In this paper, we address the problem of parallelizing multi-stream analysis in the context of multicore processors. Specifically, we concentrate on parallelizing frequent elements, top-k, and frequency counting over multiple streams. We discuss the challenges in designing an efficient parallel system for multi-stream processing. Our evaluation and analysis reveals that traditional contention based locking results in excessive overhead and wait, which in turn leads to severe performance degradation in modern multicore architectures. Based on our analysis, we propose a cooperation based locking paradigm for efficient parallelization of frequency counting. The proposed cooperation based paradigm removes waits associated with synchronization, and allows replacing locks by much cheaper atomic synchronization primitives. Our implementation of the proposed paradigm to parallelize a well known frequency counting algorithm shows the benefits of the proposed cooperation based locking paradigm when compared to the traditional contention based locking paradigm. In our experiments, the proposed cooperation based design outperforms the traditional contention based design by a factor of 2 - 5.5X for synthetic zipfian data sets.

  Hide Abstract

• Sudipto Das, Divyakant Agrawal, Amr El Abbadi, "ElasTraS: An Elastic Transactional Data Store in the Cloud",[Paper], [Talk] USENIX Workshop on Hot Topics in Cloud Computing (HotCloud '09), in conjunction with USENIX '09. [Acceptance Rate: 13/41 (32%)].
  
  Show Abstract
  
  Over the last couple of years, "Cloud Computing" or "Elastic Computing" has emerged as a compelling and successful paradigm for internet scale computing. One of the major contributing factors to this success is the elasticity of resources. But in spite of the elasticity provided by the infrastructure and the scalable design of the applications, the elephant (or the underlying database), which drives most of these web-based applications, is not very elastic and scalable, and hence limits scalability. In this paper, we propose ElasTraS which addresses this issue of scalability and elasticity of the data store in a cloud computing environment to leverage from the elastic nature of the underlying infrastructure, while providing scalable transactional data access. This paper aims at providing the design of a system in progress, highlighting the major design choices, analyzing the different guarantees provided by the system, and identifying several important challenges for the research community striving for computing in the cloud.

  Hide Abstract

• Sudipto Das, Shyam Antony, Divyakant Agrawal, Amr El Abbadi, "CoTS: A Scalable Framework for Parallelizing Frequency Counting over Data Streams",[Paper], [Poster] 25th IEEE International Conference on Data Engineering (ICDE 2009), pages 1323-1326. [Acceptance Rate: 150/554 (27%)].
  
  Show Abstract
  
  Frequency counting, frequent elements and top-k queries form a class of operators that are used for a wide range of stream analysis applications. In spite of the abundance of these algorithms, all known techniques for answering data stream queries are sequential in nature. The imminent ubiquity of Chip Multi-Processor (CMP) architectures requires algorithms that can exploit the parallelism of such architectures. In this paper, we first evaluate different naive techniques for intra-operator parallelism, and summarize the insights obtained from the naive techniques. Our experimental analysis of the naive designs shows that intra-operator parallelism is not straightforward and requires a complete redesign of the system. We then propose an efficient and scalable framework for parallelizing frequency counting, frequent elements and top-k queries over data streams. The proposed CoTS (Co-operative Thread Scheduling) framework is based on the principle of threads co-operating rather than contending. Our experiments on a state-of-the-art quad-core chip-multiprocessor architecture and synthetic data sets demonstrate the scalability of the proposed framework, and the efficiency is demonstrated by peak processing throughput of more than $60$ million elements per second.

  Hide Abstract

2008

• Sudipto Das, Divyakant Agrawal, Amr El Abbadi, "CAM Conscious Integrated Answering of Frequent Elements and Top-k Queries over Data Streams", [Paper], [Talk] 4th International Workshop on Data Management on New Hardware, DaMoN 2008, in conjunction with SIGMOD/PODS 2008, pages 1-10.
  
  Show Abstract
  
  Frequent elements and top-k queries constitute an important class of queries for data stream analysis applications. Certain applications require answers for both frequent elements and top-k queries on the same stream. In addition, the ever increasing data rates call for providing fast answers to the queries, and researchers have been looking towards exploiting specialized hardware for this purpose. Content Addressable Memory(CAM) provides an efficient way of looking up elements and hence are well suited for the class of algorithms that involve lookups. In this paper, we present a fast and efficient CAM conscious integrated solution for answering both frequent elements and top-k queries on the same stream. We call our scheme CAM conscious Space Saving with Stream Summary (CSSwSS), and it can efficiently answer continuous queries. We provide an implementation of the proposed scheme using commodity CAM chips, and the experimental evaluation demonstrates that not only does the proposed scheme outperforms existing CAM conscious techniques by an order of magnitude at query loads of about 10%, but the proposed scheme can also efficiently answer continuous queries.

  Hide Abstract

• Vinod Kone, Sudipto Das, Ben Y. Zhao, Haitao Zheng, "QUORUM: Quality of Service in Wireless Mesh Networks", [Paper] Mobile Networks and Applications Journal, Springer, Netherlands, April 2008 [MONET 12(5-6), 358-369].
  
  Show Abstract
  
  Wireless Mesh Networks (WMNs) can provide seamless broadband connectivity to network users with low setup and maintenance costs. To support next-generation applications with real-time requirements, however, these networks must provide improved quality of service guarantees. Current mesh protocols use techniques that fail to accurately predict the performance of end-to-end paths, and do not optimize performance based on knowledge of mesh network structures. In this paper, we propose QUORUM, a routing protocol optimized for WMNs that provides accurate QoS properties by correctly predicting delay and loss characteristics of data traffic. QUORUM integrates a novel end-to-end packet delay estimation mechanism with stability-aware routing policies, allowing it to more accurately follow QoS requirements while minimizing misbehavior of selfish nodes.

  Hide Abstract

2007

• Anup K. Ghosh, Sudipto Das, Rajesh Roy, Amitava Mukherjee, "Sender Side Intelligence for TCP Throughput Enhancement in Wired-cum-Wireless Networks", [Paper] The 18th Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC.07), September 2007, Athens, Greece.
  
  Show Abstract
  
  Performance of the TCP Congestion Control Algorithm has been the focus of research over the last decade. In this paper we propose modifications to TCP Congestion Control to improve its performance in wired-cum-wireless networks The key idea to determine the Optimal Congestion Window for a TCP Sender, in a particular network scenario (that corresponds to the fair share of that connection) and keep this congestion window a constant to a point where the fair share in the network has changed considerably from the instance of the calculation of the size of the last window. At this point, the TCP Congestion Window is recalculated according to the nature of new scenario. The proposed mechanism is particularly effective over wireless links, which have an inherently loss-prone nature, as Modified TCP.s congestion window being independent of packet losses (be it corruption losses or it congestion losses), keeps transmitting at the same rate at before.

  Hide Abstract

• Vinod Kone, Sudipto Das, Ben Y. Zhao and Haitao Zheng, "QUORUM - QUality Of service RoUting in wireless Mesh networks", [Paper] Proceedings of International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness (QShine) Vancouver, Canada, August 2007.
  
  Show Abstract
  
  Wireless Mesh Networks (WMNs) can provide seamless broadband connectivity to network users, with the advantage of low setup and maintenance costs. To support next-generation applications with real-time requirements, however, these networks must provide improved Quality of Service guarantees. Most current mesh network routing protocols are adapted from MANET protocols, and do not optimize for mesh network properties. In this paper, we propose QUORUM (QUality Of service RoUting in wireless Mesh networks ), a routing protocol optimized for WMNs that addresses these drawbacks. QUORUM integrates a novel end-to-end packet delay estimation mechanism with stability-aware routing policies, allowing it to more accurately follow QoS requirements while minimizing misbehavior of selfish nodes.

  Hide Abstract

2006

• Rajesh Roy, Sudipto Das, Anup K. Ghosh, Amitava Mukherjee, "Modified TCP Congestion Control Algorithm for Throughput Enhancement in Wired-cum-Wireless Networks", [Paper] In Proc. of 4th Swedish National Computer Networking Workshop, Oct 2006, Luleå, Sweden (SNCNW 2006).
  
  Show Abstract
  
  The key idea proposed in this paper is to determine the Optimal Congestion Window for a TCP Sender in a particular network scenario (that corresponds to the fair share of that connection) and keep this congestion window a constant to a point where the fair share in the network has changed considerably from the instance of the calculation of the size of the last window. At this point, the TCP Congestion Window is recalculated according to the nature of new scenario. The proposed mechanism is particularly effective over wireless links, which have an inherently loss-prone nature, as Modified TCP.s congestion window being independent of packet losses (be it corruption losses or it congestion losses), keeps transmitting at the same rate as before.

  Hide Abstract

• Sudipto Das, Rajesh Roy, Pradip K. Das, "Optimizations to Multipath Routing Protocols in Mobile Ad hoc Networks", [Paper] [Talk] In Proc of International Conference on Emerging Applications of IT Feb 2006, Kolkata, India(EAIT 2006).
  
  Show Abstract
  
  Mobile Ad hoc Networks are typically characterized by high mobility and frequent link failures. As a result, routing algorithms selecting a single path during route creation have to make frequent route discoveries resulting in decreased throughput and high endto- end delay. Multipath routing approaches like AOMDV make use of pre-computed routes determined during route discovery. This solution, however, suffers during high mobility because the alternate paths are not actively maintained. Hence, precisely when needed, the routes are often broken. In this paper, the information gathered by a node about its neighbor, in addition to those proposed in [1], is used to dynamically determine the node to which a particular data packet has to be forwarded. Using this approach a better load balancing can be obtained in addition to utilization of the additional routes, if feasible, and in the process maintaining these routes. We also explore the possibility of implementing QoS using such a scheme.

  Hide Abstract

• Rajesh Roy, Sudipto Das, Pradip K. Das,"A Pragmatic Approach towards the Improvement of Performance of Ad Hoc Routing Protocols",[Paper] [Talk] In Proc. of 4th Asian International Mobile Computing Conference, Jan 2006, Kolkata, India (AMOC 2006).
  
  Show Abstract
  
  Mobile ad hoc networks are typically characterized by high mobility and frequent link failures that result in low throughput and high end-to-end delay. In order to facilitate communication within the network, a routing protocol is used to discover routes between nodes. The primary goal of such an ad hoc network routing protocol is correct and efficient route establishment between a pair of nodes so that messages may be delivered in a timely manner. Though a large number of routing protocols have been developed for this kind of networks, most of them suffer from implementation difficulties and some inherent incapabilities to cope with highly dynamic scenarios as well as support for Quality of Services (QoS). In this paper we propose to introduce a new layer in between network layer and IEEE 802.11 MAC sub layer. This layer will interact with the underlying MAC layer and provide link connectivity information as well as various other valuable parameters (e.g. received signal strength, network resource usage etc.), which can be used for further enhancement of the routing algorithms.

  Hide Abstract

2005

• Anup K. Ghosh, Sudipto Das, Rajesh Roy, Amitava Mukherjee, "Constant Congestion Window approach for TCP - effect on Fairness", [Paper] [Talk] In Proc. of 3rd Swedish National Computer Networking Workshop, Sep 2005, Halmstad, Sweden (SNCNW 2005).
  
  Show Abstract
  
  This is an extension of the work done by Ghosh et al. [1] whereby it was indicated that a fixed congestion window performs better than a TCP Reno implementation. This paper investigates the impact of this model on the fairness of connections and comes up with suggestion to improve this.

  Hide Abstract

Top of Page

Technical Reports

2011

• Divyakant Agrawal, Sudipto Das, Amr El Abbadi, "From a Virtualized Computing Nucleus to a Cloud Computing Universe: A Case for Dynamic Clouds", UCSB CS Tecnical Report 2011-03, March 2011.
  
  Show Abstract
  
  The current model of the cloud consists of a static set of data centers (or cloud cores) which drive the computation and storage needs of large numbers of applications. We envision a new paradigm where the cloud will be comprised of a large dynamic collection of cloud cores along with a static set of cores, the nucleus, to create a cloud computing universe with a capacity much larger than the nucleus and a cost much smaller than owning the entire infrastructure. This model is rooted by the observation that a tremendous amount of computation exists outside the core that can potentially augment the nucleus’ capacity. An example of this surplus capacity are enterprises with diurnal trends in usage behavior that join the cloud during predicted periods of usage troughs. We propose to leverage this elastic and dynamic infrastructure to create a unified cloud service. A number of challenges, at all levels of the software stack, need to be addressed for these futuristic architectures to become a reality. We focus on the challenge of an elastic and agile data management infrastructure to deal with the dynamics associated with this novel paradigm.

  Hide Abstract

2010

• Sudipto Das, Shoji Nishimura, Divyakant Agrawal, Amr El Abbadi, "Live Database Migration for Elasticity in a Multitenant Database for Cloud Platforms", UCSB CS Tecnical Report 2010-09, June 2010.
  
  Show Abstract
  
  The growing popularity of cloud computing as a platform for deploying internet scale applications has seen a large number of web applications being deployed in the cloud. These applications (or tenants) are typically characterized by small data footprints, different schemas, and variable load patterns. Scalable multitenant database management systems (DBMS) running on a cluster of commodity servers are thus critical for a cloud service provider to support a large number of small applications. Multitenant DBMSs often collocate multiple tenants. databases on a single server for effective resource sharing. Due to the variability in load, elastic load balancing of tenants. data is critical for performance and cost minimization. On demand migration of tenants. databases to distribute load on an elastic cluster of machines is a critical technology for elastic load balancing. Therefore, efficient live database migration techniques with minimal disruption and impact in service is paramount in such systems. Unfortunately, most popular DBMSs were not designed to be nimble enough for efficient migration, resulting in downtime and disruption in service when the live databases need migration. We focus on this problem of live database migration in a multitenant cloud DBMS. We evaluate different database multitenancy models in the context of migration and propose an efficient technique for live migration of a tenant.s database with minimal downtime and impact on performance. We implement the proposed migration technique in a database system designed for the cloud. Our evaluation using standard OLTP benchmarks shows that our proposed technique can migrate a live tenant database with as low as 70 ms service disruption; an order of magnitude improvement compared to known heavy weight techniques for migrating a database.

  Hide Abstract

• Aaron Elmore, Sudipto Das, Divyakant Agrawal, Amr El Abbadi, "Who's Driving this Cloud? Towards Efficient Migration for Elastic and Autonomic Multitenant Databases", UCSB CS Tecnical Report 2010-05, April 2010.
  
  Show Abstract
  
  The success of cloud computing as a platform for deploying web-applications has led to a deluge of applications characterized by small data footprints but unpredictable access patterns. An autonomic and scalable multitenant database management system (DBMS) is therefore an important component of the software stack for platforms supporting these applications. Elastic load balancing is a key requirement for effective resource utilization and operational cost minimization. Efficient techniques for database migration are thus essential for elasticity in a multitenant DBMS. Our vision is a DBMS where multitenancy is viewed as virtualization in the database layer, and migration is a first class notion with the same stature as scalability, availability etc. This paper serves as the first step in this direction. We analyze the various models of database multitenancy, formalize the forms of migration, evaluate the off-the-shelf migration techniques, and identify the design space and research goals for an autonomic and elastic multitenant database.

  Hide Abstract

• Sudipto Das, Ömer Egecioglu, Amr El Abbadi, "Anonimos: An LP based Approach for Anonymizing Weighted Social Network Graphs", CoRR Abstract 1004.0048.
  
  Show Abstract
  
  The increasing popularity of social networks has initiated a fertile research area in information extraction and data mining. Anonymization of these social graphs is important to facilitate publishing these data sets for analysis by external entities. Prior work has concentrated mostly on node identity anonymization and structural anonymization. But with the growing interest in analyzing social networks as a weighted network, edge weight anonymization is also gaining importance. We present An\'onimos, a Linear Programming based technique for anonymization of edge weights that preserves linear properties of graphs. Such properties form the foundation of many important graph-theoretic algorithms such as shortest paths problem, k-nearest neighbors, minimum cost spanning tree, and maximizing information spread. As a proof of concept, we apply An\'onimos to the shortest paths problem and its extensions, prove the correctness, analyze complexity, and experimentally evaluate it using real social network data sets. Our experiments demonstrate that An\'onimos anonymizes the weights, improves k-anonymity of the weights, and also scrambles the relative ordering of the edges sorted by weights, thereby providing robust and effective anonymization of the sensitive edge-weights. Additionally, we demonstrate the composability of different models generated using An\'onimos, a property that allows a single anonymized graph to preserve multiple linear properties.

  Hide Abstract

• Sudipto Das, Shashank Agarwal, Divyakant Agrawal, Amr El Abbadi, "ElasTraS: An Elastic, Scalable, and Self Managing Transactional Database for the Cloud", UCSB CS Tecnical Report 2010-04, March 2010.
  
  Show Abstract
  
  Cloud computing has emerged as a pervasive platform for deploying scalable and highly available Internet applications. To facilitate the migration of data-driven applications to the cloud: elasticity, scalability, fault-tolerance, and self-manageability (henceforth referred to as cloud features) are fundamental requirements for database management systems (DBMS) driving such applications. Even though extremely successful in the traditional enterprise setting . the high cost of commercial relational database software, and the lack of the desired cloud features in the open source counterparts . relational databases (RDBMS) are not a competitive choice for cloud-bound applications. As a result, Key-Value stores have emerged as a preferred choice for scalable and faulttolerant data management, but lack the rich functionality, and transactional guarantees of RDBMS. We present ElasTraS, an Elastic TranSactional relational database, designed to scale out using a cluster of commodity machines while being fault-tolerant and self managing. ElasTraS is designed to support both classes of database needs for the cloud: (i) large databases partitioned across a set of nodes, and (ii) a large number of small and independent databases common in multi-tenant databases. ElasTraS borrows from the design philosophy of scalable Key-Value stores to minimize distributed synchronization and remove scalability bottlenecks, while leveraging decades of research on transaction processing, concurrency control, and recovery to support rich functionality and transactional guarantees. We present the design of ElasTraS, implementation details of our initial prototype system, and experimental results executing the TPC-C benchmark.

  Hide Abstract

2009

• Sudipto Das, Shyam Antony, Divyakant Agrawal, Amr El Abbadi, "Thread Cooperation in Multicore Architectures for Frequency Counting Over Multiple Data Streams", UCSB CS Tecnical Report 2009-04, March 2009.
  
  Show Abstract
  
  Many real-world data stream analysis applications such as network monitoring, click stream analysis etc., require combining multiple streams of data arriving from multiple sources. This is referred to as multi-stream analysis. To deal with high stream arrival rates, it is desirable that such systems be capable of supporting very high processing throughput. The advent of multicore processors and powerful servers driven by these processors open many research challenges for exploiting parallelism for high throughput processing. This calls for efficient parallel designs that can effectively utilize the parallelism of the multicores. In this paper, we address this problem of parallelizing multi-stream analysis in the context of multicore processors. Parallelizing stream analysis is extremely important since in the multicore era, performance improvement is possible only through effective parallelization. Specifically, we concentrate on parallelizing frequent elements, top-k, and frequency counting over multiple streams. We discuss the challenges in designing an efficient parallel system for processing streams originating from multiple sources. Our evaluation and analysis reveals that traditional .contention. based locking results in excessive overhead which lead to severe performance degradation in modern multicore architectures. Based on our analysis, we propose a .cooperation. based locking paradigm for efficient parallelization of frequency counting. Our implementation of the proposed paradigm to parallelize a well known frequency counting algorithm shows the benefits of the proposed .cooperation. based locking paradigm when compared to the traditional .contention. based locking paradigm. In our experiments, the proposed .cooperation. based design outperforms the traditional .contention. based design by a factor of 2 . 5.5X for synthetic zipfian data sets.

  Hide Abstract

• Sudipto Das, Omer Egecioglu, Amr El Abbadi, "Anonymizing Edge-Weighted Social Network Graphs", UCSB CS Tecnical Report 2009-03, March 2009.
  
  Show Abstract
  
  The increasing popularity of social networks has initiated a fertile research area in information extraction and data mining. Although such analysis can facilitate better understanding of sociological, behavioral, and other interesting phenomena, there is growing concern about personal privacy being breached, thereby requiring effective anonymization techniques. If we consider the social graph to be a weighted graph, then the problem of anonymization can be of various types: node identity anonymization, structural anonymization, or edge weight anonymization. In this paper, we consider edge weight anonymization in which the anonymization preserves important properties of the underlying graphs. Our approach builds a linear programming (LP) model which preserves properties of the graph that are expressible as linear functions of the edge weights. Such properties form the foundations of many prevalent graph-theoretic algorithms such as single source shortest paths tree, all-pairs shortest paths, k-nearest neighbors, minimum cost spanning tree, etc. Off-the-shelf LP solvers can be used to find solutions to the resulting model where the computed solutions form the weights of the anonymized graph. We demonstrate how this abstract model can be used for different applications, prove the correctness of the extended models, analyze their complexity for selected graph algorithms, and experimentally evaluate the proposed techniques using real social network data sets.

  Hide Abstract

2008

• Sudipto Das, Shyam Antony, Divyakant Agrawal, Amr El Abbadi, "Clouded Data: Comprehending Scalable Data Management Systems", [Paper] UCSB CS Tecnical Report 2008-18, November 2008.
  
  Show Abstract
  
  Managing petabytes of data for millions of users has been a challenge for big internet based enterprises such as Google, Yahoo!, and Amazon. Even though database management systems have a long history of managing enterprise level data and information, they are deemed to be unsuitable in this context. This resulted in an architectural redesign of data management systems with an eye towards the requirements of high scalability, high availability, and low latency while providing weaker consistency and lower application generality. In this paper, we try to comprehend what is fundamentally different in the internet-scale applications that allowed these data management systems to achieve orders of magnitude higher levels of scalability compared to traditional databases. With an understanding of these modern systems, we also make an attempt to predict future application requirements and raise two fundamental questions: where do we really stand in terms of scalable data management, and how far are we from providing scalable data management as a service, just as computing is provided as a service in large scale infrastructures?

  Hide Abstract

• Sudipto Das, Shyam Antony, Divyakant Agrawal, Amr El Abbadi, "CoTS: A Scalable Framework for Parallelizing Frequency Counting over Data Streams", [Paper] UCSB CS Tecnical Report 2008-08, June 2008.
  
  Show Abstract
  
  Applications involving analysis of data streams have gained significant popularity and importance. Frequency counting, frequent elements and top-k queries form a class of operators that are used for a wide range of stream analysis applications. In spite of the abundance of these algorithms, all known techniques for answering data stream queries are sequential in nature. The imminent ubiquity of Chip Multi-Processor (CMP) architectures requires algorithms that can exploit the parallelism of such architectures. In this paper, we first explore the challenges in parallelizing frequent elements and top-k queries in the context of the inherent parallelism available in multi-core processors, evaluate different naive techniques for intra-operator parallelism, and summarize the insights obtained from the different parallelization efforts. Our experimental analysis of the naive designs implemented in the paper shows that intra-operator parallelism is not straightforward and requires a complete redesign of the system. Based on the lessons learnt from this analysis, we design an efficient and scalable framework for parallelizing frequency counting, frequent elements and top-k queries over data streams. The proposed CoTS (Co-operative Thread Scheduling) framework is based on the principle of threads co-operating rather than contending. Our experiments on a state-of-the-art quad-core chip multiprocessor architecture and synthetic data sets demonstrate the scalability of the proposed framework, and the efficiency is demonstrated by peak throughput of more that 60 million elements per second. In addition, for skewed data distributions, despite using heavy weight synchronization primitives, the implementation of the proposed framework outperforms the sequential implementation by a factor of 2 - 4X.

  Hide Abstract

Top of Page

Talks & Presentations

2011

• "Scalable, Consistent, and Elastic Database Systems for Cloud Platforms", presented at various industry research labs. A recording of the talk presented at Microsoft Research, Redmond can be found here.
• "Albatross: Lightweight Elasticity in Shared Storage Databases for the Cloud using Live Data Migration", presented at VLDB 2011, Seattle, WA, USA.
• "Zephyr: Live Migration in Shared Nothing Databases for Elastic Cloud Platforms", presented at SIGMOD 2011, Athens, Greece.
• "Big Data and Cloud Computing: Current State and Future Opportunities"[Part1][Part2], Tutorial presented at EDBT 2011, Uppsala, Sweden.

2010

• "Big Data and Cloud Computing: New Wine or just New Bottles?"[Part1][Part2], Tutorial presented at VLDB 2010, Singapore

• "Ricardo: Integrating R and Hadoop", presented at SIGMOD 2010, Indianapolis, IN, USA

• "G-Store: A Scalable Data Store for Transactional Multi key Access in the Cloud", presented at SoCC 2010, Indianapolis, IN, USA

• "Anonymizing Weighted Social Network Graphs", presented at ICDE 2010, Long Beach, CA

2009

• "Thread Cooperation in Multicore Architectures for Frequency Counting Over Multiple Data Streams", presented at VLDB 2009, Lyon, France.

• "Out-of-Order Processing: A New Architecture for High-Performance Stream Systems", presented at CS 595D, Winter 2009 at UCSB.

2008

• "Online Routing in Triangulations", presented at CS 235, Fall 2008 at UCSB.

• "Data Stream Operators Under the Scanner: Challenges and Insights towards Efficient Parallelization", presented at GSWC 2008 at UCSB.

• "CAM Conscious Integrated Answering of Frequent Elements and Top-k Queries over Data Streams", presented at DaMoN 2008 in Conjunction with SIGMOD/PODS 2008, Vancouver, Canada.

• "Collaborative Authoring -- Can we trust it?", presented at CS 290D (Winter 08), CS@UCSB.

• "Accelerating Data Management Operations using New Hardware Paradigms", a talk for my Major Area Exam (Winter 08) at CS@UCSB for partial fulfillment for requirements towards PhD.

2007

• "Accelerating Data Stream Operations using NPU and TCAMs ", presented at CS 290D (Fall 07), CS@UCSB.

• "Simultaneous Scalability and Security for Data-Intensive Web Applications", presented at CS 595N (Spring 07): Anonymous and Privacy Preserving Systems, CS@UCSB.

• "QoS Routing in Wireless Mesh Networks", presented at CS 290F (Winter 07), CS@UCSB.

• "Approximate Data Collection in Sensor Networks using Probabilistic Models", presented at CS 595D (Winter 07): Topics in Database Systems, CS@UCSB.

2006

• "Virtual Mobile Nodes for Mobile Ad Hoc Networks", presented at CS 271 (Fall 06), CS@UCSB.

• "QoS Routing in Wireless Mesh Networks", presented at CS 276 (Fall 06), CS@UCSB.

• "Phishing", presented at CS 501 (Fall 06), CS@UCSB. Video

• "Designing DCCP: Congestion Control Without Reliability", presented at CS 595N (Fall 06): Systems and Networking Seminar, CS@UCSB.

• "Security Issues in Mobile Ad hoc Networks", presented as a partial fulfillment towards the Bachelor of Engineering Degree.

2005

• "Implementation of Ad hoc Mesh Networks", presented at the 1-day seminar on Wireless and Mobile Computing Organized by the Computer Chapter of IEEE Calcutta Section