Optimizing faceted classification through facet range identification

In an approach to faceted classification, a computer receives a search query. The computer creates a first table of facet value ranges, based on the search query. The computer fetches a first search result corresponding to the search query. The computer retrieves a first facet value associated with the first search result. The computer maps the first facet value to a first facet value range. The computer determines whether the first facet value range is in the first table of facet value ranges. The computer inserts the first facet value range into the first table of facet value ranges. The computer determines whether a number of facet value ranges in the first table of facet value ranges is below a pre-defined threshold. The computer creates a second table of facet value ranges. The computer identifies a second facet value range that includes the first facet value range.

BACKGROUND OF THE INVENTION

The present invention relates generally to the field of data processing, and more particularly to faceted classification of search results.

Document retrieval systems accept a search query and generate a result, which is a set of documents. Queries are often specified by imposing conditions on document metadata (e.g. title, author, year, etc.). Sometimes the documents are representative of real objects, for example, an online catalog lets customers search for products to buy. Result sets are often sorted according to some criteria (e.g. ascending cost). Additional useful information which can be presented in response to a query is a classification of the results according to metadata that is not included in the original query, i.e., showing how the set of results is composed, according to specific “classes” of a property. For example, when searching an online catalog for a television, a certain number of results are identified, and the set of results is subdivided according to one category (e.g. dimension in inches) and subtotals are shown for each one of the possible values of the class (3 results for “17 inches”, 5 for “20 inches”, 12 for “22 inches”, 2 for “25 inches”, etc.). This kind of result classification is called faceting.

Faceting is often applied on many different categories at the same time, projecting the result set along orthogonal directions. For example, televisions can be classified according to size, manufacturer, technology, cost range, weight, etc. Faceted searches are maximally useful when a user is trying to identify the best choice among a number of proposals. The usual operation involves a wide query, giving a big result set which is faceted among many axes, each axis subdivided into different subcategories. The user reduces the result set by selecting one or more of the facet values. The additional condition is added to the query, and facets are recalculated.

SUMMARY

Embodiments of the present invention disclose a method, a computer program product, and a system for faceted classification. The method may include one or more computer processors receiving a search query. The one or more computer processors create a first table of facet value ranges, where facet value ranges are based, at least in part, on the search query, and where a first counter of search results associated with the facet value ranges is set to zero. The one or more computer processors fetch a first search result corresponding to the search query. The one or more computer processors retrieve a first facet value associated with the first search result. The one or more computer processors map the first facet value to a first facet value range. The one or more computer processors determine whether the first facet value range is in the first table of facet value ranges. Responsive to determining the first facet value range is not in the first table of facet value ranges, the one or more computer processors insert the first facet value range into the first table of facet value ranges. Responsive to inserting the first facet value range into the first table of facet value ranges, the one or more computer processors set a second counter of search results in the first facet value range to zero. Responsive to setting the second counter of search results associated with the first facet value range to zero, the one or more computer processors increase the second counter of search results by one. Responsive to inserting the first facet value range into the first table of facet value ranges, the one or more computer processors determine whether a number of facet value ranges in the first table of facet value ranges is below a pre-defined threshold. Responsive to determining the number of facet value ranges is not below the pre-defined threshold, the one or more computer processors create a second table of facet value ranges, in which a resolution of facet value ranges in the second table of facet value ranges is more coarse than a resolution of facet value ranges in the first table of facet value ranges, and in which a third counter of search results associated with the facet value ranges is set to zero. The one or more computer processors identify a second facet value range that includes the first facet value range.

DETAILED DESCRIPTION

In faceted classification, if the classification axis is an enumeration, subcategories can be immediately defined in obvious ways. For example, if searching for a television, enumeration classifications may include plasma, LCD, and CRT. If, instead, parameters have a continuous range (e.g. price, dimensions, or dates), in order to avoid a multitude of poorly populated classes, the preference is to divide the values into ranges, or bins, such as $200-$250, $250-$300, etc. The ranges should be wide enough to let many results fall in the same bin, but also be narrow enough to permit an effective drill down of the results. For example, a range which is $50 wide can be good for televisions, but is too small for cars and too wide for candies. A static decision of range size can be suboptimal in many applications. For example, when classifying by date, searches related to recent events give results spanning several weeks, and can be faceted per day. Other searches give results spanning one century, and are preferably faceted with ranges 5 years wide.

Embodiments of the present invention recognize that efficiency can be gained by implementing a search system that automatically identifies optimal ranges for faceted classification. The improved efficiency aids the user as well as reducing computer resource consumption. Implementation of embodiments of the invention may take a variety of forms, and exemplary implementation details are discussed subsequently with reference to the Figures.

Distributed data processing environment100includes client computing device104and server computer108interconnected over network102. Network102can be, for example, a telecommunications network, a local area network (LAN), a wide area network (WAN), such as the Internet, or a combination of the three, and can include wired, wireless, or fiber optic connections. Network102can include one or more wired and/or wireless networks that are capable of receiving and transmitting data, voice, and/or video signals, including multimedia signals that include voice, data, and video information.

Client computing device104can be a desktop computer, a laptop computer, a tablet computer, a specialized computer server, a smart phone, or any programmable electronic device capable of communicating with server computer108via network102and with various components and devices within distributed data processing environment100. In general, client computing device104represents any programmable electronic device or combination of programmable electronic devices capable of executing machine readable program instructions and communicating with other computing devices via a network, such as network102. Client computing device104includes user interface106.

User interface106provides an interface between a user of client computing device104and server computer108. User interface106may be a graphical user interface (GUI) or a web user interface (WUI) and can display text, documents, web browser windows, user options, application interfaces, and instructions for operation, and includes the information (such as graphic, text, and sound) that a program presents to a user and the control sequences the user employs to control the program. User interface106may also be mobile application software that provides an interface between a user of client computing device104and server computer108. Mobile application software, or an “app”, is a computer program designed to run on smart phones, tablet computers and other mobile devices. User interface106enables a user of client computing device104to perform faceted searches with optimal ranges on server computer108.

Server computer108can be a management server, a web server, or any other electronic device or computing system capable of receiving and sending data. In other embodiments, server computer108can represent a server computing system utilizing multiple computers as a server system, such as in a cloud computing environment. In another embodiment, server computer108can be a laptop computer, a tablet computer, a netbook computer, a personal computer (PC), a desktop computer, a personal digital assistant (PDA), a smart phone, or any programmable electronic device capable of communicating with client computing device104via network102. In another embodiment, server computer108represents a computing system utilizing clustered computers and components to act as a single pool of seamless resources. Server computer108includes faceting program110and database112.

Faceting program110fetches search results via network102for a user-inputted query and automatically generates ranges for facets with continuous values according to the actual results. Faceting program110evaluates each search result individually and classifies the results in bins with very fine resolution, i.e., narrow ranges. After a certain number of results have been collected, the number of distinct categories may grow beyond a pre-defined threshold. When the number of ranges exceeds the threshold, faceting program110determines that the classification is too fine and more coarse ranges can be used. Faceting program110establishes a new set of ranges and repositions the accumulated results in the new bins. If the number of bins still exceeds the threshold, faceting program110repeats the process. When faceting program110sufficiently reduces the number of ranges, faceting program110resumes fetching search results and increases an appropriate range counter, according to each new result. Whenever the number of ranges exceeds the threshold, faceting program110makes the ranges wider to allow collapsing to occur. Faceting program110is depicted and described in further detail with respect toFIG. 2,FIG. 3A, andFIG. 3B.

Database112resides on server computer108. In another embodiment, database112can reside elsewhere in the environment. A database is an organized collection of data. Database112can be implemented with any type of storage device capable of storing data that can be accessed and utilized by server computer108, such as a database server, a hard disk drive, or a flash memory. In other embodiments, database112can represent multiple storage devices within server computer108. Database112stores results related to search queries. Database112also stores tables used by faceting program110to track range width and count entries per range. In addition, database112stores a value for the threshold number of ranges. In one embodiment, the software developer pre-defines the threshold. In another embodiment, a user may choose a preferred limit to the number of ranges via user interface106.

FIG. 2is a flowchart depicting operational steps of faceting program110, on server computer108within distributed data processing environment100ofFIG. 1, for optimizing faceted classification, in accordance with an embodiment of the present invention.

Faceting program110receives a query (step202). When a user of client computing device104begins a search query, via user interface106, faceting program110receives the query, via network102.

Faceting program110creates an empty table of current ranges (step204). Facet values are taken from the metadata associated with the item requested in the search query. The metadata includes fields that represent characteristics of an item. For example, a book has an author, a title, and a price. Fields that have continuous values, such as price, are suitable for faceting. In one embodiment, the software developer pre-defines ranges for faceting program110to use with search queries. Faceting program110begins the faceted classification process by creating an empty table of ranges of the finest resolution for the particular facet value and creating a counter for each of the ranges where the counter is initially set to zero. For example, if the search query pertains to dates, faceting program110sets the current ranges to a width of 1 day, i.e., “10/01/2014”, “10/02/2014”, “10/03/2014”, etc. In another example, if the search query pertains to prices, faceting program110may set the current ranges to a width of $1, i.e., “$0-$1”, “$1.01-$2”, “$2.01-$3”, etc. Faceting program110stores the empty table in database112. Faceting program110populates the empty table with a maximum number of ranges that matches a pre-defined threshold for quantity of ranges.

Faceting program110fetches a result and retrieves a facet value (step206). Faceting program110fetches a search result based on the query and retrieves the facet value for the search result. For example, if the query is for televisions in an online catalog, and the facet axis is price, then faceting program110fetches a particular television model from the online catalog and retrieves the price of the television.

Faceting program110maps the facet value to a range (step208). Faceting program110maps the facet value to the range that contains the facet value, according to the current resolution. For example, if the price of a television is $400, and the resolution of the ranges is a width of $1, then the range that contains the price is $399.01-$400.

Faceting program110determines whether the range is in the table (decision block210). Faceting program110compares the ranges in the table to the range that contains the facet value and determines whether the range that contains the facet value exists in the table. If faceting program110determines that the range that contains the facet value does not exist in the table (“no” branch, decision block210), then faceting program110inserts the range that contains the facet value into the table and sets a counter for the range to zero (step212). If the range that contains the value of the facet is, for example, $399.01-$400, then faceting program110adds the range $399.01-$400 to the table. In order to provide the user with a quantity of results per range, faceting program110provides a counter for each range to track the results.

Responsive to setting the counter to zero, or if faceting program110determines the range is in the table (“yes” branch, decision block210), then faceting program110increases the counter by one (step214). As faceting program110adds the search result to the table, faceting program110increases the counter of results per range by one. For example, if5of the search results are in one range, the counter for the range equals 5.

Faceting program110determines whether the number of ranges is below the threshold (decision block216). Faceting program110compares the number of ranges in the table to the pre-defined threshold number of ranges and determines whether the number of ranges in the table is below the threshold number. If faceting program110determines the number of ranges in the table is below the threshold (“yes” branch, decision block216), then faceting program110determines whether there is an additional search result to fetch (decision block234).

If faceting program110determines the number of ranges in the table is not below the threshold (“no” branch, decision block216), then faceting program110creates a new, empty table for a more coarse resolution (step218). Faceting program110creates a new, empty table in database112to accommodate a more coarse resolution of ranges than exist in the current table, and creates a counter for each of the ranges in the new table where the counter is initially set to zero. Creating a more coarse resolution enables faceting program110to reduce the number of ranges in order to maintain the threshold number of ranges and to contain the fetched facet values. For example, if the current facet axis is dates, and faceting program110determines the resolution of one day per range cannot contain the current facet value within the threshold number of ranges, then faceting program110creates a new, empty table that can accommodate a more coarse resolution, such as one week per range.

Faceting program110identifies a coarse range for a fine range in the old table (step220). For each fine range in the old table, faceting program110identifies a coarse range that includes the fine range. For example, if the fine range width is one day, then faceting program110can identify a more coarse range of one week. The range of one day falls within the range of one week. When creating the coarse range, faceting program110confirms that the fine bin range can be contained within the coarse bin range. For example, moving from a range of one day to one week is acceptable. Moving from a range of one week to one month is not acceptable because a week may reside in more than one month, such as if the end of a month lands on a Tuesday. Therefore if faceting program110identifies a more coarse range than one week, then faceting program110creates a range of two weeks or four weeks, depending on the threshold number of ranges and the actual search results.

Faceting program110determines whether the coarse range is in the new table (decision block222). Similar to the discussion of step210, faceting program110compares the ranges in the new table to the coarse range that contains the facet value and determines whether the range that contains the facet value exists in the new table. For example, if a previously fetched facet value in the coarse range has already been added to the table, the coarse range may already exist in the new table. If faceting program110determines that the coarse range that contains the facet value does not exist in the table (“no” branch, decision block222), then faceting program110inserts the coarse range that contains the facet value into the table and sets a counter for the range to zero (step224).

Responsive to faceting program110setting the counter to zero, or if faceting program110determines the coarse range is in the new table (“yes” branch, decision block222), then faceting program110adds the counter of the old, fine range to the counter of the new, coarse range (step226). In order to maintain the count of the search results, faceting program110adds the quantity of the original search results in the fine range to the counter of the more coarse range.

Faceting program110determines whether there is another fine range (decision block228). As discussed with respect to step220, faceting program110performs the process of mapping existing bins into new bins by identifying a new, coarse range for each fine range present in the old table. If faceting program110determines that another fine range exists (“yes” branch, decision block228), then faceting program110returns to step220and repeats the process of inserting a coarse range that contains the fine range into the table and increasing the counter of the coarse range.

If faceting program110determines that another fine range does not exist (“no” branch, decision block228), then faceting program110replaces the old table with the new table (step230). When faceting program110has inserted enough coarse ranges into the new table to contain all of the fine ranges, then faceting program110deletes the old table in database112and replaces the old table with the new table in database112.

Faceting program110determines whether the number of ranges is below the threshold (decision block232). As discussed earlier with respect to decision block216, faceting program110compares the number of ranges in the new table to the pre-defined threshold number of ranges and determines whether the number of ranges is below the threshold number. If faceting program110determines that the number of ranges is not below the threshold (“no” branch, decision block232), then faceting program110returns to step218and begins the process of creating a new, empty table for a new, more coarse resolution.

If faceting program110determines the number of ranges is below the threshold (“yes” branch, decision block232), then faceting program110determines whether there is an additional search result to fetch (decision block234). Faceting program110determines whether the initial query yields an additional search result. If faceting program110determines there is an additional search result (“yes” branch, decision block234), then faceting program110returns to step206, fetches the additional search result, and retrieves the facet value.

If faceting program110determines there is no additional search result (“no” branch, decision block234), then faceting program110generates output (step236). When faceting program110completes fetching search results for the user-inputted search query, faceting program110outputs a current table that includes the list of ranges and the counter associated with each range.

The discussion ofFIG. 2, above, describes faceting program110processing search results for one facet. In an embodiment, faceting program110processes one or more facets simultaneously inside the fetching loop.

FIG. 3AandFIG. 3Billustrate examples of the use of faceting program110, on server computer108within distributed data processing environment100ofFIG. 1, in accordance with an embodiment of the present invention.

FIG. 3Aillustrates an embodiment of faceting program110where the user utilizes faceting program110to further refine, or drill down, the initial search results. In numeric format diagram300, table302represents the initial results of a search query of data in numeric format where the maximum number of ranges, i.e. the threshold, is 15. Faceting program110produces initial search results with a range width of 1,000,000 which includes 7 ranges. The count of the number of search results in each range is depicted in parentheses next to the range. To produce table302, faceting program110begins with the finest resolution of range width set at 1, and processes the search results through increasingly coarse resolutions until the number of ranges is less than the threshold. Arrow304indicates a user request to drill down to the 11 results in the range 2,000,000 to 2,999,999. In response to a new request, faceting program110restarts the faceting process with the results in the specified range, using the finest resolution until the number of ranges exceeds the threshold, and then iterating through more coarse resolutions until all of the search results are contained in a number of ranges below the threshold. Faceting program110produces table306. Although the ranges in table306are each only 1 wide, there are 10 ranges, not 1,000,000. In the example, a finest resolution of 1 is adequate to contain the number of ranges below the threshold. Faceting program110can spend the allowed threshold number of ranges while leaving holes in the continuous space. Although the maximum number of ranges is 15, faceting program110creates 7 ranges in table302and 10 ranges in table306because any additional ranges do not contain results, therefore the 7 ranges and the 10 ranges efficiently display the full set of results.

FIG. 3Bis similar toFIG. 3AasFIG. 3Balso illustrates an example of the results of a user utilizing faceting program110to drill down the initial search results. In date format diagram310, table312represents the initial results of a search query of data in date format where the maximum number of ranges, i.e. the threshold, is 15. Faceting program110produces initial search results with a range width of 6 months which includes 13 ranges. The count of the number of search results in each range is depicted in parentheses next to the range. In response to a new request, faceting program110restarts the faceting process with the results in the specified range, using the finest resolution until the number of ranges exceeds the threshold, and then iterating through more coarse resolutions until all of the search results are contained in a number of ranges below the threshold. Arrow314indicates a user request to drill down to the 593 results in the range 2005-01-01 to 2005-06-31. Faceting program110produces table316. Table316includes 10 ranges, and each range is 5 days wide. In the embodiment depicted in date format diagram310, faceting program110allows the user to request to drill down the results in more than one range, via user interface106. For example, faceting program110may display a pop-up box on client computing device104with a message such as “Choose one or more ranges for additional drill down.” In date format diagram310, arrow318indicates a user request to drill down to the 5 results in the range 2005-04-06 to 2005-04-10 and to the 20 results in the range 2005-04-11 to 2005-04-15. Faceting program110restarts the faceting process and produces table320. Table320includes 8 ranges, and each range is 1 day wide. For table320, the finest resolution of 1 day wide is adequate to display the results in less than 15 bins.

Memory406and persistent storage408are computer readable storage media. In this embodiment, memory406includes random access memory (RAM)414and cache memory416. In general, memory406can include any suitable volatile or non-volatile computer readable storage media.

Faceting program110and database112are stored in persistent storage408for execution and/or access by one or more of the respective computer processor(s)404via one or more memories of memory406. In this embodiment, persistent storage408includes a magnetic hard disk drive. Alternatively, or in addition to a magnetic hard disk drive, persistent storage408can include a solid-state hard drive, a semiconductor storage device, a read-only memory (ROM), an erasable programmable read-only memory (EPROM), a flash memory, or any other computer readable storage media that is capable of storing program instructions or digital information.

Communications unit410, in these examples, provides for communications with other data processing systems or devices, including resources of client computing device104. In these examples, communications unit410includes one or more network interface cards. Communications unit410may provide communications through the use of either or both physical and wireless communications links. Faceting program110and database112may be downloaded to persistent storage408through communications unit410.

I/O interface(s)412allows for input and output of data with other devices that may be connected to server computer108. For example, I/O interface(s)412may provide a connection to external device(s)418such as a keyboard, a keypad, a touch screen, a microphone, a digital camera, and/or some other suitable input device. External device(s)418can also include portable computer readable storage media such as, for example, thumb drives, portable optical or magnetic disks, and memory cards. Software and data used to practice embodiments of the present invention, e.g., faceting program110and database112, can be stored on such portable computer readable storage media and can be loaded onto persistent storage408via I/O interface(s)412. I/O interface(s)412also connect to a display420.