Application of a fast skyline computation algorithm for serendipitous searching problems

Kenichi Koizumi; Kei Hiraki; Mary Inaba

doi:10.1117/12.2288156

20 February 2018 Application of a fast skyline computation algorithm for serendipitous searching problems

Kenichi Koizumi, Kei Hiraki, Mary Inaba

Proceedings Volume 10505, High-Speed Biomedical Imaging and Spectroscopy III: Toward Big Data Instrumentation and Management; 1050514 (2018) https://doi.org/10.1117/12.2288156
Event: SPIE BiOS, 2018, San Francisco, California, United States

Abstract

Skyline computation is a method of extracting interesting entries from a large population with multiple attributes. These entries, called skyline or Pareto optimal entries, are known to have extreme characteristics that cannot be found by outlier detection methods. Skyline computation is an important task for characterizing large amounts of data and selecting interesting entries with extreme features. When the population changes dynamically, the task of calculating a sequence of skyline sets is called continuous skyline computation. This task is known to be difficult to perform for the following reasons: (1) information of non-skyline entries must be stored since they may join the skyline in the future; (2) the appearance or disappearance of even a single entry can change the skyline drastically; (3) it is difficult to adopt a geometric acceleration algorithm for skyline computation tasks with high-dimensional datasets. Our new algorithm called jointed rooted-tree (JR-tree) manages entries using a rooted tree structure. JR-tree delays extend the tree to deep levels to accelerate tree construction and traversal. In this study, we presented the difficulties in extracting entries tagged with a rare label in high-dimensional space and the potential of fast skyline computation in low-latency cell identification technology.

Citation Download Citation

Kenichi Koizumi, Kei Hiraki, and Mary Inaba "Application of a fast skyline computation algorithm for serendipitous searching problems", Proc. SPIE 10505, High-Speed Biomedical Imaging and Spectroscopy III: Toward Big Data Instrumentation and Management, 1050514 (20 February 2018); https://doi.org/10.1117/12.2288156

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available