2010 · 24 citations · 17 references
BusinessComputer ScienceDecision SciencesBusiness IntelligenceDecision AnalysisMulti-criteria Decision MakingQuery OptimizationQuery ProcessingJoin ProcessingMulti-criteria Decision SupportMulti-criteria Decision Support SystemsMulti-objective Decision SupportUser Preferences
Multi-criteria decision support (MCDS) is crucial in many business and web applications such as web searches, B2B portals and on-line commerce. Such MCDS applications need to report results early; as soon as they are being generated so that they can react and formulate competitive decisions in near real-time. The ease in expressing user preferences in web-based applications has made Pareto-optimal (skyline) queries a popular class of MCDS queries. However, state-of-the-art techniques either focus on handling skylines on single input sets (i.e., no joins) or do not tackle the challenge of producing progressive early output results. In this work, we propose a progressive query evaluation framework ProgXe that transforms the execution of queries involving skyline over joins to be non-blocking, i.e., to be progressively generating results early and often. In ProgXe the query processing (join, mapping and skyline) is conducted at multiple levels of abstraction, thereby exploiting the knowledge gained from both input as well as mapped output spaces. This knowledge enables us to identify and reason about abstract-level relationships to guarantee correctness of early output. It also provides optimization opportunities previously missed by current techniques. To further optimize ProgXe, we incorporate an ordering technique that optimizes the rate at which results are reported by translating the optimization of tuple-level processing into a job-sequencing problem. Our experimental study over a wide variety of data sets demonstrates the superiority of our approach over state-of-the-art techniques.
17
S. Borzsony, Donald Kossmann, Konrad Stocker · 2002 · 2.2K citations
Optimal aggregation algorithms for middleware
Ronald Fagin, Amnon Lotem, Moni Naor · 2001 · 1.1K citations
On Finding the Maxima of a Set of Vectors
H. T. Kung, Fabrizio Luccio, F. P. Preparata · Journal of the ACM · 1975 · 913 citations · Full text
An optimal and progressive algorithm for skyline queries
Dimitris Papadias, Yufei Tao, Greg Fu et al. · 2003 · 806 citations
Efficient Progressive Skyline Computation
Kian‐Lee Tan, Pin-Kwang Eng, Beng Chin Ooi · Very Large Data Bases · 2001 · 703 citations