NDLI: Optimization of constrained frequent set queries with 2-variable constraints

Content Provider	ACM Digital Library
Author	Lakshmanan, Laks V. S. Pang, Alex Han, Jiawei Ng, Raymond
Abstract	Currently, there is tremendous interest in providing ad-hoc mining capabilities in database management systems. As 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 2-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.
Starting Page	157
Ending Page	168
Page Count	12
File Format	PDF
ISSN	01635808
DOI	10.1145/304181.304196
Journal	ACM SIGMOD Record (SGMD)
Volume Number	28
Issue Number	2
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1999-06-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Information Systems Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Optimization of constrained frequent set queries with 2-variable constraints

Optimization of Constrained Frequent Set Queries with 2-variable Constraints (1998)

Exploratory mining via constrained frequent set queries

Optimization of constrained frequent set queries with 2-variable constraints (1998).

Optimization of Constrained Frequent Set Queries with 2-variable Constraints (1998)

Optimization of constrained frequent set queries with 2-variable constraints (1999).

On condensed representations of constrained frequent patterns

Processing aggregate relational queries with hard time constraints

Optimization of large join queries

Optimization of constrained frequent set queries with 2-variable constraints

Similar Documents

Optimization of constrained frequent set queries with 2-variable constraints

Optimization of Constrained Frequent Set Queries with 2-variable Constraints (1998)

Exploratory mining via constrained frequent set queries

Optimization of constrained frequent set queries with 2-variable constraints (1998).

Optimization of Constrained Frequent Set Queries with 2-variable Constraints (1998)

Optimization of constrained frequent set queries with 2-variable constraints (1999).

On condensed representations of constrained frequent patterns

Processing aggregate relational queries with hard time constraints

Optimization of large join queries

Optimization of constrained frequent set queries with 2-variable constraints