Dynamic skyline computation on massive data
| Autor: | Bailing Wang, Guojun Lai, Xixian Han |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Skyline
Computer science Process (computing) InformationSystems_DATABASEMANAGEMENT Data space 02 engineering and technology computer.software_genre Human-Computer Interaction Artificial Intelligence Hardware and Architecture 020204 information systems 0202 electrical engineering electronic engineering information engineering Point (geometry) Pruning (decision trees) Data mining Tuple computer Software Information Systems Skyline computation |
| Zdroj: | Knowledge and Information Systems. 59:571-599 |
| ISSN: | 0219-3116 0219-1377 |
| DOI: | 10.1007/s10115-018-1193-y |
| Popis: | In many applications, dynamic skyline query is an important operation to find the interesting tuples in a potentially huge data space. Given the query point, dynamic skyline query returns tuples which are not dynamically dominated by other tuples. It is found that the existing algorithms cannot process dynamic skyline query on massive data efficiently. This paper proposes a novel dynamic-sorted-list-based DDS algorithm to efficiently compute dynamic skyline results on massive data. Given the query point, the dynamic sorted list of each attribute is not materialized but generated dynamically by the sorted list of the attribute. DDS retrieves the tuples in the involved dynamic sorted lists in the round-robin fashion until the early termination condition is satisfied, and computes the dynamic skyline results by retrieving the candidates. The pruning operation is devised to reduce the number of the retrieved candidates. The extensive experimental results, conducted on synthetic and real-life data sets, show that DDS outperforms the existing algorithms significantly. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink