Record Details

Optimization of constrained frequent set queries with 2-variable constraints

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Optimization of constrained frequent set queries with 2-variable constraints
 
Creator LAKSHMANAN, LVS
NG, R
HAN, JW
PANG, A
 
Description Currently, there is tremendous interest in providing ad-hoc mining capabilities in database management systems, hs a first step towards this goal, in [15] we proposed an architecture for supporting constraint-based, human-centered, exploratory mining of various kinds of rules including associations, introduced the notion of constrained frequent set queries (CFQs), and developed effective pruning optimizations for CFQs with 1-variable (1-var) constraints. While 1-var constraints are useful for constraining the antecedent and consequent separately, many natural examples of CFQs illustrate the need for constraining the antecedent and consequent jointly, for which 2-variable (2-var) constraints are indispensable. Developing pruning optimizations for CFQs with 2-var constraints is the subject of this paper. But this is a difficult problem because: (i) in 2-var constraints, both variables keep changing and, unlike 1-var constraints, there is no fixed target for pruning; (ii) as we show, "conventional" monotonicity-based optimization techniques do not apply effectively to P-var constraints. The contributions are as follows. (1) We introduce a notion of quasi-succinctness, which allows a quasi-succinct 2-var constraint to be reduced to two succinct 1-var constraints for pruning. (2) We characterize the class of 2-var constraints that are quasi-succinct. (3) We develop heuristic techniques for non-quasi-succinct constraints. Experimental results show the effectiveness of all our techniques. (4) We propose a query optimizer for CFQs and show that for a large class of constraints, the computation strategy generated by the optimizer is ccc-optimal, i.e., minimizing the effort incurred w.r.t. constraint checking and support counting.
 
Publisher ASSOC COMPUTING MACHINERY
 
Date 2011-10-27T07:46:17Z
2011-12-15T09:12:19Z
2011-10-27T07:46:17Z
2011-12-15T09:12:19Z
1999
 
Type Proceedings Paper
 
Identifier SIGMOD RECORD, VOL 28, NO 2 - JUNE 1999: SIGMOD99: PROCEEDINGS OF THE 1999 ACM SIGMOD - INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA,157-168
1-58113-084-8
http://dspace.library.iitb.ac.in/xmlui/handle/10054/16225
http://hdl.handle.net/100/2594
 
Source 1999 ACM SIGMOD International Conference on Management of Data,PHILADELPHIA, PA,JUN 01-03, 1999
 
Language English