ABSTRACT
The concept of dominance has recently attracted much interest in the context of skyline computation. Given an N-dimensional data set S, a point p is said to dominate q if p is better than q in at least one dimension and equal to or better than it in the remaining dimensions. In this paper, we propose extending the concept of dominance for business analysis from a microeconomic perspective. More specifically, we propose a new form of analysis, called Dominant Relationship Analysis (DRA), which aims to provide insight into the dominant relationships between products and potential buyers. By analyzing such relationships, companies can position their products more effectively while remaining profitable.To support DRA, we propose a novel data cube called DADA (Data Cube for Dominant Relationship Analysis), which captures the dominant relationships between products and customers. Three types of queries called Dominant Relationship Queries (DRQs) are consequently proposed for analysis purposes: 1)Linear Optimization Queries (LOQ), 2)Subspace Analysis Queries (SAQ), and 3)Comparative Dominant Queries (CDQ). Algorithms are designed for efficient computation of DADA and answering the DRQs using DADA. Results of our comprehensive experiments show the effectiveness and efficiency of DADA and its associated query processing strategies.
- {1} S. Agarwal, R. Agrawal, P. Deshpande, A. Gupta, J. Naughton, R. Ramakrishnan, and S. Sarawagi. On the Computation of Multidimensional Aggregates. In VLDB, pages 506-521, 1996. Google ScholarDigital Library
- {2} D. A. K. Alexander Hinneburg. Optimal grid-clustering: Towards breaking the curse of dimensionality in high-dimensional clustering. In VLDB, 1999. Google ScholarDigital Library
- {3} K. S. Beyer and R. Ramakrishnan. Bottom-up computation of sparse and iceberg cubes. In SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, June 1-3, 1999, Philadelphia, Pennsylvania, USA, pages 359-370, 1999. Google ScholarDigital Library
- {4} G. Birkhoff. Lattice Theory. American Mathematical Society Colloquium Publications, Rhode Island, 1973.Google Scholar
- {5} S. Börzsönyi, D. Kossmann, and K. Stocker. The skyline operator. In ICDE, 2001.Google ScholarDigital Library
- {6} T. Brijs, G. Swinnen, K. Vanhoof, and G. Wets. Using association rules for product assortment decisions: A case study. In KDD, pages 254-260, 1999. Google ScholarDigital Library
- {7} C. Y. Chan, H. V. Jagadish, K.-L. Tan, A. K. H. Tung, and Z. Zhang. Finding k-dominant skyline in high dimensional space. In ACM SIGMOD, 2006. Google ScholarDigital Library
- {8} C. Y. Chan, H. V. Jagadish, K.-L. Tan, A. K. H. Tung, and Z. Zhang. On high dimensional skylines. In EDBT, pages 478-495, 2006. Google ScholarDigital Library
- {9} Q. Chen, M. Hsu, and U. Dayal. A data-warehouse/OLAP framework for scalable telecommunication tandem traffic analysis. In ICDE, pages 201-210, 2000. Google ScholarDigital Library
- {10} B. Davey and H. Priestley. Introduction to Lattices and Order. Cambridge University Press, 1990.Google Scholar
- {11} M. Ester, R. Ge, W. Jin, and Z. Hu. A microeconomic data mining problem: customer-oriented catalog segmentation. In KDD, pages 557-562, 2004. Google ScholarDigital Library
- {12} R. Godin, R. Missaoui, and H. Alaoui. Incremental concept formation algorithms based on galois (concept) lattices. Computational Intelligence, 11:246-267, 1995.Google ScholarCross Ref
- {13} J. Gray, A. Bosworth, A. Layman, and H. Pirahesh. Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-total. In ICDE, pages 152-159, 1996. Google ScholarDigital Library
- {14} J. Gray, S. Chaudhuri, A. Bosworth, A. Layman, D. Reichart, M. Venkatrao, F. Pellow, and H. Pirahesh. Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub totals. Data Min. Knowl. Discov., 1(1):29-53, 1997. Google ScholarDigital Library
- {15} J. Han. Olap mining: Integration of olap with data mining. In Database Semantics-7, pages 3-20, 1997.Google Scholar
- {16} V. Harinarayan, A. Rajaraman, and J. Ullman. Implementing data cubes efficiently. In ACM SIGMOD, pages 205-216, 1996. Google ScholarDigital Library
- {17} C.-T. Ho, R. Agrawal, N. Megiddo, and R. Srikant. Range queries in olap data cubes. In SIGMOD Conference, pages 73-88, 1997. Google ScholarDigital Library
- {18} J. Kleinberg, C. Papadimitriou, and P. Raghavan. Segmentation problems. In STOC, 1998. Google ScholarDigital Library
- {19} J. Kleinberg, C. Papadimitriou, and P. Raghavan. A microeconomic view of data mining. In Data Min. Knowl. Discov., 2(4): 311-322, 1998. Google ScholarDigital Library
- {20} D. Kossmann, F. Ramsak, and S. Rost. Shooting stars in the sky: An online algorithm for skyline queries. In VLDB, 2002. Google ScholarDigital Library
- {21} C. Li, G. Cong, A. K. H. Tung, and S. Wang. Incremental maintenance of quotient cube for median. In KDD, pages 226-235, New York, NY, USA, 2004. ACM Press. Google ScholarDigital Library
- {22} D. Papadias, Y. Tao, G. Fu, and B. Seeger. An optimal and progressive algorithm for skyline queries. In SIGMOD, 2003. Google ScholarDigital Library
- {23} K. Ross and D. Srivastava. Fast Computation of Sparse Datacubes. In VLDB, pages 116-125, 1997. Google ScholarDigital Library
- {24} N. Roussopoulos, Y. Kotidis, and M. Roussopoulos. Cubetree: organization of and bulk incremental updates on the data cube. In ACM SIGMOD, pages 89-99, 1997. Google ScholarDigital Library
- {25} Y. Sismanis, A. Deligiannakis, N. Roussopoulos, and Y. Kotidis. Dwarf: shrinking the petacube. In SIGMOD Conference, pages 464-475, 2002. Google ScholarDigital Library
- {26} K. L. Tan, P. K. Eng, and B. C. Ooi. Efficient progressive skyline computation. In VLDB, 2001. Google ScholarDigital Library
- {27} K. Wang, S. Zhou, and J. Han. Profit mining: From patterns to actions. In EDBT, pages 70-87, 2002. Google ScholarDigital Library
- {28} R. C.-W. Wong, A. W.-C. Fu, and K. Wang. Mpis: Maximal-profit item selection with cross-selling considerations. In ICDM, pages 371-378, 2003. Google ScholarDigital Library
- {29} J. T. Yao. Sensitivity analysis for data mining. In Proceedings of The 22nd International Conference of NAFIPS (the North American Fuzzy Information Processing Society), pages 272-277, 2003.Google ScholarCross Ref
- {30} Y. Yuan, X. Lin, Q. Liu, W. Wang, J. X. Yu, and Q. Zhang. Efficient computation of skyline cube. In VLDB, pages 241-252, 2005. Google ScholarDigital Library
- {31} Z. Zhang, X. Guo, H. Lu, A. K. H. Tung, and N. Wang. Discovering strong skyline points in high dimensional spaces. In CIKM, pages 247-248, 2005. Google ScholarDigital Library
Index Terms
- DADA: a data cube for dominant relationship analysis
Recommendations
Finding k-dominant skylines in high dimensional space
SIGMOD '06: Proceedings of the 2006 ACM SIGMOD international conference on Management of dataGiven a d-dimensional data set, a point p dominates another point q if it is better than or equal to q in all dimensions and better than q in at least one dimension. A point is a skyline point if there does not exists any point that can dominate it. ...
General dominant relationship analysis based on partial order models
SAC '07: Proceedings of the 2007 ACM symposium on Applied computingDue to the importance of skyline query in many applications, it has been attracted much attention recently. Given an N-dimensional dataset D, a point p is said to dominate another point q if p is better than q in at least one dimension and equal to or ...
Microeconomic analysis using dominant relationship analysis
The concept of dominance has recently attracted much interest in the context of skyline computation. Given an N-dimensional data set S, a point p is said to dominate q if p is better than q in at least one dimension and equal to or better than it in the ...
Comments