Query result ranking over e-commerce web databases

Weifeng Su, Jiying Wang, Qiong Huang, Frederick H. LochovskyCIKM 2006 · DOI

TL;DR

This paper introduces QRRE, an automatic query result ranking system for e-commerce websites that infers user preferences from the query itself, without requiring user feedback. QRRE assigns weights to attributes based on their correlation with the query and scores attribute values based on their desirability in an e-commerce context, effectively tackling the "too many results" problem.

What Problem Does This Paper Address?

In the age of the internet, e-commerce websites often return a massive number of results for a user's query. Imagine searching for a used car and getting thousands of listings – sifting through them to find the "best deal" is a tedious and time-consuming task. Traditional databases often allow sorting by a single attribute, but users typically consider multiple factors simultaneously. While some systems allow users to manually assign weights to attributes, this is often difficult for average users and doesn't work well for categorical attributes. This paper addresses the challenge of automatically ranking query results from e-commerce databases in a way that reflects user preferences, without explicit user input.

Methods

QRRE employs a two-pronged approach:

  • Attribute Weight Assignment: The core idea here is that attributes mentioned in a user's query are likely important. Furthermore, attributes that are highly correlated with the specified attributes are also likely to be important. QRRE quantifies this correlation by comparing the distribution of attribute values in the query results to their distribution in the entire database. A larger difference suggests a stronger correlation, leading to a higher weight for that attribute. This is achieved by calculating the Kullback-Leibler (KL) divergence between the attribute distributions. To build these distributions, QRRE uses a novel "probing-and-count" method to construct histograms for attributes without full database access.
  • Attribute-Value Preference Score Assignment: This module assigns a score to each attribute value within a result tuple, indicating its desirability. QRRE makes two key assumptions for e-commerce:
  • Price Assumption: Lower prices are generally preferred.
  • Non-Price Assumption: Desirable non-price attributes (e.g., "new" car, "luxury" car) often correspond to higher prices. Based on these, the Price attribute is scored inversely to its value (lower price = higher score). For non-price attributes, their values are converted to equivalent "price points" (e.g., the average price of cars with that specific attribute value). These converted price points are then scored using the same mechanism as the actual Price attribute. The final ranking score for a tuple is a weighted sum of its attribute-value preference scores.

Datasets

The paper uses two e-commerce databases for evaluation:

  • carDB: A used car database with 100,000 tuples, containing attributes like Make, Model, Year, Price, Mileage, and Location.
  • houseDB: A real estate database with 20,000 tuples, including attributes like City, Location, Bedrooms, Bathrooms, Sq Ft, and Price.

These databases were simulated using MySQL on a P4 3.2-GHz PC.

Key Insights and Ideas

  • Query as a Preference Signal: The paper's central insight is that a user's query itself contains valuable implicit information about their preferences, which can be leveraged for ranking.
  • Correlation is Key: Beyond explicitly stated query conditions, attributes that are highly correlated with those conditions are also important indicators of user preference. This is a more nuanced understanding than simply looking at specified attributes.
  • E-commerce Specific Assumptions: The paper effectively uses domain-specific assumptions about price and desirability to create a generalizable scoring mechanism for non-price attributes.
  • No User Feedback Required: The ability to rank results effectively without explicit user input or interaction is a significant advantage, making the system more user-friendly.
  • Probing for Histograms: The novel probing-based histogram construction method allows for building attribute distributions even with limited access to autonomous web databases.

Key Results

  • Superior Ranking Quality: Experimental results show that QRRE consistently produces more relevant and intuitive rankings compared to a RANDOM baseline and the Probabilistic Information Retrieval (PIR) model.
  • Higher Average Precision: QRRE achieved a higher average precision score than PIR across both carDB and houseDB datasets. For instance, on carDB, QRRE's average precision was 0.735 compared to PIR's 0.555.
  • User Preference Alignment: User studies indicated that subjects generally preferred QRRE's rankings over PIR's, suggesting QRRE better captures user preferences.
  • Efficiency: The online processing time of QRRE grows almost linearly with the number of query results, making it scalable.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • String Attributes: QRRE currently does not handle string attributes (e.g., book titles, comments), which are common in web databases. Incorporating these would be a valuable extension.
  • Scalability of Evaluation: The current evaluation was on small-scale datasets. A larger, more comprehensive benchmark is needed for thorough evaluation.
  • E-commerce Specificity: QRRE is tailored for e-commerce. Extending it to non-e-commerce web databases would broaden its applicability.

Summary updated

BibTeX
@inproceedings{su2006query,
  author = {Weifeng Su and Jiying Wang and Qiong Huang and Frederick H. Lochovsky},
  title = {{Query result ranking over e-commerce web databases}},
  booktitle = {ACM International Conference on Information and Knowledge Management},
  year = {2006},
  doi = {10.1145/1183614.1183697},
}
Figure