[논문]빅데이터 전처리 기반의 실시간 사용자 선호 데이터 추천을 위한 개선된 스카이라인 질의 기법

김지현; 김종완

doi:10.3745/ktsde.2022.11.5.189

빅데이터 전처리 기반의 실시간 사용자 선호 데이터 추천을 위한 개선된 스카이라인 질의 기법
An Improved Skyline Query Scheme for Recommending Real-Time User Preference Data Based on Big Data Preprocessing 원문보기

정보처리학회논문지. KIPS transactions on software and data engineering. 소프트웨어 및 데이터 공학, v.11 no.5, 2022년, pp.189 - 196

김지현 (한양대학교 인공지능학과) , 김종완 (삼육대학교 인공지능융합학부)

초록
AI-Helper

스카이라인 질의(Skyline Query)는 객체의 다중 속성을 기준으로 사용자 선호에 적합한 대상을 탐색하는 기법이다. 기존 스카이라인 질의는 탐색 결과를 일괄처리(batch processing)로 반환하지만, 대화형 앱이나 모바일 환경의 등장으로 실시간 탐색 결과의 필요성이 증가하였다. 스카이라인을 위한 온라인 알고리즘(online algorithm)은 객체의 반환 속도를 향상해 실시간으로 선호 객체를 제공한다. 하지만 객체 탐색 과정에서 기존에 탐색한 영역을 재방문하여 반복 비교하는 불필요한 연산 시간이 소요된다. 본 논문은 온라인 알고리즘에서 불필요한 탐색 시간을 제거하여 스카이라인 질의 결과를 실시간으로 제공하기 위한 스카이라인 온라인 전처리 알고리즘을 제안한다. 제안 기법은 기존의 온라인 알고리즘에서 전처리를 수행함으로써 반복적으로 재탐색 되는 영역을 미리 제거하여 탐색 성능을 향상하였다. 실험 결과, 기존 온라인 알고리즘과 비교 시 이산 데이터 집합의 표준 분포, 편향 분포, 양의 상관 및 음의 상관분포에서 향상된 성능을 보였다. 제안 기법은 비교 대상을 최소화하여 탐색 성능을 향상하므로 모바일 장치의 사용이 증가하는 현실에서 사용자들에게 신속한 서비스를 제공할 수 있는 새로운 기준이 될 것이다.

Abstract ▼ AI-Helper

Skyline query is a scheme for exploring objects that are suitable for user preferences based on multiple attributes of objects. Existing skyline queries return search results as batch processing, but the need for real-time search results has increased with the advent of interactive apps or mobile environments. Online algorithm for Skyline improves the return speed of objects to explore preferred objects in real time. However, the object navigation process requires unnecessary navigation time due to repeated comparative operations. This paper proposes a Pre-processing Online Algorithm for Skyline Query (POA) to eliminate unnecessary search time in Online Algorithm exploration techniques and provide the results of skyline queries in real time. Proposed techniques use the concept of range-limiting to existing Online Algorithm to perform pretreatment and then eliminate repetitive rediscovering regions first. POAs showed improvement in standard distributions, bias distributions, positive correlations, and negative correlations of discrete data sets compared to Online Algorithm. The POAs used in this paper improve navigation performance by minimizing comparison targets for Online Algorithm, which will be a new criterion for rapid service to users in the face of increasing use of mobile devices.

주제어

표/그림 (12)

그림 Fig. 1. Block Nested Loop Query
그림 Fig. 2. Divide and Conquer Query
그림 Fig. 3. Nearest Neighbor !Query
표 Table 1. Searching with Composite Function
표 Table 2. Operation Steps in POA
그림 Fig. 5. Discrete Data Distributions
그림 Fig. 4. POA Algorithm
표 Table 3. Simulation Environments
그림 Fig. 6. Performance in a Region 200 × 200
그림 Fig. 7. Performance in a Region 300 × 300
그림 Fig. 8. Performance in Correlations
표 Table 4. Performance Comparison in Normalized Data Set

참고문헌 (15)

S. Borzsonyi, D. Kossmann, and K. Stocker, "The skyline operator," In Proceedings of IEEE Conference on Data Engineering, Heidelberg, Germany, pp.421-430, 2001.
Y. Gulzar, A. A. Alwan, and S. Turaev, "Optimizing skyline query processing in incomplete data," in IEEE Access, Vol.7, pp.178121-178138, 2019.

상세보기
Z. Cai, X. Cui, X. Su, L. Guo, Z. Liu, and Z. Ding, "Continuous road network-based skyline query for moving objects," in IEEE Transactions on Intelligent Transportation Systems, Vol.22, No.12, pp.7383-7394, 2021.

상세보기
X. Yingyuan, X. Jiao, H. Wang, C. H. Hsu, Li Liu, and W. Zheng, "Efficient continuous skyline query processing in wireless sensor networks," Sensors, Vol.19, No.13, pp.2902, 2019.

상세보기
C. Kalyvas and M. Maragoudakis, "Skyline and reverse skyline query processing in SpatialHadoop," Data Knowledge and Engineering, Vol.122, pp.55-80, 2019.

상세보기
G. Stoupas, A. Sidiropoulos, D. Katsaros, and Y. Manolopoulos, "Skyline-based university rankings," ADBIS, TPDL and EDA 2020 Common Workshops and Doctoral Consortium, pp.347-352, 2020.
Z. Zheng, K. Ruan, and M. Yu, "k-dominant Skyline query algorithm for dynamic datasets," Frontiers of Computer Science, Vol.15, No.151602, pp.1-6, 2021.
D. Kossmann, F. Ramsak, and S. Rost, "Shooting stars in the sky: An online algorithm for skyline queries," Proceedings of the 28th Very Large Data Bases Conference, pp.275-286, 2002.
T. Erlebach, F. H. Liu, H. H. Liu, M. Shalom, W. H. Wong, and S. Zaks, "Complexity and online algorithms for minimum skyline coloring of intervals," Theoretical Computer Science, Vol.788, pp.66-78, 2019.

상세보기
D. Papadias, Y. Tao, G. Fu, and B. Seeger, "An optimal and progressive algorithm for skyline queries," In: ACM SIGMOD International Conference on Management of Data, pp.467-478, 2003.
N. Roussopoulos, S. Kelley, and F. Vincent, "Nearest neighbor queries," In Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, pp.71-79, 1995.
F. V. Alejandro and M. David, "Guarantees on nearest-neighbor condensation heuristics," Computational Geometry, Vol.95, No.1, pp.101732, 2021.

상세보기
P. E. Danielsson, "Euclidean distance mapping," Computer Graphics and Image Processing, Vol.14, No.3, pp.227-248, 1980.

상세보기
T. Bellitto, A. Pecher, and A. Sedillot, "On the density of sets of the Euclidean plane avoiding distance 1," Discrete Mathematics & Theoretical Computer Science, Vol.23, No.1, 2021.

상세보기
R. Weber, H. J. Schek, and S. Blott, "A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces," Proceedings of the 24th VLDB Conference New York, USA, pp.194-205, 1998.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증