text:
@inproceedings{10.1145/2723372.2723374,
author = {Patel, Jignesh M.},
title = {From Data to Insights @ Bare Metal Speed},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723374},
doi = {10.1145/2723372.2723374},
abstract = {Data analytics platforms today largely employ data processing kernels (e.g. implementation of selection and join operator algorithms) that were developed for a now bygone hardware era. Hardware has made fundamental shifts in recent years, driven by the need to consider energy as a first-class design parameter. Consequently, across the processor-IO hierarchy, the hardware paradigm today looks very different than it did just a few years ago. I argue that because of this shift, we are now building a 'deficit' between the pace at which the hardware is evolving and the pace that is demanded of data processing kernels to keep up with the growth of big data. This deficit is unsustainable in the long run. One way to 'pay off' this deficit is to have hardware and software co-evolve to exploit the full potential of the hardware. I will provide some examples of recent work from our Wisconsin Quickstep project that demonstrates the merit of this line of thinking. I'll focus on analytical data processing environments, and argue that our new way of storing data, called BitWeaving, and flattening databases into BitWeaved de-normalized tables, which we call WideTables, provides a dramatic new way to build 'sustainable' analytical data processing systems. I will also discuss the implications of our approach on future hardware-software co-design for data analytics platforms.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1},
numpages = {1},
keywords = {intra-cycle parallelism, analytics, hardware-software co-design},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2747641,
author = {Yan, Ying and Zhang, Jiaxing and Huang, Bojun and Sun, Xuzhan and Mu, Jiaqi and Zhang, Zheng and Moscibroda, Thomas},
title = {Distributed Outlier Detection Using Compressive Sensing},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2747641},
doi = {10.1145/2723372.2747641},
abstract = {Computing outliers and related statistical aggregation functions from large-scale big data sources is a critical operation in many cloud computing scenarios, e.g. service quality assurance, fraud detection, or novelty discovery. Such problems commonly have to be solved in a distributed environment where each node only has a local slice of the entirety of the data. To process a query on the global data, each node must transmit its local slice of data or an aggregated subset thereof to a global aggregator node, which can then compute the desired statistical aggregation function. In this context, reducing the total communication cost is often critical to the overall efficiency.In this paper, we show both theoretically and empirically that these communication costs can be significantly reduced for common distributed computing problems if we take advantage of the fact that production-level big data usually exhibits a form of sparse structure. Specifically, we devise a new aggregation paradigm for outlier detection and related queries. The paradigm leverages compressive sensing for data sketching in combination with outlier detection techniques. We further propose an algorithm that works even for non-sparse data that concentrates around an unknown value. In both cases, we show that the communication cost is reduced to the logarithm of the global data size. We incorporate our approach into Hadoop and evaluate it on real web-scale production data (distributed click-data logs). Our approach reduces data shuffling IO by up to 99%, and end-to-end job duration by up to 40% on many actual production queries.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {3–16},
numpages = {14},
keywords = {big sparse data, distributed aggregation, compressive sensing, outlier detection},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723718,
author = {Zamanian, Erfan and Binnig, Carsten and Salama, Abdallah},
title = {Locality-Aware Partitioning in Parallel Database Systems},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723718},
doi = {10.1145/2723372.2723718},
abstract = {Parallel database systems horizontally partition large amounts of structured data in order to provide parallel data processing capabilities for analytical workloads in shared-nothing clusters. One major challenge when horizontally partitioning large amounts of data is to reduce the network costs for a given workload and a database schema. A common technique to reduce the network costs in parallel database systems is to co-partition tables on their join key in order to avoid expensive remote join operations. However, existing partitioning schemes are limited in that respect since only subsets of tables in complex schemata sharing the same join key can be co-partitioned unless tables are fully replicated.In this paper we present a novel partitioning scheme called predicate-based reference partition (or PREF for short) that allows to co-partition sets of tables based on given join predicates. Moreover, based on PREF, we present two automatic partitioning design algorithms to maximize data-locality. One algorithm only needs the schema and data whereas the other algorithm additionally takes the workload as input. In our experiments we show that our automated design algorithms can partition database schemata of different complexity and thus help to effectively reduce the runtime of queries under a given workload when compared to existing partitioning approaches.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {17–30},
numpages = {14},
keywords = {partitioning schemes},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2747642,
author = {Feng, Ziqiang and Lo, Eric and Kao, Ben and Xu, Wenjian},
title = {ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2747642},
doi = {10.1145/2723372.2747642},
abstract = {Scan and lookup are two core operations in main memory column stores. A scan operation scans a column and returns a result bit vector that indicates which records satisfy a filter. Once a column scan is completed, the result bit vector is converted into a list of record numbers, which is then used to look up values from other columns of interest for a query. Recently there are several in-memory data layout proposals that aim to improve the performance of in-memory data processing. However, these solutions all stand at either end of a trade-off --- each is either good in lookup performance or good in scan performance, but not both. In this paper we present ByteSlice, a new main memory storage layout that supports both highly efficient scans and lookups. ByteSlice is a byte-level columnar layout that fully leverages SIMD data-parallelism. Micro-benchmark experiments show that ByteSlice achieves a data scan speed at less than 0.5 processor cycle per column value --- a new limit of main memory data scan, without sacrificing lookup performance. Our experiments on TPC-H data and real data show that ByteSlice offers significant performance improvement over all state-of-the-art approaches.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {31–46},
numpages = {16},
keywords = {olap, simd, column store, storage layout, main memory},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2750543,
author = {Alexandrov, Alexander and Kunft, Andreas and Katsifodimos, Asterios and Sch\"{u}ler, Felix and Thamsen, Lauritz and Kao, Odej and Herb, Tobias and Markl, Volker},
title = {Implicit Parallelism through Deep Language Embedding},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2750543},
doi = {10.1145/2723372.2750543},
abstract = {The appeal of MapReduce has spawned a family of systems that implement or extend it. In order to enable parallel collection processing with User-Defined Functions (UDFs), these systems expose extensions of the MapReduce programming model as library-based dataflow APIs that are tightly coupled to their underlying runtime engine. Expressing data analysis algorithms with complex data and control flow structure using such APIs reveals a number of limitations that impede programmer's productivity.In this paper we show that the design of data analysis languages and APIs from a runtime engine point of view bloats the APIs with low-level primitives and affects programmer's productivity. Instead, we argue that an approach based on deeply embedding the APIs in a host language can address the shortcomings of current data analysis languages. To demonstrate this, we propose a language for complex data analysis embedded in Scala, which (i) allows for declarative specification of dataflows and (ii) hides the notion of data-parallelism and distributed runtime behind a suitable intermediate representation. We describe a compiler pipeline that facilitates efficient data-parallel processing without imposing runtime engine-bound syntactic or semantic restrictions on the structure of the input programs. We present a series of experiments with two state-of-the-art systems that demonstrate the optimization potential of our approach.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {47–61},
numpages = {15},
keywords = {data-parallel execution, monad comprehensions, scala macros, control flow, mapreduce, large-scale data analysis},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2750545,
author = {Chu, Shumo and Balazinska, Magdalena and Suciu, Dan},
title = {From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2750545},
doi = {10.1145/2723372.2750545},
abstract = {Big data analytics often requires processing complex queries using massive parallelism, where the main performance metrics is the communication cost incurred during data reshuffling. In this paper, we describe a system that can compute efficiently complex join queries, including queries with cyclic joins, on a massively parallel architecture. We build on two independent lines of work for multi-join query evaluation: a communication-optimal algorithm for distributed evaluation, and a worst-case optimal algorithm for sequential evaluation. We evaluate these algorithms together, then describe novel, practical optimizations for both algorithms.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {63–78},
numpages = {16},
keywords = {join query evaluation, parallel database system},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2751520,
author = {Elgamal, Tarek and Yabandeh, Maysam and Aboulnaga, Ashraf and Mustafa, Waleed and Hefeeda, Mohamed},
title = {SPCA: Scalable Principal Component Analysis for Big Data on Distributed Platforms},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2751520},
doi = {10.1145/2723372.2751520},
abstract = {Web sites, social networks, sensors, and scientific experiments currently generate massive amounts of data. Owners of this data strive to obtain insights from it, often by applying machine learning algorithms. Many machine learning algorithms, however, do not scale well to cope with the ever increasing volumes of data. To address this problem, we identify several optimizations that are crucial for scaling various machine learning algorithms in distributed settings. We apply these optimizations to the popular Principal Component Analysis (PCA) algorithm. PCA is an important tool in many areas including image processing, data visualization, information retrieval, and dimensionality reduction. We refer to the proposed optimized PCA algorithm as scalable PCA, or sPCA. sPCA achieves scalability via employing efficient large matrix operations, effectively leveraging matrix sparsity, and minimizing intermediate data. We implement sPCA on the widely-used MapReduce platform and on the memory-based Spark platform. We compare sPCA against the closest PCA implementations, which are the ones in Mahout/ MapReduce and MLlib/Spark. Our experiments show that sPCA outperforms both Mahout-PCA and MLlib-PCA by wide margins in terms of accuracy, running time, and volume of intermediate data generated during the computation.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {79–91},
numpages = {13},
keywords = {high-dimensional pca, hadoop, scalable machine learning, sparse pca, spark pca, principal component analysis},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723712,
author = {Yu, Lele and Shao, Yingxia and Cui, Bin},
title = {Exploiting Matrix Dependency for Efficient Distributed Matrix Computation},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723712},
doi = {10.1145/2723372.2723712},
abstract = {Distributed matrix computation is a popular approach for many large-scale data analysis and machine learning tasks. However existing distributed matrix computation systems generally incur heavy communication cost during the runtime, which degrades the overall performance. In this paper, we propose a novel matrix computation system, named DMac, which exploits the matrix dependencies in matrix programs for efficient matrix computation in the distributed environment. We decompose each matrix program into a sequence of operations, and reveal the matrix dependencies between operations in the program. We next design a dependency-oriented cost model to select an optimal execution strategy for each operation, and generate a communication efficient execution plan for the matrix computation program. To facilitate the matrix computation in distributed systems, we further divide the execution plan into multiple un-interleaved stages which can run in a distributed cluster with efficient local execution strategy on each worker. The DMac system has been implemented on a popular general-purpose data processing framework, Spark. The experimental results demonstrate that our techniques can significantly improve the performance of a wide range of matrix programs.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {93–105},
numpages = {13},
keywords = {dependency analysis, distributed system, matrix computing},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2747647,
author = {Teflioudi, Christina and Gemulla, Rainer and Mykytiuk, Olga},
title = {LEMP: Fast Retrieval of Large Entries in a Matrix Product},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2747647},
doi = {10.1145/2723372.2747647},
abstract = {We study the problem of efficiently retrieving large entries in the product of two given matrices, which arises in a number of data mining and information retrieval tasks. We focus on the setting where the two input matrices are tall and skinny, i.e., with millions of rows and tens to hundreds of columns. In such settings, the product matrix is large and its complete computation is generally infeasible in practice. To address this problem, we propose the LEMP algorithm, which efficiently retrieves only the large entries in the product matrix without actually computing it. LEMP maps the large-entry retrieval problem to a set of smaller cosine similarity search problems, for which existing methods can be used. We also propose novel algorithms for cosine similarity search, which are tailored to our setting. Our experimental study on large real-world datasets indicates that LEMP is up to an order of magnitude faster than state-of-the-art approaches.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {107–122},
numpages = {16},
keywords = {maximum inner product search, matrix product, large-entry retrieval},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723709,
author = {Duggan, Jennie and Papaemmanouil, Olga and Battle, Leilani and Stonebraker, Michael},
title = {Skew-Aware Join Optimization for Array Databases},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723709},
doi = {10.1145/2723372.2723709},
abstract = {Science applications are accumulating an ever-increasing amount of multidimensional data. Although some of it can be processed in a relational database, much of it is better suited to array-based engines. As such, it is important to optimize the query processing of these systems. This paper focuses on efficient query processing of join operations within an array database. These engines invariably ``chunk'' their data into multidimensional tiles that they use to efficiently process spatial queries. As such, traditional relational algorithms need to be substantially modified to take advantage of array tiles. Moreover, most n-dimensional science data is unevenly distributed in array space because its underlying observations rarely follow a uniform pattern. It is crucial that the optimization of array joins be skew-aware. In addition, owing to the scale of science applications, their query processing usually spans multiple nodes. This further complicates the planning of array joins.In this paper, we introduce a join optimization framework that is skew-aware for distributed joins. This optimization consists of two phases. In the first, a logical planner selects the query's algorithm (e.g., merge join), the granularity of the its tiles, and the reorganization operations needed to align the data. The second phase implements this logical plan by assigning tiles to cluster nodes using an analytical cost model. Our experimental results, on both synthetic and real-world data, demonstrate that this optimization framework speeds up array joins by up to 2.5X in comparison to the baseline.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {123–135},
numpages = {13},
keywords = {join optimization, skew, distributed computation, array database},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749432,
author = {Huang, Botong and Boehm, Matthias and Tian, Yuanyuan and Reinwald, Berthold and Tatikonda, Shirish and Reiss, Frederick R.},
title = {Resource Elasticity for Large-Scale Machine Learning},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749432},
doi = {10.1145/2723372.2749432},
abstract = {Declarative large-scale machine learning (ML) aims at flexible specification of ML algorithms and automatic generation of hybrid runtime plans ranging from single node, in-memory computations to distributed computations on MapReduce (MR) or similar frameworks. State-of-the-art compilers in this context are very sensitive to memory constraints of the master process and MR cluster configuration. Different memory configurations can lead to significant performance differences. Interestingly, resource negotiation frameworks like YARN allow us to explicitly request preferred resources including memory. This capability enables automatic resource elasticity, which is not just important for performance but also removes the need for a static cluster configuration, which is always a compromise in multi-tenancy environments. In this paper, we introduce a simple and robust approach to automatic resource elasticity for large-scale ML. This includes (1) a resource optimizer to find near-optimal memory configurations for a given ML program, and (2) dynamic plan migration to adapt memory configurations during runtime. These techniques adapt resources according to data, program, and cluster characteristics. Our experiments demonstrate significant improvements up to 21x without unnecessary over-provisioning and low optimization overhead.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {137–152},
numpages = {16},
keywords = {large-scale, resource optimization, resource elasticity, what-if analysis, machine learning},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723741,
author = {Oktay, Kerim Yasin and Mehrotra, Sharad and Khadilkar, Vaibhav and Kantarcioglu, Murat},
title = {SEMROD: Secure and Efficient MapReduce Over HybriD Clouds},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723741},
doi = {10.1145/2723372.2723741},
abstract = {This paper describes SEMROD, a sensitive data aware MapReduce (MR) framework for hybrid clouds. SEMROD steers data and computation through public and private machines in such a way that no knowledge about sensitive data is leaked to public machines. For this purpose, SEMROD keeps trace of intermediate keys (generated during MR execution) that become sensitive, based on which it makes dynamic task scheduling decisions. SEMROD guarantees that adversaries viz. public machines) cannot gain any ``additional'' information about sensitive data from either the data stored on public machines or the communication between public and private machines during job execution. SEMROD extends naturally from a single MR job to multi-phase MR jobs that result, for instance, from compiling Hive queries into MR jobs. Using SEMROD, computation that may involve sensitive data can exploit public machines, thereby bringing significant performance benefits. Such computation would otherwise be restricted to only private clouds. Our experiments clearly demonstrate performance advantages to using SEMROD as compared with other secure alternatives, even when the percentage of sensitive data is as high as 50%.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {153–166},
numpages = {14},
keywords = {hybrid cloud, mapreduce, secure, data processing},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2747649,
author = {Chen, Qian and Hu, Haibo and Xu, Jianliang},
title = {Authenticated Online Data Integration Services},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2747649},
doi = {10.1145/2723372.2747649},
abstract = {Data integration involves combining data from multiple sources and providing users with a unified query interface. Data integrity has been a key problem in online data integration. Although a variety of techniques have been proposed to address the data consistency and reliability issues, there is little work on assuring the integrity of integrated data and the correctness of query results. In this paper, we take the first step to propose authenticated data integration services to ensure data and query integrity even in the presence of an untrusted integration server. We develop a novel authentication code called homomorphic secret sharing seal that can aggregate the inputs from individual sources faithfully by the untrusted server for future query authentication. Based on this, we design two authenticated index structures and authentication schemes for queries on multi-dimensional data. We further study the freshness problem in multi-source query authentication and propose several advanced update strategies. Analytical models and empirical results show that our seal design and authentication schemes are efficient and robust under various system settings.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {167–181},
numpages = {15},
keywords = {data integrity, data integration, experimentation, security, algorithms, query authentication},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749439,
author = {Hang, Isabelle and Kerschbaum, Florian and Damiani, Ernesto},
title = {ENKI: Access Control for Encrypted Query Processing},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749439},
doi = {10.1145/2723372.2749439},
abstract = {A data owner outsourcing the database of a multi user application wants to prevent information leaks caused by outside attackers exploiting software vulnerabilities or by curious personnel. Query processing over encrypted data solves this problem for a single user, but provides only limited functionality in the face of access restrictions for multiple users and keys. ENKI is a system for securely executing queries over sensitive, access restricted data on an outsourced database. It introduces an encryption based access control model and techniques for query execution over encrypted, access restricted data on the database with only a few cases requiring computations on the client. A prototype of ENKI supports all queries seen in three real world use cases and executes queries from TPC-C benchmark with a modest overhead compared to the single user mode.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {183–196},
numpages = {14},
keywords = {encryption-based access control, encrypted query processing, multi user},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749433,
author = {Zaychik Moffitt, Vera and Stoyanovich, Julia and Abiteboul, Serge and Miklau, Gerome},
title = {Collaborative Access Control in WebdamLog},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749433},
doi = {10.1145/2723372.2749433},
abstract = {The management of Web users' personal information is increasingly distributed across a broad array of applications and systems, including online social networks and cloud-based services. Users wish to share data using these systems, but avoiding the risks of unintended disclosures or unauthorized access by applications has become a major challenge.We propose a novel access control model that operates within a distributed data management framework based on datalog. Using this model, users can control access to data they own and control applications they run. They can conveniently specify access control policies providing flexible tuple-level control derived using provenance information. We present a formal specification of the model, an implementation built using an open-source distributed datalog engine, and an extensive experimental evaluation showing that the computational cost of access control is modest.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {197–211},
numpages = {15},
keywords = {personal information management, distributed datalog, collaborative access control, provenance},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723721,
author = {Upadhyaya, Prasang and Balazinska, Magdalena and Suciu, Dan},
title = {Automatic Enforcement of Data Use Policies with DataLawyer},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723721},
doi = {10.1145/2723372.2723721},
abstract = {Data has value and is increasingly being exchanged for commercial and research purposes. Data, however, is typically accompanied by terms of use, which limit how it can be used. To date, there are only a few, ad-hoc methods to enforce these terms. We propose DataLawyer, a new system to formally specify usage policies and check them automatically at query runtime in a relational database management system (DBMS). We develop a new model to specify policies compactly and precisely. We introduce novel algorithms to efficiently evaluate policies that can cut policy-checking overheads to only a few percent of the total query runtime. We implement DataLawyer and evaluate it on a real database from the health-care domain.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {213–225},
numpages = {13},
keywords = {terms of use, data markets, usage management, licenses},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2742785,
author = {Huang, Yanxiang and Cui, Bin and Zhang, Wenyu and Jiang, Jie and Xu, Ying},
title = {TencentRec: Real-Time Stream Recommendation in Practice},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2742785},
doi = {10.1145/2723372.2742785},
abstract = {With the arrival of the big data era, opportunities as well as challenges arise in both industry and academia. As an important service in most web applications, accurate real-time recommendation in the context of big data is of high demand. Traditional recommender systems that analyze data and update models at regular time intervals cannot satisfy the requirements of modern web applications, calling for real-time recommender systems.In this paper, we tackle the ``big", ``real-time" and ``accurate" challenges in real-time recommendation, and propose a general real-time stream recommender system built on Storm named TencentRec from three aspects, i.e., ``system", ``algorithm", and ``data". We analyze the large amount of data streams from a wide range of applications leveraging the considerable computation ability of Storm, together with a data access component and a data storage component developed by us. To deal with various application specific demands, we have implemented several classic practical recommendation algorithms in TencentRec, including the item-based collaborative filtering, the content based, and the demographic based algorithms. Specially, we present a practical scalable item-based CF algorithm in detail, with the super characteristics such as robust to the implicit feedback problem, incremental update and real-time pruning. With the enhancement of real-time data collection and processing, we can capture the recommendation changes in real-time. We deploy the TencentRec in a series of production applications, and observe the superiority of TencentRec in providing accurate real-time recommendations for 10 billion user requests everyday.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {227–238},
numpages = {12},
keywords = {real-time recommendation, application, scalability, practice, big data},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2742788,
author = {Kulkarni, Sanjeev and Bhagat, Nikunj and Fu, Maosong and Kedigehalli, Vikas and Kellogg, Christopher and Mittal, Sailesh and Patel, Jignesh M. and Ramasamy, Karthik and Taneja, Siddarth},
title = {Twitter Heron: Stream Processing at Scale},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2742788},
doi = {10.1145/2723372.2742788},
abstract = {Storm has long served as the main platform for real-time analytics at Twitter. However, as the scale of data being processed in real-time at Twitter has increased, along with an increase in the diversity and the number of use cases, many limitations of Storm have become apparent. We need a system that scales better, has better debug-ability, has better performance, and is easier to manage -- all while working in a shared cluster infrastructure. We considered various alternatives to meet these needs, and in the end concluded that we needed to build a new real-time stream data processing system. This paper presents the design and implementation of this new system, called Heron. Heron is now the de facto stream data processing engine inside Twitter, and in this paper we also share our experiences from running Heron in production. In this paper, we also provide empirical evidence demonstrating the efficiency and scalability of Heron.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {239–250},
numpages = {12},
keywords = {real-time data processing., stream data processing systems},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2742783,
author = {Braun, Lucas and Etter, Thomas and Gasparis, Georgios and Kaufmann, Martin and Kossmann, Donald and Widmer, Daniel and Avitzur, Aharon and Iliopoulos, Anthony and Levy, Eliezer and Liang, Ning},
title = {Analytics in Motion: High Performance Event-Processing AND Real-Time Analytics in the Same Database},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2742783},
doi = {10.1145/2723372.2742783},
abstract = {Modern data-centric flows in the telecommunications industry require real time analytical processing over a rapidly changing and large dataset. The traditional approach of separating OLTP and OLAP workloads cannot satisfy this requirement. Instead, a new class of integrated solutions for handling hybrid workloads is needed. This paper presents an industrial use case and a novel architecture that integrates key-value-based event processing and SQL-based analytical processing on the same distributed store while minimizing the total cost of ownership. Our approach combines several well-known techniques such as shared scans, delta processing, a PAX-fashioned storage layout, and an interleaving of scanning and delta merging in a completely new way. Performance experiments show that our system scales out linearly with the number of servers. For instance, our system sustains event streams of 100,000 events per second while simultaneously processing 100 ad-hoc analytical queries per second, using a cluster of 12 commodity servers. In doing so, our system meets all response time goals of our telecommunication customers; that is, 10 milliseconds per event and 100 milliseconds for an ad-hoc analytical query. Moreover, our system beats commercial competitors by a factor of 2.5 in analytical and two orders of magnitude in update performance.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {251–264},
numpages = {14},
keywords = {analytics, oltp/olap engine, event-processing},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2742784,
author = {G.C., Paul Suganthan and Sun, Chong and K., Krishna Gayatri and Zhang, Haojun and Yang, Frank and Rampalli, Narasimhan and Prasad, Shishir and Arcaute, Esteban and Krishnan, Ganesh and Deep, Rohit and Raghavendra, Vijay and Doan, AnHai},
title = {Why Big Data Industrial Systems Need Rules and What We Can Do About It},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2742784},
doi = {10.1145/2723372.2742784},
abstract = {Big Data industrial systems that address problems such as classification, information extraction, and entity matching very commonly use hand-crafted rules. Today, however, little is understood about the usage of such rules. In this paper we explore this issue. We discuss how these systems differ from those considered in academia. We describe default solutions, their limitations, and reasons for using rules. We show examples of extensive rule usage in industry. Contrary to popular perceptions, we show that there is a rich set of research challenges in rule generation, evaluation, execution, optimization, and maintenance. We discuss ongoing work at WalmartLabs and UW-Madison that illustrate these challenges. Our main conclusions are (1) using rules (together with techniques such as learning and crowdsourcing) is fundamental to building semantics-intensive Big Data systems, and (2) it is increasingly critical to address rule management, given the tens of thousands of rules industrial systems often manage today in an ad-hoc fashion.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {265–276},
numpages = {12},
keywords = {classification, rule management, big data},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2731084,
author = {Idreos, Stratos and Papaemmanouil, Olga and Chaudhuri, Surajit},
title = {Overview of Data Exploration Techniques},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2731084},
doi = {10.1145/2723372.2731084},
abstract = {Data exploration is about efficiently extracting knowledge from data even if we do not know exactly what we are looking for. In this tutorial, we survey recent developments in the emerging area of database systems tailored for data exploration. We discuss new ideas on how to store and access data as well as new ideas on how to interact with a data system to enable users and applications to quickly figure out which data parts are of interest. In addition, we discuss how to exploit lessons-learned from past research, the new challenges data exploration crafts, emerging applications and future research directions.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {277–281},
numpages = {5},
keywords = {data exploration},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2742911,
author = {R\'{e}, Christopher and Agrawal, Divy and Balazinska, Magdalena and Cafarella, Michael and Jordan, Michael and Kraska, Tim and Ramakrishnan, Raghu},
title = {Machine Learning and Databases: The Sound of Things to Come or a Cacophony of Hype?},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2742911},
doi = {10.1145/2723372.2742911},
abstract = {Machine learning seems to be eating the world with a new breed of high-value data-driven applications in image analysis, search, voice recognition, mobile, and office productivity products. To paraphrase Mike Stonebraker, machine learning is no longer a zero-billion-dollar business. As the home of high-value, data-driven applications for over four decades, a natural question for database researchers to ask is: what role should the database community play in these new data-driven machine-learning-based applications?},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {283–284},
numpages = {2},
keywords = {database research, machine learning, panel},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749437,
author = {Salama, Abdallah and Binnig, Carsten and Kraska, Tim and Zamanian, Erfan},
title = {Cost-Based Fault-Tolerance for Parallel Data Processing},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749437},
doi = {10.1145/2723372.2749437},
abstract = {In order to deal with mid-query failures in parallel data engines (PDEs), different fault-tolerance schemes are implemented today: (1) fault-tolerance in parallel databases is typically implemented in a coarse-grained manner by restarting a query completely when a mid-query failure occurs, and (2) modern MapReduce-style PDEs implement a fine-grained fault-tolerance scheme, which either materializes intermediate results or implements a lineage model to recover from mid-query failures. However, neither of these schemes can efficiently handle mixed workloads with both short running interactive queries as well as long running batch queries nor do these schemes efficiently support a wide range of different cluster setups which vary in cluster size and other parameters such as the mean time between failures. In this paper, we present a novel cost-based fault-tolerance scheme which tackles this issue. Compared to the existing schemes, our scheme selects a subset of intermediates to be materialized such that the total query runtime is minimized under mid-query failures. Our experiments show that our cost-based fault-tolerance scheme outperforms all existing strategies and always selects the sweet spot for short- and long running queries as well as for different cluster setups.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {285–297},
numpages = {13},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723726,
author = {Elmore, Aaron J. and Arora, Vaibhav and Taft, Rebecca and Pavlo, Andrew and Agrawal, Divyakant and El Abbadi, Amr},
title = {Squall: Fine-Grained Live Reconfiguration for Partitioned Main Memory Databases},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723726},
doi = {10.1145/2723372.2723726},
abstract = {For data-intensive applications with many concurrent users, modern distributed main memory database management systems (DBMS) provide the necessary scale-out support beyond what is possible with single-node systems. These DBMSs are optimized for the short-lived transactions that are common in on-line transaction processing (OLTP) workloads. One way that they achieve this is to partition the database into disjoint subsets and use a single-threaded transaction manager per partition that executes transactions one-at-a-time in serial order. This minimizes the overhead of concurrency control mechanisms, but requires careful partitioning to limit distributed transactions that span multiple partitions. Previous methods used off-line analysis to determine how to partition data, but the dynamic nature of these applications means that they are prone to hotspots. In these situations, the DBMS needs to reconfigure how data is partitioned in real-time to maintain performance objectives. Bringing the system off-line to reorganize the database is unacceptable for on-line applications.To overcome this problem, we introduce the Squall technique for supporting live reconfiguration in partitioned, main memory DBMSs. Squall supports fine-grained repartitioning of databases in the presence of distributed transactions, high throughput client workloads, and replicated data. An evaluation of our approach on a distributed DBMS shows that Squall can reconfigure a database with no downtime and minimal overhead on transaction latency.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {299–313},
numpages = {15},
keywords = {migration, reconfiguration, load-balancing},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2724578,
author = {Mishima, Takeshi and Fujiwara, Yasuhiro},
title = {Madeus: Database Live Migration Middleware under Heavy Workloads for Cloud Environment},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2724578},
doi = {10.1145/2723372.2724578},
abstract = {Database-as-a-service has been gaining popularity in cloud computing because multitenant databases can reduce costs by sharing off-the-shelf resources. However, due to heavy workloads, resource sharing often causes a hot spot; one node is overloaded even while others are not. Unfortunately, a hot spot can lead to violation of service level agreements and destroy customer satisfaction. To efficiently address the hot spot problem, we propose a middleware approach called Madeus that conducts database live migration. To make efficient database live migration possible, we also introduce the lazy snapshot isolation rule (LSIR) that enables concurrently propagating syncsets, which are the datasets needed to synchronize slave with master databases. Madeus provides efficient database live migration by implementing the LSIR under snapshot isolation. Unlike current approaches, Madeus is pure middleware that is transparent to the database management system and based on commodity hardware and software. To demonstrate the superiority of our approach over current approaches, we experimentally evaluated Madeus by using PostgreSQL with the TPC-W benchmark. The results indicate that Madeus achieves more efficient live migration than three other types of middleware approaches, especially under heavy workloads; therefore, it can effectively resolve hot spots.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {315–329},
numpages = {15},
keywords = {middleware, concurrency control, hot spot, database live migration},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723711,
author = {Alvaro, Peter and Rosen, Joshua and Hellerstein, Joseph M.},
title = {Lineage-Driven Fault Injection},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723711},
doi = {10.1145/2723372.2723711},
abstract = {In large-scale data management systems, failure is practically a certainty. Fault-tolerant protocols and components are notoriously difficult to implement and debug. Worse still, choosing existing fault-tolerance mechanisms and integrating them correctly into complex systems remains an art form, and programmers have few tools to assist them.We propose a novel approach for discovering bugs in fault-tolerant data management systems: lineage-driven fault injection. A lineage-driven fault injector reasons backwards from correct system outcomes to determine whether failures in the execution could have prevented the outcome. We present MOLLY, a prototype of lineage-driven fault injection that exploits a novel combination of data lineage techniques from the database literature and state-of-the-art satisfiability testing. If fault-tolerance bugs exist for a particular configuration, MOLLY finds them rapidly, in many cases using a order of magnitude fewer executions than random fault injection. Otherwise, MOLLY certifies that the code is bug-free for that configuration.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {331–346},
numpages = {16},
keywords = {provenance, fault-tolerance, verification},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749451,
author = {Chen, Lisi and Cong, Gao},
title = {Diversity-Aware Top-k Publish/Subscribe for Text Stream},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749451},
doi = {10.1145/2723372.2749451},
abstract = {Massive amount of text data are being generated by a huge number of web users at an unprecedented scale. These data cover a wide range of topics. Users are interested in receiving a few up-to-date representative documents (e.g., tweets) that can provide them with a wide coverage of different aspects of their query topics. To address the problem, we consider the Diversity-Aware Top-k Subscription (DAS) query. Given a DAS query, we continuously maintain an up-to-date result set that contains k most recently returned documents over a text stream for the query. The DAS query takes into account text relevance, document recency, and result diversity. We propose a novel solution to efficiently processing a large number of DAS queries over a stream of documents. We demonstrate the efficiency of our approach on real-world dataset and the experimental results show that our solution is able to achieve a reduction of the processing time by 60--75% compared with two baselines. We also study the effectiveness of the DAS query.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {347–362},
numpages = {16},
keywords = {publish/subscribe, text stream, diversification},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2737783,
author = {Fakas, Georgios and Cai, Zhi and Mamoulis, Nikos},
title = {Diverse and Proportional Size-l Object Summaries for Keyword Search},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2737783},
doi = {10.1145/2723372.2737783},
abstract = {The abundance and ubiquity of graphs (e.g., Online Social Networks such as Google+ and Facebook; bibliographic graphs such as DBLP) necessitates the effective and efficient search over them. Given a set of keywords that can identify a Data Subject (DS), a recently proposed relational keyword search paradigm produces, as a query result, a set of Object Summaries (OSs). An OS is a tree structure rooted at the DS node (i.e., a tuple containing the keywords) with surrounding nodes that summarize all data held on the graph about the DS. OS snippets, denoted as size-l OSs, have also been investigated. Size-l OSs are partial OSs containing l nodes such that the summation of their importance scores results in the maximum possible total score. However, the set of nodes that maximize the total importance score may result in an uninformative size-l OSs, as very important nodes may be repeated in it, dominating other representative information. In view of this limitation, in this paper we investigate the effective and efficient generation of two novel types of OS snippets, i.e. diverse and proportional size-l OSs, denoted as DSize-l and PSize-l OSs. Namely, apart from the importance of each node, we also consider its frequency in the OS and its repetitions in the snippets. We conduct an extensive evaluation on two real graphs (DBLP and Google+). We verify effectiveness by collecting user feedback, e.g. by asking DBLP authors (i.e. the DSs themselves) to evaluate our results. In addition, we verify the efficiency of our algorithms and evaluate the quality of the snippets that they produce.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {363–375},
numpages = {13},
keywords = {proportionality, keyword search, diversity, summaries, ranking},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749445,
author = {Yang, Xiaochun and Wang, Yaoshu and Wang, Bin and Wang, Wei},
title = {Local Filtering: Improving the Performance of Approximate Queries on String Collections},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749445},
doi = {10.1145/2723372.2749445},
abstract = {We study efficient query processing for approximate string queries, which find strings within a string collection whose edit distances to the query strings are within the given thresholds. Existing methods typically hinge on the property that globally similar strings must share at least certain number of identical substrings or subsequences. They become ineffective when there are burst errors or when the number of errors is large. In this paper, we explore the opposite paradigm focusing on finding out the differences of database strings to the query string. We propose a new filtering method, called local filtering, based on the idea that two strings exhibiting substantial local dissimilarities must be globally dissimilar. We propose the concept of (positional) local distance to quantify the minimum amount of errors a query fragment contributes to the edit distance between the query and a data string. It also leads to effective pruning rules and can speed up verification via early termination. We devise a family of indexing methods based on the idea of precomputing (positional) local distances for all possible combinations of query fragments and edit distance thresholds. Based on careful analyses of subtle relationships among local distances, novel techniques are proposed to drastically reduce the amount of enumeration with no or little impact on the pruning power. Efficient query processing methods exploiting the new index and bit-parallelism are also proposed. Experimental results on real datasets show that our local filtering-based methods can achieve substantial speedup compared with state-of-the-art methods, and they are robust against factors such as dataset characteristics and large edit distance thresholds.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {377–392},
numpages = {16},
keywords = {string, edit distance, approximate query, filtering, estimation},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749447,
author = {Jiang, Minhao and Fu, Ada Wai-Chee and Wong, Raymond Chi-Wing},
title = {Exact Top-k Nearest Keyword Search in Large Networks},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749447},
doi = {10.1145/2723372.2749447},
abstract = {Top-k nearest keyword search has been of interest because of applications ranging from road network location search by keyword to search of information on an RDF repository. We consider the evaluation of a query with a given vertex and a keyword, and the problem is to find a set of $k$ nearest vertices that contain the keyword. The known algorithms for handling this problem only give approximate answers. In this paper, we propose algorithms for top-k nearest keyword search that provide exact solutions and which handle networks of very large sizes. We have also verified the performance of our solutions compared with the best-known approximation algorithms with experiments on real datasets.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {393–404},
numpages = {12},
keywords = {keyword-lookup tree, 2-hop labeling, nearest keyword search},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723723,
author = {Guo, Tao and Cao, Xin and Cong, Gao},
title = {Efficient Algorithms for Answering the M-Closest Keywords Query},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723723},
doi = {10.1145/2723372.2723723},
abstract = {As an important type of spatial keyword query, the m-closest keywords (mCK) query finds a group of objects such that they cover all query keywords and have the smallest diameter, which is defined as the largest distance between any pair of objects in the group. The query is useful in many applications such as detecting locations of web resources. However, the existing work does not study the intractability of this problem and only provides exact algorithms, which are computationally expensive.In this paper, we prove that the problem of answering mCK queries is NP-hard. We first devise a greedy algorithm that has an approximation ratio of 2. Then, we observe that an mCK query can be approximately answered by finding the circle with the smallest diameter that encloses a group of objects together covering all query keywords. We prove that the group enclosed in the circle can answer the mCK query with an approximation ratio of 2 over 3. Based on this, we develop an algorithm for finding such a circle exactly, which has a high time complexity. To improve efficiency, we propose another two algorithms that find such a circle approximately, with a ratio of 2 over √3 + ε. Finally, we propose an exact algorithm that utilizes the group found by the 2 over √3 + ε)-approximation algorithm to obtain the optimal group. We conduct extensive experiments using real-life datasets. The experimental results offer insights into both efficiency and accuracy of the proposed approximation algorithms, and the results also demonstrate that our exact algorithm outperforms the best known algorithm by an order of magnitude.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {405–418},
numpages = {14},
keywords = {geo-textual objects, spatial keyword query},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723717,
author = {Huang, Silu and Fu, Ada Wai-Chee and Liu, Ruifeng},
title = {Minimum Spanning Trees in Temporal Graphs},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723717},
doi = {10.1145/2723372.2723717},
abstract = {The computation of Minimum Spanning Trees (MSTs) is a fundamental graph problem with important applications. However, there has been little study of MSTs for temporal graphs, which is becoming common as time information is collected for many existing networks. We define two types of MSTs for temporal graphs, MSTa and MSTw, based on the optimization of time and cost, respectively. We propose efficient linear time algorithms for computing MSTa. We show that computing MSTw is much harder. We design efficient approximation algorithms based on a transformation to the Directed Steiner Tree problem (DST). Our solution also solves the classical DST problem with a better time complexity and the same approximation factor compared to the state-of-the-art algorithm. Our experiments on real temporal networks further verify the effectiveness of our algorithms. For MSTw, our solution is capable of shortening the runtime from 10 hours to 3 seconds.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {419–430},
numpages = {12},
keywords = {steiner tree, temporal graph, minimum spanning tree},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2746478,
author = {Berlowitz, Devora and Cohen, Sara and Kimelfeld, Benny},
title = {Efficient Enumeration of Maximal K-Plexes},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2746478},
doi = {10.1145/2723372.2746478},
abstract = {The problem of enumerating (i.e., generating) all maximal cliques in a graph has received extensive treatment, due to the plethora of applications in various areas such as data mining, bioinformatics, network analysis and community detection. However, requiring the enumerated subgraphs to be full cliques is too restrictive in common real-life scenarios where "almost cliques" are equally useful. Hence, the notion of a k-plex, a clique relaxation that allows every node to be "missing" k neighbors, has been introduced. But this seemingly minor relaxation casts existing algorithms for clique enumeration inapplicable, for inherent reasons. This paper presents the first provably efficient algorithms, both for enumerating the maximal k-plexes and for enumerating the maximal connected k-plexes. Our algorithms run in polynomial delay for a constant k and incremental FPT delay when k is a parameter. The importance of such algorithms is in the areas mentioned above, as well as in new applications. Extensive experimentation over both real and synthetic datasets shows the efficiency of our algorithms, and their scalability with respect to graph size, density and choice of k, as well as their clear superiority over the state-of-the-art.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {431–444},
numpages = {14},
keywords = {fixed-parameter tractability, maximal k-plex, polynomial delay, enumeration, maximal graph clique},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723740,
author = {Zhang, Zhiwei and Yu, Jeffrey Xu and Qin, Lu and Shang, Zechao},
title = {Divide & Conquer: I/O Efficient Depth-First Search},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723740},
doi = {10.1145/2723372.2723740},
abstract = {Depth-First Search (DFS), which traverses a graph in the depth- first order, is one of the fundamental graph operations, and the result of DFS over all nodes in G is a spanning tree known as a DFS-Tree. There are many graph algorithms that need DFS such as connected component computation, topological sort, community detection, eulerian path computation, graph bipartiteness testing, planar graph testing, etc, because the in-memory DFS algorithm shows it can be done in linear time w.r.t. the size of G. However, given the fact that real-world graphs grow rapidly in the big data era, the in-memory DFS algorithm cannot be used to handle a large graph that cannot be entirely held in main memory. In this paper, we focus on I/O efficiency and study semi-external algorithms to DFS a graph G which is on disk. Here, like the existing semi-external algorithms, we assume that a spanning tree of G can be held in main memory and the remaining edges of G are kept on disk, and compute the DFS-Tree in main memory with which DFS can be identified. We propose novel divide & conquer algorithms to DFS over a graph G on disk. In brief, we divide a graph into several subgraphs, compute the DFS-Tree for each subgraph independently, and then merge them together to compute the DFS-Tree for the whole graph. With the global DFS-Tree computed we identify DFS. We discuss the valid division, that can lead to the correct DFS, and the challenges to do so. We propose two division algorithms, named Divide-Star and Divide-TD, and a merge algorithm. We conduct extensive experimental studies using four real massive datasets and several synthetic datasets to confirm the I/O efficiency of our approach.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {445–458},
numpages = {14},
keywords = {graph algorithm, i/o efficient, depth-first search},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2746486,
author = {Chang, Lijun and Lin, Xuemin and Qin, Lu and Yu, Jeffrey Xu and Zhang, Wenjie},
title = {Index-Based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2746486},
doi = {10.1145/2723372.2746486},
abstract = {With the proliferation of graph applications, the problem of efficiently computing all $k$-edge connected components of a graph G for a user-given k has been recently investigated. In this paper, we study the problem of efficiently computing the steiner component with the maximum connectivity; that is, given a set q of query vertices in a graph G, we aim to find the maximum induced subgraph g of G such that g contains q and g has the maximum connectivity, where g is denoted as SMCC. To accommodate online query processing, we present an efficient algorithm based on a novel index such that the algorithm runs in linear time regarding the result size; thus, the algorithm is optimal since it needs at least linear time to output the result. Moreover, in this paper we also investigate variations of the above problem. We show that such a problem with the constraint that the size of the SMCC is not smaller than a given size can also be solved in linear time regarding the result size (thus, optimal). We also show that the problem of computing the connectivity (rather than the graph details) of SMCC can be solved in linear time regarding the query size (thus, optimal). To build the index, we extend the techniques in [7] to accommodate batch processing and computation sharing. To efficiently support the applications with graph updates, we also present novel increment techniques. Finally, we conduct extensive performance studies on large real and synthetic graphs, which demonstrate that our index-based algorithms significantly outperform baseline algorithms by several orders of magnitude and our indexing algorithms are efficient.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {459–474},
numpages = {16},
keywords = {dynamic graph, steiner maximum-connected component, k-edge connected com- ponent, maximum spanning tree},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2737791,
author = {Gurukar, Saket and Ranu, Sayan and Ravindran, Balaraman},
title = {COMMIT: A Scalable Approach to Mining Communication Motifs from Dynamic Networks},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2737791},
doi = {10.1145/2723372.2737791},
abstract = {A fundamental problem in behavioral analysis of human interactions is to understand how communications unfold. In this paper, we study this problem by mining Communication motifs from dynamic interaction networks. A communication motif is a recurring subgraph that has a similar sequence of information flow. Mining communication motifs requires us to explore the exponential subgraph search space where existing techniques fail to scale. To tackle this scalability bottleneck, we develop a technique called COMMIT. COMMIT converts a dynamic graph into a database of sequences. Through careful analysis in the sequence space, only a small portion of the exponential search space is accessed to identify regions embedding communication motifs. Extensive experiments on three different social networks show COMMIT to be up to two orders of magnitude faster than baseline techniques. Furthermore, qualitative analysis demonstrate communication motifs to be effective in characterizing the recurring patterns of interactions while also revealing the role that the underlying social network plays in shaping human behavior.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {475–489},
numpages = {15},
keywords = {communication motifs, graph mining, interaction networks},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723724,
author = {Beedkar, Kaustubh and Gemulla, Rainer},
title = {LASH: Large-Scale Sequence Mining with Hierarchies},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723724},
doi = {10.1145/2723372.2723724},
abstract = {We propose LASH, a scalable, distributed algorithm for mining sequential patterns in the presence of hierarchies. LASH takes as input a collection of sequences, each composed of items from some application-specific vocabulary. In contrast to traditional approaches to sequence mining, the items in the vocabulary are arranged in a hierarchy: both input sequences and sequential patterns may consist of items from different levels of the hierarchy. Such hierarchies naturally occur in a number of applications including mining natural-language text, customer transactions, error logs, or event sequences. LASH is the first parallel algorithm for mining frequent sequences with hierarchies; it is designed to scale to very large datasets. At its heart, LASH partitions the data using a novel, hierarchy-aware variant of item-based partitioning and subsequently mines each partition independently and in parallel using a customized mining algorithm called pivot sequence miner. LASH is amenable to a MapReduce implementation; we propose effective and efficient algorithms for both the construction and the actual mining of partitions. Our experimental study on large real-world datasets suggest good scalability and run-time efficiency.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {491–503},
numpages = {13},
keywords = {hierarchies, mapreduce, frequent sequence mining, data mining},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2751521,
author = {Cochez, Michael and Mou, Hao},
title = {Twister Tries: Approximate Hierarchical Agglomerative Clustering for Average Distance in Linear Time},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2751521},
doi = {10.1145/2723372.2751521},
abstract = {Many commonly used data-mining techniques utilized across research fields perform poorly when used for large data sets. Sequential agglomerative hierarchical non-overlapping clustering is one technique for which the algorithms' scaling properties prohibit clustering of a large amount of items. Besides the unfavorable time complexity of O(n2), these algorithms have a space complexity of O(n2), which can be reduced to O(n) if the time complexity is allowed to rise to O(n2 log2n). In this paper, we propose the use of locality-sensitive hashing combined with a novel data structure called twister tries to provide an approximate clustering for average linkage. Our approach requires only linear space. Furthermore, its time complexity is linear in the number of items to be clustered, making it feasible to apply it on a larger scale. We evaluate the approach both analytically and by applying it to several data sets.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {505–517},
numpages = {13},
keywords = {locality-sensitive hashing, hierarchical clustering, linear complexity, average linkage},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2737792,
author = {Gan, Junhao and Tao, Yufei},
title = {DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2737792},
doi = {10.1145/2723372.2737792},
abstract = {DBSCAN is a popular method for clustering multi-dimensional objects. Just as notable as the method's vast success is the research community's quest for its efficient computation. The original KDD'96 paper claimed an algorithm with O(n log n) running time, where n is the number of objects. Unfortunately, this is a mis-claim; and that algorithm actually requires O(n2) time. There has been a fix in 2D space, where a genuine O(n log n)-time algorithm has been found. Looking for a fix for dimensionality d ≥ 3 is currently an important open problem.In this paper, we prove that for d ≥ 3, the DBSCAN problem requires Ω(n4/3) time to solve, unless very significant breakthroughs---ones widely believed to be impossible---could be made in theoretical computer science. This (i) explains why the community's search for fixing the aforementioned mis-claim has been futile for d ≥ 3, and (ii) indicates (sadly) that all DBSCAN algorithms must be intolerably slow even on moderately large n in practice. Surprisingly, we show that the running time can be dramatically brought down to O(n) in expectation regardless of the dimensionality d, as soon as slight inaccuracy in the clustering results is permitted. We formalize our findings into the new notion of ρ-approximate DBSCAN, which we believe should replace DBSCAN on big data due to the latter's computational intractability.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {519–530},
numpages = {12},
keywords = {density-based clustering, dbscan, algorithm},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749457,
author = {Nazi, Azade and Das, Mahashweta and Das, Gautam},
title = {The TagAdvisor: Luring the Lurkers to Review Web Items},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749457},
doi = {10.1145/2723372.2749457},
abstract = {The increasing popularity and widespread use of online review sites over the past decade has motivated businesses of all types to possess an expansive arsenal of user feedback (preferably positive) in order to mark their reputation and presence in the Web. Though a significant proportion of purchasing decisions today are driven by average numeric scores (e.g., movie rating in IMDB), detailed reviews are critical for activities such as buying an expensive digital SLR camera, reserving a vacation package, etc. Since writing a detailed review for a product (or, a service) is usually time-consuming and may not offer any incentive, the number of useful reviews available in the Web is far from many. The corpus of reviews available at our disposal for making informed decisions also suffers from spam and misleading content, typographical and grammatical errors, etc. In this paper, we address the problem of how to engage the lurkers (i.e., people who read reviews but never take time and effort to write one) to participate and write online reviews by systematically simplifying the reviewing task. Given a user and an item that she wants to review, the task is to identify the top-$k$ meaningful phrases (i.e., tags) from the set of all tags (i.e., available user feedback for items) that, when advised, would help her review an item easily. We refer to it as the TagAdvisor problem, and formulate it as a general-constrained optimization goal. Our framework is centered around three measures - relevance (i.e., how well the result set of tags describes an item to a user), coverage (i.e., how well the result set of tags covers the different aspects of an item), and polarity (i.e., how well sentiment is attached to the result set of tags) in order to help a user review an item satisfactorily. By adopting different definitions of coverage, we identify two concrete problem instances that enable a wide range of real-world scenarios. We show that these problems are NP-hard and develop practical algorithms with theoretical bounds to solve them efficiently. We conduct detailed experiments on synthetic and real data crawled from the web to validate the utility of our problem and effectiveness of our solutions.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {531–543},
numpages = {13},
keywords = {relevance, polarity, coverage, personalized tag advisor},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723738,
author = {Peng, Liping and Diao, Yanlei},
title = {Supporting Data Uncertainty in Array Databases},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723738},
doi = {10.1145/2723372.2723738},
abstract = {Uncertain data management has become crucial to scientific applications. Recently, array databases have gained popularity for scientific data processing due to performance benefits. In this paper, we address uncertain data management in array databases, which may involve both value uncertainty within individual tuples and position uncertainty regarding where a tuple should belong in an array given uncertain dimension attributes. Our work defines the formal semantics of array operations under both value and position uncertainty. To address the new challenge raised by position uncertainty, we propose a suite of storage and evaluation strategies for array operations, with a focus on a new scheme that bounds the overhead of querying by strategically treating tuples with large variances via replication in storage. Results from real datasets show that for common workloads, our best-performing techniques outperform alternative methods based on state-of-the-art indexes by 1.7x to 4.3x for the Subarray operation and 1 to 2 orders of magnitude for Structure-Join, at only a small storage cost.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {545–560},
numpages = {16},
keywords = {store-multiple, uncertainty, array databases},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2750544,
author = {Razniewski, Simon and Korn, Flip and Nutt, Werner and Srivastava, Divesh},
title = {Identifying the Extent of Completeness of Query Answers over Partially Complete Databases},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2750544},
doi = {10.1145/2723372.2750544},
abstract = {In many applications including loosely coupled cloud databases, collaborative editing and network monitoring, data from multiple sources is regularly used for query answering. For reasons such as system failures, insufficient author knowledge or network issues, data may be temporarily unavailable or generally nonexistent. Hence, not all data needed for query answering may be available.In this paper, we propose a natural class of completeness patterns, expressed by selections on database tables, to specify complete parts of database tables. We then show how to adapt the operators of relational algebra so that they manipulate these completeness patterns to compute completeness patterns pertaining to query answers. Our proposed algebra is computationally sound and complete with respect to the information that the patterns provide. We show that stronger completeness patterns can be obtained by considering not only the schema but also the database instance and we extend the algebra to take into account this additional information. We develop novel techniques to efficiently implement the computation of completeness patterns on query answers and demonstrate their scalability on real data.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {561–576},
numpages = {16},
keywords = {data completeness, data quality},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723735,
author = {Peng, Peng and Wong, Raymong Chi-Wing},
title = {K-Hit Query: Top-k Query with Probabilistic Utility Function},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723735},
doi = {10.1145/2723372.2723735},
abstract = {Multi-criteria decision making problem has been well studied for many years. One popular query for multi-criteria decision making is top-k queries which require each user to specify an exact utility function. In many cases, the utility function of a user is probabilistic and finding the distribution on the utility functions has been widely explored in the machine learning areas, such as user's recommender systems, Bayesian learning models and user's preference elicitation, for improving user's experience. Motivated by this, we propose a new type of queries called k-hit queries, which has not been studied before. Given a set D of tuples in the database, the distribution θ on utility functions and a positive integer k, we would like to select a set of k tuples from D in order to maximize the probability that at least one of tuples in the selection set is the favorite of a user. All applications for top-k queries can naturally be used in k-hit queries. In this paper, we present various interesting properties of k-hit queries. Besides, based on these properties, we propose a novel algorithm called k-hit_Alg for k-hit queries. Finally, we conducted comprehensive experiments to show that the performance of our proposed method, k hit_Alg, is superior compared with other existing algorithms which were originally used to answer other existing queries.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {577–592},
numpages = {16},
keywords = {geometry, skyline query, top-k query, sampling, algorithm, preference query},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2737789,
author = {Li, Furong and Lee, Mong Li and Hsu, Wynne and Tan, Wang-Chiew},
title = {Linking Temporal Records for Profiling Entities},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2737789},
doi = {10.1145/2723372.2737789},
abstract = {To harness the rich amount of information available on the Web today, many organizations start to aggregate public (and private) data to derive new knowledge bases. A fundamental challenge in constructing an accurate integrated knowledge repository from different data sources is to understand how facts across different sources are related to one another over time. This challenge, referred to as the temporal record linkage problem, goes far beyond the traditional record linkage problem as it requires a fine-grained analysis of how two facts are temporally related if they both refer to the same entity.In this paper, we present a new solution for understanding how two facts may be temporally related and exploit the knowledge to profile how entities evolve over time. Our solution makes use of a novel transition model which captures sophisticated patterns of value transitions. Specifically, our transition model captures the probability that an entity may change to a particular attribute value after some time period. This transition model can be considered jointly with various source quality metrics to fine-tune how records should be temporally linked to entities. In particular, we showcase how the freshness of data sources can be built into a source-aware temporal matching algorithm that jointly considers the value transitions and the freshness of data sources to link temporal records to entities in the right time period. In this way, an increasingly complete and up-to-date entity profile can be derived as more and more temporal records are aggregated from different sources. Our suite of experimental results on real world datasets demonstrate that our proposed method is able to outperform the state-of-the-art techniques and build more complete profiles for entities by identifying their true matching temporal records at the right time period.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {593–605},
numpages = {13},
keywords = {temporal data, record linkage, information integration, entity profiling},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2742794,
author = {Huang, Yiqing and Zhu, Fangzhou and Yuan, Mingxuan and Deng, Ke and Li, Yanhua and Ni, Bing and Dai, Wenyuan and Yang, Qiang and Zeng, Jia},
title = {Telco Churn Prediction with Big Data},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2742794},
doi = {10.1145/2723372.2742794},
abstract = {We show that telco big data can make churn prediction much more easier from the $3$V's perspectives: Volume, Variety, Velocity. Experimental results confirm that the prediction performance has been significantly improved by using a large volume of training data, a large variety of features from both business support systems (BSS) and operations support systems (OSS), and a high velocity of processing new coming data. We have deployed this churn prediction system in one of the biggest mobile operators in China. From millions of active customers, this system can provide a list of prepaid customers who are most likely to churn in the next month, having $0.96$ precision for the top $50000$ predicted churners in the list. Automatic matching retention campaigns with the targeted potential churners significantly boost their recharge rates, leading to a big business value.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {607–618},
numpages = {12},
keywords = {telco churn prediction, customer retention, big data},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2742786,
author = {Erling, Orri and Averbuch, Alex and Larriba-Pey, Josep and Chafi, Hassan and Gubichev, Andrey and Prat, Arnau and Pham, Minh-Duc and Boncz, Peter},
title = {The LDBC Social Network Benchmark: Interactive Workload},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2742786},
doi = {10.1145/2723372.2742786},
abstract = {The Linked Data Benchmark Council (LDBC) is now two years underway and has gathered strong industrial participation for its mission to establish benchmarks, and benchmarking practices for evaluating graph data management systems. The LDBC introduced a new choke-point driven methodology for developing benchmark workloads, which combines user input with input from expert systems architects, which we outline. This paper describes the LDBC Social Network Benchmark (SNB), and presents database benchmarking innovation in terms of graph query functionality tested, correlated graph generation techniques, as well as a scalable benchmark driver on a workload with complex graph dependencies. SNB has three query workloads under development: Interactive, Business Intelligence, and Graph Algorithms. We describe the SNB Interactive Workload in detail and illustrate the workload with some early results, as well as the goals for the two other workloads.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {619–630},
numpages = {12},
keywords = {graph databases, benchmarking, rdf databases},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2742787,
author = {Nothaft, Frank Austin and Massie, Matt and Danford, Timothy and Zhang, Zhao and Laserson, Uri and Yeksigian, Carl and Kottalam, Jey and Ahuja, Arun and Hammerbacher, Jeff and Linderman, Michael and Franklin, Michael J. and Joseph, Anthony D. and Patterson, David A.},
title = {Rethinking Data-Intensive Science Using Scalable Analytics Systems},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2742787},
doi = {10.1145/2723372.2742787},
abstract = {"Next generation" data acquisition technologies are allowing scientists to collect exponentially more data at a lower cost. These trends are broadly impacting many scientific fields, including genomics, astronomy, and neuroscience. We can attack the problem caused by exponential data growth by applying horizontally scalable techniques from current analytics systems to accelerate scientific processing pipelines.In this paper, we describe ADAM, an example genomics pipeline that leverages the open-source Apache Spark and Parquet systems to achieve a 28x speedup over current genomics pipelines, while reducing cost by 63%. From building this system, we were able to distill a set of techniques for implementing scientific analyses efficiently using commodity "big data" systems. To demonstrate the generality of our architecture, we then implement a scalable astronomy image processing system which achieves a 2.8--8.9x improvement over the state-of-the-art MPI-based system.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {631–646},
numpages = {16},
keywords = {design},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2742792,
author = {Wang, Yue and Xu, Yingzhong and Liu, Yue and Chen, Jian and Hu, Songlin},
title = {QMapper for Smart Grid: Migrating SQL-Based Application to Hive},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2742792},
doi = {10.1145/2723372.2742792},
abstract = {Apache Hive has been widely used by Internet companies for big data analytics applications. It can provide the capability of compiling high-level languages into efficient MapReduce workflows, which frees users from complicated and time consuming programming. The popularity of Hive and its HiveQL-compatible systems like Impala and Shark attracts attentions from traditional enterprises as well. However, enterprise big data processing systems such as Smart Grid applications often have to migrate their RDBMS-based legacy applications to Hive rather than directly writing new logic in HiveQL. Considering their differences in syntax and cost model, manual translation from SQL in RDBMS to HiveQL is very difficult, error-prone, and often leads to poor performance.In this paper, we propose QMapper, a tool for automatically translating SQL into proper HiveQL. QMapper consists of a rule-based rewriter and a cost-based optimizer. The experiments based on the TPC-H benchmark demonstrate that, compared to manually rewritten Hive queries provided by Hive contributors, QMapper dramatically reduces the query latency on average. Our real world Smart Grid application also shows its efficiency.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {647–658},
numpages = {12},
keywords = {hive, system migration, sql on hadoop, join optimization},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2753770,
author = {Widom, Jennifer},
title = {Three Favorite Results},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2753770},
doi = {10.1145/2723372.2753770},
abstract = {Being honored as the ACM Athena Lecturer has inspired me to reflect upon the research I've conducted over my career to date. Conventional wisdom says good things come in threes, so I've picked three of my favorite results to cover during the talk. For each one I'll explain the context and motivation, the result itself, and why it ranks as one of my favorites. The three results span foundations, implementation, and user-interface, and they represent three of my favorite research areas: semistructured data, data streams, and uncertain data.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {659},
numpages = {1},
keywords = {semistructured data, uncertain data, data streams},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723373,
author = {Haas, Laura M.},
title = {The Power Behind the Throne: Information Integration in the Age of Data-Driven Discovery},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723373},
doi = {10.1145/2723372.2723373},
abstract = {Integrating data has always been a challenge. The information management community has made great progress in tackling this challenge, both on the theory and the practice. But in the last ten years, the world has changed dramatically. New platforms, devices and applications have made huge volumes of heterogeneous data available at speeds never contemplated before, while the quality of the available data has if anything degraded. Unstructured and semi-structured formats and no-sql data stores undercut the old reliable tools of schema, forcing applications to deal with data at the instance level. Deep expertise in the data and domain, in the tools and systems for integration and analysis, in mathematics, computer science, and business are needed to discover insights from data, but rarely are all of these skills found in a single individual or even team. Meanwhile, the availability of all these data has raised expectations for rapid breakthroughs in many sciences, for quick solutions to business problems, and for ever more sophisticated applications that combine and analyze information to solve our daily needs. These expectations raise the bar for integration technology, while opening the door for it to play a broader role. Integration has always been a key player in handling data variety, for example, but now more than ever must deal with scale (in the number of types as well as in the volume and speed of data). While data cleansing has been one step of an integration pipeline, this technology must be leveraged throughout data integration, so that the integration process is better able to deal with the uncertainty in data, offering means to eliminate or reduce it, or, to elucidate it by linking important contextual information, such as provenance and usage. The complexity of today's data-driven challenges in fact suggests that the integration process should be context-aware, so that data sets may be combined differently depending on the proposed usage.In the Accelerated Discovery Lab, we support data scientists working with a broad range of data as they try to find the insights to solve problems of business or societal importance. Clearly, integration is essential to insight. However, integration has to be across more than just datasets and schemas, and it has to be done more dynamically and flexibly than the standard tools allow. It is needed at multiple levels: (1) to build rich (but flexible) collections of diverse data, (2) to tightly bind individual data points into entities, allowing deeper explorations and (3) to bring together data and context to enable re-use by users with differing expertise. We think of the environment we are building as an integration hub for data, people and applications. It allows users to import, explore and create data and knowledge, inspired by the work of others, while it captures the patterns of decision-making and the provenance of decisions. I will describe the environment we are creating, the advances in the field that enable it, and the challenges that remain.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {661},
numpages = {1},
keywords = {information integration, data analytics, big data},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2751519,
author = {Loesing, Simon and Pilman, Markus and Etter, Thomas and Kossmann, Donald},
title = {On the Design and Scalability of Distributed Shared-Data Databases},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2751519},
doi = {10.1145/2723372.2751519},
abstract = {Database scale-out is commonly implemented by partitioning data across several database instances. This approach, however, has several restrictions. In particular, partitioned databases are inflexible in large-scale deployments and assume a partition-friendly workload in order to scale. In this paper, we analyze an alternative architecture design for distributed relational databases that overcomes the limitations of partitioned databases. The architecture is based on two fundamental principles: We decouple query processing and transaction management from data storage, and we share data across query processing nodes. The combination of these design choices provides scalability, elasticity, and operational flexibility without making any assumptions on the workload. As a drawback, sharing data among multiple database nodes causes synchronization overhead. To address this limitation, we introduce techniques for scalable transaction processing in shared-data environments. Specifically, we describe mechanisms for efficient data access, concurrency control, and data buffering. In combination with new hardware trends, the techniques enable performance characteristics that top state-of-the-art partitioned databases.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {663–676},
numpages = {14},
keywords = {shared-data, transaction processing, optimistic concurrency control, decoupled storage},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@dataset{10.1145/review-2723372.2751519_R52092,
author = {Brinkmann, Filip-Martin},
title = {Review ID:R52092 for DOI: 10.1145/2723372.2751519},
publisher = {Association for Computing Machinery},
url = {https://doi.org/10.1145/review-2723372.2751519_R52092}
}

@inproceedings{10.1145/2723372.2749436,
author = {Neumann, Thomas and M\"{u}hlbauer, Tobias and Kemper, Alfons},
title = {Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749436},
doi = {10.1145/2723372.2749436},
abstract = {Multi-Version Concurrency Control (MVCC) is a widely employed concurrency control mechanism, as it allows for execution modes where readers never block writers. However, most systems implement only snapshot isolation (SI) instead of full serializability. Adding serializability guarantees to existing SI implementations tends to be prohibitively expensive.We present a novel MVCC implementation for main-memory database systems that has very little overhead compared to serial execution with single-version concurrency control, even when maintaining serializability guarantees. Updating data in-place and storing versions as before-image deltas in undo buffers not only allows us to retain the high scan performance of single-version systems but also forms the basis of our cheap and fine-grained serializability validation mechanism. The novel idea is based on an adaptation of precision locking and verifies that the (extensional) writes of recently committed transactions do not intersect with the (intensional) read predicate space of a committing transaction. We experimentally show that our MVCC model allows very fast processing of transactions with point accesses as well as read-heavy transactions and that there is little need to prefer SI over full serializability any longer.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {677–689},
numpages = {13},
keywords = {mvcc, multi-version concurrency control, serializability},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2746480,
author = {Kimura, Hideaki},
title = {FOEDUS: OLTP Engine for a Thousand Cores and NVRAM},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2746480},
doi = {10.1145/2723372.2746480},
abstract = {Server hardware is about to drastically change. As typified by emerging hardware such as UC Berkeley's Firebox project and by Intel's Rack-Scale Architecture (RSA), next generation servers will have thousands of cores, large DRAM, and huge NVRAM. We analyze the characteristics of these machines and find that no existing database is appropriate. Hence, we are developing FOEDUS, an open-source, from-scratch database engine whose architecture is drastically different from traditional databases. It extends in-memory database technologies to further scale up and also allows transactions to efficiently manipulate data pages in both DRAM and NVRAM. We evaluate the performance of FOEDUS in a large NUMA machine (16 sockets and 240 physical cores) and find that FOEDUS achieves multiple orders of magnitude higher TPC-C throughput compared to H-Store with anti-caching.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {691–706},
numpages = {16},
keywords = {nvram, many-cores},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749441,
author = {Arulraj, Joy and Pavlo, Andrew and Dulloor, Subramanya R.},
title = {Let's Talk About Storage & Recovery Methods for Non-Volatile Memory Database Systems},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749441},
doi = {10.1145/2723372.2749441},
abstract = {The advent of non-volatile memory (NVM) will fundamentally change the dichotomy between memory and durable storage in database management systems (DBMSs). These new NVM devices are almost as fast as DRAM, but all writes to it are potentially persistent even after power loss. Existing DBMSs are unable to take full advantage of this technology because their internal architectures are predicated on the assumption that memory is volatile. With NVM, many of the components of legacy DBMSs are unnecessary and will degrade the performance of data intensive applications.To better understand these issues, we implemented three engines in a modular DBMS testbed that are based on different storage management architectures: (1) in-place updates, (2) copy-on-write updates, and (3) log-structured updates. We then present NVM-aware variants of these architectures that leverage the persistence and byte-addressability properties of NVM in their storage and recovery methods. Our experimental evaluation on an NVM hardware emulator shows that these engines achieve up to 5.5X higher throughput than their traditional counterparts while reducing the amount of wear due to write operations by up to 2X. We also demonstrate that our NVM-aware recovery protocols allow these engines to recover almost instantaneously after the DBMS restarts.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {707–722},
numpages = {16},
keywords = {oltp, non-volatile memory, storage engines, recovery},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2737785,
author = {Zhang, Jun and Cormode, Graham and Procopiuc, Cecilia M. and Srivastava, Divesh and Xiao, Xiaokui},
title = {Private Release of Graph Statistics Using Ladder Functions},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2737785},
doi = {10.1145/2723372.2737785},
abstract = {Protecting the privacy of individuals in graph structured data while making accurate versions of the data available is one of the most challenging problems in data privacy. Most efforts to date to perform this data release end up mired in complexity, overwhelm the signal with noise, and are not effective for use in practice. In this paper, we introduce a new method which guarantees differential privacy. It specifies a probability distribution over possible outputs that is carefully defined to maximize the utility for the given input, while still providing the required privacy level. The distribution is designed to form a 'ladder', so that each output achieves the highest 'rung' (maximum probability) compared to less preferable outputs. We show how our ladder framework can be applied to problems of counting the number of occurrences of subgraphs, a vital objective in graph analysis, and give algorithms whose cost is comparable to that of computing the count exactly. Our experimental study confirms that our method outperforms existing methods for counting triangles and stars in terms of accuracy, and provides solutions for some problems for which no effective method was previously known. The results of our algorithms can be used to estimate the parameters of suitable graph models, allowing synthetic graphs to be sampled.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {731–745},
numpages = {15},
keywords = {differential privacy, local sensitivity, subgraph counting},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2747643,
author = {Yang, Bin and Sato, Issei and Nakagawa, Hiroshi},
title = {Bayesian Differential Privacy on Correlated Data},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2747643},
doi = {10.1145/2723372.2747643},
abstract = {Differential privacy provides a rigorous standard for evaluating the privacy of perturbation algorithms. It has widely been regarded that differential privacy is a universal definition that deals with both independent and correlated data and a differentially private algorithm can protect privacy against arbitrary adversaries. However, recent research indicates that differential privacy may not guarantee privacy against arbitrary adversaries if the data are correlated.In this paper, we focus on the private perturbation algorithms on correlated data. We investigate the following three problems: (1) the influence of data correlations on privacy; (2) the influence of adversary prior knowledge on privacy; and (3) a general perturbation algorithm that is private for prior knowledge of any subset of tuples in the data when the data are correlated. We propose a Pufferfish definition of privacy, called Bayesian differential privacy, by which the privacy level of a probabilistic perturbation algorithm can be evaluated even when the data are correlated and when the prior knowledge is incomplete. We present a Gaussian correlation model to accurately describe the structure of data correlations and analyze the Bayesian differential privacy of the perturbation algorithm on the basis of this model. Our results show that privacy is poorest for an adversary who has the least prior knowledge. We further extend this model to a more general one that considers uncertain prior knowledge.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {747–762},
numpages = {16},
keywords = {optimization, differential privacy, gaussian markov random field, private data analysis, output perturbation},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749455,
author = {Mavroforakis, Charalampos and Chenette, Nathan and O'Neill, Adam and Kollios, George and Canetti, Ran},
title = {Modular Order-Preserving Encryption, Revisited},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749455},
doi = {10.1145/2723372.2749455},
abstract = {Order-preserving encryption (OPE) schemes, whose ciphertexts preserve the natural ordering of the plaintexts, allow efficient range query processing over outsourced encrypted databases without giving the server access to the decryption key. Such schemes have recently received increased interest in both the database and the cryptographic communities. In particular, modular order-preserving encryption (MOPE), due to Boldyreva et al., is a promising extension that increases the security of the basic OPE by introducing a secret modular offset to each data value prior to encrypting it. However, executing range queries via MOPE in a naive way allows the adversary to learn this offset, negating any potential security gains of this approach.In this paper, we systematically address this vulnerability and show that MOPE can be used to build a practical system for executing range queries on encrypted data while providing a significant security improvement over the basic OPE. We introduce two new query execution algorithms for MOPE: our first algorithm is efficient if the user's query distribution is well-spread, while the second scheme is efficient even for skewed query distributions. Interestingly, our second algorithm achieves this efficiency by leaking the least-important bits of the data, whereas OPE is known to leak the most-important bits of the data. We also show that our algorithms can be extended to the case where the query distribution is adaptively learned online. We present new, appropriate security models for MOPE and use them to rigorously analyze the security of our proposed schemes. Finally, we design a system prototype that integrates our schemes on top of an existing database system and apply query optimization methods to execute SQL queries with range predicates efficiently. We provide a performance evaluation of our prototype under a number of different database and query distributions, using both synthetic and real datasets},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {763–777},
numpages = {15},
keywords = {database encryption, range queries, order preserving encryption, database security model},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749453,
author = {Allard, Tristan and H\'{e}brail, Georges and Masseglia, Florent and Pacitti, Esther},
title = {Chiaroscuro: Transparency and Privacy for Massive Personal Time-Series Clustering},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749453},
doi = {10.1145/2723372.2749453},
abstract = {The advent of on-body/at-home sensors connected to personal devices leads to the generation of fine grain highly sensitive personal data at an unprecendent rate. However, despite the promises of large scale analytics there are obvious privacy concerns that prevent individuals to share their personnal data. In this paper, we propose Chiaroscuro, a complete solution for clustering personal data with strong privacy guarantees. The execution sequence produced by Chiaroscuro is massively distributed on personal devices, coping with arbitrary connections and disconnections. Chiaroscuro builds on our novel data structure, called Diptych, which allows the participating devices to collaborate privately by combining encryption with differential privacy. Our solution yields a high clustering quality while minimizing the impact of the differentially private perturbation. Chiaroscuro is both correct and secure. Finally, we provide an experimental validation of our approach on both real and synthetic sets of time-series.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {779–794},
numpages = {16},
keywords = {sensors, gossip, secure multi-party computation, time-series, differential privacy, k-means, clustering},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749443,
author = {Wei, Zhewei and Luo, Ge and Yi, Ke and Du, Xiaoyong and Wen, Ji-Rong},
title = {Persistent Data Sketching},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749443},
doi = {10.1145/2723372.2749443},
abstract = {A persistent data structure, also known as a multiversion data structure in the database literature, is a data structure that preserves all its previous versions as it is updated over time. Every update (inserting, deleting, or changing a data record) to the data structure creates a new version, while all the versions are kept in the data structure so that any previous version can still be queried.Persistent data structures aim at recording all versions accurately, which results in a space requirement that is at least linear to the number of updates. In many of today's big data applications, in particular for high-speed streaming data, the volume and velocity of the data are so high that we cannot afford to store everything. Therefore, streaming algorithms have received a lot of attention in the research community, which use only sublinear space by sacrificing slightly on accuracy.All streaming algorithms work by maintaining a small data structure in memory, which is usually called a em sketch, summary, or synopsis. The sketch is updated upon the arrival of every element in the stream, thus is ephemeral, meaning that it can only answer queries about the current status of the stream. In this paper, we aim at designing persistent sketches, thereby giving streaming algorithms the ability to answer queries about the stream at any prior time.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {795–810},
numpages = {16},
keywords = {sketch, approximation, persistence},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2746485,
author = {Lin, Qian and Ooi, Beng Chin and Wang, Zhengkui and Yu, Cui},
title = {Scalable Distributed Stream Join Processing},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2746485},
doi = {10.1145/2723372.2746485},
abstract = {Efficient and scalable stream joins play an important role in performing real-time analytics for many cloud applications. However, like in conventional database processing, online theta-joins over data streams are computationally expensive and moreover, being memory-based processing, they impose high memory requirement on the system. In this paper, we propose a novel stream join model, called join-biclique, which organizes a large cluster as a complete bipartite graph. Join-biclique has several strengths over state-of-the-art techniques, including memory-efficiency, elasticity and scalability. These features are essential for building efficient and scalable streaming systems. Based on join-biclique, we develop a scalable distributed stream join system, BiStream, over a large-scale commodity cluster. Specifically, BiStream is designed to support efficient full-history joins, window-based joins and online data aggregation. BiStream also supports adaptive resource management to dynamically scale out and down the system according to its application workloads. We provide both theoretical cost analysis and extensive experimental evaluations to evaluate the efficiency, elasticity and scalability of BiStream.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {811–825},
numpages = {15},
keywords = {distributed system, data streams, stream join},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723730,
author = {Song, Shaoxu and Zhang, Aoqian and Wang, Jianmin and Yu, Philip S.},
title = {SCREEN: Stream Data Cleaning under Speed Constraints},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723730},
doi = {10.1145/2723372.2723730},
abstract = {Stream data are often dirty, for example, owing to unreliable sensor reading, or erroneous extraction of stock prices. Most stream data cleaning approaches employ a smoothing filter, which may seriously alter the data without preserving the original information. We argue that the cleaning should avoid changing those originally correct/clean data, a.k.a. the minimum change principle in data cleaning. To capture the knowledge about what is clean, we consider the (widely existing) constraints on the speed of data changes, such as fuel consumption per hour, or daily limit of stock prices. Guided by these semantic constraints, in this paper, we propose SCREEN, the first constraint-based approach for cleaning stream data. It is notable that existing data repair techniques clean (a sequence of) data as a whole and fail to support stream computation. To this end, we have to relax the global optimum over the entire sequence to the local optimum in a window. Rather than the commonly observed NP-hardness of general data repairing problems, our major contributions include: (1) polynomial time algorithm for global optimum, (2) linear time algorithm towards local optimum under an efficient Median Principle,(3) support on out-of-order arrivals of data points, and(4) adaptive window size for balancing repair accuracy and efficiency. Experiments on real datasets demonstrate that SCREEN can show significantly higher repair accuracy than the existing approaches such as smoothing.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {827–841},
numpages = {15},
keywords = {speed constraints, data repairing},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2746481,
author = {Guo, Long and Zhang, Dongxiang and Li, Guoliang and Tan, Kian-Lee and Bao, Zhifeng},
title = {Location-Aware Pub/Sub System: When Continuous Moving Queries Meet Dynamic Event Streams},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2746481},
doi = {10.1145/2723372.2746481},
abstract = {In this paper, we propose a new location-aware pub/sub system, Elaps, that continuously monitors moving users subscribing to dynamic event streams from social media and E-commerce applications. Users are notified instantly when there is a matching event nearby. To the best of our knowledge, Elaps is the first to take into account continuous moving queries against dynamic event streams. Like existing works on continuous moving query processing,Elaps employs the concept of safe region to reduce communication overhead. However, unlike existing works which assume data from publishers are static, updates to safe regions may be triggered by newly arrived events. In Elaps, we develop a concept called textit{impact region} that allows us to identify whether a safe region is affected by newly arrived events. Moreover, we propose a novel cost model to optimize the safe region size to keep the communication overhead low. Based on the cost model, we design two incremental methods, iGM and idGM, for safe region construction. In addition, Elaps uses boolean expression, which is more expressive than keywords, to model user intent and we propose a novel index, BEQ-Tree, to handle spatial boolean expression matching. In our experiments, we use geo-tweets from Twitter and venues from Foursquare to simulate publishers and boolean expressions generated from AOL search log to represent users intentions. We test user movement in both synthetic trajectories and real taxi trajectories. The results show that Elaps can significantly reduce the communication overhead and disseminate events to users in real-time.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {843–857},
numpages = {15},
keywords = {continuous moving queries, dynamic event streams, pub/sub},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735357,
author = {Katsipoulakis, Nick R. and Thoma, Cory and Gratta, Eric A. and Labrinidis, Alexandros and Lee, Adam J. and Chrysanthis, Panos K.},
title = {CE-Storm: Confidential Elastic Processing of Data Streams},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735357},
doi = {10.1145/2723372.2735357},
abstract = {Data Stream Management Systems (DSMS) are crucial for modern high-volume/high-velocity data-driven applications, necessitating a distributed approach to processing them. In addition, data providers often require certain levels of confidentiality for their data, especially in cases of user-generated data, such as those coming out of physical activity/health tracking devices (i.e., our motivating application). This demonstration will showcase Synefo, an infrastructure that enables elastic scaling of DSMS operators, and CryptStream, a framework that provides confidentiality and access controls for data streams while allowing computation on untrusted servers, fused as CE-Storm. We will demonstrate both systems working in tandem and also visualize their behavior over time under different scenarios.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {859–864},
numpages = {6},
keywords = {continuous queries, confidentiality, distributed data stream management system, elasticity},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735358,
author = {Dietrich, Benjamin and Grust, Torsten},
title = {A SQL Debugger Built from Spare Parts: Turning a SQL: 1999 Database System into Its Own Debugger},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735358},
doi = {10.1145/2723372.2735358},
abstract = {We demonstrate a new incarnation of Habitat, an observational debugger for SQL. In observational debugging, users highlight parts of a presumably faulty query to observe the evaluation of SQL subexpressions and learn about the query's actual runtime behavior. The present version of Habitat has been redesigned from scratch and employs a query instrumentation technique that exclusively relies on the SQL facilities of the underlying RDBMS. We particularly shed light on new features like (1) the debugging of recursive SQL queries and (2) the observation of row groups (before and after aggregation). Habitat can turn any reasonably modern SQL:1999 RDBMS into its own language-level SQL debugger.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {865–870},
numpages = {6},
keywords = {sql, debuggers, observational debugging},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735361,
author = {Bao, Zhifeng and Zeng, Yong and Jagadish, H.V. and Ling, Tok Wang},
title = {Exploratory Keyword Search with Interactive Input},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735361},
doi = {10.1145/2723372.2735361},
abstract = {Due to the intrinsic ambiguity of keyword queries, users usually need to reformulate their queries multiple times to get the desired information. Even worse, users either have no way to precisely specify their search intention, or have limited domain knowledge on the data to precisely express their search intention. Moreover, they may just have a general interest to explore the data by keyword query. Therefore, our goal is to design an exploratory search paradigm that is able to bring humans more actively into the search process, in order to meet various user information needs, ranging from simple lookup to learning and understanding of the data.Besides, keyword queries against data with structure, such as XML, can run into multiple difficulties: how to identify the search target; more types of ambiguity arise as a keyword can be part of the structure as well as content of data, etc. Effectively addressing these requires solutions to multiple challenges. While some have been addressed to some extent individually, there is no previous effort to develop a comprehensive system to meet these important user needs and meet all of these challenges.Therefore, we propose a framework called ClearMap that natively supports visualized exploratory search paradigm on XML data. In particular, we offer an interactive and visualized mechanism to present the outcome of the query, enable user to explore and manipulate the underlying data to

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr