Abstract | ||
---|---|---|
In recent years, there has been significant interest in the development of ranking functions and efficient top-k retrieval algorithms to help users in ad hoc search and retrieval in databases (e.g., buyers searching for products in a catalog). We introduce a complementary problem: How to guide a seller in selecting the best attributes of a new tuple (e.g., a new product) to highlight so that it stands out in the crowd of existing competitive products and is widely visible to the pool of potential buyers. We develop several formulations of this problem. Although the problems are NP-complete, we give several exact and approximation algorithms that work well in practice. One type of exact algorithms is based on Integer Programming (IP) formulations of the problems. Another class of exact methods is based on maximal frequent item set mining algorithms. The approximation algorithms are based on greedy heuristics. A detailed performance study illustrates the benefits of our methods on real and synthetic data. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1109/TKDE.2009.72 | IEEE Trans. Knowl. Data Eng. |
Keywords | Field | DocType |
maximize visibility,exact method,new product,efficient top-k retrieval algorithm,approximation algorithm,integer programming,new tuple,complementary problem,exact algorithm,competitive product,best attribute,greedy algorithms,computational complexity,data engineering,approximation algorithms,marketing,linear programming,data mining,database systems,synthetic data,information retrieval,np complete problem,relational databases,approximation theory,greedy heuristic | Data mining,Computer science,Theoretical computer science,Heuristics,Integer programming,Linear programming,Artificial intelligence,Approximation algorithm,Ranking,Tuple,Greedy algorithm,Machine learning,Computational complexity theory | Journal |
Volume | Issue | ISSN |
21 | 7 | 1041-4347 |
Citations | PageRank | References |
8 | 0.52 | 23 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
muhammed miah | 1 | 49 | 2.85 |
Gautam Das | 2 | 4083 | 335.74 |
Vagelis Hristidis | 3 | 2814 | 185.78 |
Heikki Mannila | 4 | 6595 | 1495.69 |