PICC Counting: Who Needs Joins When You Can Propagate Efficiently?.

Counting is a common task in many data mining applications, including market basket data analysis, scientific inquiry, and other high dimensional data management applications. Given a single table, obtaining the instance counts of the entries in the table is relatively cheap. In situations where the attributes of interest are distributed across different tables, however, the problem of computing instance counts can be very expensive. The naive solution, joining all the relevant relations to obtain a single table suitable for counting, is rarely practical. In this paper, we propose PICC (Propagation-based Instance Counts on Concise Graphs), a novel counting technique for discovering instance counts in databases. We first propose a propagation-based instance counting scheme which avoids joins to obtain a single table. We then present a method for summarizing a database into a concise synopsis and describe how to use this along with the propagation scheme to estimate the required counts efficiently. The experiment results show that the proposed technique, PICC, provides significant execution time and accuracy gains over the existing solutions to this problem. 1 Motivation and Related Work In many data analysis applications, such as business intelligence or scientific inquiry, it is common for the analysts to look for relationships and patterns across various data attributes. For example consider an archaeologist carrying out a study on animal bone specimens collected at various sites using the relation boneDB shown in Figure 1. For her analysis, this scientist may want to answer the following question, “What is the number of Coyote bones found in AZ?”. In algebraic terms, her question would translate to COUNT (∗)(σspe.=′Coyote′ ∧ found in=′AZ′(boneDB)) In this example, counts of the relevant value pairs can be computed (relatively) cheaply by a single pass over the boneDB table. This is, however, only a best case ∗Supported by NSF Grant “Archaeological Data Integration for the Study of Long-Term Human and Social Dynamics (0624341)” †Computer Science and Engineering Dept. Arizona State University, Tempe, AZ, 85287, USA. {jong, candan}@asu.edu boneDB Skull Skull Skull Skull Skull Skull bType bC_1 bC_1 bC_1 bC_1 bC_1 bC_1 bCode CA CA AZ AZ AZ AZ found_in species inst. researcher Wolf USC Brady Coyote USC Brady Wolf ASU Mike Coyote ASU Mike Wolf ASU Tom Coyote ASU Tom Figure 1: Motivating example: an archaeology database scenario. In the real-world, databases commonly consist of multiple tables and users’ interest (specified using queries) usually spans multiple such tables. Counting becomes costlier when the context of analysis spans multiple tables in a database. Consider, for instance, the database schema and instances shown in Figures 2 (a) and (b), respectively. Example 1.1. Given the database schema in Figure 2 (a), one way to compute the instance count in the database for the pair of attributes-values “species=’Coyote”’ and “found in=’AZ”’ is to join the individual tables to obtain a combined “countingcontext” table on which counting can be performed: SBE ← (SpecBone bType BoneCode) bCode Excavation CountingContext ← SBE inst. Researcher. The resulting CountingContext table (Figure 2(c)), obtained by joining Researcher, Excavation, BoneCode, and SpecBone, contains the same information as the boneDB table in Figure 1 and thus can be used to obtain the counts the analyst needs. Combining all the tables, however, can be expensive for large databases. In general, neither on demand construction of a combined table to be used as the counting context, nor constant maintenance of the context is practical. Thus our goal in this paper is to develop an efficient and effective approach to estimate counts, without having to combine all relevant relations in the database into a single relation. 1.1 Selectivity Estimation and Counting In many data mining applications, such as market basket analysis and transactional data analysis, knowledge about multi-attribute instance counts (e.g., numbers of 756 Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.