- 93 views
- 78 downloads
Interactive Set Discovery
-
- Author / Creator
- Hasnat, Md Arif
-
We study the problem of set discovery where given a few example tuples of a desired set, we want to find the set in a collection of sets. A challenge is that the example tuples may not uniquely identify a set, and a large number of candidate sets may be returned. Our focus is on interactive exploration to set discovery where additional example tuples from the candidate sets are shown and the user either accepts or rejects them as members of the target set. The goal is to find the target set with the least number of user interactions. The problem can be cast as an optimization problem where we want to fi nd a decision tree that can guide the search to the target set with the least number of questions to be answered by the user. We propose a general algorithm that is capable of reaching an optimal solution and two variations of it that strike a balance between the quality of a solution and the running time. We also propose a novel pruning strategy that safely reduces the search space without introducing false negatives. We evaluate the efficiency and the effectiveness of our algorithms through an extensive experimental study using both real and synthetic datasets and comparing them to previous approaches in the literature. We show that our pruning strategy reduces the running time of the search algorithms by 2-5 orders of magnitude.
-
- Subjects / Keywords
-
- Interactive Exploration
- Set Discovery
- Decision Tree
- Cost Optimization
- Lookahead
- Lower Bound
- Query Discovery
- Query Reverse Engineering
- Pruning
- Example-Based Queries
- Interactive Learning of Queries
- Cost-Efficient Decision Tree
- Optimal Decision Tree
- Feature Selection
- Attribute Selection
- Search Space Reduction
- Human in the Loop
- Database Usability
- User Feedback
- User Interaction
- Active Learning
- Membership Questions
-
- Graduation date
- Fall 2021
-
- Type of Item
- Thesis
-
- Degree
- Master of Science
-
- License
- This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.