Abstract In recent years, research in query processing has changed a lot. It has moved from traditional query processing (e.g., Selection, Nearest Neighbor (NN), Top-k, Skyline), to reverse query processing (e.g., Reverse NN, Reverse Top-k, Reverse Skyline), to maximal reverse query processing (e.g., find spatial points that maximize the number of Reverse NNs), and so on. This study considers a novel problem in this research area: given a set of selection queries with conjunctive conditions, create a tuple that maximizes the number of queries that return this tuple in their answers; that means maximizing the query results for reverse selection queries Surprisingly, there is no prior work on this problem, even though it has several natural applications, such as selecting product features or choosing the topics of a blog. The NP-completeness of the problem will be proved. The study will develop efficient exact algorithms and theoretical approximation algorithm with provable error bounds as well as a scalable heuristic that works well in practice for larger datasets. The study will conduct extensive experiments on real and synthetic data to demonstrate the effectiveness of the proposed algorithms.
Recommended Citation: Miah, M., (2015). Maximizing Reverse Selection Queries. Proceedings of the EDSIG Conference, (2015) n.3606, Wilmington, NC