Dynamic faceted search for discovery-driven analysis

ABSTRACT

We propose a dynamic faceted search system for discovery-driven analysis on data with both textual content and structured attributes. From a keyword query, we want to dynamically select a small set of "interesting" attributes and present aggregates on them to a user. Similar to work in OLAP exploration, we define "interestingness" as how surprising an aggregated value is, based on a given expectation. We make two new contributions by proposing a novel "navigational" expectation that's particularly useful in the context of faceted search, and a novel interestingness measure through judicious application of p-values. Through a user survey, we find the new expectation and interestingness metric quite effective. We develop an efficient dynamic faceted search system by improving a popular open source engine, Solr. Our system exploits compressed bitmaps for caching the posting lists in an inverted index, and a novel directory structure called a bitset tree for fast bitset intersection. We conduct a comprehensive experimental study on large real data sets and show that our engine performs 2 to 3 times faster than Solr.

REFERENCES

• 1: DBXplorer: A System for Keyword-Based Search over Relational Databases, Proceedings of the 18th International Conference on Data Engineering, p.5, February 26-March 01, 2002
• 2: http://base.google.com/
• 3: http://clusty.com/
• 4: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 5: W. Dakka, et al: Automatic discovery of useful facet terms. In SIGIR Faceted Search Workshop, 2006
• 6: DBLP dataset: http://dblp.uni-trier.de/xml/
• 7: Bradley Efron and Robert J. Tibshirani: An introduction to the bootstrap. Chapman & Hall, 1993
• 8: http://endeca.com/
• 9: The Flamenco Search Interface Project. http://flamenco.berkeley.edu/
• 10: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 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: 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
• 13: Ihab F. Ilyas , Volker Markl , Peter Haas , Paul Brown , Ashraf Aboulnaga, CORDS: automatic discovery of correlations and soft functional dependencies, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007641]
• 14: Xiaohui Long , Torsten Suel, Optimized query execution in large search engines with global page ordering, Proceedings of the 29th international conference on Very large data bases, p.129-140, September 09-12, 2003, Berlin, Germany
• 15: http://lucene.apache.org/
• 16: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 17: Patent dataset: http://www.nber.org/patents
• 18: John Roddick, et al: A Survey of Temporal Knowledge Discovery Paradigms and Methods. In TKDE, 2002
• 19: Sunita Sarawagi: User-Adaptive Exploration of Multidimensional Data. VLDB 2000: 307--316
• 20: Sunita Sarawagi , Rakesh Agrawal , Nimrod Megiddo, Discovery-Driven Exploration of OLAP Data Cubes, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.168-182, March 23-27, 1998
• 21: http://incubator.apache.org/solr/
• 22: Jayme Luiz Szwarcfiter, Optimal multiway search trees for variable size keys, Acta Informatica, v.21 n.1, p.47-60, May 1984 [doi>10.1007/BF00289139]
• 23: http://www.ibm.com/software/data/discovery/content
• 24: Ian H. Witten , Timothy C. Bell , Alistair Moffat, Managing Gigabytes: Compressing and Indexing Documents and Images, John Wiley & Sons, Inc., New York, NY, 1994
• 25: http://www.research.ibm.com/UIMA/
• 26: Ping Wu, et al: From Keyword-based Retrieval to Keyword-driven Analytical Processing: A Multi-faceted Approach. SIGMOD 2007
• 27: Kesheng Wu , Ekow J. Otoo , Arie Shoshani, Optimizing bitmap indices with efficient compression, ACM Transactions on Database Systems (TODS), v.31 n.1, p.1-38, March 2006 [doi>10.1145/1132863.1132864]
• 28: http://commons.apache.org/math/
• 29: Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer, Generalized Search Trees for Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.562-573, September 11-15, 1995
• 30: Liqiang Geng , Howard J. Hamilton, Interestingness measures for data mining: A survey, ACM Computing Surveys (CSUR), v.38 n.3, p.9-es, 2006 [doi>10.1145/1132960.1132963]
• 31: Friedman, et al: Exploratory Projection Pursuit. In JASA, 1987.
• 32: Swayne, et al: XGobi: Interactive Dynamic Data Visualization in the X Window System. In JCGS, 1998.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.m Miscellaneous

General Terms:
Algorithms, Experimentation