Beyond basic faceted search

ABSTRACT

This paper extends traditional faceted search to support richer information discovery tasks over more complex data models. Our first extension adds exible, dynamic business intelligence aggregations to the faceted application, enabling users to gain insight into their data that is far richer than just knowing the quantities of documents belonging to each facet. We see this capability as a step toward bringing OLAP capabilities, traditionally supported by databases over relational data, to the domain of free-text queries over metadata-rich content. Our second extension shows how one can efficiently extend a faceted search engine to support correlated facets - a more complex information model in which the values associated with a document across multiple facets are not independent. We show that by reducing the problem to a recently solved tree-indexing scenario, data with correlated facets can be efficiently indexed and retrieved

REFERENCES

• 1: Sameet Agarwal , Rakesh Agrawal , Prasad Deshpande , Ashish Gupta , Jeffrey F. Naughton , Raghu Ramakrishnan , Sunita Sarawagi, On the Computation of Multidimensional Aggregates, Proceedings of the 22th International Conference on Very Large Data Bases, p.506-521, September 03-06, 1996
• 2: Peter Anick and Suresh Tipirneni. Method and apparatus for automatic construction of faceted terminological feedback for document retrieval, 2003. US Patent 6519586.
• 3: Will Archer Arentz and Aleksander Øhrn. Multidimensional visualization and navigation in search results. In Proc. 8th International Conference on Knowledge Based Intelligent Information and Engineering Systems (KES'2004), pages 620--627, September 2004.
• 4: Ramon C. Barquin , Herb A. Edelstein, Building, using, and managing the data warehouse, Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• 5: Andrei Z. Broder, Nadav Eiron, Marcus Fontoura, Michael Herscovici, Ronny Lempel, John McPherson, Runping Qi, and Eugene J. Shekita. Indexing of shared content in information retrieval systems. In Proc. 10th International Conference on Extending Database Technology (EDBT 2006), pages 313--330, March 2006.
• 6: E. F. Codd, S. B. Codd, and C. T. Salley. Providing olap (on-line analytical processing) to user-analysts: An IT mandate. Technical Report Technical Report, E. F. Codd & Associates, 1993.
• 7: Wisam Dakka, Rishabh Dayal, and Panagiotis G. Ipeirotis. Automatic discovery of useful facet terms. In Andrei Z. Broder and Yoelle S. Maarek, editors, Proc. SIGIR 2006 Workshop on Faceted Search, pages 18--22, August 2006.
• 8: Wisam Dakka , Panagiotis G. Ipeirotis , Kenneth R. Wood, Automatic construction of multifaceted browsing interfaces, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099738]
• 9: Ronald Fagin , R. Guha , Ravi Kumar , Jasmine Novak , D. Sivakumar , Andrew Tomkins, Multi-structural databases, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065191]
• 10: R. Fagin , Ph. Kolaitis , R. Kumar , J. Novak , D. Sivakumar , A. Tomkins, Efficient implementation of large-scale multi-structural databases, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 11: Daniel Feinstein and Frank Smadja. Hierarchical tags and faceted search. the rawsugar approach. In Andrei Z. Broder and Yoelle S. Maarek, editors, Proc. SIGIR 2006 Workshop on Faceted Search, pages 23--25, August 2006.
• 12: Marcus Fontoura, Ronny Lempel, Runping Qi, and Jason Zien. Inverted index support for numeric search. Internet Mathematics, 3(2):153--185, May 2007.
• 13: 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
• 14: Marti A. Hearst. Design recommendations for hierarchical faceted search interfaces. In Andrei Z. Broder and Yoelle S. Maarek, editors, Proc. SIGIR 2006 Workshop on Faceted Search, pages 26--30, August 2006.
• 15: Christian Kohlschütter, Paul-Alexandru Chirita, and Wolfgang Nejdl. Using link analysis to identify aspects in faceted web search. In Andrei Z. Broder and Yoelle S. Maarek, editors, SIGIR'2006 Workshop on Faceted Search, pages 55--59, August 2006.
• 16: Marc F. Krellenstein. Method and apparatus for searching a database of records, 1999. US Patent 5924090.
• 17: Daniel N. Meredith and Jan H. Pieper. Beta: Better extraction through aggregation. In Andrei Z. Broder and Yoelle S. Maarek, editors, SIGIR'2006 Workshop on Faceted Search, pages 8--12, August 2006.
• 18: Tapio Niemi , Marko Niinimäki , Jyrki Nummenmaa , Peter Thanisch, Constructing an OLAP cube from distributed XML data, Proceedings of the 5th ACM international workshop on Data Warehousing and OLAP, p.22-27, November 08-08, 2002, McLean, Virginia, USA [doi>10.1145/583890.583894]
• 19: Themistoklis Palpanas , Richard Sidle , Roberta Cochrane , Hamid Pirahesh, Incremental maintenance for non-distributive aggregate functions, Proceedings of the 28th international conference on Very Large Data Bases, p.802-813, August 20-23, 2002, Hong Kong, China
• 20: Kenneth A. Ross and Angel Janevski. Querying faceted databases. In Proc. 2004 Semantic Web and Databases Workshop (SWDB'2004), pages 199--218, August 2004.
• 21: Kenneth A. Ross , Divesh Srivastava, Fast Computation of Sparse Datacubes, Proceedings of the 23rd International Conference on Very Large Data Bases, p.116-125, August 25-29, 1997
• 22: Nick Roussopoulos , Yannis Kotidis , Mema Roussopoulos, Cubetree: organization of and bulk incremental updates on the data cube, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.89-99, May 11-15, 1997, Tucson, Arizona, United States
• 23: Ben Shneiderman , David Feldman , Anne Rose , Xavier Ferré Grau, Visualizing digital library search results with categorical and hierarchical axes, Proceedings of the fifth ACM conference on Digital libraries, p.57-66, June 02-07, 2000, San Antonio, Texas, United States [doi>10.1145/336597.336637]
• 24: Emilia Stoica, Marti A. Hearst, and Megan Richardson. Automating creation of hierarchical faceted metadata structures. In Proc. NAACL-HLT 2007, Rochester, NY, pages 244--251, April 2007.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms

Keywords:
business intelligence, multifaceted search, search engines