Efficiently Processing Skyline Query on Multi-Instance Data

Shu-I Chiu and Kuo-Wei Hsu
Volume: 13, No: 5, Page: 1277 ~ 1298, Year: 2017
Keywords: Multi-Instance Data, Product Search, Ranking, Recommendation, Skyline Query Processing
Full Text:

Related to the maximum vector problem, a skyline query is to discover dominating tuples from a set of tuples, where each defines an object (such as a hotel) in several dimensions (such as the price and the distance to the beach). A tuple, an instance of an object, dominates another tuple if it is equally good or better in all dimensions and better in at least one dimension. Traditionally, skyline queries are defined upon single- instance data or upon objects each of which is associated with an instance. However, in some cases, an object is not associated with a single instance but rather by multiple instances. For example, on a review website, many users assign scores to a product or a service, and a user’s score is an instance of the object representing the product or the service. Such data is an example of multi-instance data. Unlike most (if not all) others considering the traditional setting, we consider skyline queries defined upon multi-instance data. We define the dominance calculation and propose an algorithm to reduce its computational cost. We use synthetic and real data to evaluate the proposed methods, and the results demonstrate their utility.

Article Statistics
Multiple requests among the same broswer session are counted as one view (or download).
If you mouse over a chart, a box will show the data point's value.

Cite this article
IEEE Style
S. C. K. Hsu, "Efficiently Processing Skyline Query on Multi-Instance Data," Journal of Information Processing Systems, vol. 13, no. 5, pp. 1277~1298, 2017. DOI: 10.3745/JIPS.04.0049.

ACM Style
Shu-I Chiu and Kuo-Wei Hsu. 2017. Efficiently Processing Skyline Query on Multi-Instance Data, Journal of Information Processing Systems, 13, 5, (2017), 1277~1298. DOI: 10.3745/JIPS.04.0049.