Dynamic Skyline Computation with LSD Trees
Given a set of high-dimensional feature vectors <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>S</mi><mo>⊂</mo><msup><mi mathvariant="double-struck">R<...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-02-01
|
| Series: | Analytics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2813-2203/2/1/9 |
| _version_ | 1797613902282883072 |
|---|---|
| author | Dominik Köppl |
| author_facet | Dominik Köppl |
| author_sort | Dominik Köppl |
| collection | DOAJ |
| description | Given a set of high-dimensional feature vectors <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>S</mi><mo>⊂</mo><msup><mi mathvariant="double-struck">R</mi><mi>n</mi></msup></mrow></semantics></math></inline-formula>, the skyline or Pareto problem is to report the subset of vectors in <i>S</i> that are not dominated by any vector of <i>S</i>. Vectors closer to the origin are preferred: we say a vector <i>x</i> is dominated by another distinct vector <i>y</i> if <i>x</i> is equally or further away from the origin than <i>y</i> with respect to all its dimensions. The dynamic skyline problem allows us to shift the origin, which changes the answer set. This problem is crucial for dynamic recommender systems where users can shift the parameters and thus shift the origin. For each origin shift, a recomputation of the answer set from scratch is time intensive. To tackle this problem, we propose a parallel algorithm for dynamic skyline computation that uses multiple local split decision (LSD) trees concurrently. The geometric nature of the LSD trees allows us to reuse previous results. Experiments show that our proposed algorithm works well if the dimension is small in relation to the number of tuples to process. |
| first_indexed | 2024-03-11T07:02:12Z |
| format | Article |
| id | doaj.art-16d0e1f2d78e4dc8869814061d88b627 |
| institution | Directory Open Access Journal |
| issn | 2813-2203 |
| language | English |
| last_indexed | 2024-03-11T07:02:12Z |
| publishDate | 2023-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Analytics |
| spelling | doaj.art-16d0e1f2d78e4dc8869814061d88b6272023-11-17T09:09:59ZengMDPI AGAnalytics2813-22032023-02-012114616210.3390/analytics2010009Dynamic Skyline Computation with LSD TreesDominik Köppl0M&D Data Science Center, Tokyo Medical and Dental University, Tokyo 113-8510, JapanGiven a set of high-dimensional feature vectors <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>S</mi><mo>⊂</mo><msup><mi mathvariant="double-struck">R</mi><mi>n</mi></msup></mrow></semantics></math></inline-formula>, the skyline or Pareto problem is to report the subset of vectors in <i>S</i> that are not dominated by any vector of <i>S</i>. Vectors closer to the origin are preferred: we say a vector <i>x</i> is dominated by another distinct vector <i>y</i> if <i>x</i> is equally or further away from the origin than <i>y</i> with respect to all its dimensions. The dynamic skyline problem allows us to shift the origin, which changes the answer set. This problem is crucial for dynamic recommender systems where users can shift the parameters and thus shift the origin. For each origin shift, a recomputation of the answer set from scratch is time intensive. To tackle this problem, we propose a parallel algorithm for dynamic skyline computation that uses multiple local split decision (LSD) trees concurrently. The geometric nature of the LSD trees allows us to reuse previous results. Experiments show that our proposed algorithm works well if the dimension is small in relation to the number of tuples to process.https://www.mdpi.com/2813-2203/2/1/9skyline computationparallel algorithmspreference evaluationapplication of geometric data structures |
| spellingShingle | Dominik Köppl Dynamic Skyline Computation with LSD Trees Analytics skyline computation parallel algorithms preference evaluation application of geometric data structures |
| title | Dynamic Skyline Computation with LSD Trees |
| title_full | Dynamic Skyline Computation with LSD Trees |
| title_fullStr | Dynamic Skyline Computation with LSD Trees |
| title_full_unstemmed | Dynamic Skyline Computation with LSD Trees |
| title_short | Dynamic Skyline Computation with LSD Trees |
| title_sort | dynamic skyline computation with lsd trees |
| topic | skyline computation parallel algorithms preference evaluation application of geometric data structures |
| url | https://www.mdpi.com/2813-2203/2/1/9 |
| work_keys_str_mv | AT dominikkoppl dynamicskylinecomputationwithlsdtrees |