Computer automated discovery of interestingness in faceted search

• US 7,493,319 B1
• Filed: 05/09/2008
• Issued: 02/17/2009
• Est. Priority Date: 10/22/2007
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Dash, Debabrata, Megiddo, Nimrod, Lohman, Guy M., Rao, Jun
• Primary Examiner(s): Chace; Christian
• Assistant Examiner(s): Syed; Farhan M
• Application Number:
  US12/118,206
• Time in Patent Office: 284 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5, 707/8, 707/10, 707/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

Exemplary embodiments of the present invention relate to enhanced faceted search support for OLAP queries over unstructured text as well as structured dimensions by the dynamic and automatic discovery of dimensions that are determined to be most “interesting” to a user based upon the data. Within the exemplary embodiments “interestingness” is defined as how surprising a summary along some dimensions is from a user'"'"'s expectation. Further, multi-attribute facets are determined and a user is optionally permitted to specify the distribution of values that she expects, and/or the distance metric by which actual and expected distributions are to be compared.

Claims

1. A computer program produce that includes a computer readable storage media, the media having stored thereon a sequence of instructions, when executed by the processor, causes the processor to perform an enhanced on-line analytical processing faceted search, by:

receiving at least one keyword as a constraint value for a query;

receiving input in regards to a selection of a probability baseline distribution value, wherein the probability baseline distribution value is determined as a product of an absolute baseline or a relative baseline;

receiving input in regard to a selection of a metric to determine a distance between a normalized probability distribution of search results on a facet set and a baseline distribution value;

determining a set of candidate facet, wherein encoding said set of candidate facet by pre-pending said set of candidate facet with a path from root to said set of candidate facet in a facet hierarchy, the candidate facet sets being based upon the keyword constraint value;

determining a probability distribution of the search results on a facet set and a baseline distribution value utilizing bit-set trees, wherein the utilization of bit-set trees contributes to the increased speed in determining the probability distribution of the search results;

eliminating uninteresting candidate facet combinations in an instance that a number of values within the probability distribution of the search results exceed a predetermined threshold, wherein said uninteresting candidate facet combinations are not within the same said facet hierarchy;

determining most interesting facet combinations;

returning for each interesting facet combination, a small number of most interesting values in it, the small number of most interesting values being the values whose associated probability differs the most between the query distribution and the baseline distribution; and

approximating the distance between the normalized probability distribution of search results on a facet set and a baseline distribution utilizing a random sample from the probability distribution.