text:
either quickly find desired information or learn the relationship among data items, as well as provide interactive suggestions when their expected results do not exist in the data. A preliminary version of ClearMap and its source code are available for try at http://xmlclearmap.comp.nus.edu.sg.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {871–876},
numpages = {6},
keywords = {usability, interaction, keyword search},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735364,
author = {Scheibli, Daniel and Dinse, Christian and Boehm, Alexander},
title = {QE3D: Interactive Visualization and Exploration of Complex, Distributed Query Plans},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735364},
doi = {10.1145/2723372.2735364},
abstract = {QE3D is a novel query plan visualization tool that aims at providing an intuitive and holistic view of distributed query plans executed by the SAP HANA database management system. In this demonstration, we show how its interactive, three-dimensional plan representation helps to understand and quickly identify hotspots in complex, real-world scenarios.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {877–881},
numpages = {5},
keywords = {sql query analysis, sql, parallel database, visualization},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735366,
author = {Morcos, John and Abedjan, Ziawasch and Ilyas, Ihab Francis and Ouzzani, Mourad and Papotti, Paolo and Stonebraker, Michael},
title = {DataXFormer: An Interactive Data Transformation Tool},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735366},
doi = {10.1145/2723372.2735366},
abstract = {While syntactic transformations require the application of a formula on the input values, such as unit conversion or date format conversions, semantic transformations, such as "zip code to city", require a look-up in some reference data. We recently presented DataXFormer, a system that leverages Web tables, Web forms, and expert sourcing to cover a wide range of transformations. In this demonstration, we present the user-interaction with DataXFormer and show scenarios on how it can be used to transform data and explore the effectiveness and efficiency of several approaches for transformation discovery, leveraging about 112 million tables and online sources.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {883–888},
numpages = {6},
keywords = {wrapper, web tables, data transformation, web forms, data integration, data enrichment, deep web},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735371,
author = {Ji, Yuanzhen and Zhou, Hongjin and Jerzak, Zbigniew and Nica, Anisoara and Hackenbroich, Gregor and Fetzer, Christof},
title = {Quality-Driven Continuous Query Execution over Out-of-Order Data Streams},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735371},
doi = {10.1145/2723372.2735371},
abstract = {Executing continuous queries over out-of-order data streams, where tuples are not ordered according to timestamps, is challenging; because high result accuracy and low result latency are two conflicting performance metrics. Although many applications allow trading exact query results for lower latency, they still expect the produced results to meet a certain quality requirement. However, none of existing disorder handling approaches have considered minimizing the result latency while meeting user-specified requirements on the quality of query results.In this demonstration, we showcase AQ-K-slack, an adaptive, buffer-based disorder handling approach, which supports executing sliding window aggregate queries over out-of-order data streams in a quality-driven manner. By adapting techniques from the field of sampling-based approximate query processing and control theory, AQ-K-slack dynamically adjusts the input buffer size at query runtime to minimize the result latency, while respecting a user-specified threshold on relative errors in produced query results.We demonstrate a prototype stream processing system, which extends SAP Event Stream Processor with the implementation of AQ-K-slack. Through an interactive interface, the audience will learn the effect of different factors, such as the aggregate function, the window specification, the result error threshold, and stream properties, on the latency and the accuracy of query results. Moreover, they can experience the effectiveness of AQ-K-slack in obtaining user-desired latency vs. result accuracy trade-offs, compared to naive disorder handling approaches that make extreme trade-offs. For instance, by scarifying 1% result accuracy, our system can reduce the result latency by 80% when compared to the state of the art.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {889–894},
numpages = {6},
keywords = {continuous queries, disorder handling, out-of-order data streams, data stream processing},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735375,
author = {Mytilinis, Ioannis and Giannakopoulos, Ioannis and Konstantinou, Ioannis and Doka, Katerina and Tsitsigkos, Dimitrios and Terrovitis, Manolis and Giampouras, Lampros and Koziris, Nectarios},
title = {MoDisSENSE: A Distributed Spatio-Temporal and Textual Processing Platform for Social Networking Services},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735375},
doi = {10.1145/2723372.2735375},
abstract = {The amount of social networking data that is being produced and consumed daily is huge and it is constantly increasing. A user's digital footprint coming from social networks or mobile devices, such as comments and check-ins contains valuable information about his preferences. The collection and analysis of such footprints using also information about the users' friends and their footprints offers many opportunities in areas such as personalized search, recommendations, etc. When the size of the collected data or the complexity of the applied methods increases, traditional storage and processing systems are not enough and distributed approaches are employed. In this work, we present MoDisSENSE, an open-source distributed platform that provides personalized search for points of interest and trending events based on the user's social graph by combining spatio-textual user generated data. The system is designed with scalability in mind, it is built using a combination of latest state-of-the art big data frameworks and its functionality is offered through easy to use mobile and web clients which support the most popular social networks. We give an overview of its architectural components and technologies and we evaluate its performance and scalability using different query types over various cluster sizes. Using the web or mobile clients, users are allowed to register themselves with their own social network credentials, perform socially enhanced queries for POIs, browse the results and explore the automatic blog creation functionality that is extracted by analyzing already collected GPS traces.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {895–900},
numpages = {6},
keywords = {recommendation systems, social mobile applications, spatio-textual data processing},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735379,
author = {Hu, Qiang and Liu, Qi and Wang, Xiaoli and Tung, Anthony K.H. and Goyal, Shubham and Yang, Jisong},
title = {DocRicher: An Automatic Annotation System for Text Documents Using Social Media},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735379},
doi = {10.1145/2723372.2735379},
abstract = {We demonstrate a system, DocRicher, to enrich a text document with social media, that implicitly reference certain passages of it. The aim is to provide an automatic annotation interface to satisfy users' information need, without cumbersome queries to traditional search engines. The system consists of four components: text analysis, query construction, data assignment, and user feedback. Through text analysis, the system decomposes a text document into appropriate topical passages, of which each is represented using detected key phrases. By submitting combinations of these phrases as queries to social media systems, the relevant results are used to suggest new annotations, that are linked to the corresponding passages. We have built a user-friendly visualization tool for users to browse automatically recommended annotations on their reading documents. Users are either allowed to rate a recommended annotation by accepting it or not; or add a new annotation by manually highlighting texts and adding personal comments. Both these annotations are regarded as the ground truth to derive new queries for retrieving more relevant contents. We also apply data fusion to merge the query results from various contexts and retain most relevant ones.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {901–906},
numpages = {6},
keywords = {ranking, document enrichment, social media},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735380,
author = {Yuan, Li-Yan and Wu, Lengdong and You, Jia-Huai and Chi, Yan},
title = {A Demonstration of Rubato DB: A Highly Scalable NewSQL Database System for OLTP and Big Data Applications},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735380},
doi = {10.1145/2723372.2735380},
abstract = {We propose to demonstrate Rubato DB, a highly scalable NewSQL system, supporting various consistency levels from ACID to BASE for OLTP and big data applications. Rubato DB employs the staged grid architecture with a novel formula based protocol for distributed concurrency control. Our demonstration will present Rubato DB as one NewSQL database management system running on a collection of commodity servers against two of benchmark sets.The demo attendees can modify the configuration of system size, fine-tune the query workload, and visualize the performance on the fly by the graphical user interface. Attendees can experiment with various system scales, and thus grasp the potential scalability of Rubato DB, whose performance, with the increase of the number of servers used, can achieve a linear growth for both OLTP application with the strong consistency properties and key-value storage applications with the weak consistency properties.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {907–912},
numpages = {6},
keywords = {scalability, architecture, concurrency control, base, acid},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735381,
author = {Zeng, Kai and Agarwal, Sameer and Dave, Ankur and Armbrust, Michael and Stoica, Ion},
title = {G-OLA: Generalized On-Line Aggregation for Interactive Analysis on Big Data},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735381},
doi = {10.1145/2723372.2735381},
abstract = {Nearly 15 years ago, Hellerstein, Haas and Wang proposed online aggregation (OLA), a technique that allows users to (1) observe the progress of a query by showing iteratively refined approximate answers, and (2) stop the query execution once its result achieves the desired accuracy. In this demonstration, we present G-OLA, a novel mini-batch execution model that generalizes OLA to support general OLAP queries with arbitrarily nested aggregates using efficient delta maintenance techniques. We have implemented G-OLA in FluoDB, a parallel online query execution framework that is built on top of the Spark cluster computing framework that can scale to massive data sets. We will demonstrate FluoDB on a cluster of 100 machines processing roughly 10TB of real-world session logs from a video-sharing website. Using an ad optimization and an A/B testing based scenario, we will enable users to perform real-time data analysis via web-based query consoles and dashboards.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {913–918},
numpages = {6},
keywords = {online aggregation},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2731081,
author = {Sakurai, Yasushi and Matsubara, Yasuko and Faloutsos, Christos},
title = {Mining and Forecasting of Big Time-Series Data},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2731081},
doi = {10.1145/2723372.2731081},
abstract = {Given a large collection of time series, such as web-click logs, electric medical records and motion capture sensors, how can we efficiently and effectively find typical patterns? How can we statistically summarize all the sequences, and achieve a meaningful segmentation? What are the major tools for forecasting and outlier detection? Time-series data analysis is becoming of increasingly high importance, thanks to the decreasing cost of hardware and the increasing on-line processing capability.The objective of this tutorial is to provide a concise and intuitive overview of the most important tools that can help us find patterns in large-scale time-series sequences. We review the state of the art in four related fields: (1) similarity search and pattern discovery, (2) linear modeling and summarization, (3) non-linear modeling and forecasting, and (4) the extension of time-series mining and tensor analysis. The emphasis of the tutorial is to provide the intuition behind these powerful tools, which is usually lost in the technical literature, as well as to introduce case studies that illustrate their practical use.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {919–922},
numpages = {4},
keywords = {time-series, pattern discovery, tensors, forecasting},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749442,
author = {Wang, Xiaoyang and Zhang, Ying and Zhang, Wenjie and Lin, Xuemin and Cheema, Muhammad Aamir},
title = {Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749442},
doi = {10.1145/2723372.2749442},
abstract = {In many domains such as computational geometry and database management, an object may be described by multiple instances (points). Then the distance (or similarity) between two objects is captured by the pair-wise distances among their instances. In the past, numerous nearest neighbor (NN) functions have been proposed to define the distance between objects with multiple instances and to identify the NN object. Nevertheless, considering that a user may not have a specific NN function in mind, it is desirable to provide her with a set of NN candidates. Ideally, the set of NN candidates must include every object that is NN for at least one of the NN functions and must exclude every non-promising object. However, no one has studied the problem of NN candidates computation from this perspective. Although some of the existing works aim at returning a set of candidate objects, they do not focus on the NN functions while computing the candidate objects. As a result, they either fail to include an NN object w.r.t. some NN functions or include a large number of unnecessary objects that have no potential to be the NN regardless of the NN functions.Motivated by this, we classify the existing NN functions for objects with multiple instances into three families by characterizing their key features. Then, we advocate three spatial dominance operators to compute NN candidates where each operator is optimal w.r.t. different coverage of NN functions. Efficient algorithms are proposed for the dominance check and corresponding NN candidates computation. Extensive empirical study on real and synthetic datasets shows that our proposed operators can significantly reduce the number of NN candidates. The comprehensive performance evaluation demonstrates the efficiency of our computation techniques.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {923–938},
numpages = {16},
keywords = {spatial dominance, nn candidates, nn functions},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749434,
author = {Tauheed, Farhan and Heinis, Thomas and Ailamaki, Anastasia},
title = {THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749434},
doi = {10.1145/2723372.2749434},
abstract = {Simulations have become ubiquitous in many domains of science. Today scientists study natural phenomena by first building massive three-dimensional spatial models and then by simulating the models at discrete intervals of time to mimic the behavior of natural phenomena. One frequently occurring challenge during simulations is the repeated computation of spatial self-joins of the model at each simulation time step. The join is performed to access a group of neighboring spatial objects (groups of particles, molecules or cosmological objects) so that scientists can calculate the cumulative effect (like gravitational force) on an object. Computing a self-join even in memory, soon becomes a performance bottleneck in simulation applications. The problem becomes even worse as scientists continue to improve the precision of simulations by increasing the number as well as the size (3D extent) of the objects. This leads to an exponential increase in join selectivity that challenges the performance and scalability of state-of-the-art approaches.We propose THERMAL-JOIN, a novel spatial self-join algorithm for dynamic memory-resident workloads. The algorithm groups objects in spatial proximity together into hot spots. Hot spots minimize the cost of computing join as objects assigned to a hot spot are guaranteed to overlap with each other. Using a nested spatial grid, THERMAL-JOIN partitions and indexes the dataset to locate hot spots. With experiments we show that our approach provides a speedup between 8 to 12x compared to the state of the art and also scales as scientists improve the precision of their simulations.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {939–950},
numpages = {12},
keywords = {scientific data management, dynamic workload, spatial self-join, high selectivity join},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723728,
author = {Chen, Lu and Gao, Yunjun and Li, Xinhan and Jensen, Christian S. and Chen, Gang and Zheng, Baihua},
title = {Indexing Metric Uncertain Data for Range Queries},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723728},
doi = {10.1145/2723372.2723728},
abstract = {Range queries in metric spaces have applications in many areas such as multimedia retrieval, computational biology, and location-based services, where metric uncertain data exists in different forms, resulting from equipment limitations, high-throughput sequencing technologies, privacy preservation, or others. In this paper, we represent metric uncertain data by using an object-level model and a bi-level model, respectively. Two novel indexes, the uncertain pivot B+-tree (UPB-tree) and the uncertain pivot B+-forest (UPB-forest), are proposed accordingly in order to support probabilistic range queries w.r.t. a wide range of uncertain data types and similarity metrics. Both index structures use a small set of effective pivots chosen based on a newly defined criterion, and employ the B+-tree(s) as the underlying index. By design, they are easy to be integrated into any existing DBMS. In addition, we present efficient metric probabilistic range query algorithms, which utilize the validation and pruning techniques based on our derived probability lower and upper bounds. Extensive experiments with both real and synthetic data sets demonstrate that, compared against existing state-of-the-art indexes for metric uncertain data, the UPB-tree and UPB-forest incur much lower construction costs, consume smaller storage spaces, and can support more efficient metric probabilistic range queries.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {951–965},
numpages = {15},
keywords = {uncertain data, metric space, range query, index structure},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749456,
author = {Wang, Sibo and Lin, Wenqing and Yang, Yi and Xiao, Xiaokui and Zhou, Shuigeng},
title = {Efficient Route Planning on Public Transportation Networks: A Labelling Approach},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749456},
doi = {10.1145/2723372.2749456},
abstract = {A public transportation network can often be modeled as a timetable graph where (i) each node represents a station; and (ii) each directed edge (u,v) is associated with a timetable that records the departure (resp. arrival) time of each vehicle at station u (resp. v). Several techniques have been proposed for various types of route planning on timetable graphs, e.g., retrieving the route from a node to another with the shortest travel time. These techniques, however, either provide insufficient query efficiency or incur significant space overheads.This paper presents Timetable Labelling (TTL), an efficient indexing technique for route planning on timetable graphs. The basic idea of TTL is to associate each node $u$ with a set of labels, each of which records the shortest travel time from u to some other node v given a certain departure time from u; such labels would then be used during query processing to improve efficiency. In addition, we propose query algorithms that enable TTL to support three popular types of route planning queries, and investigate how we reduce the space consumption of TTL with advanced preprocessing and label compression methods. By conducting an extensive set of experiments on real world datasets, we demonstrate that TTL significantly outperforms the states of the art in terms of query efficiency, while incurring moderate preprocessing and space overheads.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {967–982},
numpages = {16},
keywords = {algorithm, path queries, transportation network},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723722,
author = {Anagnostopoulos, Aris and Becchetti, Luca and Fazzone, Adriano and Mele, Ida and Riondato, Matteo},
title = {The Importance of Being Expert: Efficient Max-Finding in Crowdsourcing},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723722},
doi = {10.1145/2723372.2723722},
abstract = {Crowdsourcing is a computational paradigm whose distinctive feature is the involvement of human workers in key steps of the computation. It is used successfully to address problems that would be hard or impossible to solve for machines. As we highlight in this work, the exclusive use of nonexpert individuals may prove ineffective in some cases, especially when the task at hand or the need for accurate solutions demand some degree of specialization to avoid excessive uncertainty and inconsistency in the answers. We address this limitation by proposing an approach that combines the wisdom of the crowd with the educated opinion of experts. We present a computational model for crowdsourcing that envisions two classes of workers with different expertise levels. One of its distinctive features is the adoption of the threshold error model, whose roots are in psychometrics and which we extend from previous theoretical work. Our computational model allows to evaluate the performance of crowdsourcing algorithms with respect to accuracy and cost. We use our model to develop and analyze an algorithm for approximating the best, in a broad sense, of a set of elements. The algorithm uses na\"{\i}ve and expert workers to find an element that is a constant-factor approximation to the best. We prove upper and lower bounds on the number of comparisons needed to solve this problem, showing that our algorithm uses expert and na\"{\i}ve workers optimally up to a constant factor. Finally, we evaluate our algorithm on real and synthetic datasets using the CrowdFlower crowdsourcing platform, showing that our approach is also effective in practice.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {983–998},
numpages = {16},
keywords = {max algorithm, worker models, crowdsourcing, human computation},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723731,
author = {Hung, Nguyen Quoc Viet and Thang, Duong Chi and Weidlich, Matthias and Aberer, Karl},
title = {Minimizing Efforts in Validating Crowd Answers},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723731},
doi = {10.1145/2723372.2723731},
abstract = {In recent years, crowdsourcing has become essential in a wide range of Web applications. One of the biggest challenges of crowdsourcing is the quality of crowd answers as workers have wide-ranging levels of expertise and the worker community may contain faulty workers. Although various techniques for quality control have been proposed, a post-processing phase in which crowd answers are validated is still required. Validation is typically conducted by experts, whose availability is limited and who incur high costs. Therefore, we develop a probabilistic model that helps to identify the most beneficial validation questions in terms of both, improvement of result correctness and detection of faulty workers. Our approach allows us to guide the expert's work by collecting input on the most problematic cases, thereby achieving a set of high quality answers even if the expert does not validate the complete answer set. Our comprehensive evaluation using both real-world and synthetic datasets demonstrates that our techniques save up to 50% of expert efforts compared to baseline methods when striving for perfect result correctness. In absolute terms, for most cases, we achieve close to perfect correctness after expert input has been sought for only 20% of the questions.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {999–1014},
numpages = {16},
keywords = {guiding user feedback, crowdsourcing, expectation maximization, validation},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2750550,
author = {Fan, Ju and Li, Guoliang and Ooi, Beng Chin and Tan, Kian-lee and Feng, Jianhua},
title = {ICrowd: An Adaptive Crowdsourcing Framework},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2750550},
doi = {10.1145/2723372.2750550},
abstract = {Crowdsourcing is widely accepted as a means for resolving tasks that machines are not good at. Unfortunately, Crowdsourcing may yield relatively low-quality results if there is no proper quality control. Although previous studies attempt to eliminate "bad" workers by using qualification tests, the accuracies estimated from qualifications may not be accurate, because workers have diverse accuracies across tasks. Thus, the quality of the results could be further improved by selectively assigning tasks to the workers who are well acquainted with the tasks. To this end, we propose an adaptive crowdsourcing framework, called iCrowd. iCrowd on-the-fly estimates accuracies of a worker by evaluating her performance on the completed tasks, and predicts which tasks the worker is well acquainted with. When a worker requests for a task, iCrowd assigns her a task, to which the worker has the highest estimated accuracy among all online workers. Once a worker submits an answer to a task, iCrowd analyzes her answer and adjusts estimation of her accuracies to improve subsequent task assignments. This paper studies the challenges that arise in iCrowd. The first is how to estimate diverse accuracies of a worker based on her completed tasks. The second is instant task assignment. We deploy iCrowd on Amazon Mechanical Turk, and conduct extensive experiments on real datasets. Experimental results show that iCrowd achieves higher quality than existing approaches.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1015–1030},
numpages = {16},
keywords = {adaptive task assignment, quality control, crowdsourcing},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749430,
author = {Zheng, Yudian and Wang, Jiannan and Li, Guoliang and Cheng, Reynold and Feng, Jianhua},
title = {QASCA: A Quality-Aware Task Assignment System for Crowdsourcing Applications},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749430},
doi = {10.1145/2723372.2749430},
abstract = {A crowdsourcing system, such as the Amazon Mechanical Turk (AMT), provides a platform for a large number of questions to be answered by Internet workers. Such systems have been shown to be useful to solve problems that are difficult for computers, including entity resolution, sentiment analysis, and image recognition. In this paper, we investigate the online task assignment problem: Given a pool of n questions, which of the k questions should be assigned to a worker? A poor assignment may not only waste time and money, but may also hurt the quality of a crowdsourcing application that depends on the workers' answers. We propose to consider quality measures (also known as evaluation metrics) that are relevant to an application during the task assignment process. Particularly, we explore how Accuracy and F-score, two widely-used evaluation metrics for crowdsourcing applications, can facilitate task assignment. Since these two metrics assume that the ground truth of a question is known, we study their variants that make use of the probability distributions derived from workers' answers. We further investigate online assignment strategies, which enables optimal task assignments. Since these algorithms are expensive, we propose solutions that attain high quality in linear time. We develop a system called the Quality-Aware Task Assignment System for Crowdsourcing Applications (QASCA) on top of AMT. We evaluate our approaches on five real crowdsourcing applications. We find that QASCA is efficient, and attains better result quality (of more than 8% improvement) compared with existing methods.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1031–1046},
numpages = {16},
keywords = {online task assignment, crowdsourcing, quality control},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749440,
author = {Verroios, Vasilis and Lofgren, Peter and Garcia-Molina, Hector},
title = {TDP: An Optimal-Latency Budget Allocation Strategy for Crowdsourced MAXIMUM Operations},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749440},
doi = {10.1145/2723372.2749440},
abstract = {Latency is a critical factor when using a crowdsourcing platform to solve a problem like entity resolution or sorting. In practice, most frameworks attempt to reduce latency by heuristically splitting a budget of questions into rounds, so that after each round the answers are analyzed and new questions are selected. We focus on one of the most extensively studied crowdsourcing operations, the MAX operation (finding the best element in a collection under human criteria), and we study the problem of budget allocation into rounds for this operation. We provide a polynomial-time dynamic-programming budget allocation algorithm that minimizes the latency when questions form tournaments in each round. Furthermore, we study the general case where questions can be asked in any arbitrary way in each round. Our theoretical results for the general case indicate that our approach is also optimal under certain worst and average-case scenarios. We compare our approach to alternatives on Amazon Mechanical Turk, where many of our theory assumptions do not necessarily hold. We find that our approach is also optimal in practice and achieves a notable improvement over alternatives in most cases.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1047–1062},
numpages = {16},
keywords = {crowdsourcing top-k, crowdsourcing maximum operator, crowdsourcing budget allocation, crowdsourcing latency, crowdsourcing sorting},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735352,
author = {Wong, Petrie and He, Zhian and Feng, Ziqiang and Xu, Wenjian and Lo, Eric},
title = {Thrifty: Offering Parallel Database as a Service Using the Shared-Process Approach},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735352},
doi = {10.1145/2723372.2735352},
abstract = {Recently, Amazon has announced Redshift, a Parallel-Database-as-a Service (PDaaS). Redshift adopts the "virtual cluster" approach to implement multitenancy, which has the merit of hard isolation among tenants (i.e., tenants do not interfere even when sharing resources). However, that benefit comes with poor resource utilization due to the significant redundancy incurred in the resources. In this demonstration, we present Thrifty, a Parallel-Database-as-a-Service operated using the "shared-process" approach. Compared with Redshift, each tenant in Thrifty does not occupy an exclusive amount of resource but share the database processes together, leading to better resource utilization. To avoid contention among tenants, Thrifty uses a proper cluster design, a tenant placement scheme, and a query routing mechanism to achieve soft isolation. In the demonstration, an attendee will be invited to register with Thrifty as a tenant to rent a parallel database instance. Then the attendee will be allowed to view the dashboard of a Thrifty's administrator. Next, the attendee will be invited to control (e.g., increase) the workload of the tenant so as to see how Thrifty carries out online re- consolidation and elastic scaling.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1063–1068},
numpages = {6},
keywords = {database-as-a-service, parallel databases, consolidation, multi-tenant databases, cloud databases},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735354,
author = {Van Aken, Dana and Difallah, Djellel E. and Pavlo, Andrew and Curino, Carlo and Cudr\'{e}-Mauroux, Philippe},
title = {BenchPress: Dynamic Workload Control in the OLTP-Bench Testbed},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735354},
doi = {10.1145/2723372.2735354},
abstract = {Benchmarking is an essential activity when choosing database products, tuning systems, and understanding the trade-offs of the underlying engines. But the workloads available for this effort are often restrictive and non-representative of the ever changing requirements of the modern database applications. We recently introduced OLTP-Bench, an extensible testbed for benchmarking relational databases that is bundled with 15 workloads. The key features that set this framework apart is its ability to tightly control the request rate and dynamically change the transaction mixture. This allows an administrator to compose complex execution targets that recreate real system loads, and opens the doors to new research directions involving tuning for special execution patterns and multi-tenancy. In this demonstration, we highlight OLTP-Bench's important features through the BenchPress game. It allows users to control the benchmark behavior in real time for multiple database management systems.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1069–1073},
numpages = {5},
keywords = {oltp, flappy bird, performance, tuning, benchmarking, configuration, experimentation},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735360,
author = {Megler, V.M. and Maier, David},
title = {Demonstrating "Data Near Here": Scientific Data Search},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735360},
doi = {10.1145/2723372.2735360},
abstract = {Prior work proposed "Data Near Here" (DNH), a data search engine for scientific archives that is modeled on Internet search engines. DNH performs a periodic, asynchronous scan of each dataset in an archive, extracting lightweight features that are combined to form a dataset summary. During a search, DNH assesses the similarity of the search terms to the summary features and returns to the user, at interactive timescales, a ranked list of datasets for further exploration and analysis. We will demonstrate the search capabilities and ancillary metadata-browsing features for an archive of observational oceanographic data. While comparing search terms to complete datasets might seem ideal, interactive search speed would be impossible with archives of realistic size. We include an analysis showing that our summary-based approach gives a reasonable approximation of such a "complete dataset" similarity measure.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1075–1080},
numpages = {6},
keywords = {ranked data search, scientific data},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735363,
author = {Chevalier, Jules and Subercaze, Julien and Gravier, Christophe and Laforest, Fr\'{e}d\'{e}rique},
title = {Slider: An Efficient Incremental Reasoner},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735363},
doi = {10.1145/2723372.2735363},
abstract = {The Semantic Web has gained substantial momentum over the last decade. It contributes to the manifestation of knowledge from data, and leverages implicit knowledge through reasoning algorithms. The main drawbacks of current reasoning methods over ontologies are two-fold: first they struggle to provide scalability for large datasets, and second, the batch processing reasoners who provide the best scalability so far are unable to infer knowledge from evolving data. We contribute to solving these problems by introducing Slider, an efficient incremental reasoner. Slider goes a significant step beyond existing system, including i) performance, by more than a 70% improvement in average compared to the fastest reasoner available to the best of our knowledge, and ii) inferences on streams of semantic data, by using intrinsic features that are themselves streams-oriented. Slider is fragment agnostic and conceived to handle expanding data with a growing background knowledge base. It natively supports pdf and RDFS, and its architecture allows to extend it to more complex fragments with a minimal effort. In this demo a web-based interface allows the users to visualize the internal behaviour of Slider during the inference, to better understand its design and principles.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1081–1086},
numpages = {6},
keywords = {web of data, incremental reasoning, streamed reasoning},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735365,
author = {Vulimiri, Ashish and Curino, Carlo and Godfrey, Philip Brighten and Jungblut, Thomas and Karanasos, Konstantinos and Padhye, Jitendra and Varghese, George},
title = {WANalytics: Geo-Distributed Analytics for a Data Intensive World},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735365},
doi = {10.1145/2723372.2735365},
abstract = {Many large organizations collect massive volumes of data each day in a geographically distributed fashion, at data centers around the globe. Despite their geographically diverse origin the data must be processed and analyzed as a whole to extract insight. We call the problem of supporting large-scale geo-distributed analytics Wide-Area Big Data (WABD). To the best of our knowledge, WABD is currently addressed by copying all the data to a central data center where the analytics are run. This approach consumes expensive cross-data center bandwidth and is incompatible with data sovereignty restrictions that are starting to take shape. We instead propose WANalytics, a system that solves the WABD problem by orchestrating distributed query execution and adjusting data replication across data centers in order to minimize bandwidth usage, while respecting sovereignty requirements. WANalytics achieves an up to 360x reduction in data transfer cost when compared to the centralized approach on both real Microsoft production workloads and standard synthetic benchmarks, including TPC-CH and Berkeley Big-Data. In this demonstration, attendees will interact with a live geo-scale multi-data center deployment of WANalytics, allowing them to experience the data transfer reduction our system achieves, and to explore how it dynamically adapts execution strategy in response to changes in the workload and environment.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1087–1092},
numpages = {6},
keywords = {federation, analytics, olap, geo-distribution, sovereignty},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735367,
author = {Wu, Huayu and Tan, Jo-Anne and Ng, Wee Siong and Xue, Mingqiang and Chen, Wei},
title = {FTT: A System for Finding and Tracking Tourists in Public Transport Services},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735367},
doi = {10.1145/2723372.2735367},
abstract = {The tourism industry is a key economic driver for many cities. To understand tourists' traveling patterns can help both public and private relevant sectors design and improve their services to serve tourists better and get additional values from it. The existing approaches to discover tourists' traveling pattern focus on small sets of known tourists extracted from social media or other channels. The accuracy of the mining result cannot be guaranteed due to the small and bias set of samples.In this paper, we present our system FTT (Finding and Tracking Tourists) to identify tourists from public transport commuters in a city, and to further track their movements from one place to another. Our target is a large set of tourists and their trajectories extracted from public transport riding records, which more accurately represent the movements of general tourists. In particular, we design an iterative learning algorithm to find the tourists among public transport commuters, and provide interface to answer user queries on tourists' traveling patterns. The result will be visualized on top of a city map.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1093–1098},
numpages = {6},
keywords = {travel pattern, data analytics, tourist finding, public transport},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735368,
author = {Wang, Haozhou and Zheng, Kai and Zhou, Xiaofang and Sadiq, Shazia},
title = {SharkDB: An In-Memory Storage System for Massive Trajectory Data},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735368},
doi = {10.1145/2723372.2735368},
abstract = {An increasing amount of motion history data, which is called trajectory, is being collected from different sources such as GPS-enabled mobile devices, surveillance cameras and social networks. However it is hard to store and manage trajectory data in traditional database systems, since its variable lengths and asynchronous sampling rates do not fit disk-based and tuple-oriented structures, which are the fundamental structures of traditional database systems. We implement a novel trajectory storage system that is motivated by the success of column store and recent development of in-memory based databases. In this storage design, we try to explore the potential opportunities, which can boost the performance of query processing for trajectory data. To achieve this, we partition the trajectories into frames as column-oriented storage in order to store the sample points of a moving object, which are aligned by the time interval, within the main memory. Furthermore, the frames can be highly compressed and well structured to increase the memory utilization ratio and reduce the CPU-cache missing. It is also easier for parallelizing data processing on the multi-core server since the frames are mutually independent.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1099–1104},
numpages = {6},
keywords = {in-memory, column-oriented data structure, trajectory},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735369,
author = {Perez, Yonathan and Sosi\v{c}, Rok and Banerjee, Arijit and Puttagunta, Rohan and Raison, Martin and Shah, Pararth and Leskovec, Jure},
title = {Ringo: Interactive Graph Analytics on Big-Memory Machines},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735369},
doi = {10.1145/2723372.2735369},
abstract = {We present Ringo, a system for analysis of large graphs. Graphs provide a way to represent and analyze systems of interacting objects (people, proteins, webpages) with edges between the objects denoting interactions (friendships, physical interactions, links). Mining graphs provides valuable insights about individual objects as well as the relationships among them.In building Ringo, we take advantage of the fact that machines with large memory and many cores are widely available and also relatively affordable. This allows us to build an easy-to-use interactive high-performance graph analytics system. Graphs also need to be built from input data, which often resides in the form of relational tables. Thus, Ringo provides rich functionality for manipulating raw input data tables into various kinds of graphs. Furthermore, Ringo also provides over 200 graph analytics functions that can then be applied to constructed graphs.We show that a single big-memory machine provides a very attractive platform for performing analytics on all but the largest graphs as it offers excellent performance and ease of use as compared to alternative approaches. With Ringo, we also demonstrate how to integrate graph analytics with an iterative process of trial-and-error data exploration and rapid experimentation, common in data mining workloads.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1105–1110},
numpages = {6},
keywords = {algorithms, graphs, graph processing, performance, graph analytics, networks},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735373,
author = {Christensen, Robert and Wang, Lu and Li, Feifei and Yi, Ke and Tang, Jun and Villa, Natalee},
title = {STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735373},
doi = {10.1145/2723372.2735373},
abstract = {We present the STORM system to enable spatio-temporal online reasoning and management of large spatio-temporal data. STORM supports interactive spatio-temporal analytics through novel spatial online sampling techniques. Online spatio-temporal aggregation and analytics are then derived based on the online samples, where approximate answers with approximation quality guarantees can be provided immediately from the start of query execution. The quality of these online approximations improve over time. This demonstration proposal describes key ideas in the design of the STORM system, and presents the demonstration plan.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1111–1116},
numpages = {6},
keywords = {spatial online analytics, storm, spatial online sampling},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735374,
author = {Camacho-Rodr\'{\i}guez, Jes\'{u}s and Colazzo, Dario and Manolescu, Ioana and Naranjo, Juan A.M.},
title = {PAXQuery: Parallel Analytical XML Processing},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735374},
doi = {10.1145/2723372.2735374},
abstract = {XQuery is a general-purpose programming language for processing semi-structured data, and as such, it is very expressive. As a consequence, optimizing and parallelizing complex analytics XQuery queries is still an open, challenging problem.We demonstrate PAXQuery, a novel system that parallelizes the execution of XQuery queries over large collections of XML documents. PAXQuery compiles a rich subset of XQuery into plans expressed in the PArallelization ConTracts (PACT) programming model. Thanks to this translation, the resulting plans are optimized and executed in a massively parallel fashion by the Apache Flink system. The result is a scalable system capable of querying massive amounts of XML data very efficiently, as proved by the experimental results we outline.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1117–1122},
numpages = {6},
keywords = {xml data management, xquery parallelization, xquery processing},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2747644,
author = {M\"{u}ller, Ingo and Sanders, Peter and Lacurie, Arnaud and Lehner, Wolfgang and F\"{a}rber, Franz},
title = {Cache-Efficient Aggregation: Hashing Is Sorting},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2747644},
doi = {10.1145/2723372.2747644},
abstract = {For decades researchers have studied the duality of hashing and sorting for the implementation of the relational operators, especially for efficient aggregation. Depending on the underlying hardware and software architecture, the specifically implemented algorithms, and the data sets used in the experiments, different authors came to different conclusions about which is the better approach. In this paper we argue that in terms of cache efficiency, the two paradigms are actually the same. We support our claim by showing that the complexity of hashing is the same as the complexity of sorting in the external memory model. Furthermore we make the similarity of the two approaches obvious by designing an algorithmic framework that allows to switch seamlessly between hashing and sorting during execution. The fact that we mix hashing and sorting routines in the same algorithmic framework allows us to leverage the advantages of both approaches and makes their similarity obvious. On a more practical note, we also show how to achieve very low constant factors by tuning both the hashing and the sorting routines to modern hardware. Since we observe a complementary dependency of the constant factors of the two routines to the locality of the input, we exploit our framework to switch to the faster routine where appropriate. The result is a novel relational aggregation algorithm that is cache-efficient---independently and without prior knowledge of input skew and output cardinality---, highly parallelizable on modern multi-core systems, and operating at a speed close to the memory bandwidth, thus outperforming the state-of-the-art by up to 3.7x.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1123–1136},
numpages = {14},
keywords = {hashing, shared-memory, sorting, adaptive algorithm, cache-efficient, grouping, aggregation, robust performance, group by},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723733,
author = {Li, Guoliang and He, Jian and Deng, Dong and Li, Jian},
title = {Efficient Similarity Join and Search on Multi-Attribute Data},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723733},
doi = {10.1145/2723372.2723733},
abstract = {In this paper we study similarity join and search on multi- attribute data. Traditional methods on single-attribute data have pruning power only on single attributes and cannot efficiently support multi-attribute data. To address this problem, we propose a prefix tree index which has holis- tic pruning ability on multiple attributes. We propose a cost model to quantify the prefix tree which can guide the prefix tree construction. Based on the prefix tree, we devise a filter-verification framework to support similarity search and join on multi-attribute data. The filter step prunes a large number of dissimilar results and identifies some candi- dates using the prefix tree and the verification step verifies the candidates to generate the final answer. For similar- ity join, we prove that constructing an optimal prefix tree is NP-complete and develop a greedy algorithm to achieve high performance. For similarity search, since one prefix tree cannot support all possible search queries, we extend the cost model to support similarity search and devise a budget-based algorithm to construct multiple high-quality prefix trees. We also devise a hybrid verification algorithm to improve the verification step. Experimental results show our method significantly outperforms baseline approaches.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1137–1151},
numpages = {15},
keywords = {similarity search, multi-attribute data, similarity join},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723719,
author = {Petraki, Eleni and Idreos, Stratos and Manegold, Stefan},
title = {Holistic Indexing in Main-Memory Column-Stores},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723719},
doi = {10.1145/2723372.2723719},
abstract = {Great database systems performance relies heavily on index tuning, i.e., creating and utilizing the best indices depending on the workload. However, the complexity of the index tuning process has dramatically increased in recent years due to ad-hoc workloads and shortage of time and system resources to invest in tuning.This paper introduces holistic indexing, a new approach to automated index tuning in dynamic environments. Holistic indexing requires zero set-up and tuning effort, relying on adaptive index creation as a side-effect of query processing. Indices are created incrementally and partially;they are continuously refined as we process more and more queries. Holistic indexing takes the state-of-the-art adaptive indexing ideas a big step further by introducing the notion of a system which never stops refining the index space, taking educated decisions about which index we should incrementally refine next based on continuous knowledge acquisition about the running workload and resource utilization. When the system detects idle CPU cycles, it utilizes those extra cycles by refining the adaptive indices which are most likely to bring a benefit for future queries. Such idle CPU cycles occur when the system cannot exploit all available cores up to 100%, i.e., either because the workload is not enough to saturate the CPUs or because the current tasks performed for query processing are not easy to parallelize to the point where all available CPU power is exploited.In this paper, we present the design of holistic indexing for column-oriented database architectures and we discuss a detailed analysis against parallel versions of state-of-the-art indexing and adaptive indexing approaches. Holistic indexing is implemented in an open-source column-store DBMS. Our detailed experiments on both synthetic and standard benchmarks (TPC-H) and workloads (SkyServer) demonstrate that holistic indexing brings significant performance gains by being able to continuously refine the physical design in parallel to query processing, exploiting any idle CPU resources.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1153–1166},
numpages = {14},
keywords = {self-organization, holistic indexing},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749454,
author = {Mozafari, Barzan and Goh, Eugene Zhen Ye and Yoon, Dong Young},
title = {CliffGuard: A Principled Framework for Finding Robust Database Designs},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749454},
doi = {10.1145/2723372.2749454},
abstract = {A fundamental problem in database systems is choosing the best physical design, i.e., a small set of auxiliary structures that enable the fastest execution of future queries. Almost all commercial databases come with designer tools that create a number of indices or materialized views (together comprising the physical design) that they exploit during query processing. Existing designers are what we call nominal; that is, they assume that their input parameters are precisely known and equal to some nominal values. For instance, since future workload is often not known a priori, it is common for these tools to optimize for past workloads in hopes that future queries and data will be similar. In practice, however, these parameters are often noisy or missing. Since nominal designers do not take the influence of such uncertainties into account, they find designs that are sub-optimal and remarkably brittle. Often, as soon as the future workload deviates from the past, their overall performance falls off a cliff, leading to customer discontent and expensive redesigns. Thus, we propose a new type of database designer that is robust against parameter uncertainties, so that overall performance degrades more gracefully when future workloads deviate from the past. Users express their risk tolerance by deciding on how much nominal optimality they are willing to trade for attaining their desired level of robustness against uncertain situations. To the best of our knowledge, this paper is the first to adopt the recent breakthroughs in the theory of robust optimization to build a practical framework for solving some of the most fundamental problems in databases, replacing today's brittle designs with a principled world of robust designs that can guarantee predictable and consistent performance.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1167–1182},
numpages = {16},
keywords = {robust optimization, workload resilience, database performance, physical design},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723715,
author = {Joglekar, Manas and Garcia-Molina, Hector and Parameswaran, Aditya and Re, Christopher},
title = {Exploiting Correlations for Expensive Predicate Evaluation},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723715},
doi = {10.1145/2723372.2723715},
abstract = {User Defined Function(UDFs) are used increasingly to augment query languages with extra, application dependent functionality. Selection queries involving UDF predicates tend to be expensive, either in terms of monetary cost or latency. In this paper, we study ways to efficiently evaluate selection queries with UDF predicates. We provide a family of techniques for processing queries at low cost while satisfying user-specified precision and recall constraints. Our techniques are applicable to a variety of scenarios including when selection probabilities of tuples are available beforehand, when this information is available but noisy, or when no such prior information is available. We also generalize our techniques to more complex queries. Finally, we test our techniques on real datasets, and show that they achieve significant savings in UDF evaluations of up to $80%$, while incurring only a small reduction in accuracy.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1183–1198},
numpages = {16},
keywords = {user defined functions, approximate query processing},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2737786,
author = {Bergman, Moria and Milo, Tova and Novgorodov, Slava and Tan, Wang-Chiew},
title = {Query-Oriented Data Cleaning with Oracles},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2737786},
doi = {10.1145/2723372.2737786},
abstract = {As key decisions are often made based on information contained in a database, it is important for the database to be as complete and correct as possible. For this reason, many data cleaning tools have been developed to automatically resolve inconsistencies in databases. However, data cleaning tools provide only best-effort results and usually cannot eradicate all errors that may exist in a database. Even more importantly, existing data cleaning tools do not typically address the problem of determining what information is missing from a database.To overcome the limitations of existing data cleaning techniques, we present QOCO, a novel query-oriented system for cleaning data with oracles. Under this framework, incorrect (resp. missing) tuples are removed from (added to) the result of a query through edits that are applied to the underlying database, where the edits are derived by interacting with domain experts which we model as oracle crowds. We show that the problem of determining minimal interactions with oracle crowds to derive database edits for removing (adding) incorrect (missing) tuples to the result of a query is NP-hard in general and present heuristic algorithms that interact with oracle crowds. Finally, we implement our algorithms in our prototype system QOCO and show that it is effective and efficient through a comprehensive suite of experiments.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1199–1214},
numpages = {16},
keywords = {data cleaning, crowdsourcing},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2747646,
author = {Khayyat, Zuhair and Ilyas, Ihab F. and Jindal, Alekh and Madden, Samuel and Ouzzani, Mourad and Papotti, Paolo and Quian\'{e}-Ruiz, Jorge-Arnulfo and Tang, Nan and Yin, Si},
title = {BigDansing: A System for Big Data Cleansing},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2747646},
doi = {10.1145/2723372.2747646},
abstract = {Data cleansing approaches have usually focused on detecting and fixing errors with little attention to scaling to big datasets. This presents a serious impediment since data cleansing often involves costly computations such as enumerating pairs of tuples, handling inequality joins, and dealing with user-defined functions. In this paper, we present BigDansing, a Big Data Cleansing system to tackle efficiency, scalability, and ease-of-use issues in data cleansing. The system can run on top of most common general purpose data processing platforms, ranging from DBMSs to MapReduce-like frameworks. A user-friendly programming interface allows users to express data quality rules both declaratively and procedurally, with no requirement of being aware of the underlying distributed platform. BigDansing takes these rules into a series of transformations that enable distributed computations and several optimizations, such as shared scans and specialized joins operators. Experimental results on both synthetic and real datasets show that BigDansing outperforms existing baseline systems up to more than two orders of magnitude without sacrificing the quality provided by the repair algorithms.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1215–1230},
numpages = {16},
keywords = {distributed data repair, distributed data cleansing, cleansing abstraction, schema constraints},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2750549,
author = {Wang, Xiaolan and Dong, Xin Luna and Meliou, Alexandra},
title = {Data X-Ray: A Diagnostic Tool for Data Errors},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2750549},
doi = {10.1145/2723372.2750549},
abstract = {A lot of systems and applications are data-driven, and the correctness of their operation relies heavily on the correctness of their data. While existing data cleaning techniques can be quite effective at purging datasets of errors, they disregard the fact that a lot of errors are systematic, inherent to the process that produces the data, and thus will keep occurring unless the problem is corrected at its source. In contrast to traditional data cleaning, in this paper we focus on data diagnosis: explaining where and how the errors happen in a data generative process.We develop a large-scale diagnostic framework called DATA X-RAY. Our contributions are three-fold. First, we transform the diagnosis problem to the problem of finding common properties among erroneous elements, with minimal domain-specific assumptions. Second, we use Bayesian analysis to derive a cost model that implements three intuitive principles of good diagnoses. Third, we design an efficient, highly-parallelizable algorithm for performing data diagnosis on large-scale data. We evaluate our cost model and algorithm using both real-world and synthetic data, and show that our diagnostic framework produces better diagnoses and is orders of magnitude more efficient than existing techniques.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1231–1245},
numpages = {15},
keywords = {data cleaning, data profiling, error diagnosis},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749431,
author = {Chu, Xu and Morcos, John and Ilyas, Ihab F. and Ouzzani, Mourad and Papotti, Paolo and Tang, Nan and Ye, Yin},
title = {KATARA: A Data Cleaning System Powered by Knowledge Bases and Crowdsourcing},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749431},
doi = {10.1145/2723372.2749431},
abstract = {Classical approaches to clean data have relied on using integrity constraints, statistics, or machine learning. These approaches are known to be limited in the cleaning accuracy, which can usually be improved by consulting master data and involving experts to resolve ambiguity. The advent of knowledge bases KBs both general-purpose and within enterprises, and crowdsourcing marketplaces are providing yet more opportunities to achieve higher accuracy at a larger scale. We propose KATARA, a knowledge base and crowd powered data cleaning system that, given a table, a KB, and a crowd, interprets table semantics to align it with the KB, identifies correct and incorrect data, and generates top-k possible repairs for incorrect data. Experiments show that KATARA can be applied to various datasets and KBs, and can efficiently annotate data and suggest possible repairs.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1247–1261},
numpages = {15},
keywords = {crowdsourcing, knowledge base, data cleaning, data quality},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723739,
author = {Wang, Sibo and Xiao, Xiaokui and Lee, Chun-Hee},
title = {Crowd-Based Deduplication: An Adaptive Approach},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723739},
doi = {10.1145/2723372.2723739},
abstract = {Data deduplication stands as a building block for data integration and data cleaning. The state-of-the-art techniques focus on how to exploit crowdsourcing to improve the accuracy of deduplication. However, they either incur significant overheads on the crowd or offer inferior accuracy.This paper presents ACD, a new crowd-based algorithm for data deduplication. The basic idea of ACD is to adopt correlation clustering (which is a classic machine-based algorithm for data deduplication) under a crowd-based setting. We propose non-trivial techniques to reduce the time required in performing correlation clustering with the crowd, and devise methods to postprocess the results of correlation clustering for better accuracy of deduplication. With extensive experiments on the Amazon Mechanical Turk, we demonstrate that ACD outperforms the states of the art by offering a high precision of deduplication while incurring moderate crowdsourcing overheads.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1263–1277},
numpages = {15},
keywords = {data deduplication, crowdsourcing, correlating clustering},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723729,
author = {Nawab, Faisal and Arora, Vaibhav and Agrawal, Divyakant and El Abbadi, Amr},
title = {Minimizing Commit Latency of Transactions in Geo-Replicated Data Stores},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723729},
doi = {10.1145/2723372.2723729},
abstract = {Cross datacenter replication is increasingly being deployed to bring data closer to the user and to overcome datacenter outages. The extent of the influence of wide-area communication on serializable transactions is not yet clear. In this work, we derive a lower-bound on commit latency. The sum of the commit latency of any two datacenters is at least the Round-Trip Time (RTT) between them. We use the insights and lessons learned while deriving the lower-bound to develop a commit protocol, called Helios, that achieves low commit latencies. Helios actively exchanges transaction logs (history) between datacenters. The received logs are used to decide whether a transaction can commit or not. The earliest point in the received logs that is needed to commit a transaction is decided by Helios to ensure a low commit latency. As we show in the paper, Helios is theoretically able to achieve the lower-bound commit latency. Also, in a real-world deployment on five datacenters, Helios has a commit latency that is close to the optimal.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1279–1294},
numpages = {16},
keywords = {multi-datacenter, cloud computing, geo-replication},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2737788,
author = {Bernstein, Philip A. and Das, Sudipto and Ding, Bailu and Pilman, Markus},
title = {Optimizing Optimistic Concurrency Control for Tree-Structured, Log-Structured Databases},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2737788},
doi = {10.1145/2723372.2737788},
abstract = {Scaling-out a database system typically requires partitioning the database across multiple servers. If applications do not partition perfectly, then transactions accessing multiple partitions end up being distributed, which has well-known scalability challenges. To address them, we describe a high-performance transaction mechanism that uses optimistic concurrency control on a multi-versioned tree-structured database stored in a shared log. The system scales out by adding servers, without partitioning the database.Our solution is modeled on the Hyder architecture, published by Bernstein, Reid, and Das at CIDR 2011. We present the design and evaluation of the first full implementation of that architecture. The core of the system is a log roll-forward algorithm, called meld, that does optimistic concurrency control. Meld is inherently sequential and is therefore the main bottleneck. Our main algorithmic contributions are optimizations to meld that significantly increase transaction throughput. They use a pipelined design that parallelizes meld onto multiple threads. The slowest pipeline stage is much faster than the original meld algorithm, yielding a 3x improvement of system throughput over the original meld algorithm.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1295–1309},
numpages = {15},
keywords = {scale-out transaction processing, optimistic concurrency control},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723720,
author = {Roy, Sudip and Kot, Lucja and Bender, Gabriel and Ding, Bailu and Hojjat, Hossein and Koch, Christoph and Foster, Nate and Gehrke, Johannes},
title = {The Homeostasis Protocol: Avoiding Transaction Coordination Through Program Analysis},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723720},
doi = {10.1145/2723372.2723720},
abstract = {Datastores today rely on distribution and replication to achieve improved performance and fault-tolerance. But correctness of many applications depends on strong consistency properties--something that can impose substantial overheads, since it requires coordinating the behavior of multiple nodes. This paper describes a new approach to achieving strong consistency in distributed systems while minimizing communication between nodes. The key insight is to allow the state of the system to be inconsistent during execution, as long as this inconsistency is bounded and does not affect transaction correctness. In contrast to previous work, our approach uses program analysis to extract semantic information about permissible levels of inconsistency and is fully automated. We then employ a novel homeostasis protocol to allow sites to operate independently, without communicating, as long as any inconsistency is governed by appropriate treaties between the nodes. We discuss mechanisms for optimizing treaties based on workload characteristics to minimize communication, as well as a prototype implementation and experiments that demonstrate the benefits of our approach on common transactional benchmarks.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1311–1326},
numpages = {16},
keywords = {program analysis, geo-replication, coordination-free},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2737784,
author = {Bailis, Peter and Fekete, Alan and Franklin, Michael J. and Ghodsi, Ali and Hellerstein, Joseph M. and Stoica, Ion},
title = {Feral Concurrency Control: An Empirical Investigation of Modern Application Integrity},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2737784},
doi = {10.1145/2723372.2737784},
abstract = {The rise of data-intensive "Web 2.0" Internet services has led to a range of popular new programming frameworks that collectively embody the latest incarnation of the vision of Object-Relational Mapping (ORM) systems, albeit at unprecedented scale. In this work, we empirically investigate modern ORM-backed applications' use and disuse of database concurrency control mechanisms. Specifically, we focus our study on the common use of feral, or application-level, mechanisms for maintaining database integrity, which, across a range of ORM systems, often take the form of declarative correctness criteria, or invariants. We quantitatively analyze the use of these mechanisms in a range of open source applications written using the Ruby on Rails ORM and find that feral invariants are the most popular means of ensuring integrity (and, by usage, are over 37 times more popular than transactions). We evaluate which of these feral invariants actually ensure integrity (by usage, up to 86.9%) and which---due to concurrency errors and lack of database support---may lead to data corruption (the remainder), which we experimentally quantify. In light of these findings, we present recommendations for database system designers for better supporting these modern ORM programming patterns, thus eliminating their adverse effects on application integrity.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1327–1342},
numpages = {16},
keywords = {ruby on rails, invariants, orms, application integrity, concurrency control, impedance mismatch},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2742793,
author = {Weimer, Markus and Chen, Yingda and Chun, Byung-Gon and Condie, Tyson and Curino, Carlo and Douglas, Chris and Lee, Yunseong and Majestro, Tony and Malkhi, Dahlia and Matusevych, Sergiy and Myers, Brandon and Narayanamurthy, Shravan and Ramakrishnan, Raghu and Rao, Sriram and Sears, Russel and Sezgin, Beysim and Wang, Julia},
title = {REEF: Retainable Evaluator Execution Framework},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2742793},
doi = {10.1145/2723372.2742793},
abstract = {Resource Managers like Apache YARN have emerged as a critical layer in the cloud computing system stack, but the developer abstractions for leasing cluster resources and instantiating application logic are very low-level. This flexibility comes at a high cost in terms of developer effort, as each application must repeatedly tackle the same challenges (e.g., fault-tolerance, task scheduling and coordination) and re-implement common mechanisms (e.g., caching, bulk-data transfers). This paper presents REEF, a development framework that provides a control-plane for scheduling and coordinating task-level (data-plane) work on cluster resources obtained from a Resource Manager. REEF provides mechanisms that facilitate resource re-use for data caching, and state management abstractions that greatly ease the development of elastic data processing work-flows on cloud platforms that support a Resource Manager service. REEF is being used to develop several commercial offerings such as the Azure Stream Analytics service. Furthermore, we demonstrate REEF development of a distributed shell application, a machine learning algorithm, and a port of the CORFU [4] system. REEF is also currently an Apache Incubator project that has attracted contributors from several instititutions.1 http://reef.incubator.apache.org},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1343–1355},
numpages = {13},
keywords = {hadoop, high performance computing, big data, databases, machine learning, distributed systems},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2742790,
author = {Saha, Bikas and Shah, Hitesh and Seth, Siddharth and Vijayaraghavan, Gopal and Murthy, Arun and Curino, Carlo},
title = {Apache Tez: A Unifying Framework for Modeling and Building Data Processing Applications},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2742790},
doi = {10.1145/2723372.2742790},
abstract = {The broad success of Hadoop has led to a fast-evolving and diverse ecosystem of application engines that are building upon the YARN resource management layer. The open-source implementation of MapReduce is being slowly replaced by a collection of engines dedicated to specific verticals. This has led to growing fragmentation and repeated efforts with each new vertical engine re-implementing fundamental features (e.g. fault-tolerance, security, stragglers mitigation, etc.) from scratch.In this paper, we introduce Apache Tez, an open-source framework designed to build data-flow driven processing runtimes. Tez provides a scaffolding and library components that can be used to quickly build scalable and efficient data-flow centric engines. Central to our design is fostering component re-use, without hindering customizability of the performance-critical data plane. This is in fact the key differentiator with respect to the previous generation of systems (e.g. Dryad, MapReduce) and even emerging ones (e.g. Spark), that provided and mandated a fixed data plane implementation. Furthermore, Tez provides native support to build runtime optimizations, such as dynamic partition pruning for Hive.Tez is deployed at Yahoo!, Microsoft Azure, LinkedIn and numerous Hortonworks customer sites, and a growing number of engines are being integrated with it. This confirms our intuition that most of the popular vertical engines can leverage a core set of building blocks. We complement qualitative accounts of real-world adoption with quantitative experimental evidence that Tez-based implementations of Hive, Pig, Spark, and Cascading on YARN outperform their original YARN implementation on popular benchmarks (TPC-DS, TPC-H) and production workloads.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1357–1369},
numpages = {13},
keywords = {distributed data processing, apache hadoop, open source, big data},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2742796,
author = {Aref, Molham and ten Cate, Balder and Green, Todd J. and Kimelfeld, Benny and Olteanu, Dan and Pasalic, Emir and Veldhuizen, Todd L. and Washburn, Geoffrey},
title = {Design and Implementation of the LogicBlox System},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2742796},
doi = {10.1145/2723372.2742796},
abstract = {The LogicBlox system aims to reduce the complexity of software development for modern applications which enhance and automate decision-making and enable their users to evolve their capabilities via a ``self-service'' model. Our perspective in this area is informed by over twenty years of experience building dozens of mission-critical enterprise applications that are in use by hundreds of large enterprises across industries such as retail, telecommunications, banking, and government. We designed and built LogicBlox to be the system we wished we had when developing those applications.In this paper, we discuss the design considerations behind the LogicBlox system and give an overview of its implementation, highlighting innovative aspects. These include: LogiQL, a unified and declarative language based on Datalog; the use of purely functional data structures; novel join processing strategies; advanced incremental maintenance and live programming facilities; a novel concurrency control scheme; and built-in support for prescriptive and predictive analytics.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1371–1382},
numpages = {12},
keywords = {incremental maintenance, live programming, logicblox, leapfrog triejoin, logiql, predictive analytics, transaction repair, datalog},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2742797,
author = {Armbrust, Michael and Xin, Reynold S. and Lian, Cheng and Huai, Yin and Liu, Davies and Bradley, Joseph K. and Meng, Xiangrui and Kaftan, Tomer and Franklin, Michael J. and Ghodsi, Ali and Zaharia, Matei},
title = {Spark SQL: Relational Data Processing in Spark},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2742797},
doi = {10.1145/2723372.2742797},
abstract = {Spark SQL is a new module in Apache Spark that integrates relational processing with Spark's functional programming API. Built on our experience with Shark, Spark SQL lets Spark programmers leverage the benefits of relational processing (e.g. declarative queries and optimized storage), and lets SQL users call complex analytics libraries in Spark (e.g. machine learning). Compared to previous systems, Spark SQL makes two main additions. First, it offers much tighter integration between relational and procedural processing, through a declarative DataFrame API that integrates with procedural Spark code. Second, it includes a highly extensible optimizer, Catalyst, built using features of the Scala programming language, that makes it easy to add composable rules, control code generation, and define extension points. Using Catalyst, we have built a variety of features (e.g. schema inference for JSON, machine learning types, and query federation to external databases) tailored for the complex needs of modern data analysis. We see Spark SQL as an evolution of both SQL-on-Spark and of Spark itself, offering richer APIs and optimizations while keeping the benefits of the Spark programming model.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1383–1394},
numpages = {12},
keywords = {databases, spark, hadoop, machine learning, data warehouse},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735353,
author = {Salihoglu, Semih and Shin, Jaeho and Khanna, Vikesh and Truong, Ba Quan and Widom, Jennifer},
title = {Graft: A Debugging Tool For Apache Giraph},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735353},
doi = {10.1145/2723372.2735353},
abstract = {We address the problem of debugging programs written for Pregel-like systems. After interviewing Giraph and GPS users, we developed Graft. Graft supports the debugging cycle that users typically go through: (1) Users describe programmatically the set of vertices they are interested in inspecting. During execution, Graft captures the context information of these vertices across supersteps. (2) Using Graft's GUI, users visualize how the values and messages of the captured vertices change from superstep to superstep,narrowing in suspicious vertices and supersteps. (3) Users replay the exact lines of the code vertex.compute() function that executed for the suspicious vertices and supersteps, by copying code that Graft generates into their development environments' line-by-line debuggers. Graft also has features to construct end-to-end tests for Giraph programs. Graft is open-source and fully integrated into Apache Giraph's main code base.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1403–1408},
numpages = {6},
keywords = {debugging, distributed graph systems, distributed bulk synchronous parallel graph systems},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735355,
author = {Xiao, Dongqing and Bashllari, Armir and Menard, Tyler and Eltabakh, Mohamed},
title = {Even Metadata is Getting Big: Annotation Summarization Using InsightNotes},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735355},
doi = {10.1145/2723372.2735355},
abstract = {In this paper, we demonstrate the InsightNotes system, a summary-based annotation management engine over relational databases. InsightNotes addresses the unique challenges that arise in modern applications (especially scientific applications) that rely on rich and large-scale repositories of curation and annotation information. In these applications, the number and size of the raw annotations may grow beyond what end-users and scientists can comprehend and analyze. InsightNotes overcomes these limitations by integrating mining and summarization techniques with the annotation management engine in novel ways. The objective is to create concise and meaningful representations of the raw annotations, called ''annotation summaries'', to be the basic unit of processing. The core functionalities of InsightNotes include: (1) Extensibility, where domain experts can define the summary types suitable for their application, (2) Incremental Maintenance, where the system efficiently maintains the annotation summaries under the continuous addition of new annotations, (3) Summary-Aware Query Processing and Propagation, where the execution engine and query operators are extended for manipulating and propagating the annotation summaries within the query pipeline under complex transformations, and (4) Zoom-in Query Processing, where end-users can interactively expand specific annotation summaries of interest and retrieve their detailed (raw) annotations. We will demonstrate the InsightNotes's features using a real-world annotated database from the ornithological domain (the science of studying birds). We will design an interactive demonstration that engage the audience in annotating the data, visualizing how annotations are summarized and propagated, and zooming-in when desired to retrieve more details.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1409–1414},
numpages = {6},
keywords = {summary-based annotation management, query processing, scientific annotations},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735356,
author = {Gruenheid, Anja and Kossmann, Donald and Rekatsinas, Theodoros and Srivastava, Divesh},
title = {StoryPivot: Comparing and Contrasting Story Evolution},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735356},
doi = {10.1145/2723372.2735356},
abstract = {As the world evolves around us, so does the digital coverage of it. Events of diverse types, associated with different actors and various locations, are continuously captured by multiple information sources such as news articles, blogs, social media etc. day by day. In the digital world, these events are represented through information snippets that contain information on the involved entities, a description of the event, when the event occurred, etc. In our work, we observe that events (and their corresponding digital representations) are often inter-connected, i.e., they form stories which represent evolving relationships between events over time. Take as an example the plane crash in Ukraine in July 2014 which involved multiple entities such as "Ukraine", "Malaysia", and "Russia" and multiple events ranging from the actual crash to the incident investigation and the presentation of the investigator's findings. In this demonstration we present StoryPivot, a framework that helps its users to detect evolving stories in event datasets over time. To resolve stories, we differentiate between story identification, the problem of connecting events over time within a source, and story alignment, the problem of integrating stories across sources. The goal of this demonstration is to present an interactive exploration of both these problems and how events can be dynamically interpreted and put into context in real-world datasets.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1415–1420},
numpages = {6},
keywords = {story evolution, story detection, event processing, event management},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735359,
author = {Ulrich, Alexander and Grust, Torsten},
title = {The Flatter, the Better: Query Compilation Based on the Flattening Transformation},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735359},
doi = {10.1145/2723372.2735359},
abstract = {We demonstrate the insides and outs of a query compiler based on the flattening transformation, a translation technique designed by the programming language community to derive efficient data-parallel implementations from iterative programs. Flattening admits the straightforward formulation of intricate query logic including deeply nested loops over (possibly ordered) data or the construction of rich data structures. To demonstrate the level of expressiveness that can be achieved, we will bring a compiler frontend that accepts queries embedded into the Haskell programming language. Compilation via flattening takes places in a series of simple steps all of which will be made tangible by the demonstration. The final output is a program of lifted primitive operations which existing query engines can efficiently implement. We provide backends based on PostgreSQL and VectorWise to make this point however, most set-oriented or data-parallel engines could benefit from a flattening-based query compiler.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1421–1426},
numpages = {6},
keywords = {list comprehensions, flattening, nested data parallelism},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735362,
author = {Jergler, Martin and Sadoghi, Mohammad and Jacobsen, Hans-Arno},
title = {D2WORM: A Management Infrastructure for Distributed Data-Centric Workflows},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735362},
doi = {10.1145/2723372.2735362},
abstract = {Unlike traditional activity-flow-based models, data-centric workflows primarily focus on the data to drive a business. This enables the unification of operational management, concurrent process analytics, compliance with process or associated data constraints, and adaptability to changing environments. In this demonstration, we present D2Worm, a Distributed Data-centric Workflow Management system. D2Worm allows users to (1) graphically model data-centric workflows in a declarative fashion based on the Guard-Stage-Milestone (GSM) meta-model, (2) automatically compile the modelled workflow into several fine-granular workflow units (WFUs), and (3) deploy these WFUs on distributed infrastructures. A WFU is a system component that manages a subset of the workflow's data model and, at the same time, represents part of the global control flow by evaluating conditions over the data. WFUs communicate with each other over a publish/subscribe messaging infrastructure that allows the architecture to scale from a single node to dozens of machines distributed over different data-centers. In addition, D2Worm is able to (4) concurrently execute multiple workflow instances and monitor their behavior in real-time.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1427–1432},
numpages = {6},
keywords = {data-centric workflows, workflow distribution, publish/subscribe},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735370,
author = {Amsterdamer, Yael and Kukliansky, Anna and Milo, Tova},
title = {NL<sub>2</sub>CM: A Natural Language Interface to Crowd Mining},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735370},
doi = {10.1145/2723372.2735370},
abstract = {The joint processing of general data, which can refer to objective data such as geographical locations, with individual data, which is related to the habits and opinions of individuals, is required in many real-life scenarios. For this purpose, crowd mining platforms combine searching knowledge bases for general data, with mining the crowd for individual, unrecorded data. Existing such platforms require queries to be stated in a formal language. To bridge the gap between na\"{\i}ve users, who are not familiar with formal query languages, and crowd mining platforms, we develop NL2CM, a prototype system which translates natural language (NL) questions into well-formed crowd mining queries.The mix of general and individual information needs raises unique challenges. In particular, the different types of needs must be identified and translated into separate query parts. To account for these challenges, we develop new, dedicated modules and embed them within the modular and easily extensible architecture of NL2CM. Some of the modules interact with the user during the translation process to resolve uncertainties and complete missing data. We demonstrate NL2CM by translating questions of the audience, in different domains, into NL2CM, a crowd mining query language which is based on SPARQL.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1433–1438},
numpages = {6},
keywords = {individual and general data, natural language to query translation, crowd mining},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735372,
author = {Dudoladov, Sergey and Xu, Chen and Schelter, Sebastian and Katsifodimos, Asterios and Ewen, Stephan and Tzoumas, Kostas and Markl, Volker},
title = {Optimistic Recovery for Iterative Dataflows in Action},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735372},
doi = {10.1145/2723372.2735372},
abstract = {Over the past years, parallel dataflow systems have been employed for advanced analytics in the field of data mining where many algorithms are iterative.These systems typically provide fault tolerance by periodically checkpointing the algorithm's state and, in case of failure, restoring a consistent state from a checkpoint.In prior work, we presented an optimistic recovery mechanism that in certain cases eliminates the need to checkpoint the intermediate state of an iterative algorithm. In case of failure, our mechanism uses a compensation function to transit the algorithm to a consistent state, from which the execution can continue and successfully converge. Since this recovery mechanism does not checkpoint any state, it achieves optimal failure-free performance while guaranteeing fault tolerance.In this paper, we demonstrate our recovery mechanism with the Apache Flink data processing engine. During our demonstration, attendees will be able to run graph algorithms and trigger failures to observe the algorithms recovering with compensation functions instead of checkpoints.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1439–1443},
numpages = {5},
keywords = {iterative algorithms, fault-tolerance, optimistic recovery},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735376,
author = {Lallali, Saliha and Anciaux, Nicolas and Sandu Popa, Iulian and Pucheral, Philippe},
title = {A Secure Search Engine for the Personal Cloud},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735376},
doi = {10.1145/2723372.2735376},
abstract = {The emerging Personal Could paradigm holds the promise of a Privacy-by-Design storage and computing platform where personal data remain under the individual's control while being shared by valuable applications. However, leaving the data management control to user's hands pushes the security issues to the user's platform. This demonstration presents a Secure Personal Cloud Platform relying on a query and access control engine embedded in a tamper resistant hardware device connected to the user's platform. The main difficulty lies in the design of an inverted document index and its related search and update algorithms capable of tackling the strong hardware constraints of these devices. We have implemented our engine on a real tamper resistant hardware device and present its capacity to regulate the access to a personal dataspace. The objective of this demonstration is to show (1) that secure hardware is a key enabler of the Personal Cloud paradigm and (2) that new embedded indexing and querying techniques can tackle the hardware constraints of tamper-resistant devices and provide scalable solutions for the Personal Cloud.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1445–1450},
numpages = {6},
keywords = {personal cloud, access control, embedded search engine},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735377,
author = {Doka, Katerina and Papailiou, Nikolaos and Tsoumakos, Dimitrios and Mantas, Christos and Koziris, Nectarios},
title = {IReS: Intelligent, Multi-Engine Resource Scheduler for Big Data Analytics Workflows},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735377},
doi = {10.1145/2723372.2735377},
abstract = {Big data analytics tools are steadily gaining ground at becoming indispensable to businesses worldwide. The complexity of the tasks they execute is ever increasing due to the surge in data and task heterogeneity. Current analytics platforms, while successful in harnessing multiple aspects of this ``data deluge", bind their efficacy to a single data and compute model and often depend on proprietary systems. However, no single execution engine is suitable for all types of computation and no single data store is suitable for all types of data. To this end, we demonstrate IReS, the Intelligent Resource Scheduler for complex analytics workflows executed over multi-engine environments. Our system models the cost and performance of the required tasks over the available platforms. IReS is then able to match distinct workflow parts to the execution and/or storage engine among the available ones in order to optimize with respect to a user-defined policy. During the demo, the attendees will be able to execute workflows that match real use cases and parametrize the input datasets and optimization policy. The underlying platform supports multiple compute and data engines, allowing the user to choose any subset of them. Through the inspection of the produced plan, its execution and the collection and presentation of numerous cost and performance metrics, the audience will experience first-hand how IReS takes advantage of heterogeneous runtimes and data stores and effectively models operator cost and performance for actual and diverse workflows.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1451–1456},
numpages = {6},
keywords = {analytics workflows, cost modelling, profiling, big data, multi-engine optimization},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2735378,
author = {Rabl, Tilmann and Danisch, Manuel and Frank, Michael and Schindler, Sebastian and Jacobsen, Hans-Arno},
title = {Just Can't Get Enough: Synthesizing Big Data},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2735378},
doi = {10.1145/2723372.2735378},
abstract = {With the rapidly decreasing prices for storage and storage systems ever larger data sets become economical. While only few years ago only successful transactions would be recorded in sales systems, today every user interaction will be stored for ever deeper analysis and richer user modeling. This has led to the development of big data systems, which offer high scalability and novel forms of analysis. Due to the rapid development and ever increasing variety of the big data landscape, there is a pressing need for tools for testing and benchmarking. Vendors have little options to showcase the performance of their systems but to use trivial data sets like TeraSort or WordCount. Since customers' real data is typically subject to privacy regulations and rarely can be utilized, simplistic proof-of-concepts have to be used, leaving both, customers and vendors, unclear of the target use-case performance. As a solution, we present an automatic approach to data synthetization from existing data sources. Our system enables a fully automatic generation of large amounts of complex, realistic, synthetic data.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1457–1462},
numpages = {6},
keywords = {dbsynth, pdgf, data generator},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2750547,
author = {Barthels, Claude and Loesing, Simon and Alonso, Gustavo and Kossmann, Donald},
title = {Rack-Scale In-Memory Join Processing Using RDMA},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2750547},
doi = {10.1145/2723372.2750547},
abstract = {Database systems running on a cluster of machines, i.e. rack-scale databases, are a common architecture for many large databases and data appliances. As the data movement across machines is often a significant bottleneck, these systems typically use a low-latency, high-throughput network such as InfiniBand. To achieve the necessary performance, parallel join algorithms must take advantage of the primitives provided by the network to speed up data transfer.In this paper we focus on implementing parallel in-memory joins using Remote Direct Memory Access (RDMA), a communication mechanism to transfer data directly into the memory of a remote machine. The results of this paper are, to our knowledge, the first detailed analysis of parallel hash joins using RDMA. To capture their behavior independently of the network characteristics, we develop an analytical model and test our implementation on two different types of networks. The experimental results show that the model is accurate and the resulting distributed join exhibits good performance.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1463–1475},
numpages = {13},
keywords = {distributed query processing, distributed join, rack scale databases, join processing with rdma},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749438,
author = {Heimel, Max and Kiefer, Martin and Markl, Volker},
title = {Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749438},
doi = {10.1145/2723372.2749438},
abstract = {Quickly and accurately estimating the selectivity of multidimensional predicates is a vital part of a modern relational query optimizer. The state-of-the art in this field are multidimensional histograms, which offer good estimation quality but are complex to construct and hard to maintain. Kernel Density Estimation (KDE) is an interesting alternative that does not suffer from these problems. However, existing KDE-based selectivity estimators can hardly compete with the estimation quality of state-of-the art methods.In this paper, we substantially expand the state-of-the-art in KDE-based selectivity estimation by improving along three dimensions: First, we demonstrate how to numerically optimize a KDE model, leading to substantially improved estimates. Second, we develop methods to continuously adapt the estimator to changes in both the database and the query workload. Finally, we show how to drastically improve the performance by pushing computations onto a GPU.We provide an implementation of our estimator and experimentally evaluate it on a variety of datasets and workloads, demonstrating that it efficiently scales up to very large model sizes, adapts itself to database changes, and typically outperforms the estimation quality of both existing Kernel Density Estimators as well as state-of-the-art multidimensional histograms.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1477–1492},
numpages = {16},
keywords = {gpu-accelerated databases, gpgpu, query optimization, graphics cards, gpu-assisted query optimization, self-tuning databases, cardinality estimation, opencl, selectivity estimation, bandwidth selection, kernel density estimator},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2747645,
author = {Polychroniou, Orestis and Raghavan, Arun and Ross, Kenneth A.},
title = {Rethinking SIMD Vectorization for In-Memory Databases},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2747645},
doi = {10.1145/2723372.2747645},
abstract = {Analytical databases are continuously adapting to the underlying hardware in order to saturate all sources of parallelism. At the same time, hardware evolves in multiple directions to explore different trade-offs. The MIC architecture, one such example, strays from the mainstream CPU design by packing a larger number of simpler cores per chip, relying on SIMD instructions to fill the performance gap. Databases have been attempting to utilize the SIMD capabilities of CPUs. However, mainstream CPUs have only recently adopted wider SIMD registers and more advanced instructions, since they do not rely primarily on SIMD for efficiency. In this paper, we present novel vectorized designs and implementations of database operators, based on advanced SIMD operations, such as gathers and scatters. We study selections, hash tables, and partitioning; and combine them to build sorting and joins. Our evaluation on the MIC-based Xeon Phi co-processor as well as the latest mainstream CPUs shows that our vectorization designs are up to an order of magnitude faster than the state-of-the-art scalar and vector approaches. Also, we highlight the impact of efficient vectorization on the algorithmic design of in-memory database operators, as well as the architectural design and power efficiency of hardware, by making simple cores comparably fast to complex cores. This work is applicable to CPUs and co-processors with advanced SIMD capabilities, using either many simple cores or fewer complex cores.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1493–1508},
numpages = {16},
keywords = {vectorization, simd, xeon phi},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2737787,
author = {Li, Yinan and Chasseur, Craig and Patel, Jignesh M.},
title = {A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2737787},
doi = {10.1145/2723372.2737787},
abstract = {In-memory data analytic systems that use vertical bit-parallel scan methods generally use encoding techniques. We observe that in such environments, there is an opportunity to turn skew in both the data and predicate distributions (usually a problem for query processing) into a benefit that can be leveraged to encode the column values. This paper proposes a padded encoding scheme to address this opportunity. The proposed scheme creates encodings that map common attribute values to codes that can easily be distinguished from other codes by only examining a few bits in the full code. Consequently, scans on columns stored using the padded encoding scheme can safely prune the computation without examining all the bits in the code, thereby reducing the memory bandwidth and CPU cycles that are consumed when evaluating scan queries. Our padded encoding method results in a fixed-length encoding, as fixed-length encodings are easier to manage. However, the proposed padded encoding may produce longer (fixed-length) codes than those produced by popular order-preserving encoding methods, such as dictionary-based encoding. This additional space overhead has the potential to negate the gains from early pruning of the scan computation. However, as we demonstrate empirically, the additional space overhead is generally small, and the padded encoding scheme provides significant performance improvements.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1509–1524},
numpages = {16},
keywords = {bit-parallel, scan, analytics, encoding, skew},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723710,
author = {Li, Hui and Bhowmick, Sourav S. and Cui, Jiangtao and Gao, Yunjun and Ma, Jianfeng},
title = {GetReal: Towards Realistic Selection of Influence Maximization Strategies in Competitive Networks},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723710},
doi = {10.1145/2723372.2723710},
abstract = {State-of-the-art classical influence maximization (IM) techniques are "competition-unaware" as they assume that a group (company) finds seeds (users) in a network independent of other groups who are also simultaneously interested in finding such seeds in the same network. However, in reality several groups often compete for the same market (e.g., Samsung, HTC, and Apple for the smart phone market) and hence may attempt to select seeds in the same network. This has led to increasing body of research in devising IM techniques for competitive networks. Despite the considerable progress made by these efforts toward finding seeds in a more realistic settings, unfortunately, they still make several unrealistic assumptions (e.g., a new company being aware of a rival's strategy, alternate seed selection, etc.) making their deployment impractical in real-world networks. In this paper, we propose a novel framework based on game theory to provide a more realistic solution to the IM problem in competitive networks by jettisoning these unrealistic assumptions. Specifically, we seek to find the "best" IM strategy (an algorithm or a mixture of algorithms) a group should adopt in the presence of rivals so that it can maximize its influence. As each group adopts some strategy, we model the problem as a game with each group as competitors and the expected influences under the strategies as payoffs. We propose a novel algorithm called GetReal to find each group's best solution by leveraging the competition between different groups. Specifically, it seeks to find whether there exist a Nash Equilibrium (NE) in a game, which guarantees that there exist an "optimal" strategy for each group. Our experimental study on real-world networks demonstrates the superiority of our solution in a more realistic environment.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1525–1537},
numpages = {13},
keywords = {nash equilibrium, pure and mixed strategies, influence maximization, competitive network, game theory},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723734,
author = {Tang, Youze and Shi, Yanchen and Xiao, Xiaokui},
title = {Influence Maximization in Near-Linear Time: A Martingale Approach},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723734},
doi = {10.1145/2723372.2723734},
abstract = {Given a social network G and a positive integer k, the influence maximization problem asks for k nodes (in G) whose adoptions of a certain idea or product can trigger the largest expected number of follow-up adoptions by the remaining nodes. This problem has been extensively studied in the literature, and the state-of-the-art technique runs in O((k+l) (n+m) log n ε2) expected time and returns a (1-1 e-ε)-approximate solution with at least 1 - 1/n l probability.This paper presents an influence maximization algorithm that provides the same worst-case guarantees as the state of the art, but offers significantly improved empirical efficiency. The core of our algorithm is a set of estimation techniques based on martingales, a classic statistical tool. Those techniques not only provide accurate results with small computation overheads, but also enable our algorithm to support a larger class of information diffusion models than existing methods do. We experimentally evaluate our algorithm against the states of the art under several popular diffusion models, using real social networks with up to 1.4 billion edges. Our experimental results show that the proposed algorithm consistently outperforms the states of the art in terms of computation efficiency, and is often orders of magnitude faster.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1539–1554},
numpages = {16},
keywords = {sampling, influence maximization},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723737,
author = {Hu, Zhiting and Yao, Junjie and Cui, Bin and Xing, Eric},
title = {Community Level Diffusion Extraction},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723737},
doi = {10.1145/2723372.2723737},
abstract = {How does online content propagate on social networks? Billions of users generate, consume, and spread tons of information every day. This unprecedented scale of dynamics becomes invaluable to reflect our zeitgeist. However, most present diffusion extraction works have only touched individual user level and cannot obtain comprehensive clues.This paper introduces a new approach, i.e., COmmunity Level Diffusion (COLD), to uncover and explore temporal diffusion. We model topics and communities in a unified latent framework, and extract inter-community influence dynamics. With a well-designed multi-component model structure and a parallel inference implementation on GraphLab, the COLD method is expressive while remaining efficient.The extracted community level patterns enable diffusion exploration from a new perspective. We leverage the compact yet robust representations to develop new prediction and analysis applications. Extensive experiments on large social datasets show significant improvement in prediction accuracy. We can also find communities play very different roles in diffusion processes depending on their interest. Our method guarantees high scalability with increasing data size.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1555–1569},
numpages = {15},
keywords = {community detection, graph model, information diffusion},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2723716,
author = {Shin, Kijung and Jung, Jinhong and Lee, Sael and Kang, U.},
title = {BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2723716},
doi = {10.1145/2723372.2723716},
abstract = {Given a large graph, how can we calculate the relevance between nodes fast and accurately? Random walk with restart (RWR) provides a good measure for this purpose and has been applied to diverse data mining applications including ranking, community detection, link prediction, and anomaly detection. Since calculating RWR from scratch takes long, various preprocessing methods, most of which are related to inverting adjacency matrices, have been proposed to speed up the calculation. However, these methods do not scale to large graphs because they usually produce large and dense matrices which do not fit into memory.In this paper, we propose BEAR, a fast, scalable, and accurate method for computing RWR on large graphs. BEAR comprises the preprocessing step and the query step. In the preprocessing step, BEAR reorders the adjacency matrix of a given graph so that it contains a large and easy-to-invert submatrix, and precomputes several matrices including the Schur complement of the submatrix. In the query step, BEAR computes the RWR scores for a given query node quickly using a block elimination approach with the matrices computed in the preprocessing step. Through extensive experiments, we show that BEAR significantly outperforms other state-of-the-art methods in terms of preprocessing and query speed, space efficiency, and accuracy.},
booktitle = {Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data},
pages = {1571–1585},
numpages = {15},
keywords = {proximity, relevance score, random walk with restart},
location = {Melbourne, Victoria, Australia},
series = {SIGMOD '15}
}

@inproceedings{10.1145/2723372.2749449,
author = {Ruchansky, Natali and Bonchi, Francesco and Garc\'{\i}a-Soriano, David and Gullo, Francesco and Kourtellis, Nicolas},
title = {The Minimum Wiener Connector Problem},
year = {2015},
isbn = {9781450327589},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2723372.2749449},
doi = {10.1145/2723372.2749449},
abstract = {The Wiener index of a graph is the sum of all pairwise shortest-path distances between its vertices. In this paper we study the novel problem of finding a minimum Wiener connector: given a connected graph G=(V,E) and a set Q ⊆ V of query vertices, find a subgraph of G that connects all query vertices and has minimum Wiener index.We show that MIN WIENER CONNECTOR admits a polynomial-time (albeit impractical) exact algorithm for the special case where the number of query vertices is bounded. We show that in general the problem is NP-hard, and has no PTAS unless P = NP. Our main contribution is a constant-factor approximation algorithm running in time \~{O}(|

license_type: permissive

branch_name: refs/heads/main

extension: bib