File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/1559845.1559897
- Scopus: eid_2-s2.0-70849097739
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Scalable skyline computation using object-based space partitioning
Title | Scalable skyline computation using object-based space partitioning |
---|---|
Authors | |
Keywords | Preference Skyline Space partitioning |
Issue Date | 2009 |
Publisher | ACM. |
Citation | The 2009 International Conference on Management of Data and 28th Symposium on Principles of Database Systems (SIGMOD-PODS'09), Providence, RI., 29 June-2 July 2009. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data (SIGMOD'09), 2009, p. 483-494 How to Cite? |
Abstract | The skyline operator returns from a set of multi-dimensional objects a subset of superior objects that are not dominated by others. This operation is considered very important in multi-objective analysis of large datasets. Although a large number of skyline methods have been proposed, the majority of them focuses on minimizing the I/O cost. However, in high dimensional spaces, the problem can easily become CPU-bound due to the large number of computations required for comparing objects with current skyline points while scanning the database. Based on this observation, we propose a dynamic indexing technique for skyline points that can be integrated into state-of-the-art sort-based skyline algorithms to boost their computational performance. The new indexing and dominance checking approach is supported by a theoretical analysis, while our experiments show that it scales well with the input size and dimensionality not only because unnecessary dominance checks are avoided but also because it allows efficient dominance checking with the help of bitwise operations. © 2009 ACM. |
Persistent Identifier | http://hdl.handle.net/10722/61173 |
ISBN | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Zhang, S | en_HK |
dc.contributor.author | Mamoulis, N | en_HK |
dc.contributor.author | Cheung, DWL | en_HK |
dc.date.accessioned | 2010-07-13T03:32:29Z | - |
dc.date.available | 2010-07-13T03:32:29Z | - |
dc.date.issued | 2009 | en_HK |
dc.identifier.citation | The 2009 International Conference on Management of Data and 28th Symposium on Principles of Database Systems (SIGMOD-PODS'09), Providence, RI., 29 June-2 July 2009. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data (SIGMOD'09), 2009, p. 483-494 | en_HK |
dc.identifier.isbn | 978-1-60558-551-2 | - |
dc.identifier.uri | http://hdl.handle.net/10722/61173 | - |
dc.description.abstract | The skyline operator returns from a set of multi-dimensional objects a subset of superior objects that are not dominated by others. This operation is considered very important in multi-objective analysis of large datasets. Although a large number of skyline methods have been proposed, the majority of them focuses on minimizing the I/O cost. However, in high dimensional spaces, the problem can easily become CPU-bound due to the large number of computations required for comparing objects with current skyline points while scanning the database. Based on this observation, we propose a dynamic indexing technique for skyline points that can be integrated into state-of-the-art sort-based skyline algorithms to boost their computational performance. The new indexing and dominance checking approach is supported by a theoretical analysis, while our experiments show that it scales well with the input size and dimensionality not only because unnecessary dominance checks are avoided but also because it allows efficient dominance checking with the help of bitwise operations. © 2009 ACM. | en_HK |
dc.language | eng | en_HK |
dc.publisher | ACM. | - |
dc.relation.ispartof | Proceedings of the 2009 ACM SIGMOD International Conference on Management of data (SIGMOD'09) | en_HK |
dc.subject | Preference | en_HK |
dc.subject | Skyline | en_HK |
dc.subject | Space partitioning | en_HK |
dc.title | Scalable skyline computation using object-based space partitioning | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Mamoulis, N: nikos@cs.hku.hk | en_HK |
dc.identifier.email | Cheung, DWL: dcheung@cs.hku.hk | en_HK |
dc.identifier.authority | Mamoulis, N=rp00155 | en_HK |
dc.identifier.authority | Cheung, DWL=rp00101 | en_HK |
dc.description.nature | link_to_OA_fulltext | - |
dc.identifier.doi | 10.1145/1559845.1559897 | en_HK |
dc.identifier.scopus | eid_2-s2.0-70849097739 | en_HK |
dc.identifier.hkuros | 164473 | en_HK |
dc.identifier.hkuros | 166354 | - |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-70849097739&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.spage | 483 | en_HK |
dc.identifier.epage | 494 | en_HK |
dc.publisher.place | United States | - |
dc.identifier.scopusauthorid | Cheung, DW=34567902600 | en_HK |
dc.identifier.scopusauthorid | Mamoulis, N=6701782749 | en_HK |
dc.identifier.scopusauthorid | Zhang, S=35773857200 | en_HK |
dc.customcontrol.immutable | sml 140526 | - |