Answering aggregate keyword queries on relational databases using minimal group-bys

ABSTRACT

Keyword search has been recently extended to relational databases to retrieve information from text-rich attributes. However, all the existing methods focus on finding individual tuples matching a set of query keywords from one table or the join of multiple tables. In this paper, we motivate a novel problem of aggregate keyword search: finding minimal group-bys covering a set of query keywords well, which is useful in many applications. We develop two interesting approaches to tackle the problem, and further extend our methods to allow partial matches. An extensive empirical evaluation using both real data sets and synthetic data sets is reported to verify the effectiveness of aggregate keyword search and the efficiency of our methods.

REFERENCES

• 1: S. Agrawal et al. DBXplorer: A system for keyword-based search over relational databases. In ICDE'02.
• 2: Sihem Amer-Yahia , Pat Case , Thomas Rölleke , Jayavel Shanmugasundaram , Gerhard Weikum, Report on the DB/IR panel at SIGMOD 2005, ACM SIGMOD Record, v.34 n.4, December 2005 [doi>10.1145/1107499.1107514]
• 3: Kevin Beyer , Raghu Ramakrishnan, Bottom-up computation of sparse and Iceberg CUBE, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.359-370, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 4: G. Bhalotia et al. Keyword searching and browsing in databases using banks. In ICDE'02.
• 5: S. Chaudhuri et al. Integrating DB and IR technologies: What is the sound of one hand clapping? In CIDR'05.
• 6: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 7: B. Ding et al. Finding top-k min-cost connected trees in databases. In ICDE'07.
• 8: Min Fang , Narayanan Shivakumar , Hector Garcia-Molina , Rajeev Motwani , Jeffrey D. Ullman, Computing Iceberg Queries Efficiently, Proceedings of the 24rd International Conference on Very Large Data Bases, p.299-310, August 24-27, 1998
• 9: Ying Feng , Divyakant Agrawal , Amr El Abbadi , Ahmed Metwally, Range CUBE: Efficient Cube Computation by Exploiting Data Correlation, Proceedings of the 20th International Conference on Data Engineering, p.658, March 30-April 02, 2004
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996
• 12: Jiawei Han , Jian Pei , Guozhu Dong , Ke Wang, Efficient computation of Iceberg cubes with complex measures, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.1-12, May 21-24, 2001, Santa Barbara, California, United States
• 13: Donna Harman , R. Baeza-Yates , Edward Fox , W. Lee, Inverted files, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 14: Hao He , Haixun Wang , Jun Yang , Philip S. Yu, BLINKS: ranked keyword searches on graphs, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247516]
• 15: Vagelis Hristidis , Luis Gravano , Yannis Papakonstantinou, Efficient IR-style keyword search over relational databases, Proceedings of the 29th international conference on Very large data bases, p.850-861, September 09-12, 2003, Berlin, Germany
• 16: Vagelis Hristidis , Yannis Papakonstantinou, Discover: keyword search in relational databases, Proceedings of the 28th international conference on Very Large Data Bases, p.670-681, August 20-23, 2002, Hong Kong, China
• 17: Varun Kacholia , Shashank Pandit , Soumen Chakrabarti , S. Sudarshan , Rushi Desai , Hrishikesh Karambelkar, Bidirectional expansion for keyword search on graph databases, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 18: Benny Kimelfeld , Yehoshua Sagiv, Finding and approximating top-k answers in keyword proximity search, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142377]
• 19: Fang Liu , Clement Yu , Weiyi Meng , Abdur Chowdhury, Effective keyword search in relational databases, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142536]
• 20: Yi Luo , Xuemin Lin , Wei Wang , Xiaofang Zhou, Spark: top-k keyword query in relational databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247495]
• 21: Raymond T. Ng , Alan Wagner , Yu Yin, Iceberg-cube computation with PC clusters, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.25-36, May 21-24, 2001, Santa Barbara, California, United States
• 22: Quang Hieu Vu , Beng Chin Ooi , Dimitris Papadias , Anthony K. H. Tung, A graph method for keyword-based selection of the top-K databases, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376707]
• 23: Gerhard Weikum, DB&IR: both sides now, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247484]
• 24: Ping Wu , Yannis Sismanis , Berthold Reinwald, Towards keyword-driven analytical processing, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247549]
• 25: Dong Xin , Jiawei Han , Xiaolei Li , Benjamin W. Wah, Star-cubing: computing iceberg cubes by top-down and bottom-up integration, Proceedings of the 29th international conference on Very large data bases, p.476-487, September 09-12, 2003, Berlin, Germany
• 26: Bei Yu , Guoliang Li , Karen Sollins , Anthony K. H. Tung, Effective keyword-based selection of relational databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247498]