Applying Z-Curve Technique to Compute Skyline Set in Multi Criteria Decision Making System

T. Vijaya Saradhi,Kodukula Subrahmanyam,P. Venkateswara Rao,Hye-jin Kim 보안공학연구지원센터 2016 International Journal of Database Theory and Appli Vol.9 No.12

The skyline queries are the best tools to be used in distributed multi criteria decision making of web based applications for user commendations. However, as the Data dimensions are increasing size of dominance set and skyline set is also increasing. Increasing dimensionality becomes the major problem with real word databases. In skyline computation major cost depends on finding dominance tests between high dimensional objects and the order in which they are accessing. Space filling Z-curve is the best suitable way to address the challenges in skyline computation. In this proposed work, we incorporated Z-curve with optimized skyline boundary detection algorithm to effective access and early pruning. In this paper efficient hybrid index structure was proposed which takes the advantage of sorting and partition approaches to improve the storage and search efficiency. Experimental results show that our propose approach is better than the previous static skyline computation techniques in terms of searching and finding skyline set.

A Filter Lining Scheme for Efficient Skyline Computation

김지현,김명 한국멀티미디어학회 2011 멀티미디어학회논문지 Vol.14 No.12

The skyline of a multidimensional data set is the maximal subset whose elements are not dominated by other elements of the set. Skyline computation is considered to be very useful for a decision making system that deals with multidimensional data analyses. Recently, a great deal of interests has been shown to improve the performance of skyline computation algorithms. In order to speedup, the number of comparisons between data elements should be reduced. In this paper, we propose a filter lining scheme to accomplish such objectives. The scheme divides the multidimensional data space into angle-based partitions, and places a filter for each partition, and then connects them together in order to establish the final filter line. The filter line can be used to eliminate data, that are not part of the skyline, from the original data set in the preprocessing stage. The filter line is adaptively improved during the data scanning stage. In addition, skylines are computed for each remaining data partition, and are then merged to form the final skyline. Our scheme is an improvement of the previously reported simple preprocessing scheme using simple filters. The performance of the scheme is shown by experiments.

A Filter Lining Scheme for Efficient Skyline Computation

Kim, Ji-Hyun,Kim, Myung Korea Multimedia Society 2011 멀티미디어학회논문지 Vol.14 No.12

The skyline of a multidimensional data set is the maximal subset whose elements are not dominated by other elements of the set. Skyline computation is considered to be very useful for a decision making system that deals with multidimensional data analyses. Recently, a great deal of interests has been shown to improve the performance of skyline computation algorithms. In order to speedup, the number of comparisons between data elements should be reduced. In this paper, we propose a filter lining scheme to accomplish such objectives. The scheme divides the multidimensional data space into angle-based partitions, and places a filter for each partition, and then connects them together in order to establish the final filter line. The filter line can be used to eliminate data, that are not part of the skyline, from the original data set in the preprocessing stage. The filter line is adaptively improved during the data scanning stage. In addition, skylines are computed for each remaining data partition, and are then merged to form the final skyline. Our scheme is an improvement of the previously reported simple preprocessing scheme using simple filters. The performance of the scheme is shown by experiments.

An efficient skyline framework for matchmaking applications

Han, H.,Jung, H.,Eom, H.,Yeom, H.Y. Academic Press 2011 JOURNAL OF NETWORK AND COMPUTER APPLICATIONS - Vol.34 No.1

In this article, we present a skyline-based matchmaking framework. The current method of carrying out the matchmaking procedure identifies items based on users' specifications. We rethink matchmaking procedures in such a way that they can find items that can satisfy a specific computing demand from a user and recommend a collection of better candidates among the identified items. This endows a user with the right of choice on deciding the best-possible items. We approach the recommendation from the perspective of skyline computation and present an efficient skyline algorithm that gathers interesting item candidates efficiently. To devise an efficient sequential skyline algorithm, we adopt (i) lattice-based indexing using a lattice composition technique and (ii) an optimized dominance-check algorithm. Moreover, we parallelize the algorithm using breadth-first-search (BFS). Our extensive experimental results show that our algorithm outperforms current state-of-the-art algorithms, and the speedup factor of the parallelized algorithm is near-linear.

Finding Probabilistic Skyline Points by using Dimensionality Reduction and Boundary detection Approach in Distributed Environment

Vijaya Saradhi.T,Kodukula Subrahmanyam,Debnath Bhattacharyya,Tai-hoon Kim 보안공학연구지원센터 2015 International Journal of Software Engineering and Vol.9 No.8

A skyline of a n-dimensional data contains the data objects that are not dominated by any other data object on all dimensions. However, as the number of data dimensions increases the probability of domination points become very low, accordingly the number of points in the skyline becomes large. Also skyline search space has been identified as the key problem in real-time multidimensional databases. None of the traditional search techniques include the use of dimensionality reduction to optimize the search space. Skyline query computation on the server consecutively reduces the amount of data transferred between the server sites. Traditional static lower bound and upper bound probability computation will increase the number of non-dominance points. In this proposed work, an optimized skyline boundary detection algorithm is used to filter the skyline objects and pruning the local probability. Also, global probability computation was improved on the large skyline databases in order to minimize the search space and storage .The experimental results show that the efficiency of the proposed approach compared to traditional static skyline bound techniques in terms of time and search space are concerned.

Group skyline computation

Im, H.,Park, S. North-Holland [etc ; Elsevier Science Ltd 2012 Information sciences Vol.188 No.-

Given a multi-dimensional dataset of tuples, skyline computation returns a subset of tuples that are not dominated by any other tuples when all dimensions are considered together. Conventional skyline computation, however, is inadequate to answer various queries that need to analyze not just individual tuples of a dataset but also their combinations. In this paper, we study group skyline computation which is based on the notion of dominance relation between groups of the same number of tuples. It determines the dominance relation between two groups by comparing their aggregate values such as sums or averages of elements of individual dimensions, and identifies a set of skyline groups that are not dominated by any other groups. We investigate properties of group skyline computation and develop a group skyline algorithm GDynamic which is equivalent to a dynamic algorithm that fills a table of skyline groups. Experimental results show that GDynamic is a practical group skyline algorithm.

원위 요골 골절에서 나사못 돌출 확인을 위한 Skyline View와 수술 중 시행한 컴퓨터 단층 촬영의 비교

임경훈,강홍제 대한수부외과학회 2019 대한수부외과학회지 Vol.24 No.2

Purpose: The aim of our study was to compare and analyze intraoperative fluoroscopy (skyline view) and mobile cone-beam computed tomography (CBCT) for detecting protruded screws in volar locked plating used for distal radius frac-tures.Methods: We carried out a prospective analysis of 35 patients who had undergone both intraoperative fluoroscopy and mobile CBCT. The patients had all undergone volar locking plate fixation for a distal radial fracture at our institution between January and May 2017. Skyline view and mobile CBCT were carried out and protruded screws were replaced. Screw tip cortex distance (STCD) was measured using skyline view and mobile CBCT and compared with each area of the distal radius.Results: Three screws were found to be protruding after skyline view, and further seven screws were found to be protrud-ing after computed tomography (CT) scan. The mean STCD for each compartment was 3.8±0.6 mm, 3.5±1.8 mm, 2.2±1.3 mm, 3.7±1.6 mm, and 3.9±1.4 mm in the skyline view, respectively, and 3.5±0.7 mm, 0.8±1.6 mm, 0.9±1.1 mm, 2.1±1.6 mm, and 3.7±1.9 mm in the CT scan, respectively (p<0.05). The mean STCD of all screws was 1.2 mm longer in the sky-line view than in the CT scan. Conclusion: The skyline view showed approximately 1-2 mm difference compared to CBCT; therefore, it would be better to insert the screw 2 mm shorter than seen in the skyline view. 목적: 수장부 잠김 금속판을 이용한 원위 요골 골절 수술 후 돌출된 나사못을 발견하는 데 있어 skyline view의 정확성을 수술 중 촬영한 cone-beam computed tomography (CBCT)와 비교하여 분석하고자 한다.방법: 원위 요골 골절에 대하여 수장판 잠김 금속판 고정술을 시행 후 수술 중에 skyline view와 CBCT를 모두 촬영한 35명의 환자를 대상하였다. Skyline view를 촬영한 뒤 돌출된 나사못을 교체한 후 CBCT를 촬영하여 추가로 돌출된 나사못을 교체하였다. 수술 후 요골의 배측을 5개의 영역으로 나누어 나사못의 돌출 정도(screw tip cor-tex distance, STCD)를 측정하여 비교하였다.결과: 나사못 돌출은 skyline view에서 3개가 확인되었으며, computed tomography (CT) 촬영 후에는 추가로 7개가 확인되어 교체되었다. STCD는 skyline view에서 각 영역에서 3.8 mm, 3.5 mm, 2.2 mm, 3.7 mm, 3.9 mm이었고, CT에서는 3.5 mm, 0.8 mm, 0.9 mm, 2.1 mm, 3.7 mm로 측정되어 2, 3, 4번 영역에서 통계적으로 유의한 차이를 보였다.결론: Skyline view는 수술 중 CT와 약 1-2 mm가량의 오차를 보여 skyline view에서 보이는 것보다 2 mm가량 짧게 나사못을 삽입하는 것이 좋을 것으로 생각된다.

다차원 데이터 분석을 위한 확장 스카이라인 계산 알고리즘

김지현,김명 한국정보과학회 2011 데이타베이스 연구 Vol.27 No.3

다차원 데이터 집합의 원소들 중에서 집합 내의 다른 원소에게 지배당하지 않는 원소들로 구성된 부분집합을 그 집합의 스카이라인이라고 한다. 스카이라인은 사용자가 원하는 조건에 최적인 원소들로 구성되어 있으므로, 대용량 데이터 집합의 의사결정 시스템에 특히 활용도가 높은 연산이다. 그러나 질의 객체가 이동하는모바일 환경에서는 위치 제약 조건으로 인해 질의 객체 주변의 스카이라인 원소들이 근처에 있는 다른 원소들 보다 더 낫다는 보장이 없다. 본 연구에서는 이러한 환경에서 스카이라인 원소들 이외에 질적으로 사용자의 요구조건에 더 맞는 다른 원소들도 찾아주는 알고리즘을 개발하였다. 개발한 알고리즘은 성능평가를 통해 효율성을 검증하였다. The skyline of a multidimensional data set consists of the elements that are not dominated by other elements of the set. It is considered to be the set that is most preferable by the user or query object, so that the skyline computation is especially useful for decision making systems dealing with large data sets. However, in a mobile environment where query objects are moving around, due to the location-based restrictions, the skyline points around the query objects may not be the most preferable by the user. In this work, we develop an algorithm for computing elements that can be better in quality for the moving query objects than the skyline points around them. The performance and usability of the algorithm is evaluated by experiments.

A Three-phase Large Scale Skyline Service Selection Framework in Clouds

Jinzhong LI,Jintao ZE,Lei PENG,Wenlang Luo 보안공학연구지원센터 2016 International Journal of Grid and Distributed Comp Vol.9 No.4

For the large scale services with high-dimensional QoS attributes and distributed environment, traditional service selection approaches are faced with unprecedented challenges in terms of efficiency and performance of QoS. To address these challenges, we propose a three-phase large scale Skyline service selection framework for service composition in clouds. This framework adopts distributed parallel Skyline computation with MapReduce to prune redundant candidate services, and employs parallel multi-objective optimization algorithm based on MapReduce to select Skyline services from the tremendous amount of Skyline services warehouse for composing single service into a set of more powerful Skyline composite services, then applies Top-k query processing technology or multiple attribute decision making support method to select k Skyline composite services from the set of Skyline composite services. Through theoretical analysis, the framework can efficiently solve the service selection problem with large scale services, high-dimensional QoS in cloud computing environment, and quickly generate better composite services with the global optimal QoS.

데이터 샘플링 기반 프루닝 기법을 도입한 효율적인 각도 기반 공간 분할 병렬 스카이라인 질의 처리 기법

최우성 ( Woosung Choi ),김민석 ( Minseok Kim ),( Gromyko Diana ),정재화 ( Jaehwa Chung ),정순영 ( Soonyong Jung ) 한국정보처리학회 2017 정보처리학회논문지. 소프트웨어 및 데이터 공학 Vol.6 No.1

Given a multi-dimensional dataset of tuples, a skyline query returns a subset of tuples which are not `dominated` by any other tuples. Skyline query is very useful in Big data analysis since it filters out uninteresting items. Much interest was devoted to the MapReduce-based parallel processing of skyline queries in large-scale distributed environment. There are three requirements to improve parallelism in MapReduced-based algorithms: (1) workload should be well balanced (2) avoid redundant computations (3) Optimize network communication cost. In this paper, we introduce MR-SEAP (MapReduce sample Skyline object Equality Angular Partitioning), an efficient angular space partitioning based skyline query processing using sampling-based pruning, which satisfies requirements above. We conduct an extensive experiment to evaluate MR-SEAP.